Change Map and PtrSet grow rate

8 files changed, 104 insertions, 84 deletions

diff --git a/src/check_decl.cpp b/src/check_decl.cpp
index 351a8d0a0..3501ba84d 100644
--- a/src/check_decl.cpp
+++ b/src/check_decl.cpp
@@ -822,6 +822,20 @@ void check_entity_decl(Checker *c, Entity *e, DeclInfo *d, Type *named_type) {
 		return;
 	}
 
+#if 0
+	char buf[256] = {};
+	isize n = gb_snprintf(buf, 256, "%.*s %d", LIT(e->token.string), e->kind);
+	Timings timings = {};
+	timings_init(&timings, make_string(cast(u8 *)buf, n-1), 16);
+	defer ({
+		timings_print_all(&timings);
+		timings_destroy(&timings);
+	});
+#define TIME_SECTION(str) timings_start_section(&timings, str_lit(str))
+#else
+#define TIME_SECTION(str)
+#endif
+
 	if (d == nullptr) {
 		d = decl_info_of_entity(&c->info, e);
 		if (d == nullptr) {
@@ -860,6 +874,8 @@ void check_entity_decl(Checker *c, Entity *e, DeclInfo *d, Type *named_type) {
 	}
 
 	c->context = prev;
+
+#undef TIME_SECTION
 }
 
 
diff --git a/src/check_expr.cpp b/src/check_expr.cpp
index b153b65a3..9981a4543 100644
--- a/src/check_expr.cpp
+++ b/src/check_expr.cpp
@@ -5054,13 +5054,13 @@ ExprKind check_expr_base_internal(Checker *c, Operand *o, AstNode *node, Type *t
 
 	case_ast_node(bl, BasicLit, node);
 		Type *t = t_invalid;
-		switch (bl->kind) {
+		switch (bl->token.kind) {
 		case Token_Integer: t = t_untyped_integer; break;
 		case Token_Float:   t = t_untyped_float;   break;
 		case Token_String:  t = t_untyped_string;  break;
 		case Token_Rune:    t = t_untyped_rune;    break;
 		case Token_Imag: {
-			String s = bl->string;
+			String s = bl->token.string;
 			Rune r = s[s.len-1];
 			switch (r) {
 			case 'i': t = t_untyped_complex; break;
@@ -5072,7 +5072,7 @@ ExprKind check_expr_base_internal(Checker *c, Operand *o, AstNode *node, Type *t
 		}
 		o->mode  = Addressing_Constant;
 		o->type  = t;
-		o->value = exact_value_from_basic_literal(*bl);
+		o->value = exact_value_from_basic_literal(bl->token);
 	case_end;
 
 	case_ast_node(bd, BasicDirective, node);
@@ -5429,7 +5429,6 @@ ExprKind check_expr_base_internal(Checker *c, Operand *o, AstNode *node, Type *t
 			}
 
 			for (; index < elem_count; index++) {
-				GB_ASSERT(cl->elems.data != nullptr);
 				AstNode *e = cl->elems[index];
 				if (e == nullptr) {
 					error(node, "Invalid literal element");
@@ -5449,9 +5448,7 @@ ExprKind check_expr_base_internal(Checker *c, Operand *o, AstNode *node, Type *t
 				check_expr_with_type_hint(c, &operand, e, elem_type);
 				check_assignment(c, &operand, elem_type, context_name);
 
-				if (is_constant) {
-					is_constant = operand.mode == Addressing_Constant;
-				}
+				is_constant = is_constant && operand.mode == Addressing_Constant;
 			}
 			if (max < index) {
 				max = index;
@@ -6093,7 +6090,7 @@ gbString write_expr_to_string(gbString str, AstNode *node) {
 	case_end;
 
 	case_ast_node(bl, BasicLit, node);
-		str = string_append_token(str, *bl);
+		str = string_append_token(str, bl->token);
 	case_end;
 
 	case_ast_node(bd, BasicDirective, node);
diff --git a/src/checker.cpp b/src/checker.cpp
index 6fc4ca8da..873851509 100644
--- a/src/checker.cpp
+++ b/src/checker.cpp
@@ -269,6 +269,14 @@ i32 is_scope_an_ancestor(Scope *parent, Scope *child) {
 struct EntityGraphNode;
 typedef PtrSet<EntityGraphNode *> EntityGraphNodeSet;
 
+struct EntityGraphNode {
+	Entity *     entity; // Procedure, Variable, Constant
+	EntityGraphNodeSet pred;
+	EntityGraphNodeSet succ;
+	isize        index; // Index in array/queue
+	isize        dep_count;
+};
+
 void entity_graph_node_set_destroy(EntityGraphNodeSet *s) {
 	if (s->hashes.data != nullptr) {
 		ptr_set_destroy(s);
@@ -290,16 +298,6 @@ void entity_graph_node_set_remove(EntityGraphNodeSet *s, EntityGraphNode *n) {
 	ptr_set_remove(s, n);
 }
 
-
-struct EntityGraphNode {
-	Entity *     entity; // Procedure, Variable, Constant
-	EntityGraphNodeSet pred;
-	EntityGraphNodeSet succ;
-	isize        index; // Index in array/queue
-	isize        dep_count;
-};
-
-
 void entity_graph_node_destroy(EntityGraphNode *n, gbAllocator a) {
 	entity_graph_node_set_destroy(&n->pred);
 	entity_graph_node_set_destroy(&n->succ);
@@ -1119,8 +1117,17 @@ isize type_info_index(CheckerInfo *info, Type *type, bool error_on_failure) {
 }
 
 
-void add_untyped(CheckerInfo *i, AstNode *expression, bool lhs, AddressingMode mode, Type *basic_type, ExactValue value) {
-	map_set(&i->untyped, hash_node(expression), make_expr_info(lhs, mode, basic_type, value));
+void add_untyped(CheckerInfo *i, AstNode *expression, bool lhs, AddressingMode mode, Type *type, ExactValue value) {
+	if (expression == nullptr) {
+		return;
+	}
+	if (mode == Addressing_Invalid) {
+		return;
+	}
+	if (mode == Addressing_Constant && type == t_invalid) {
+		compiler_error("add_untyped - invalid type: %s", type_to_string(type));
+	}
+	map_set(&i->untyped, hash_node(expression), make_expr_info(lhs, mode, type, value));
 }
 
 void add_type_and_value(CheckerInfo *i, AstNode *expression, AddressingMode mode, Type *type, ExactValue value) {
@@ -1130,13 +1137,8 @@ void add_type_and_value(CheckerInfo *i, AstNode *expression, AddressingMode mode
 	if (mode == Addressing_Invalid) {
 		return;
 	}
-
-	if (mode == Addressing_Constant) {
-		if (is_type_constant_type(type)) {
-			if (!(type != t_invalid || is_type_constant_type(type))) {
-				compiler_error("add_type_and_value - invalid type: %s", type_to_string(type));
-			}
-		}
+	if (mode == Addressing_Constant && type == t_invalid) {
+		compiler_error("add_type_and_value - invalid type: %s", type_to_string(type));
 	}
 
 	TypeAndValue tv = {};
@@ -1148,20 +1150,18 @@ void add_type_and_value(CheckerInfo *i, AstNode *expression, AddressingMode mode
 
 void add_entity_definition(CheckerInfo *i, AstNode *identifier, Entity *entity) {
 	GB_ASSERT(identifier != nullptr);
-	if (identifier->kind == AstNode_Ident) {
-		if (is_blank_ident(identifier)) {
-			return;
-		}
-		if (identifier->Ident.entity != nullptr) {
-			return;
-		}
-
-		identifier->Ident.entity = entity;
-		entity->identifier = identifier;
-		array_add(&i->definitions, entity);
-	} else {
-		// NOTE(bill): Error should be handled elsewhere
+	GB_ASSERT(identifier->kind == AstNode_Ident);
+	if (is_blank_ident(identifier)) {
+		return;
 	}
+	if (identifier->Ident.entity != nullptr) {
+		// NOTE(bill): Identifier has already been handled
+		return;
+	}
+
+	identifier->Ident.entity = entity;
+	entity->identifier = identifier;
+	array_add(&i->definitions, entity);
 }
 
 bool add_entity(Checker *c, Scope *scope, AstNode *identifier, Entity *entity) {
@@ -1510,7 +1510,7 @@ Array<EntityGraphNode *> generate_entity_dependency_graph(CheckerInfo *info) {
 	gbAllocator a = heap_allocator();
 
 	Map<EntityGraphNode *> M = {}; // Key: Entity *
-	map_init(&M, a);
+	map_init(&M, a, info->entities.count);
 	defer (map_destroy(&M));
 	for_array(i, info->entities) {
 		Entity *e = info->entities[i];
@@ -1522,7 +1522,6 @@ Array<EntityGraphNode *> generate_entity_dependency_graph(CheckerInfo *info) {
 		}
 	}
 
-
 	// Calculate edges for graph M
 	for_array(i, M.entries) {
 		Entity *   e = cast(Entity *)M.entries[i].key.ptr;
@@ -1546,7 +1545,7 @@ Array<EntityGraphNode *> generate_entity_dependency_graph(CheckerInfo *info) {
 	}
 
 	Array<EntityGraphNode *> G = {};
-	array_init(&G, a, 2*M.entries.count);
+	array_init(&G, a, M.entries.count);
 
 	for_array(i, M.entries) {
 		auto *entry = &M.entries[i];
@@ -1589,7 +1588,6 @@ Array<EntityGraphNode *> generate_entity_dependency_graph(CheckerInfo *info) {
 		GB_ASSERT(n->dep_count >= 0);
 	}
 
-
 	return G;
 }
 
@@ -3146,8 +3144,22 @@ Array<Entity *> find_entity_path(Entity *start, Entity *end, Map<Entity *> *visi
 
 
 void calculate_global_init_order(Checker *c) {
+#if 0
+	Timings timings = {};
+	timings_init(&timings, str_lit("calculate_global_init_order"), 16);
+	defer ({
+		timings_print_all(&timings);
+		timings_destroy(&timings);
+	});
+#define TIME_SECTION(str) timings_start_section(&timings, str_lit(str))
+#else
+#define TIME_SECTION(str)
+#endif
+
+
 	CheckerInfo *info = &c->info;
 
+	TIME_SECTION("generate entity dependency graph");
 	Array<EntityGraphNode *> dep_graph = generate_entity_dependency_graph(info);
 	defer ({
 		for_array(i, dep_graph) {
@@ -3156,6 +3168,7 @@ void calculate_global_init_order(Checker *c) {
 		array_free(&dep_graph);
 	});
 
+	TIME_SECTION("priority queue create");
 	// NOTE(bill): Priority queue
 	auto pq = priority_queue_create(dep_graph, entity_graph_node_cmp, entity_graph_node_swap);
 
@@ -3163,6 +3176,7 @@ void calculate_global_init_order(Checker *c) {
 	ptr_set_init(&emitted, heap_allocator());
 	defer (ptr_set_destroy(&emitted));
 
+	TIME_SECTION("queue sort");
 	while (pq.queue.count > 0) {
 		EntityGraphNode *n = priority_queue_pop(&pq);
 		Entity *e = n->entity;
@@ -3220,6 +3234,8 @@ void calculate_global_init_order(Checker *c) {
 		}
 		gb_printf("\n");
 	}
+
+#undef TIME_SECTION
 }
 
 
diff --git a/src/integer128.cpp b/src/integer128.cpp
index e9a0cb1ca..583c67281 100644
--- a/src/integer128.cpp
+++ b/src/integer128.cpp
@@ -491,6 +491,11 @@ void u128_divide(u128 a, u128 b, u128 *quo, u128 *rem) {
 		if (rem) *rem = U128_ZERO;
 		return;
 	}
+	if (a.hi == 0 && b.hi == 0) {
+		if (quo) *quo = u128_from_u64(a.lo/b.lo);
+		if (rem) *rem = u128_from_u64(a.lo%b.lo);
+		return;
+	}
 	u128 r = a;
 	u128 d = b;
 	u128 x = U128_ONE;
@@ -670,7 +675,7 @@ i128 i128_mul(i128 a, i128 b) {
 }
 
 void i128_divide(i128 a, i128 b, i128 *quo_, i128 *rem_) {
-	// TODO(bill): Optimize this i128 division calculation
+	// IMPORTANT TODO(bill): Optimize this i128 division calculation
 	i128 iquo = {0};
 	i128 irem = {0};
 	if (a.hi == 0 && b.hi == 0) {
diff --git a/src/ir.cpp b/src/ir.cpp
index 66d0f3ee4..3a64585d4 100644
--- a/src/ir.cpp
+++ b/src/ir.cpp
@@ -4683,8 +4683,8 @@ irValue *ir_build_expr(irProcedure *proc, AstNode *expr) {
 
 	switch (expr->kind) {
 	case_ast_node(bl, BasicLit, expr);
-		TokenPos pos = bl->pos;
-		GB_PANIC("Non-constant basic literal %.*s(%td:%td) - %.*s", LIT(pos.file), pos.line, pos.column, LIT(token_strings[bl->kind]));
+		TokenPos pos = bl->token.pos;
+		GB_PANIC("Non-constant basic literal %.*s(%td:%td) - %.*s", LIT(pos.file), pos.line, pos.column, LIT(token_strings[bl->token.kind]));
 	case_end;
 
 	case_ast_node(bd, BasicDirective, expr);
diff --git a/src/map.cpp b/src/map.cpp
index 0ff39cac6..08a059d56 100644
--- a/src/map.cpp
+++ b/src/map.cpp
@@ -183,9 +183,12 @@ gb_internal b32 map__full(Map<T> *h) {
 	return 0.75f * h->hashes.count <= h->entries.count;
 }
 
+#define MAP_ARRAY_GROW_FORMULA(x) (4*(x) + 7)
+GB_STATIC_ASSERT(MAP_ARRAY_GROW_FORMULA(0) > 0);
+
 template <typename T>
 gb_inline void map_grow(Map<T> *h) {
-	isize new_count = ARRAY_GROW_FORMULA(h->entries.count);
+	isize new_count = MAP_ARRAY_GROW_FORMULA(h->entries.count);
 	map_rehash(h, new_count);
 }
 
diff --git a/src/parser.cpp b/src/parser.cpp
index f735744f1..23b99a2ba 100644
--- a/src/parser.cpp
+++ b/src/parser.cpp
@@ -157,7 +157,9 @@ Array<AstNode *> make_ast_node_array(AstFile *f, isize init_capacity = 8) {
 	}) \
 	AST_NODE_KIND(Implicit,       "implicit",        Token) \
 	AST_NODE_KIND(Undef,          "undef",           Token) \
-	AST_NODE_KIND(BasicLit,       "basic literal",   Token) \
+	AST_NODE_KIND(BasicLit,       "basic literal",   struct { \
+		Token token; \
+	}) \
 	AST_NODE_KIND(BasicDirective, "basic directive", struct { \
 		Token token; \
 		String name; \
@@ -543,7 +545,7 @@ Token ast_node_token(AstNode *node) {
 	case AstNode_Ident:          return node->Ident.token;
 	case AstNode_Implicit:       return node->Implicit;
 	case AstNode_Undef:          return node->Undef;
-	case AstNode_BasicLit:       return node->BasicLit;
+	case AstNode_BasicLit:       return node->BasicLit.token;
 	case AstNode_BasicDirective: return node->BasicDirective.token;
 	case AstNode_ProcGroup:      return node->ProcGroup.token;
 	case AstNode_ProcLit:        return ast_node_token(node->ProcLit.type);
@@ -1110,7 +1112,7 @@ AstNode *ast_undef(AstFile *f, Token token) {
 
 AstNode *ast_basic_lit(AstFile *f, Token basic_lit) {
 	AstNode *result = make_ast_node(f, AstNode_BasicLit);
-	result->BasicLit = basic_lit;
+	result->BasicLit.token = basic_lit;
 	return result;
 }
 
@@ -2179,30 +2181,8 @@ AstNode *parse_operand(AstFile *f, bool lhs) {
 		return parse_call_expr(f, ast_implicit(f, advance_token(f)));
 
 
-	case Token_String: {
-		Token token = advance_token(f);
-		if (f->curr_token.kind == Token_String) {
-			// NOTE(bill): Allow neighbouring string literals to be merge together to
-			// become one big string
-			String s = f->curr_token.string;
-			Array<u8> data = {};
-			array_init_count(&data, heap_allocator(), token.string.len+s.len);
-			gb_memmove(data.data, token.string.text, token.string.len);
-
-			while (f->curr_token.kind == Token_String) {
-				String s = f->curr_token.string;
-				isize old_count = data.count;
-				array_resize(&data, data.count + s.len);
-				gb_memmove(data.data+old_count, s.text, s.len);
-				advance_token(f);
-			}
-
-			token.string = make_string(data.data, data.count);
-			array_add(&f->tokenizer.allocated_strings, token.string);
-		}
-
-		return ast_basic_lit(f, token);
-	}
+	case Token_String:
+		return ast_basic_lit(f, advance_token(f));
 
 	case Token_OpenBrace:
 		if (!lhs) return parse_literal_value(f, nullptr);
diff --git a/src/ptr_set.cpp b/src/ptr_set.cpp
index d16002b3e..317b8e68c 100644
--- a/src/ptr_set.cpp
+++ b/src/ptr_set.cpp
@@ -17,14 +17,14 @@ struct PtrSet {
 	Array<PtrSetEntry<T>> entries;
 };
 
-template <typename T> void ptr_set_init             (PtrSet<T> *s, gbAllocator a, isize capacity = 16);
-template <typename T> void ptr_set_destroy          (PtrSet<T> *s);
-template <typename T> T    ptr_set_add              (PtrSet<T> *s, T ptr);
-template <typename T> bool ptr_set_exists           (PtrSet<T> *s, T ptr);
-template <typename T> void ptr_set_remove           (PtrSet<T> *s, T ptr);
-template <typename T> void ptr_set_clear            (PtrSet<T> *s);
-template <typename T> void ptr_set_grow             (PtrSet<T> *s);
-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 = 16);
+template <typename T> void ptr_set_destroy(PtrSet<T> *s);
+template <typename T> T    ptr_set_add    (PtrSet<T> *s, T ptr);
+template <typename T> bool ptr_set_exists (PtrSet<T> *s, T ptr);
+template <typename T> void ptr_set_remove (PtrSet<T> *s, T ptr);
+template <typename T> void ptr_set_clear  (PtrSet<T> *s);
+template <typename T> void ptr_set_grow   (PtrSet<T> *s);
+template <typename T> void ptr_set_rehash (PtrSet<T> *s, isize new_count);
 
 
 template <typename T>
@@ -88,9 +88,12 @@ gb_internal b32 ptr_set__full(PtrSet<T> *s) {
 	return 0.75f * s->hashes.count <= s->entries.count;
 }
 
+#define PTR_ARRAY_GROW_FORMULA(x) (4*(x) + 7)
+GB_STATIC_ASSERT(PTR_ARRAY_GROW_FORMULA(0) > 0);
+
 template <typename T>
 gb_inline void ptr_set_grow(PtrSet<T> *s) {
-	isize new_count = ARRAY_GROW_FORMULA(s->entries.count);
+	isize new_count = PTR_ARRAY_GROW_FORMULA(s->entries.count);
 	ptr_set_rehash(s, new_count);
 }