Minor fixes to improve hash map/set performance

6 files changed, 28 insertions, 34 deletions

diff --git a/src/checker.cpp b/src/checker.cpp
index ef7d72e65..a5885705e 100644
--- a/src/checker.cpp
+++ b/src/checker.cpp
@@ -219,7 +219,7 @@ bool decl_info_has_init(DeclInfo *d) {
 
 
 
-Scope *create_scope(Scope *parent, gbAllocator allocator, isize init_elements_capacity=16) {
+Scope *create_scope(Scope *parent, gbAllocator allocator, isize init_elements_capacity=DEFAULT_SCOPE_CAPACITY) {
 	Scope *s = gb_alloc_item(allocator, Scope);
 	s->parent = parent;
 	string_map_init(&s->elements, heap_allocator(), init_elements_capacity);
diff --git a/src/checker.hpp b/src/checker.hpp
index efd6aae54..409bc9de2 100644
--- a/src/checker.hpp
+++ b/src/checker.hpp
@@ -167,10 +167,12 @@ enum ScopeFlag : i32 {
 	ScopeFlag_Type   = 1<<6,
 
 	ScopeFlag_HasBeenImported = 1<<10, // This is only applicable to file scopes
-	
-	ScopeFlag_ContextDefined = 1<<16, 
+
+	ScopeFlag_ContextDefined = 1<<16,
 };
 
+enum { DEFAULT_SCOPE_CAPACITY = 29 };
+
 struct Scope {
 	Ast *         node;
 	Scope *       parent;
@@ -178,7 +180,7 @@ struct Scope {
 	Scope *       next;
 	Scope *       first_child;
 	Scope *       last_child;
-	StringMap<Entity *> elements; 
+	StringMap<Entity *> elements;
 
 	Array<Ast *>    delayed_directives;
 	Array<Ast *>    delayed_imports;
@@ -251,7 +253,7 @@ struct CheckerInfo {
 	                               // as it needs to be iterated across
 	StringMap<AstFile *>    files;    // Key (full path)
 	StringMap<AstPackage *> packages; // Key (full path)
-	StringMap<Entity *>     foreigns; 
+	StringMap<Entity *>     foreigns;
 	Array<Entity *>       definitions;
 	Array<Entity *>       entities;
 	Array<DeclInfo *>     variable_init_order;
diff --git a/src/map.cpp b/src/map.cpp
index ae6bf9f74..85836fccb 100644
--- a/src/map.cpp
+++ b/src/map.cpp
@@ -89,8 +89,11 @@ template <typename T> void  multi_map_remove_all(Map<T> *h, HashKey const &key);
 
 template <typename T>
 gb_inline void map_init(Map<T> *h, gbAllocator a, isize capacity) {
-	array_init(&h->hashes,  a, 0, capacity);
+	array_init(&h->hashes,  a, capacity);
 	array_init(&h->entries, a, 0, capacity);
+	for (isize i = 0; i < capacity; i++) {
+		h->hashes.data[i] = -1;
+	}
 }
 
 template <typename T>
@@ -161,7 +164,7 @@ template <typename T>
 void map_rehash(Map<T> *h, isize new_count) {
 	isize i, j;
 	Map<T> nh = {};
-	map_init(&nh, h->hashes.allocator);
+	map_init(&nh, h->hashes.allocator, new_count);
 	array_resize(&nh.hashes, new_count);
 	array_reserve(&nh.entries, h->entries.count);
 	for (i = 0; i < new_count; i++) {
diff --git a/src/parser.hpp b/src/parser.hpp
index 7cb380ffb..bfe290c8f 100644
--- a/src/parser.hpp
+++ b/src/parser.hpp
@@ -167,7 +167,7 @@ enum ProcInlining {
 enum ProcTag {
 	ProcTag_bounds_check    = 1<<0,
 	ProcTag_no_bounds_check = 1<<1,
-	
+
 	ProcTag_require_results = 1<<4,
 	ProcTag_optional_ok     = 1<<5,
 };
diff --git a/src/ptr_set.cpp b/src/ptr_set.cpp
index b87657274..e343628af 100644
--- a/src/ptr_set.cpp
+++ b/src/ptr_set.cpp
@@ -7,8 +7,8 @@ struct PtrSetFindResult {
 
 template <typename T>
 struct PtrSetEntry {
-	T       ptr;
-	isize   next;
+	T     ptr;
+	isize next;
 };
 
 template <typename T>
@@ -29,8 +29,11 @@ template <typename T> void ptr_set_rehash (PtrSet<T> *s, isize new_count);
 
 template <typename T>
 void ptr_set_init(PtrSet<T> *s, gbAllocator a, isize capacity) {
-	array_init(&s->hashes,  a, 0, capacity);
+	array_init(&s->hashes,  a, capacity);
 	array_init(&s->entries, a, 0, capacity);
+	for (isize i = 0; i < capacity; i++) {
+		s->hashes.data[i] = -1;
+	}
 }
 
 template <typename T>
@@ -53,9 +56,9 @@ template <typename T>
 gb_internal PtrSetFindResult ptr_set__find(PtrSet<T> *s, T ptr) {
 	PtrSetFindResult fr = {-1, -1, -1};
 	if (s->hashes.count > 0) {
-		uintptr p = cast(uintptr)ptr;
-		uintptr n = cast(uintptr)s->hashes.count;
-		fr.hash_index = cast(isize)(p % n);
+		u64 hash = 0xcbf29ce484222325ull ^ cast(u64)cast(uintptr)ptr;
+		u64 n = cast(u64)s->hashes.count;
+		fr.hash_index = cast(isize)(hash % n);
 		fr.entry_index = s->hashes[fr.hash_index];
 		while (fr.entry_index >= 0) {
 			if (s->entries[fr.entry_index].ptr == ptr) {
@@ -69,23 +72,6 @@ gb_internal PtrSetFindResult ptr_set__find(PtrSet<T> *s, T ptr) {
 }
 
 template <typename T>
-gb_internal PtrSetFindResult ptr_set__find_from_entry(PtrSet<T> *s, PtrSetEntry<T> *e) {
-	PtrSetFindResult fr = {-1, -1, -1};
-	if (s->hashes.count > 0) {
-		fr.hash_index  = e->key.key % s->hashes.count;
-		fr.entry_index = s->hashes[fr.hash_index];
-		while (fr.entry_index >= 0) {
-			if (&s->entries[fr.entry_index] == e) {
-				return fr;
-			}
-			fr.entry_prev = fr.entry_index;
-			fr.entry_index = s->entries[fr.entry_index].next;
-		}
-	}
-	return fr;
-}
-
-template <typename T>
 gb_internal b32 ptr_set__full(PtrSet<T> *s) {
 	return 0.75f * s->hashes.count <= s->entries.count;
 }
diff --git a/src/string_map.cpp b/src/string_map.cpp
index 485048154..7a446937a 100644
--- a/src/string_map.cpp
+++ b/src/string_map.cpp
@@ -7,7 +7,7 @@ struct StringMapFindResult {
 
 struct StringHashKey {
 	u64    hash;
-	String string; 
+	String string;
 };
 
 StringHashKey string_hashing_proc(void const *data, isize len) {
@@ -65,8 +65,11 @@ template <typename T> void string_map_rehash           (StringMap<T> *h, isize n
 
 template <typename T>
 gb_inline void string_map_init(StringMap<T> *h, gbAllocator a, isize capacity) {
-	array_init(&h->hashes,  a, 0, capacity);
+	array_init(&h->hashes,  a, capacity);
 	array_init(&h->entries, a, 0, capacity);
+	for (isize i = 0; i < capacity; i++) {
+		h->hashes.data[i] = -1;
+	}
 }
 
 template <typename T>
@@ -136,7 +139,7 @@ template <typename T>
 void string_map_rehash(StringMap<T> *h, isize new_count) {
 	isize i, j;
 	StringMap<T> nh = {};
-	string_map_init(&nh, h->hashes.allocator);
+	string_map_init(&nh, h->hashes.allocator, new_count);
 	array_resize(&nh.hashes, new_count);
 	array_reserve(&nh.entries, h->entries.count);
 	for (i = 0; i < new_count; i++) {