commit 99df56f9d2228fa896f6e7f6e4fa8f8a2da208e2
parent 4634ef110c2d073a3ea87f870d5044dcf089cc9a
Author: Drew DeVault <sir@cmpwn.com>
Date: Thu, 11 Mar 2021 10:18:29 -0500
Store a cache of loaded modules
harec was accidentally quadratic without this. This reduces the build
time of the stdlib to basically nothing.
Diffstat:
9 files changed, 82 insertions(+), 22 deletions(-)
diff --git a/include/check.h b/include/check.h
@@ -9,7 +9,16 @@ struct build_tags;
struct expression;
struct scope;
+#define MODCACHE_BUCKETS 256
+
+struct modcache {
+ struct identifier ident;
+ struct scope *scope;
+ struct modcache *next;
+};
+
struct context {
+ struct modcache **modcache;
struct type_store *store;
const struct type *fntype;
struct identifier *ns;
@@ -85,8 +94,14 @@ struct ast_unit;
struct scope *check(struct type_store *ts,
struct build_tags *tags,
const struct ast_unit *aunit,
- struct unit *unit,
- bool scan_only);
+ struct unit *unit);
+
+struct scope *check_internal(struct type_store *ts,
+ struct modcache **cache,
+ struct build_tags *tags,
+ const struct ast_unit *aunit,
+ struct unit *unit,
+ bool scan_only);
void check_expression(struct context *ctx,
const struct ast_expression *aexpr,
diff --git a/include/identifier.h b/include/identifier.h
@@ -2,12 +2,14 @@
#define HARE_IDENTIFIER_H
#include <stddef.h>
#include <stdbool.h>
+#include <stdint.h>
struct identifier {
char *name;
struct identifier *ns;
};
+uint32_t identifier_hash(uint32_t init, const struct identifier *ident);
char *identifier_unparse(const struct identifier *ident);
int identifier_unparse_static(
const struct identifier *ident, char *buf, size_t len);
diff --git a/include/mod.h b/include/mod.h
@@ -4,6 +4,8 @@
#include "scope.h"
#include "type_store.h"
-struct scope *module_resolve(struct identifier *ident, struct type_store *store);
+struct modcache;
+struct scope *module_resolve(struct modcache *cache[],
+ struct identifier *ident, struct type_store *store);
#endif
diff --git a/src/check.c b/src/check.c
@@ -2628,10 +2628,10 @@ scan_declarations(struct context *ctx, const struct ast_decls *decls)
}
static void
-load_import(struct ast_imports *import,
+load_import(struct context *ctx, struct ast_imports *import,
struct type_store *ts, struct scope *scope)
{
- struct scope *mod = module_resolve(&import->ident, ts);
+ struct scope *mod = module_resolve(ctx->modcache, &import->ident, ts);
switch (import->mode) {
case AST_IMPORT_IDENTIFIER:
@@ -2720,14 +2720,19 @@ load_import(struct ast_imports *import,
}
struct scope *
-check(struct type_store *ts, struct build_tags *tags,
- const struct ast_unit *aunit, struct unit *unit, bool scan_only)
+check_internal(struct type_store *ts,
+ struct modcache **cache,
+ struct build_tags *tags,
+ const struct ast_unit *aunit,
+ struct unit *unit,
+ bool scan_only)
{
struct context ctx = {0};
ctx.ns = unit->ns;
ctx.tags = tags;
ctx.store = ts;
ctx.store->check_context = &ctx;
+ ctx.modcache = cache;
// Top-level scope management involves:
//
@@ -2750,7 +2755,7 @@ check(struct type_store *ts, struct build_tags *tags,
for (struct ast_imports *imports = su->imports;
imports; imports = imports->next) {
- load_import(imports, ts, ctx.scope);
+ load_import(&ctx, imports, ts, ctx.scope);
bool found = false;
for (struct imports *uimports = unit->imports;
@@ -2776,6 +2781,10 @@ check(struct type_store *ts, struct build_tags *tags,
next = &(*next)->next;
}
+ if (scan_only) {
+ return ctx.unit;
+ }
+
// Second pass populates the expression graph
struct scopes *scope = subunit_scopes;
struct declarations **next_decl = &unit->declarations;
@@ -2790,3 +2799,14 @@ check(struct type_store *ts, struct build_tags *tags,
return ctx.unit;
}
+
+struct scope *
+check(struct type_store *ts,
+ struct build_tags *tags,
+ const struct ast_unit *aunit,
+ struct unit *unit)
+{
+ struct modcache *modcache[MODCACHE_BUCKETS];
+ memset(modcache, 0, sizeof(modcache));
+ return check_internal(ts, modcache, tags, aunit, unit, false);
+}
diff --git a/src/identifier.c b/src/identifier.c
@@ -8,6 +8,17 @@
#include "identifier.h"
#include "util.h"
+uint32_t
+identifier_hash(uint32_t init, const struct identifier *ident)
+{
+ init = fnv1a_s(init, ident->name);
+ init = fnv1a(init, 0);
+ if (ident->ns) {
+ init = identifier_hash(init, ident->ns);
+ }
+ return init;
+}
+
static int
_asprintf(char **strp, const char *fmt, ...)
{
diff --git a/src/lex.c b/src/lex.c
@@ -9,7 +9,6 @@
#include <stdlib.h>
#include <string.h>
#include "lex.h"
-#include "trace.h"
#include "utf8.h"
#include "util.h"
@@ -710,7 +709,6 @@ lex2(struct lexer *lexer, struct token *out, uint32_t c)
break;
case '/':
while ((c = next(lexer, NULL, false)) != UTF8_INVALID && c != '\n') ;
- trace(TR_LEX, "comment");
return _lex(lexer, out);
default:
push(lexer, c, false);
@@ -912,10 +910,7 @@ _lex(struct lexer *lexer, struct token *out)
enum lexical_token
lex(struct lexer *lexer, struct token *out)
{
- enum lexical_token l = _lex(lexer, out);
- const char *s = token_str(out);
- trace(TR_LEX, "%s", s);
- return l;
+ return _lex(lexer, out);
}
void
@@ -1107,7 +1102,5 @@ void
unlex(struct lexer *lexer, struct token *in)
{
assert(lexer->un.token == T_ERROR && "Only one unlex is supported");
- const char *s = token_str(in);
- trace(TR_LEX, "(unlex) %s", s);
lexer->un = *in;
}
diff --git a/src/main.c b/src/main.c
@@ -137,7 +137,7 @@ main(int argc, char *argv[])
struct type_store ts = {0};
builtin_types_init();
- check(&ts, tags, &aunit, &unit, false);
+ check(&ts, tags, &aunit, &unit);
if (stage == STAGE_CHECK) {
return 0;
}
diff --git a/src/mod.c b/src/mod.c
@@ -1,6 +1,7 @@
#include <assert.h>
#include <errno.h>
#include <limits.h>
+#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
@@ -44,8 +45,18 @@ open_typedefs(struct identifier *ident)
}
struct scope *
-module_resolve(struct identifier *ident, struct type_store *store)
+module_resolve(struct modcache *cache[],
+ struct identifier *ident,
+ struct type_store *store)
{
+ uint32_t hash = identifier_hash(FNV1A_INIT, ident);
+ struct modcache **bucket = &cache[hash % MODCACHE_BUCKETS];
+ for (; *bucket; bucket = &(*bucket)->next) {
+ if (identifier_eq(&(*bucket)->ident, ident)) {
+ return (*bucket)->scope;
+ }
+ }
+
struct lexer lexer = {0};
struct ast_unit aunit = {0};
@@ -64,5 +75,14 @@ module_resolve(struct identifier *ident, struct type_store *store)
// TODO: Free unused bits
struct unit u = {0};
- return check(store, NULL, &aunit, &u, true);
+ struct scope *scope = check_internal(store,
+ cache, NULL, &aunit, &u, true);
+
+ bucket = &cache[hash % MODCACHE_BUCKETS];
+ struct modcache *item = xcalloc(1, sizeof(struct modcache));
+ identifier_dup(&item->ident, ident);
+ item->scope = scope;
+ item->next = *bucket;
+ *bucket = item;
+ return scope;
}
diff --git a/src/scope.c b/src/scope.c
@@ -6,8 +6,6 @@
#include "trace.h"
#include "util.h"
-#include <stdio.h>
-
static uint32_t
name_hash(uint32_t init, const struct identifier *ident)
{
@@ -93,7 +91,6 @@ scope_insert(struct scope *scope, enum object_type otype,
uint32_t hash = name_hash(FNV1A_INIT, name);
struct scope_object **bucket = &scope->buckets[hash % SCOPE_BUCKETS];
if (*bucket) {
- //fprintf(stderr, "%u %u\n", hash, hash % SCOPE_BUCKETS);
o->mnext = *bucket;
}
*bucket = o;
