harec

commit d10486b7b86b1f0ece7d86969916c279a334d494
parent 6c6bcd46c2d73f2f4ebacbd38d8bdb1dc1e62490
Author: Drew DeVault <sir@cmpwn.com>
Date:   Thu, 11 Mar 2021 09:26:59 -0500

Use a hash map for scope objects

This improves performance by about 20% according to my measurements. We
should look into opentracing to get more insights.

Diffstat:
M
include/scope.h
 | 
22
++++++++++++++++------
M
src/check.c
 | 
6
+++---
M
src/gen.c
 | 
2
+-
M
src/scope.c
 | 
39
+++++++++++++++++++++++++++++----------

4 files changed, 49 insertions(+), 20 deletions(-)
diff --git a/include/scope.h b/include/scope.h
@@ -4,6 +4,8 @@
 #include "identifier.h"
 #include "trace.h"
 
+#define SCOPE_BUCKETS 4096
+
 enum object_type {
 	O_BIND,
 	O_CONST,
@@ -11,24 +13,32 @@ enum object_type {
 	O_TYPE,
 };
 
-// XXX: This might be better as a hash map
 struct scope_object {
 	enum object_type otype;
 	// name is the name of the object within this scope (for lookups)
-	// ident is the global identifier
-	// (these may be different in some cases)
+	// ident is the global identifier (these may be different in some cases)
 	struct identifier name, ident;
+
 	const struct type *type;
 	struct expression *value; // For O_CONST
-	struct scope_object *next, *prev;
+
+	struct scope_object *lnext; // Linked list
+	struct scope_object *mnext; // Hash map
 };
 
 struct scope {
 	enum expr_type type;
 	const char *label;
-	struct scope_object *objects, *last;
-	struct scope_object **next; // List order matters for functions
 	struct scope *parent;
+
+	// Linked list in insertion order
+	// Used for function parameters, where order matters
+	struct scope_object *objects;
+	struct scope_object **next;
+
+	// Hash map in reverse insertion order
+	// Used for lookups, and accounts for shadowing
+	struct scope_object *buckets[SCOPE_BUCKETS];
 };
 
 struct scopes {
diff --git a/src/check.c b/src/check.c
@@ -2636,7 +2636,7 @@ load_import(struct ast_imports *import,
 	switch (import->mode) {
 	case AST_IMPORT_IDENTIFIER:
 		for (struct scope_object *obj = mod->objects;
-				obj; obj = obj->next) {
+				obj; obj = obj->lnext) {
 			scope_insert(scope, obj->otype, &obj->ident,
 				&obj->name, obj->type, obj->value);
 			if (obj->name.ns && obj->name.ns->ns) {
@@ -2664,7 +2664,7 @@ load_import(struct ast_imports *import,
 		break;
 	case AST_IMPORT_ALIAS:
 		for (struct scope_object *obj = mod->objects;
-				obj; obj = obj->next) {
+				obj; obj = obj->lnext) {
 			struct identifier ns = {
 				.name = obj->name.ns->name,
 				.ns = import->alias,
@@ -2703,7 +2703,7 @@ load_import(struct ast_imports *import,
 				continue;
 			};
 			for (struct scope_object *o = mod->objects;
-					o; o = o->next) {
+					o; o = o->lnext) {
 				if (!identifier_eq(o->name.ns, &ident)) {
 					continue;
 				};
diff --git a/src/gen.c b/src/gen.c
@@ -2878,7 +2878,7 @@ gen_function_decl(struct gen_context *ctx, const struct declaration *decl)
 			gen_store(ctx, &val, &src);
 		}
 
-		obj = obj->next;
+		obj = obj->lnext;
 		next = &param->next;
 	}
 
diff --git a/src/scope.c b/src/scope.c
@@ -6,6 +6,14 @@
 #include "trace.h"
 #include "util.h"
 
+#include <stdio.h>
+
+static uint32_t
+name_hash(uint32_t init, const struct identifier *ident)
+{
+	return fnv1a_s(init, ident->name);
+}
+
 struct scope *
 scope_push(struct scope **stack, enum trace_sys sys)
 {
@@ -42,7 +50,7 @@ scope_free(struct scope *scope)
 
 	struct scope_object *obj = scope->objects;
 	while (obj) {
-		struct scope_object *next = obj->next;
+		struct scope_object *next = obj->lnext;
 		free(obj);
 		obj = next;
 	}
@@ -76,23 +84,34 @@ scope_insert(struct scope *scope, enum object_type otype,
 		assert(otype == O_CONST);
 		assert(value->type == EXPR_CONSTANT);
 	}
+
+	// Linked list
 	*scope->next = o;
-	scope->next = &o->next;
-	o->prev = scope->last;
-	scope->last = o;
+	scope->next = &o->lnext;
+
+	// Hash map
+	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;
+
 	return o;
 }
 
 const struct scope_object *
 scope_lookup(struct scope *scope, const struct identifier *ident)
 {
-	struct scope_object *o = scope->last;
-	while (o) {
-		if (identifier_eq(&o->ident, ident)
-				|| identifier_eq(&o->name, ident)) {
-			return o;
+	uint32_t hash = name_hash(FNV1A_INIT, ident);
+	struct scope_object *bucket = scope->buckets[hash % SCOPE_BUCKETS];
+	while (bucket) {
+		if (identifier_eq(&bucket->name, ident)
+				|| identifier_eq(&bucket->ident, ident)) {
+			return bucket;
 		}
-		o = o->prev;
+		bucket = bucket->mnext;
 	}
 	if (scope->parent) {
 		return scope_lookup(scope->parent, ident);