From 252be0fb417f9cdde5e9c4b348cd995a20433aea Mon Sep 17 00:00:00 2001 From: gingerBill Date: Tue, 3 Jan 2023 11:59:52 +0000 Subject: Make all maps use heap allocator implicitly --- src/ptr_map.cpp | 18 ++++++++++++++---- 1 file changed, 14 insertions(+), 4 deletions(-) (limited to 'src/ptr_map.cpp') diff --git a/src/ptr_map.cpp b/src/ptr_map.cpp index 434680e91..083cd6697 100644 --- a/src/ptr_map.cpp +++ b/src/ptr_map.cpp @@ -46,7 +46,7 @@ gb_internal gb_inline u32 ptr_map_hash_key(void const *key) { } -template gb_internal void map_init (PtrMap *h, gbAllocator a, isize capacity = 16); +template gb_internal void map_init (PtrMap *h, isize capacity = 16); template gb_internal void map_destroy (PtrMap *h); template gb_internal V * map_get (PtrMap *h, K key); template gb_internal void map_set (PtrMap *h, K key, V const &value); @@ -68,11 +68,15 @@ template gb_internal void multi_map_remove (PtrMap< template gb_internal void multi_map_remove_all(PtrMap *h, K key); #endif +gb_internal gbAllocator map_allocator(void) { + return heap_allocator(); +} + template -gb_internal gb_inline void map_init(PtrMap *h, gbAllocator a, isize capacity) { +gb_internal gb_inline void map_init(PtrMap *h, isize capacity) { capacity = next_pow2_isize(capacity); - slice_init(&h->hashes, a, capacity); - array_init(&h->entries, a, 0, capacity); + slice_init(&h->hashes, map_allocator(), capacity); + array_init(&h->entries, map_allocator(), 0, capacity); for (isize i = 0; i < capacity; i++) { h->hashes.data[i] = MAP_SENTINEL; } @@ -80,6 +84,9 @@ gb_internal gb_inline void map_init(PtrMap *h, gbAllocator a, isize capaci template gb_internal gb_inline void map_destroy(PtrMap *h) { + if (h->entries.allocator.proc == nullptr) { + h->entries.allocator = map_allocator(); + } slice_free(&h->hashes, h->entries.allocator); array_free(&h->entries); } @@ -162,6 +169,9 @@ gb_internal void map_reset_entries(PtrMap *h) { template gb_internal void map_reserve(PtrMap *h, isize cap) { + if (h->entries.allocator.proc == nullptr) { + h->entries.allocator = map_allocator(); + } array_reserve(&h->entries, cap); if (h->entries.count*2 < h->hashes.count) { return; -- cgit v1.2.3 From 0fb3032b731b640a2d0d1d62b9f8dd548e224b0e Mon Sep 17 00:00:00 2001 From: gingerBill Date: Tue, 3 Jan 2023 14:45:09 +0000 Subject: General improves to `alloc_ast_node` and other unnecessary checks --- src/common.cpp | 2 +- src/main.cpp | 4 ++-- src/parser.cpp | 4 +--- src/parser.hpp | 5 ++--- src/ptr_map.cpp | 6 ++++-- src/thread_pool.cpp | 6 +++--- src/threading.cpp | 1 + src/types.cpp | 4 ++-- 8 files changed, 16 insertions(+), 16 deletions(-) (limited to 'src/ptr_map.cpp') diff --git a/src/common.cpp b/src/common.cpp index 199a263a1..988a992d0 100644 --- a/src/common.cpp +++ b/src/common.cpp @@ -43,9 +43,9 @@ gb_internal void debugf(char const *fmt, ...); #error Odin on Windows requires a 64-bit build-system. The 'Developer Command Prompt' for VS still defaults to 32-bit shell. The 64-bit shell can be found under the name 'x64 Native Tools Command Prompt' for VS. For more information, please see https://odin-lang.org/docs/install/#for-windows #endif -#include "threading.cpp" #include "unicode.cpp" #include "array.cpp" +#include "threading.cpp" #include "queue.cpp" #include "common_memory.cpp" #include "string.cpp" diff --git a/src/main.cpp b/src/main.cpp index 7ac78241e..c07d2c400 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -13,11 +13,11 @@ #endif #include "exact_value.cpp" #include "build_settings.cpp" - gb_global ThreadPool global_thread_pool; gb_internal void init_global_thread_pool(void) { isize thread_count = gb_max(build_context.thread_count, 1); - thread_pool_init(&global_thread_pool, permanent_allocator(), thread_count, "ThreadPoolWorker"); + isize worker_count = thread_count-1; + thread_pool_init(&global_thread_pool, permanent_allocator(), worker_count, "ThreadPoolWorker"); } gb_internal bool thread_pool_add_task(WorkerTaskProc *proc, void *data) { return thread_pool_add_task(&global_thread_pool, proc, data); diff --git a/src/parser.cpp b/src/parser.cpp index 046469c16..c6f35d326 100644 --- a/src/parser.cpp +++ b/src/parser.cpp @@ -64,11 +64,9 @@ gb_global std::atomic global_total_node_memory_allocated; // NOTE(bill): And this below is why is I/we need a new language! Discriminated unions are a pain in C/C++ gb_internal Ast *alloc_ast_node(AstFile *f, AstKind kind) { - gbAllocator a = ast_allocator(f); - isize size = ast_node_size(kind); - Ast *node = cast(Ast *)gb_alloc(a, size); + Ast *node = cast(Ast *)arena_alloc(&global_thread_local_ast_arena, size, 16); node->kind = kind; node->file_id = f ? f->id : 0; diff --git a/src/parser.hpp b/src/parser.hpp index b492cfa85..d81194831 100644 --- a/src/parser.hpp +++ b/src/parser.hpp @@ -821,9 +821,8 @@ gb_internal gb_inline bool is_ast_when_stmt(Ast *node) { gb_global gb_thread_local Arena global_thread_local_ast_arena = {}; -gb_internal gbAllocator ast_allocator(AstFile *f) { - Arena *arena = &global_thread_local_ast_arena; - return arena_allocator(arena); +gb_internal gb_inline gbAllocator ast_allocator(AstFile *f) { + return arena_allocator(&global_thread_local_ast_arena); } gb_internal Ast *alloc_ast_node(AstFile *f, AstKind kind); diff --git a/src/ptr_map.cpp b/src/ptr_map.cpp index 083cd6697..264136881 100644 --- a/src/ptr_map.cpp +++ b/src/ptr_map.cpp @@ -27,6 +27,7 @@ struct PtrMap { gb_internal gb_inline u32 ptr_map_hash_key(uintptr key) { + u32 res; #if defined(GB_ARCH_64_BIT) key = (~key) + (key << 21); key = key ^ (key >> 24); @@ -34,12 +35,13 @@ gb_internal gb_inline u32 ptr_map_hash_key(uintptr key) { key = key ^ (key >> 14); key = (key + (key << 2)) + (key << 4); key = key ^ (key << 28); - return cast(u32)key; + res = cast(u32)key; #elif defined(GB_ARCH_32_BIT) u32 state = ((u32)key) * 747796405u + 2891336453u; u32 word = ((state >> ((state >> 28u) + 4u)) ^ state) * 277803737u; - return (word >> 22u) ^ word; + res = (word >> 22u) ^ word; #endif + return res ^ (res == MAP_SENTINEL); } gb_internal gb_inline u32 ptr_map_hash_key(void const *key) { return ptr_map_hash_key((uintptr)key); diff --git a/src/thread_pool.cpp b/src/thread_pool.cpp index 07ab3d323..276e93dff 100644 --- a/src/thread_pool.cpp +++ b/src/thread_pool.cpp @@ -5,7 +5,7 @@ struct ThreadPool; gb_thread_local Thread *current_thread; -gb_internal void thread_pool_init(ThreadPool *pool, gbAllocator const &a, isize thread_count, char const *worker_name); +gb_internal void thread_pool_init(ThreadPool *pool, gbAllocator const &a, isize worker_count, char const *worker_name); gb_internal void thread_pool_destroy(ThreadPool *pool); gb_internal bool thread_pool_add_task(ThreadPool *pool, WorkerTaskProc *proc, void *data); gb_internal void thread_pool_wait(ThreadPool *pool); @@ -25,9 +25,9 @@ gb_internal isize current_thread_index(void) { return current_thread ? current_thread->idx : 0; } -gb_internal void thread_pool_init(ThreadPool *pool, gbAllocator const &a, isize thread_count, char const *worker_name) { +gb_internal void thread_pool_init(ThreadPool *pool, gbAllocator const &a, isize worker_count, char const *worker_name) { pool->allocator = a; - slice_init(&pool->threads, a, thread_count + 1); + slice_init(&pool->threads, a, worker_count + 1); // NOTE: this needs to be initialized before any thread starts pool->running.store(true, std::memory_order_seq_cst); diff --git a/src/threading.cpp b/src/threading.cpp index aca77cd8f..78943150e 100644 --- a/src/threading.cpp +++ b/src/threading.cpp @@ -398,6 +398,7 @@ gb_internal void thread_init(ThreadPool *pool, Thread *t, isize idx) { t->idx = idx; } + gb_internal void thread_init_and_start(ThreadPool *pool, Thread *t, isize idx) { thread_init(pool, t, idx); isize stack_size = 0; diff --git a/src/types.cpp b/src/types.cpp index d33c36e94..fa7c1d7f7 100644 --- a/src/types.cpp +++ b/src/types.cpp @@ -2535,13 +2535,13 @@ gb_internal bool are_types_identical_internal(Type *x, Type *y, bool check_tuple if (x->kind == Type_Named) { Entity *e = x->Named.type_name; - if (e != nullptr && e->kind == Entity_TypeName && e->TypeName.is_type_alias) { + if (e->TypeName.is_type_alias) { x = x->Named.base; } } if (y->kind == Type_Named) { Entity *e = y->Named.type_name; - if (e != nullptr && e->kind == Entity_TypeName && e->TypeName.is_type_alias) { + if (e->TypeName.is_type_alias) { y = y->Named.base; } } -- cgit v1.2.3 From ec69101101d56e90ee183e449eb5bb3605e3afbe Mon Sep 17 00:00:00 2001 From: gingerBill Date: Tue, 3 Jan 2023 18:39:37 +0000 Subject: Convert `minimum_dependency_type_info_set` to use a `PtrMap` --- src/checker.cpp | 19 +++++++------------ src/checker.hpp | 2 +- src/llvm_backend_type.cpp | 7 ++++--- src/ptr_map.cpp | 1 - src/ptr_set.cpp | 10 ---------- 5 files changed, 12 insertions(+), 27 deletions(-) (limited to 'src/ptr_map.cpp') diff --git a/src/checker.cpp b/src/checker.cpp index 11e0dfa47..78f96e47f 100644 --- a/src/checker.cpp +++ b/src/checker.cpp @@ -1153,6 +1153,9 @@ gb_internal void init_checker_info(CheckerInfo *i) { array_init(&i->init_procedures, a, 0, 0); array_init(&i->required_foreign_imports_through_force, a, 0, 0); + map_init(&i->objc_msgSend_types); + string_map_init(&i->load_file_cache); + array_init(&i->all_procedures, heap_allocator()); TIME_SECTION("checker info: mpmc queues"); @@ -1160,16 +1163,7 @@ gb_internal void init_checker_info(CheckerInfo *i) { mpmc_init(&i->definition_queue, a, 1<<20); mpmc_init(&i->required_global_variable_queue, a, 1<<10); mpmc_init(&i->required_foreign_imports_through_force_queue, a, 1<<10); - - TIME_SECTION("checker info: mutexes"); - mpmc_init(&i->intrinsics_entry_point_usage, a, 1<<10); // just waste some memory here, even if it probably never used - - map_init(&i->objc_msgSend_types); - string_map_init(&i->load_file_cache); - - array_init(&i->all_procedures, heap_allocator()); - } gb_internal void destroy_checker_info(CheckerInfo *i) { @@ -2031,10 +2025,11 @@ gb_internal void add_min_dep_type_info(Checker *c, Type *t) { ti_index = type_info_index(&c->info, t, false); } GB_ASSERT(ti_index >= 0); - if (ptr_set_update(set, ti_index)) { - // Type Already exists + if (map_get(set, ti_index)) { + // Type already exists; return; } + map_set(set, ti_index, set->entries.count); // Add nested types if (t->kind == Type_Named) { @@ -2275,7 +2270,7 @@ gb_internal void generate_minimum_dependency_set(Checker *c, Entity *start) { isize min_dep_set_cap = next_pow2_isize(entity_count*4); // empirically determined factor ptr_set_init(&c->info.minimum_dependency_set, min_dep_set_cap); - ptr_set_init(&c->info.minimum_dependency_type_info_set); + map_init(&c->info.minimum_dependency_type_info_set); #define FORCE_ADD_RUNTIME_ENTITIES(condition, ...) do { \ if (condition) { \ diff --git a/src/checker.hpp b/src/checker.hpp index 60800349b..bb870e077 100644 --- a/src/checker.hpp +++ b/src/checker.hpp @@ -336,7 +336,7 @@ struct CheckerInfo { Scope * init_scope; Entity * entry_point; PtrSet minimum_dependency_set; - PtrSet minimum_dependency_type_info_set; + PtrMap minimum_dependency_type_info_set; diff --git a/src/llvm_backend_type.cpp b/src/llvm_backend_type.cpp index c306cdead..b9b450404 100644 --- a/src/llvm_backend_type.cpp +++ b/src/llvm_backend_type.cpp @@ -2,9 +2,10 @@ gb_internal isize lb_type_info_index(CheckerInfo *info, Type *type, bool err_on_ auto *set = &info->minimum_dependency_type_info_set; isize index = type_info_index(info, type, err_on_not_found); if (index >= 0) { - isize i = ptr_set_entry_index(set, index); - if (i >= 0) { - return i+1; + auto *found = map_get(set, index); + if (found) { + GB_ASSERT(*found >= 0); + return *found + 1; } } if (err_on_not_found) { diff --git a/src/ptr_map.cpp b/src/ptr_map.cpp index 264136881..ae3cd4b40 100644 --- a/src/ptr_map.cpp +++ b/src/ptr_map.cpp @@ -229,7 +229,6 @@ gb_internal void map_set(PtrMap *h, K key, V const &value) { } } - template gb_internal void map__erase(PtrMap *h, MapFindResult const &fr) { MapFindResult last; diff --git a/src/ptr_set.cpp b/src/ptr_set.cpp index 9b8b678f8..f730a47ff 100644 --- a/src/ptr_set.cpp +++ b/src/ptr_set.cpp @@ -12,7 +12,6 @@ struct PtrSetEntry { template struct PtrSet { - Slice hashes; Array> entries; }; @@ -154,15 +153,6 @@ gb_internal gb_inline bool ptr_set_exists(PtrSet *s, T ptr) { return index != MAP_SENTINEL; } -template -gb_internal gb_inline isize ptr_set_entry_index(PtrSet *s, T ptr) { - isize index = ptr_set__find(s, ptr).entry_index; - if (index != MAP_SENTINEL) { - return index; - } - return -1; -} - // Returns true if it already exists template gb_internal T ptr_set_add(PtrSet *s, T ptr) { -- cgit v1.2.3 From d06a0e7093c3f06a474a040385f1b9dfdfce29ad Mon Sep 17 00:00:00 2001 From: gingerBill Date: Wed, 4 Jan 2023 13:30:27 +0000 Subject: Improve the `PtrSet` to be as simple and small as possible --- src/check_stmt.cpp | 1 + src/checker.cpp | 33 +++--- src/ptr_map.cpp | 2 +- src/ptr_set.cpp | 303 +++++++++++++++++++++++------------------------------ src/threading.cpp | 20 ++-- 5 files changed, 157 insertions(+), 202 deletions(-) (limited to 'src/ptr_map.cpp') diff --git a/src/check_stmt.cpp b/src/check_stmt.cpp index 9547035d0..b4dd4cd7d 100644 --- a/src/check_stmt.cpp +++ b/src/check_stmt.cpp @@ -1289,6 +1289,7 @@ gb_internal void check_type_switch_stmt(CheckerContext *ctx, Ast *node, u32 mod_ for (Type *t : variants) { if (!type_ptr_set_exists(&seen, t)) { array_add(&unhandled, t); + gb_printf_err("HERE: %p %s\n", t, type_to_string(t)); } } diff --git a/src/checker.cpp b/src/checker.cpp index 78f96e47f..b8709f15e 100644 --- a/src/checker.cpp +++ b/src/checker.cpp @@ -66,15 +66,10 @@ gb_internal void scope_reserve(Scope *scope, isize capacity) { } gb_internal void entity_graph_node_set_destroy(EntityGraphNodeSet *s) { - if (s->hashes.data != nullptr) { - ptr_set_destroy(s); - } + ptr_set_destroy(s); } gb_internal void entity_graph_node_set_add(EntityGraphNodeSet *s, EntityGraphNode *n) { - if (s->hashes.data == nullptr) { - ptr_set_init(s); - } ptr_set_add(s, n); } @@ -2556,7 +2551,6 @@ gb_internal Array generate_entity_dependency_graph(CheckerInf } // IMPORTANT NOTE/TODO(bill, 2020-11-15): These three calls take the majority of the // the time to process - entity_graph_node_set_add(&p->succ, s); entity_graph_node_set_add(&s->pred, p); // Remove edge to 'n' @@ -2577,7 +2571,7 @@ gb_internal Array generate_entity_dependency_graph(CheckerInf for_array(i, G) { EntityGraphNode *n = G[i]; n->index = i; - n->dep_count = n->succ.entries.count; + n->dep_count = n->succ.count; GB_ASSERT(n->dep_count >= 0); } @@ -4228,7 +4222,7 @@ gb_internal Array generate_import_dependency_graph(Checker *c for (auto const &entry : M) { auto n = entry.value; n->index = i++; - n->dep_count = n->succ.entries.count; + n->dep_count = n->succ.count; GB_ASSERT(n->dep_count >= 0); array_add(&G, n); } @@ -5706,17 +5700,6 @@ gb_internal void check_parsed_files(Checker *c) { check_scope_usage(c, f->scope); } - TIME_SECTION("add untyped expression values"); - // Add untyped expression values - for (UntypedExprInfo u = {}; mpmc_dequeue(&c->global_untyped_queue, &u); /**/) { - GB_ASSERT(u.expr != nullptr && u.info != nullptr); - if (is_type_typed(u.info->type)) { - compiler_error("%s (type %s) is typed!", expr_to_string(u.expr), type_to_string(u.info->type)); - } - add_type_and_value(&c->builtin_ctx, u.expr, u.info->mode, u.info->type, u.info->value); - } - - TIME_SECTION("add basic type information"); // Add "Basic" type information for (isize i = 0; i < Basic_COUNT; i++) { @@ -5810,6 +5793,16 @@ gb_internal void check_parsed_files(Checker *c) { GB_ASSERT(c->info.entity_queue.count.load(std::memory_order_relaxed) == 0); GB_ASSERT(c->info.definition_queue.count.load(std::memory_order_relaxed) == 0); + TIME_SECTION("add untyped expression values"); + // Add untyped expression values + for (UntypedExprInfo u = {}; mpmc_dequeue(&c->global_untyped_queue, &u); /**/) { + GB_ASSERT(u.expr != nullptr && u.info != nullptr); + if (is_type_typed(u.info->type)) { + compiler_error("%s (type %s) is typed!", expr_to_string(u.expr), type_to_string(u.info->type)); + } + add_type_and_value(&c->builtin_ctx, u.expr, u.info->mode, u.info->type, u.info->value); + } + TIME_SECTION("sort init procedures"); check_sort_init_procedures(c); diff --git a/src/ptr_map.cpp b/src/ptr_map.cpp index ae3cd4b40..8869bf3fe 100644 --- a/src/ptr_map.cpp +++ b/src/ptr_map.cpp @@ -41,7 +41,7 @@ gb_internal gb_inline u32 ptr_map_hash_key(uintptr key) { u32 word = ((state >> ((state >> 28u) + 4u)) ^ state) * 277803737u; res = (word >> 22u) ^ word; #endif - return res ^ (res == MAP_SENTINEL); + return res; } gb_internal gb_inline u32 ptr_map_hash_key(void const *key) { return ptr_map_hash_key((uintptr)key); diff --git a/src/ptr_set.cpp b/src/ptr_set.cpp index e2b3f2372..8be2b0524 100644 --- a/src/ptr_set.cpp +++ b/src/ptr_set.cpp @@ -1,19 +1,22 @@ template -struct PtrSetEntry { - static_assert(sizeof(T) == sizeof(void *), "Key size must be pointer size"); - - T ptr; - MapIndex next; +struct TypeIsPointer { + enum {value = false}; +}; - operator T() const noexcept { - return this->ptr; - } +template +struct TypeIsPointer { + enum {value = true}; }; + template struct PtrSet { - Slice hashes; - Array> entries; + static_assert(TypeIsPointer::value, "PtrSet::T must be a pointer"); + static constexpr T TOMBSTONE = (T)(~uintptr(0)); + + T * keys; + usize count; + usize capacity; }; template gb_internal void ptr_set_init (PtrSet *s, isize capacity = 16); @@ -30,225 +33,183 @@ gb_internal gbAllocator ptr_set_allocator(void) { template gb_internal void ptr_set_init(PtrSet *s, isize capacity) { + GB_ASSERT(s->keys == nullptr); if (capacity != 0) { capacity = next_pow2_isize(gb_max(16, capacity)); + s->keys = gb_alloc_array(ptr_set_allocator(), T, capacity); + // This memory will be zeroed, no need to explicitly zero it } - - slice_init(&s->hashes, ptr_set_allocator(), capacity); - array_init(&s->entries, ptr_set_allocator(), 0, capacity); - for (isize i = 0; i < capacity; i++) { - s->hashes.data[i] = MAP_SENTINEL; - } + s->count = 0; + s->capacity = capacity; } template gb_internal void ptr_set_destroy(PtrSet *s) { - if (s->entries.allocator.proc == nullptr) { - s->entries.allocator = ptr_set_allocator(); - } - slice_free(&s->hashes, s->entries.allocator); - array_free(&s->entries); + gb_free(ptr_set_allocator(), s->keys); + s->keys = nullptr; + s->count = 0; + s->capacity = 0; } template -gb_internal MapIndex ptr_set__add_entry(PtrSet *s, T ptr) { - PtrSetEntry e = {}; - e.ptr = ptr; - e.next = MAP_SENTINEL; - array_add(&s->entries, e); - return cast(MapIndex)(s->entries.count-1); -} - - -template -gb_internal MapFindResult ptr_set__find(PtrSet *s, T ptr) { - MapFindResult fr = {MAP_SENTINEL, MAP_SENTINEL, MAP_SENTINEL}; - if (s->hashes.count != 0) { - u32 hash = ptr_map_hash_key(ptr); - fr.hash_index = cast(MapIndex)(hash & (s->hashes.count-1)); - fr.entry_index = s->hashes.data[fr.hash_index]; - while (fr.entry_index != MAP_SENTINEL) { - if (s->entries.data[fr.entry_index].ptr == ptr) { - return fr; +gb_internal isize ptr_set__find(PtrSet *s, T ptr) { + GB_ASSERT(ptr != nullptr); + if (s->count != 0) { + #if 0 + for (usize i = 0; i < s->capacity; i++) { + if (s->keys[i] == ptr) { + return i; } - fr.entry_prev = fr.entry_index; - fr.entry_index = s->entries.data[fr.entry_index].next; } - } - return fr; -} - -template -gb_internal MapFindResult ptr_set__find_from_entry(PtrSet *s, PtrSetEntry *e) { - MapFindResult fr = {MAP_SENTINEL, MAP_SENTINEL, MAP_SENTINEL}; - if (s->hashes.count != 0) { - u32 hash = ptr_map_hash_key(e->ptr); - fr.hash_index = cast(MapIndex)(hash & (s->hashes.count-1)); - fr.entry_index = s->hashes.data[fr.hash_index]; - while (fr.entry_index != MAP_SENTINEL) { - if (&s->entries.data[fr.entry_index] == e) { - return fr; + #else + u32 hash = ptr_map_hash_key(ptr); + usize mask = s->capacity-1; + usize hash_index = cast(usize)hash & mask; + for (usize i = 0; i < s->capacity; i++) { + T key = s->keys[hash_index]; + if (key == ptr) { + return hash_index; + } else if (key == nullptr) { + return -1; } - fr.entry_prev = fr.entry_index; - fr.entry_index = s->entries.data[fr.entry_index].next; + hash_index = (hash_index+1)&mask; } + #endif } - return fr; + return -1; } template gb_internal bool ptr_set__full(PtrSet *s) { - return 0.75f * s->hashes.count <= s->entries.count; + return 0.75f * s->capacity <= s->count; } template -gb_internal void ptr_set_reset_entries(PtrSet *s) { - for (isize i = 0; i < s->hashes.count; i++) { - s->hashes.data[i] = MAP_SENTINEL; - } - for (isize i = 0; i < s->entries.count; i++) { - MapFindResult fr; - PtrSetEntry *e = &s->entries.data[i]; - e->next = MAP_SENTINEL; - fr = ptr_set__find_from_entry(s, e); - if (fr.entry_prev == MAP_SENTINEL) { - s->hashes[fr.hash_index] = cast(MapIndex)i; - } else { - s->entries[fr.entry_prev].next = cast(MapIndex)i; - } +gb_internal gb_inline void ptr_set_grow(PtrSet *old_set) { + if (old_set->capacity == 0) { + ptr_set_init(old_set); + return; } -} -template -gb_internal void ptr_set_reserve(PtrSet *s, isize cap) { - if (s->entries.allocator.proc == nullptr) { - s->entries.allocator = ptr_set_allocator(); - } - array_reserve(&s->entries, cap); - if (s->entries.count*2 < s->hashes.count) { - return; + PtrSet new_set = {}; + ptr_set_init(&new_set, gb_max(old_set->capacity<<1, 16)); + + for (T ptr : *old_set) { + bool was_new = ptr_set_update(&new_set, ptr); + GB_ASSERT(!was_new); } - slice_resize(&s->hashes, s->entries.allocator, cap*2); - ptr_set_reset_entries(s); -} + GB_ASSERT(old_set->count == new_set.count); -template -gb_internal gb_inline void ptr_set_grow(PtrSet *s) { - isize new_count = gb_max(s->hashes.count<<1, 16); - ptr_set_reserve(s, new_count); + ptr_set_destroy(old_set); + + *old_set = new_set; } template gb_internal gb_inline bool ptr_set_exists(PtrSet *s, T ptr) { - isize index = ptr_set__find(s, ptr).entry_index; - return index != MAP_SENTINEL; + return ptr_set__find(s, ptr) >= 0; } -// Returns true if it already exists -template -gb_internal T ptr_set_add(PtrSet *s, T ptr) { - MapIndex index; - MapFindResult fr; - if (s->hashes.count == 0) { - ptr_set_grow(s); - } - fr = ptr_set__find(s, ptr); - if (fr.entry_index == MAP_SENTINEL) { - index = ptr_set__add_entry(s, ptr); - if (fr.entry_prev != MAP_SENTINEL) { - s->entries.data[fr.entry_prev].next = index; - } else { - s->hashes.data[fr.hash_index] = index; - } - } - if (ptr_set__full(s)) { - ptr_set_grow(s); - } - return ptr; -} template gb_internal bool ptr_set_update(PtrSet *s, T ptr) { // returns true if it previously existsed - bool exists = false; - MapIndex index; - MapFindResult fr; - if (s->hashes.count == 0) { + if (ptr_set_exists(s, ptr)) { + return true; + } + + if (s->keys == nullptr) { + ptr_set_init(s); + } else if (ptr_set__full(s)) { ptr_set_grow(s); } - fr = ptr_set__find(s, ptr); - if (fr.entry_index != MAP_SENTINEL) { - exists = true; - } else { - index = ptr_set__add_entry(s, ptr); - if (fr.entry_prev != MAP_SENTINEL) { - s->entries.data[fr.entry_prev].next = index; - } else { - s->hashes.data[fr.hash_index] = index; + GB_ASSERT(s->count < s->capacity); + GB_ASSERT(s->capacity >= 0); + + usize mask = s->capacity-1; + u32 hash = ptr_map_hash_key(ptr); + usize hash_index = (cast(usize)hash) & mask; + GB_ASSERT(hash_index < s->capacity); + for (usize i = 0; i < s->capacity; i++) { + T *key = &s->keys[hash_index]; + GB_ASSERT(*key != ptr); + if (*key == PtrSet::TOMBSTONE || *key == nullptr) { + *key = ptr; + s->count++; + return false; } + hash_index = (hash_index+1)&mask; } - if (ptr_set__full(s)) { - ptr_set_grow(s); - } - return exists; -} - + GB_PANIC("ptr set out of memory"); + return false; +} template -gb_internal void ptr_set__erase(PtrSet *s, MapFindResult fr) { - MapFindResult last; - if (fr.entry_prev == MAP_SENTINEL) { - s->hashes.data[fr.hash_index] = s->entries.data[fr.entry_index].next; - } else { - s->entries.data[fr.entry_prev].next = s->entries.data[fr.entry_index].next; - } - if (cast(isize)fr.entry_index == s->entries.count-1) { - array_pop(&s->entries); - return; - } - s->entries.data[fr.entry_index] = s->entries.data[s->entries.count-1]; - last = ptr_set__find(s, s->entries.data[fr.entry_index].ptr); - if (last.entry_prev != MAP_SENTINEL) { - s->entries.data[last.entry_prev].next = fr.entry_index; - } else { - s->hashes.data[last.hash_index] = fr.entry_index; - } +gb_internal T ptr_set_add(PtrSet *s, T ptr) { + ptr_set_update(s, ptr); + return ptr; } + template gb_internal void ptr_set_remove(PtrSet *s, T ptr) { - MapFindResult fr = ptr_set__find(s, ptr); - if (fr.entry_index != MAP_SENTINEL) { - ptr_set__erase(s, fr); + isize index = ptr_set__find(s, ptr); + if (index >= 0) { + GB_ASSERT(s->count > 0); + s->keys[index] = PtrSet::TOMBSTONE; + s->count--; } } template gb_internal gb_inline void ptr_set_clear(PtrSet *s) { - array_clear(&s->entries); - for (isize i = 0; i < s->hashes.count; i++) { - s->hashes.data[i] = MAP_SENTINEL; - } + s->count = 0; + gb_zero_size(s->keys, s->capacity*gb_size_of(T)); } - -template -gb_internal PtrSetEntry *begin(PtrSet &m) noexcept { - return m.entries.data; -} template -gb_internal PtrSetEntry const *begin(PtrSet const &m) noexcept { - return m.entries.data; -} +struct PtrSetIterator { + PtrSet *set; + usize index; + + PtrSetIterator &operator++() noexcept { + for (;;) { + ++index; + if (set->capacity == index) { + return *this; + } + T key = set->keys[index]; + if (key != nullptr && key != PtrSet::TOMBSTONE) { + return *this; + } + } + } + + bool operator==(PtrSetIterator const &other) const noexcept { + return this->set == other.set && this->index == other.index; + } + + + operator T *() const { + return &set->keys[index]; + } +}; template -gb_internal PtrSetEntry *end(PtrSet &m) noexcept { - return m.entries.data + m.entries.count; +gb_internal PtrSetIterator begin(PtrSet &set) noexcept { + usize index = 0; + while (index < set.capacity) { + T key = set.keys[index]; + if (key != nullptr && key != PtrSet::TOMBSTONE) { + break; + } + index++; + } + return PtrSetIterator{&set, index}; } - template -gb_internal PtrSetEntry const *end(PtrSet const &m) noexcept { - return m.entries.data + m.entries.count; +gb_internal PtrSetIterator end(PtrSet &set) noexcept { + return PtrSetIterator{&set, set.capacity}; } \ No newline at end of file diff --git a/src/threading.cpp b/src/threading.cpp index 27a17112e..bf298e024 100644 --- a/src/threading.cpp +++ b/src/threading.cpp @@ -699,13 +699,13 @@ extern "C" int __ulock_wake(uint32_t operation, void *addr, uint64_t wake_value) gb_internal void futex_signal(Futex *f) { for (;;) { int ret = __ulock_wake(UL_COMPARE_AND_WAIT | ULF_NO_ERRNO, f, 0); - if (ret >= 0) { + if (ret == 0) { return; } - if (ret == EINTR || ret == EFAULT) { + if (ret == -EINTR || ret == -EFAULT) { continue; } - if (ret == ENOENT) { + if (ret == -ENOENT) { return; } GB_PANIC("Failed in futex wake!\n"); @@ -716,13 +716,13 @@ gb_internal void futex_broadcast(Futex *f) { for (;;) { enum { ULF_WAKE_ALL = 0x00000100 }; int ret = __ulock_wake(UL_COMPARE_AND_WAIT | ULF_NO_ERRNO | ULF_WAKE_ALL, f, 0); - if (ret >= 0) { + if (ret == 0) { return; } - if (ret == EINTR || ret == EFAULT) { + if (ret == -EINTR || ret == -EFAULT) { continue; } - if (ret == ENOENT) { + if (ret == -ENOENT) { return; } GB_PANIC("Failed in futex wake!\n"); @@ -732,16 +732,16 @@ gb_internal void futex_broadcast(Futex *f) { gb_internal void futex_wait(Futex *f, Footex val) { for (;;) { int ret = __ulock_wait(UL_COMPARE_AND_WAIT | ULF_NO_ERRNO, f, val, 0); - if (ret >= 0) { + if (ret == 0) { if (*f != val) { return; } continue; } - if (ret == EINTR || ret == EFAULT) { - continue; + if (ret == -EINTR || ret == -EFAULT) { + -continue; } - if (ret == ENOENT) { + if (ret == -ENOENT) { return; } -- cgit v1.2.3 From bbb2164e38e3930cb79c5e7bc61b421e38131361 Mon Sep 17 00:00:00 2001 From: gingerBill Date: Thu, 5 Jan 2023 01:25:37 +0000 Subject: Inline map gets; cast explicitly on TOMBSTONE checking --- src/ptr_map.cpp | 27 +++++++++++++++++++-------- src/ptr_set.cpp | 10 +++++----- src/string_map.cpp | 15 ++++++++++++--- 3 files changed, 36 insertions(+), 16 deletions(-) (limited to 'src/ptr_map.cpp') diff --git a/src/ptr_map.cpp b/src/ptr_map.cpp index 8869bf3fe..c33bf9ffb 100644 --- a/src/ptr_map.cpp +++ b/src/ptr_map.cpp @@ -112,11 +112,12 @@ gb_internal MapFindResult map__find(PtrMap *h, K key) { fr.hash_index = cast(MapIndex)(hash & (h->hashes.count-1)); fr.entry_index = h->hashes.data[fr.hash_index]; while (fr.entry_index != MAP_SENTINEL) { - if (h->entries.data[fr.entry_index].key == key) { + auto *entry = &h->entries.data[fr.entry_index]; + if (entry->key == key) { return fr; } fr.entry_prev = fr.entry_index; - fr.entry_index = h->entries.data[fr.entry_index].next; + fr.entry_index = entry->next; } return fr; } @@ -190,18 +191,28 @@ gb_internal void map_rehash(PtrMap *h, isize new_count) { template gb_internal V *map_get(PtrMap *h, K key) { - MapIndex index = map__find(h, key).entry_index; - if (index != MAP_SENTINEL) { - return &h->entries.data[index].value; + MapFindResult fr = {MAP_SENTINEL, MAP_SENTINEL, MAP_SENTINEL}; + if (h->hashes.count != 0) { + u32 hash = ptr_map_hash_key(key); + fr.hash_index = cast(MapIndex)(hash & (h->hashes.count-1)); + fr.entry_index = h->hashes.data[fr.hash_index]; + while (fr.entry_index != MAP_SENTINEL) { + auto *entry = &h->entries.data[fr.entry_index]; + if (entry->key == key) { + return &entry->value; + } + fr.entry_prev = fr.entry_index; + fr.entry_index = entry->next; + } } return nullptr; } template gb_internal V &map_must_get(PtrMap *h, K key) { - MapIndex index = map__find(h, key).entry_index; - GB_ASSERT(index != MAP_SENTINEL); - return h->entries.data[index].value; + V *ptr = map_get(h, key); + GB_ASSERT(ptr != nullptr); + return *ptr; } template diff --git a/src/ptr_set.cpp b/src/ptr_set.cpp index 8be2b0524..019ede8a5 100644 --- a/src/ptr_set.cpp +++ b/src/ptr_set.cpp @@ -12,7 +12,7 @@ struct TypeIsPointer { template struct PtrSet { static_assert(TypeIsPointer::value, "PtrSet::T must be a pointer"); - static constexpr T TOMBSTONE = (T)(~uintptr(0)); + static constexpr uintptr TOMBSTONE = ~(uintptr)(0ull); T * keys; usize count; @@ -133,7 +133,7 @@ gb_internal bool ptr_set_update(PtrSet *s, T ptr) { // returns true if it pre for (usize i = 0; i < s->capacity; i++) { T *key = &s->keys[hash_index]; GB_ASSERT(*key != ptr); - if (*key == PtrSet::TOMBSTONE || *key == nullptr) { + if (*key == (T)PtrSet::TOMBSTONE || *key == nullptr) { *key = ptr; s->count++; return false; @@ -157,7 +157,7 @@ gb_internal void ptr_set_remove(PtrSet *s, T ptr) { isize index = ptr_set__find(s, ptr); if (index >= 0) { GB_ASSERT(s->count > 0); - s->keys[index] = PtrSet::TOMBSTONE; + s->keys[index] = (T)PtrSet::TOMBSTONE; s->count--; } } @@ -180,7 +180,7 @@ struct PtrSetIterator { return *this; } T key = set->keys[index]; - if (key != nullptr && key != PtrSet::TOMBSTONE) { + if (key != nullptr && key != (T)PtrSet::TOMBSTONE) { return *this; } } @@ -202,7 +202,7 @@ gb_internal PtrSetIterator begin(PtrSet &set) noexcept { usize index = 0; while (index < set.capacity) { T key = set.keys[index]; - if (key != nullptr && key != PtrSet::TOMBSTONE) { + if (key != nullptr && key != (T)PtrSet::TOMBSTONE) { break; } index++; diff --git a/src/string_map.cpp b/src/string_map.cpp index 74a16de73..facd00bb0 100644 --- a/src/string_map.cpp +++ b/src/string_map.cpp @@ -180,9 +180,18 @@ gb_internal void string_map_rehash(StringMap *h, isize new_count) { template gb_internal T *string_map_get(StringMap *h, StringHashKey const &key) { - isize index = string_map__find(h, key).entry_index; - if (index != MAP_SENTINEL) { - return &h->entries.data[index].value; + MapFindResult fr = {MAP_SENTINEL, MAP_SENTINEL, MAP_SENTINEL}; + if (h->hashes.count != 0) { + fr.hash_index = cast(MapIndex)(key.hash & (h->hashes.count-1)); + fr.entry_index = h->hashes.data[fr.hash_index]; + while (fr.entry_index != MAP_SENTINEL) { + auto *entry = &h->entries.data[fr.entry_index]; + if (string_hash_key_equal(entry->key, key)) { + return &entry->value; + } + fr.entry_prev = fr.entry_index; + fr.entry_index = entry->next; + } } return nullptr; } -- cgit v1.2.3 From 1517f1d7793c8985664600a820e3434dfdf83810 Mon Sep 17 00:00:00 2001 From: gingerBill Date: Thu, 5 Jan 2023 11:54:21 +0000 Subject: Add uncomment `add_type_info_type` calls for type assertions --- src/check_decl.cpp | 60 ++++++++++++++++++++++++++++------------------------ src/check_expr.cpp | 8 +++---- src/checker.cpp | 38 +++++---------------------------- src/llvm_backend.cpp | 1 + src/ptr_map.cpp | 29 +++++++++++++++++++++++++ 5 files changed, 71 insertions(+), 65 deletions(-) (limited to 'src/ptr_map.cpp') diff --git a/src/check_decl.cpp b/src/check_decl.cpp index 644771dcd..d4ae9c59d 100644 --- a/src/check_decl.cpp +++ b/src/check_decl.cpp @@ -1411,6 +1411,37 @@ end:; } +gb_internal void add_deps_from_child_to_parent(DeclInfo *decl) { + if (decl && decl->parent) { + Scope *ps = decl->parent->scope; + if (ps->flags & (ScopeFlag_File & ScopeFlag_Pkg & ScopeFlag_Global)) { + return; + } else { + // NOTE(bill): Add the dependencies from the procedure literal (lambda) + // But only at the procedure level + rw_mutex_shared_lock(&decl->deps_mutex); + rw_mutex_lock(&decl->parent->deps_mutex); + + for (Entity *e : decl->deps) { + ptr_set_add(&decl->parent->deps, e); + } + + rw_mutex_unlock(&decl->parent->deps_mutex); + rw_mutex_shared_unlock(&decl->deps_mutex); + + rw_mutex_shared_lock(&decl->type_info_deps_mutex); + rw_mutex_lock(&decl->parent->type_info_deps_mutex); + + for (Type *t : decl->type_info_deps) { + ptr_set_add(&decl->parent->type_info_deps, t); + } + + rw_mutex_unlock(&decl->parent->type_info_deps_mutex); + rw_mutex_shared_unlock(&decl->type_info_deps_mutex); + } + } +} + struct ProcUsingVar { Entity *e; Entity *uvar; @@ -1576,34 +1607,7 @@ gb_internal bool check_proc_body(CheckerContext *ctx_, Token token, DeclInfo *de check_scope_usage(ctx->checker, ctx->scope); - // if (decl->parent) { - // Scope *ps = decl->parent->scope; - // if (ps->flags & (ScopeFlag_File & ScopeFlag_Pkg & ScopeFlag_Global)) { - // return true; - // } else { - // // NOTE(bill): Add the dependencies from the procedure literal (lambda) - // // But only at the procedure level - // rw_mutex_shared_lock(&decl->deps_mutex); - // rw_mutex_lock(&decl->parent->deps_mutex); - - // for (Entity *e : decl->deps) { - // ptr_set_add(&decl->parent->deps, e); - // } - - // rw_mutex_unlock(&decl->parent->deps_mutex); - // rw_mutex_shared_unlock(&decl->deps_mutex); - - // rw_mutex_shared_lock(&decl->type_info_deps_mutex); - // rw_mutex_lock(&decl->parent->type_info_deps_mutex); - - // for (Type *t : decl->type_info_deps) { - // ptr_set_add(&decl->parent->type_info_deps, t); - // } - - // rw_mutex_unlock(&decl->parent->type_info_deps_mutex); - // rw_mutex_shared_unlock(&decl->type_info_deps_mutex); - // } - // } + add_deps_from_child_to_parent(decl); return true; } diff --git a/src/check_expr.cpp b/src/check_expr.cpp index e9e61486e..e0519d26b 100644 --- a/src/check_expr.cpp +++ b/src/check_expr.cpp @@ -8777,8 +8777,8 @@ gb_internal ExprKind check_type_assertion(CheckerContext *c, Operand *o, Ast *no return kind; } - // add_type_info_type(c, o->type); - // add_type_info_type(c, bsrc->Union.variants[0]); + add_type_info_type(c, o->type); + add_type_info_type(c, bsrc->Union.variants[0]); o->type = bsrc->Union.variants[0]; o->mode = Addressing_OptionalOk; @@ -8810,8 +8810,8 @@ gb_internal ExprKind check_type_assertion(CheckerContext *c, Operand *o, Ast *no return kind; } - // add_type_info_type(c, o->type); - // add_type_info_type(c, t); + add_type_info_type(c, o->type); + add_type_info_type(c, t); o->type = t; o->mode = Addressing_OptionalOk; diff --git a/src/checker.cpp b/src/checker.cpp index 8cb6ea99d..a2ed73119 100644 --- a/src/checker.cpp +++ b/src/checker.cpp @@ -2026,14 +2026,13 @@ gb_internal void add_min_dep_type_info(Checker *c, Type *t) { ti_index = type_info_index(&c->info, t, false); } GB_ASSERT(ti_index >= 0); - if (map_get(set, ti_index)) { - // Type already exists; - return; - } // IMPORTANT NOTE(bill): this must be copied as `map_set` takes a const ref // and effectively assigns the `+1` of the value isize const count = set->entries.count; - map_set(set, ti_index, count); + if (map_set_if_not_previously_exists(set, ti_index, count)) { + // Type already exists; + return; + } // Add nested types if (t->kind == Type_Named) { @@ -5650,34 +5649,7 @@ gb_internal void check_walk_all_dependencies(DeclInfo *decl) { for (DeclInfo *child = decl->next_child; child != nullptr; child = child->next_sibling) { check_walk_all_dependencies(child); } - if (decl->parent && decl->parent->entity && decl->parent->entity->kind == Entity_Procedure) { - Scope *ps = decl->parent->scope; - if (ps->flags & (ScopeFlag_File & ScopeFlag_Pkg & ScopeFlag_Global)) { - return; - } else { - // NOTE(bill): Add the dependencies from the procedure literal (lambda) - // But only at the procedure level - rw_mutex_shared_lock(&decl->deps_mutex); - rw_mutex_lock(&decl->parent->deps_mutex); - - for (Entity *e : decl->deps) { - ptr_set_add(&decl->parent->deps, e); - } - - rw_mutex_unlock(&decl->parent->deps_mutex); - rw_mutex_shared_unlock(&decl->deps_mutex); - - rw_mutex_shared_lock(&decl->type_info_deps_mutex); - rw_mutex_lock(&decl->parent->type_info_deps_mutex); - - for (Type *t : decl->type_info_deps) { - ptr_set_add(&decl->parent->type_info_deps, t); - } - - rw_mutex_unlock(&decl->parent->type_info_deps_mutex); - rw_mutex_shared_unlock(&decl->type_info_deps_mutex); - } - } + add_deps_from_child_to_parent(decl); } gb_internal void check_update_dependency_tree_for_procedures(Checker *c) { diff --git a/src/llvm_backend.cpp b/src/llvm_backend.cpp index 304e5ef36..192e5cc56 100644 --- a/src/llvm_backend.cpp +++ b/src/llvm_backend.cpp @@ -1920,6 +1920,7 @@ gb_internal void lb_generate_code(lbGenerator *gen) { if (!ptr_set_exists(min_dep_set, e)) { continue; } + DeclInfo *decl = decl_info_of_entity(e); if (decl == nullptr) { continue; diff --git a/src/ptr_map.cpp b/src/ptr_map.cpp index c33bf9ffb..89d2cbf9d 100644 --- a/src/ptr_map.cpp +++ b/src/ptr_map.cpp @@ -52,6 +52,7 @@ template gb_internal void map_init (PtrMap< template gb_internal void map_destroy (PtrMap *h); template gb_internal V * map_get (PtrMap *h, K key); template gb_internal void map_set (PtrMap *h, K key, V const &value); +template gb_internal bool map_set_if_not_previously_exists(PtrMap *h, K key, V const &value); // returns true if it previously existed template gb_internal void map_remove (PtrMap *h, K key); template gb_internal void map_clear (PtrMap *h); template gb_internal void map_grow (PtrMap *h); @@ -240,6 +241,34 @@ gb_internal void map_set(PtrMap *h, K key, V const &value) { } } +// returns true if it previously existed +template +gb_internal bool map_set_if_not_previously_exists(PtrMap *h, K key, V const &value) { + MapIndex index; + MapFindResult fr; + if (h->hashes.count == 0) { + map_grow(h); + } + fr = map__find(h, key); + if (fr.entry_index != MAP_SENTINEL) { + return true; + } else { + index = map__add_entry(h, key); + if (fr.entry_prev != MAP_SENTINEL) { + h->entries.data[fr.entry_prev].next = index; + } else { + h->hashes.data[fr.hash_index] = index; + } + } + h->entries.data[index].value = value; + + if (map__full(h)) { + map_grow(h); + } + return false; +} + + template gb_internal void map__erase(PtrMap *h, MapFindResult const &fr) { MapFindResult last; -- cgit v1.2.3 From 7124d541a132fc94b2c66c54bd73eb0d103ce3d3 Mon Sep 17 00:00:00 2001 From: gingerBill Date: Wed, 11 Jan 2023 18:10:27 +0000 Subject: General optimizations --- src/check_type.cpp | 3 ++- src/checker.cpp | 15 ++++++++------- src/checker.hpp | 2 +- src/ptr_map.cpp | 36 ++++++++++++++++++++++++++++++++++++ src/types.cpp | 54 ++++++++++++++++++++++++++++++++++++++++++++++++++++-- 5 files changed, 99 insertions(+), 11 deletions(-) (limited to 'src/ptr_map.cpp') diff --git a/src/check_type.cpp b/src/check_type.cpp index fd4e965d4..0863af967 100644 --- a/src/check_type.cpp +++ b/src/check_type.cpp @@ -2405,7 +2405,8 @@ gb_internal Type *make_soa_struct_internal(CheckerContext *ctx, Ast *array_typ_e } soa_struct->Struct.soa_count = cast(i32)count; - scope = create_scope(ctx->info, ctx->scope, 8); + scope = create_scope(ctx->info, ctx->scope); + string_map_init(&scope->elements, 8); soa_struct->Struct.scope = scope; String params_xyzw[4] = { diff --git a/src/checker.cpp b/src/checker.cpp index 4e8d19016..473af7128 100644 --- a/src/checker.cpp +++ b/src/checker.cpp @@ -220,11 +220,9 @@ gb_internal DeclInfo *make_decl_info(Scope *scope, DeclInfo *parent) { -gb_internal Scope *create_scope(CheckerInfo *info, Scope *parent, isize init_elements_capacity=DEFAULT_SCOPE_CAPACITY) { +gb_internal Scope *create_scope(CheckerInfo *info, Scope *parent) { Scope *s = gb_alloc_item(permanent_allocator(), Scope); s->parent = parent; - string_map_init(&s->elements, init_elements_capacity); - ptr_set_init(&s->imported, 0); if (parent != nullptr && parent != builtin_pkg->scope) { Scope *prev_head_child = parent->head_child.exchange(s, std::memory_order_acq_rel); @@ -246,7 +244,8 @@ gb_internal Scope *create_scope_from_file(CheckerInfo *info, AstFile *f) { GB_ASSERT(f->pkg->scope != nullptr); isize init_elements_capacity = gb_max(DEFAULT_SCOPE_CAPACITY, 2*f->total_file_decl_count); - Scope *s = create_scope(info, f->pkg->scope, init_elements_capacity); + Scope *s = create_scope(info, f->pkg->scope); + string_map_init(&s->elements, init_elements_capacity); s->flags |= ScopeFlag_File; @@ -265,7 +264,8 @@ gb_internal Scope *create_scope_from_package(CheckerContext *c, AstPackage *pkg) } isize init_elements_capacity = gb_max(DEFAULT_SCOPE_CAPACITY, 2*total_pkg_decl_count); - Scope *s = create_scope(c->info, builtin_pkg->scope, init_elements_capacity); + Scope *s = create_scope(c->info, builtin_pkg->scope); + string_map_init(&s->elements, init_elements_capacity); s->flags |= ScopeFlag_Pkg; s->pkg = pkg; @@ -1753,7 +1753,8 @@ gb_internal void add_type_info_type_internal(CheckerContext *c, Type *t) { add_type_info_dependency(c->info, c->decl, t); MUTEX_GUARD_BLOCK(&c->info->type_info_mutex) { - auto found = map_get(&c->info->type_info_map, t); + MapFindResult fr; + auto found = map_try_get(&c->info->type_info_map, t, &fr); if (found != nullptr) { // Types have already been added return; @@ -1777,7 +1778,7 @@ gb_internal void add_type_info_type_internal(CheckerContext *c, Type *t) { ti_index = c->info->type_info_types.count; array_add(&c->info->type_info_types, t); } - map_set(&c->checker->info.type_info_map, t, ti_index); + map_set_internal_from_try_get(&c->checker->info.type_info_map, t, ti_index, fr); if (prev) { // NOTE(bill): If a previous one exists already, no need to continue diff --git a/src/checker.hpp b/src/checker.hpp index 8b8819d97..806eb2e51 100644 --- a/src/checker.hpp +++ b/src/checker.hpp @@ -223,7 +223,7 @@ enum ScopeFlag : i32 { ScopeFlag_ContextDefined = 1<<16, }; -enum { DEFAULT_SCOPE_CAPACITY = 29 }; +enum { DEFAULT_SCOPE_CAPACITY = 32 }; struct Scope { Ast * node; diff --git a/src/ptr_map.cpp b/src/ptr_map.cpp index 89d2cbf9d..598904906 100644 --- a/src/ptr_map.cpp +++ b/src/ptr_map.cpp @@ -192,6 +192,26 @@ gb_internal void map_rehash(PtrMap *h, isize new_count) { template gb_internal V *map_get(PtrMap *h, K key) { + MapIndex hash_index = MAP_SENTINEL; + MapIndex entry_prev = MAP_SENTINEL; + MapIndex entry_index = MAP_SENTINEL; + if (h->hashes.count != 0) { + u32 hash = ptr_map_hash_key(key); + hash_index = cast(MapIndex)(hash & (h->hashes.count-1)); + entry_index = h->hashes.data[hash_index]; + while (entry_index != MAP_SENTINEL) { + auto *entry = &h->entries.data[entry_index]; + if (entry->key == key) { + return &entry->value; + } + entry_prev = entry_index; + entry_index = entry->next; + } + } + return nullptr; +} +template +gb_internal V *map_try_get(PtrMap *h, K key, MapFindResult *fr_) { MapFindResult fr = {MAP_SENTINEL, MAP_SENTINEL, MAP_SENTINEL}; if (h->hashes.count != 0) { u32 hash = ptr_map_hash_key(key); @@ -206,9 +226,25 @@ gb_internal V *map_get(PtrMap *h, K key) { fr.entry_index = entry->next; } } + if (h->hashes.count == 0 || map__full(h)) { + map_grow(h); + } + if (fr_) *fr_ = fr; return nullptr; } + +template +gb_internal void map_set_internal_from_try_get(PtrMap *h, K key, V const &value, MapFindResult const &fr) { + MapIndex index = map__add_entry(h, key); + if (fr.entry_prev != MAP_SENTINEL) { + h->entries.data[fr.entry_prev].next = index; + } else { + h->hashes.data[fr.hash_index] = index; + } + h->entries.data[index].value = value; +} + template gb_internal V &map_must_get(PtrMap *h, K key) { V *ptr = map_get(h, key); diff --git a/src/types.cpp b/src/types.cpp index 99f393cc5..69c1ebe68 100644 --- a/src/types.cpp +++ b/src/types.cpp @@ -2528,9 +2528,58 @@ gb_internal bool lookup_subtype_polymorphic_selection(Type *dst, Type *src, Sele gb_internal bool are_types_identical_internal(Type *x, Type *y, bool check_tuple_names); gb_internal bool are_types_identical(Type *x, Type *y) { + if (x == y) { + return true; + } + + if ((x == nullptr && y != nullptr) || + (x != nullptr && y == nullptr)) { + return false; + } + + if (x->kind == Type_Named) { + Entity *e = x->Named.type_name; + if (e->TypeName.is_type_alias) { + x = x->Named.base; + } + } + if (y->kind == Type_Named) { + Entity *e = y->Named.type_name; + if (e->TypeName.is_type_alias) { + y = y->Named.base; + } + } + if (x->kind != y->kind) { + return false; + } + return are_types_identical_internal(x, y, false); } gb_internal bool are_types_identical_unique_tuples(Type *x, Type *y) { + if (x == y) { + return true; + } + + if (!x | !y) { + return false; + } + + if (x->kind == Type_Named) { + Entity *e = x->Named.type_name; + if (e->TypeName.is_type_alias) { + x = x->Named.base; + } + } + if (y->kind == Type_Named) { + Entity *e = y->Named.type_name; + if (e->TypeName.is_type_alias) { + y = y->Named.base; + } + } + if (x->kind != y->kind) { + return false; + } + return are_types_identical_internal(x, y, true); } @@ -2540,11 +2589,11 @@ gb_internal bool are_types_identical_internal(Type *x, Type *y, bool check_tuple return true; } - if ((x == nullptr && y != nullptr) || - (x != nullptr && y == nullptr)) { + if (!x | !y) { return false; } + #if 0 if (x->kind == Type_Named) { Entity *e = x->Named.type_name; if (e->TypeName.is_type_alias) { @@ -2560,6 +2609,7 @@ gb_internal bool are_types_identical_internal(Type *x, Type *y, bool check_tuple if (x->kind != y->kind) { return false; } + #endif switch (x->kind) { case Type_Generic: -- cgit v1.2.3