Merge pull request #2181 from odin-lang/map-dev

New `map` internals

18 files changed, 777 insertions, 300 deletions

diff --git a/src/build_settings.cpp b/src/build_settings.cpp
index 8067d1d01..1cd2899c4 100644
--- a/src/build_settings.cpp
+++ b/src/build_settings.cpp
@@ -307,6 +307,8 @@ struct BuildContext {
 
 	bool   disallow_rtti;
 
+	bool   use_static_map_calls;
+
 	RelocMode reloc_mode;
 	bool   disable_red_zone;
 
diff --git a/src/check_builtin.cpp b/src/check_builtin.cpp
index 51306bd7b..809d1d9a5 100644
--- a/src/check_builtin.cpp
+++ b/src/check_builtin.cpp
@@ -5370,6 +5370,43 @@ bool check_builtin_procedure(CheckerContext *c, Operand *operand, Ast *call, i32
 			break;
 		}
 
+	case BuiltinProc_type_map_info:
+		{
+			Operand op = {};
+			Type *bt = check_type(c, ce->args[0]);
+			Type *type = base_type(bt);
+			if (type == nullptr || type == t_invalid) {
+				error(ce->args[0], "Expected a type for '%.*s'", LIT(builtin_name));
+				return false;
+			}
+			if (!is_type_map(type)) {
+				gbString t = type_to_string(type);
+				error(ce->args[0], "Expected a map type for '%.*s', got %s", LIT(builtin_name), t);
+				gb_string_free(t);
+				return false;
+			}
+
+			add_map_key_type_dependencies(c, type);
+
+			operand->mode = Addressing_Value;
+			operand->type = t_map_info_ptr;
+			break;
+		}
+	case BuiltinProc_type_map_cell_info:
+		{
+			Operand op = {};
+			Type *bt = check_type(c, ce->args[0]);
+			Type *type = base_type(bt);
+			if (type == nullptr || type == t_invalid) {
+				error(ce->args[0], "Expected a type for '%.*s'", LIT(builtin_name));
+				return false;
+			}
+
+			operand->mode = Addressing_Value;
+			operand->type = t_map_cell_info_ptr;
+			break;
+		}
+
 	case BuiltinProc_constant_utf16_cstring:
 		{
 			String value = {};
diff --git a/src/check_expr.cpp b/src/check_expr.cpp
index 9e48fd8ad..c58aac609 100644
--- a/src/check_expr.cpp
+++ b/src/check_expr.cpp
@@ -285,6 +285,37 @@ void error_operand_no_value(Operand *o) {
 	}
 }
 
+void add_map_get_dependencies(CheckerContext *c) {
+	if (build_context.use_static_map_calls) {
+		add_package_dependency(c, "runtime", "map_desired_position");
+		add_package_dependency(c, "runtime", "map_probe_distance");
+	} else {
+		add_package_dependency(c, "runtime", "__dynamic_map_get");
+	}
+}
+
+void add_map_set_dependencies(CheckerContext *c) {
+	init_core_source_code_location(c->checker);
+
+	if (t_map_set_proc == nullptr) {
+		Type *map_set_args[5] = {/*map*/t_rawptr, /*hash*/t_uintptr, /*key*/t_rawptr, /*value*/t_rawptr, /*#caller_location*/t_source_code_location};
+		t_map_set_proc = alloc_type_proc_from_types(map_set_args, gb_count_of(map_set_args), t_rawptr, false, ProcCC_Odin);
+	}
+
+	if (build_context.use_static_map_calls) {
+		add_package_dependency(c, "runtime", "__dynamic_map_check_grow");
+		add_package_dependency(c, "runtime", "map_insert_hash_dynamic");
+	} else {
+		add_package_dependency(c, "runtime", "__dynamic_map_set");
+	}
+}
+
+void add_map_reserve_dependencies(CheckerContext *c) {
+	init_core_source_code_location(c->checker);
+	add_package_dependency(c, "runtime", "__dynamic_map_reserve");
+}
+
+
 
 void check_scope_decls(CheckerContext *c, Slice<Ast *> const &nodes, isize reserve_size) {
 	Scope *s = c->scope;
@@ -1364,8 +1395,6 @@ bool is_polymorphic_type_assignable(CheckerContext *c, Type *poly, Type *source,
 			bool key   = is_polymorphic_type_assignable(c, poly->Map.key, source->Map.key, true, modify_type);
 			bool value = is_polymorphic_type_assignable(c, poly->Map.value, source->Map.value, true, modify_type);
 			if (key || value) {
-				poly->Map.entry_type = nullptr;
-				poly->Map.internal_type = nullptr;
 				poly->Map.lookup_result_type = nullptr;
 				init_map_internal_types(poly);
 				return true;
@@ -3246,7 +3275,7 @@ void check_binary_expr(CheckerContext *c, Operand *x, Ast *node, Type *type_hint
 				check_assignment(c, x, yt->Map.key, str_lit("map 'not_in'"));
 			}
 
-			add_package_dependency(c, "runtime", "__dynamic_map_get");
+			add_map_get_dependencies(c);
 		} else if (is_type_bit_set(rhs_type)) {
 			Type *yt = base_type(rhs_type);
 
@@ -8557,8 +8586,8 @@ ExprKind check_compound_literal(CheckerContext *c, Operand *o, Ast *node, Type *
 		if (build_context.no_dynamic_literals && cl->elems.count) {
 			error(node, "Compound literals of dynamic types have been disabled");
 		} else {
-			add_package_dependency(c, "runtime", "__dynamic_map_reserve");
-			add_package_dependency(c, "runtime", "__dynamic_map_set");
+			add_map_reserve_dependencies(c);
+			add_map_set_dependencies(c);
 		}
 		break;
 	}
@@ -8994,8 +9023,8 @@ ExprKind check_index_expr(CheckerContext *c, Operand *o, Ast *node, Type *type_h
 		o->type = t->Map.value;
 		o->expr = node;
 
-		add_package_dependency(c, "runtime", "__dynamic_map_get");
-		add_package_dependency(c, "runtime", "__dynamic_map_set");
+		add_map_get_dependencies(c);
+		add_map_set_dependencies(c);
 		return Expr_Expr;
 	}
 
diff --git a/src/check_type.cpp b/src/check_type.cpp
index 2ffe04342..4d94fce6c 100644
--- a/src/check_type.cpp
+++ b/src/check_type.cpp
@@ -2176,70 +2176,36 @@ Type *make_optional_ok_type(Type *value, bool typed) {
 	return t;
 }
 
-void init_map_entry_type(Type *type) {
-	GB_ASSERT(type->kind == Type_Map);
-	if (type->Map.entry_type != nullptr) return;
-
-	// NOTE(bill): The preload types may have not been set yet
-	GB_ASSERT(t_map_hash != nullptr);
-
-	/*
-	struct {
-		hash:  uintptr,
-		next:  int,
-		key:   Key,
-		value: Value,
-	}
-	*/
-	Scope *s = create_scope(nullptr, builtin_pkg->scope);
-
-	auto fields = slice_make<Entity *>(permanent_allocator(), 4);
-	fields[0] = alloc_entity_field(s, make_token_ident(str_lit("hash")),  t_uintptr,       false, 0, EntityState_Resolved);
-	fields[1] = alloc_entity_field(s, make_token_ident(str_lit("next")),  t_int,           false, 1, EntityState_Resolved);
-	fields[2] = alloc_entity_field(s, make_token_ident(str_lit("key")),   type->Map.key,   false, 2, EntityState_Resolved);
-	fields[3] = alloc_entity_field(s, make_token_ident(str_lit("value")), type->Map.value, false, 3, EntityState_Resolved);
-
-	Type *entry_type = alloc_type_struct();
-	entry_type->Struct.fields  = fields;
-	entry_type->Struct.tags    = gb_alloc_array(permanent_allocator(), String, fields.count);
-	
-	type_set_offsets(entry_type);
-	type->Map.entry_type = entry_type;
+
+// IMPORTANT NOTE(bill): This must match the definition in dynamic_map_internal.odin
+enum : i64 {
+	MAP_CACHE_LINE_LOG2 = 6,
+	MAP_CACHE_LINE_SIZE = 1 << MAP_CACHE_LINE_LOG2
+};
+GB_STATIC_ASSERT(MAP_CACHE_LINE_SIZE >= 64);
+void map_cell_size_and_len(Type *type, i64 *size_, i64 *len_) {
+	i64 elem_sz = type_size_of(type);
+
+	i64 len = 1;
+	if (0 < elem_sz && elem_sz < MAP_CACHE_LINE_SIZE) {
+		len = MAP_CACHE_LINE_SIZE / elem_sz;
+	}
+	i64 size = align_formula(elem_sz * len, MAP_CACHE_LINE_SIZE);
+	if (size_) *size_ = size;
+	if (len_)  *len_ = len;
 }
 
 void init_map_internal_types(Type *type) {
 	GB_ASSERT(type->kind == Type_Map);
-	init_map_entry_type(type);
-	if (type->Map.internal_type != nullptr) return;
+	GB_ASSERT(t_allocator != nullptr);
+	if (type->Map.lookup_result_type != nullptr) return;
 
 	Type *key   = type->Map.key;
 	Type *value = type->Map.value;
 	GB_ASSERT(key != nullptr);
 	GB_ASSERT(value != nullptr);
 
-	Type *generated_struct_type = alloc_type_struct();
-
-	/*
-	struct {
-		hashes:  []int;
-		entries: [dynamic]EntryType;
-	}
-	*/
-	Scope *s = create_scope(nullptr, builtin_pkg->scope);
-
-	Type *hashes_type  = alloc_type_slice(t_int);
-	Type *entries_type = alloc_type_dynamic_array(type->Map.entry_type);
-
-
-	auto fields = slice_make<Entity *>(permanent_allocator(), 2);
-	fields[0] = alloc_entity_field(s, make_token_ident(str_lit("hashes")),  hashes_type,  false, 0, EntityState_Resolved);
-	fields[1] = alloc_entity_field(s, make_token_ident(str_lit("entries")), entries_type, false, 1, EntityState_Resolved);
-
-	generated_struct_type->Struct.fields = fields;
-	type_set_offsets(generated_struct_type);
-	
-	type->Map.internal_type         = generated_struct_type;
-	type->Map.lookup_result_type    = make_optional_ok_type(value);
+	type->Map.lookup_result_type = make_optional_ok_type(value);
 }
 
 void add_map_key_type_dependencies(CheckerContext *ctx, Type *key) {
@@ -2255,35 +2221,27 @@ void add_map_key_type_dependencies(CheckerContext *ctx, Type *key) {
 		}
 
 		if (is_type_simple_compare(key)) {
-			i64 sz = type_size_of(key);
-			if (1 <= sz && sz <= 16) {
-				char buf[20] = {};
-				gb_snprintf(buf, 20, "default_hasher%d", cast(i32)sz);
-				add_package_dependency(ctx, "runtime", buf);
-				return;
-			} else {
-				add_package_dependency(ctx, "runtime", "default_hasher_n");
-				return;
-			}
+			add_package_dependency(ctx, "runtime", "default_hasher");
+			return;
 		}
 
 		if (key->kind == Type_Struct) {
-			add_package_dependency(ctx, "runtime", "default_hasher_n");
+			add_package_dependency(ctx, "runtime", "default_hasher");
 			for_array(i, key->Struct.fields) {
 				Entity *field = key->Struct.fields[i];
 				add_map_key_type_dependencies(ctx, field->type);
 			}
 		} else if (key->kind == Type_Union) {
-			add_package_dependency(ctx, "runtime", "default_hasher_n");
+			add_package_dependency(ctx, "runtime", "default_hasher");
 			for_array(i, key->Union.variants) {
 				Type *v = key->Union.variants[i];
 				add_map_key_type_dependencies(ctx, v);
 			}
 		} else if (key->kind == Type_EnumeratedArray) {
-			add_package_dependency(ctx, "runtime", "default_hasher_n");
+			add_package_dependency(ctx, "runtime", "default_hasher");
 			add_map_key_type_dependencies(ctx, key->EnumeratedArray.elem);
 		} else if (key->kind == Type_Array) {
-			add_package_dependency(ctx, "runtime", "default_hasher_n");
+			add_package_dependency(ctx, "runtime", "default_hasher");
 			add_map_key_type_dependencies(ctx, key->Array.elem);
 		}
 	}
diff --git a/src/checker.cpp b/src/checker.cpp
index dd81e2a48..4d1ef4614 100644
--- a/src/checker.cpp
+++ b/src/checker.cpp
@@ -922,10 +922,13 @@ void init_universal(void) {
 
 	{
 		Type *equal_args[2] = {t_rawptr, t_rawptr};
-		t_equal_proc = alloc_type_proc_from_types(equal_args, 2, t_bool, false, ProcCC_Contextless);
+		t_equal_proc = alloc_type_proc_from_types(equal_args, gb_count_of(equal_args), t_bool, false, ProcCC_Contextless);
 
 		Type *hasher_args[2] = {t_rawptr, t_uintptr};
-		t_hasher_proc = alloc_type_proc_from_types(hasher_args, 2, t_uintptr, false, ProcCC_Contextless);
+		t_hasher_proc = alloc_type_proc_from_types(hasher_args, gb_count_of(hasher_args), t_uintptr, false, ProcCC_Contextless);
+
+		Type *map_get_args[3] = {/*map*/t_rawptr, /*hash*/t_uintptr, /*key*/t_rawptr};
+		t_map_get_proc = alloc_type_proc_from_types(map_get_args, gb_count_of(map_get_args), t_rawptr, false, ProcCC_Contextless);
 	}
 
 // Constants
@@ -1933,7 +1936,8 @@ void add_type_info_type_internal(CheckerContext *c, Type *t) {
 		init_map_internal_types(bt);
 		add_type_info_type_internal(c, bt->Map.key);
 		add_type_info_type_internal(c, bt->Map.value);
-		add_type_info_type_internal(c, bt->Map.internal_type);
+		add_type_info_type_internal(c, t_uintptr); // hash value
+		add_type_info_type_internal(c, t_allocator);
 		break;
 
 	case Type_Tuple:
@@ -2155,7 +2159,8 @@ void add_min_dep_type_info(Checker *c, Type *t) {
 		init_map_internal_types(bt);
 		add_min_dep_type_info(c, bt->Map.key);
 		add_min_dep_type_info(c, bt->Map.value);
-		add_min_dep_type_info(c, bt->Map.internal_type);
+		add_min_dep_type_info(c, t_uintptr); // hash value
+		add_min_dep_type_info(c, t_allocator);
 		break;
 
 	case Type_Tuple:
@@ -2838,16 +2843,21 @@ void init_core_source_code_location(Checker *c) {
 		return;
 	}
 	t_source_code_location = find_core_type(c, str_lit("Source_Code_Location"));
-	t_source_code_location_ptr = alloc_type_pointer(t_allocator);
+	t_source_code_location_ptr = alloc_type_pointer(t_source_code_location);
 }
 
 void init_core_map_type(Checker *c) {
-	if (t_map_hash != nullptr) {
+	if (t_map_info != nullptr) {
 		return;
 	}
-	t_map_hash = find_core_type(c, str_lit("Map_Hash"));
-	t_map_header = find_core_type(c, str_lit("Map_Header"));
-	t_map_header_table = find_core_type(c, str_lit("Map_Header_Table"));
+	init_mem_allocator(c);
+	t_map_info      = find_core_type(c, str_lit("Map_Info"));
+	t_map_cell_info = find_core_type(c, str_lit("Map_Cell_Info"));
+	t_raw_map       = find_core_type(c, str_lit("Raw_Map"));
+
+	t_map_info_ptr      = alloc_type_pointer(t_map_info);
+	t_map_cell_info_ptr = alloc_type_pointer(t_map_cell_info);
+	t_raw_map_ptr       = alloc_type_pointer(t_raw_map);
 }
 
 void init_preload(Checker *c) {
diff --git a/src/checker_builtin_procs.hpp b/src/checker_builtin_procs.hpp
index c59ae7867..e03e94ab4 100644
--- a/src/checker_builtin_procs.hpp
+++ b/src/checker_builtin_procs.hpp
@@ -277,6 +277,8 @@ BuiltinProc__type_simple_boolean_end,
 
 	BuiltinProc_type_equal_proc,
 	BuiltinProc_type_hasher_proc,
+	BuiltinProc_type_map_info,
+	BuiltinProc_type_map_cell_info,
 
 BuiltinProc__type_end,
 
@@ -570,8 +572,10 @@ gb_global BuiltinProc builtin_procs[BuiltinProc_COUNT] = {
 
 	{STR_LIT("type_field_index_of"), 2, false, Expr_Expr, BuiltinProcPkg_intrinsics},
 
-	{STR_LIT("type_equal_proc"),  1, false, Expr_Expr, BuiltinProcPkg_intrinsics},
-	{STR_LIT("type_hasher_proc"), 1, false, Expr_Expr, BuiltinProcPkg_intrinsics},
+	{STR_LIT("type_equal_proc"),    1, false, Expr_Expr, BuiltinProcPkg_intrinsics},
+	{STR_LIT("type_hasher_proc"),   1, false, Expr_Expr, BuiltinProcPkg_intrinsics},
+	{STR_LIT("type_map_info"),      1, false, Expr_Expr, BuiltinProcPkg_intrinsics},
+	{STR_LIT("type_map_cell_info"), 1, false, Expr_Expr, BuiltinProcPkg_intrinsics},
 
 
 	{STR_LIT(""), 0, false, Expr_Stmt, BuiltinProcPkg_intrinsics},
diff --git a/src/llvm_backend.cpp b/src/llvm_backend.cpp
index 1d2c00700..594224e6a 100644
--- a/src/llvm_backend.cpp
+++ b/src/llvm_backend.cpp
@@ -140,7 +140,7 @@ lbContextData *lb_push_context_onto_stack(lbProcedure *p, lbAddr ctx) {
 }
 
 
-lbValue lb_get_equal_proc_for_type(lbModule *m, Type *type) {
+lbValue lb_equal_proc_for_type(lbModule *m, Type *type) {
 	type = base_type(type);
 	GB_ASSERT(is_type_comparable(type));
 
@@ -157,8 +157,8 @@ lbValue lb_get_equal_proc_for_type(lbModule *m, Type *type) {
 
 	static u32 proc_index = 0;
 
-	char buf[16] = {};
-	isize n = gb_snprintf(buf, 16, "__$equal%u", ++proc_index);
+	char buf[32] = {};
+	isize n = gb_snprintf(buf, 32, "__$equal%u", ++proc_index);
 	char *str = gb_alloc_str_len(permanent_allocator(), buf, n-1);
 	String proc_name = make_string_c(str);
 
@@ -166,6 +166,9 @@ lbValue lb_get_equal_proc_for_type(lbModule *m, Type *type) {
 	map_set(&m->equal_procs, type, p);
 	lb_begin_procedure_body(p);
 
+	lb_add_attribute_to_proc(m, p->value, "readonly");
+	lb_add_attribute_to_proc(m, p->value, "nounwind");
+
 	LLVMValueRef x = LLVMGetParam(p->value, 0);
 	LLVMValueRef y = LLVMGetParam(p->value, 1);
 	x = LLVMBuildPointerCast(p->builder, x, ptr_type, "");
@@ -173,6 +176,8 @@ lbValue lb_get_equal_proc_for_type(lbModule *m, Type *type) {
 	lbValue lhs = {x, pt};
 	lbValue rhs = {y, pt};
 
+	lb_add_proc_attribute_at_index(p, 1+0, "nonnull");
+	lb_add_proc_attribute_at_index(p, 1+1, "nonnull");
 
 	lbBlock *block_same_ptr = lb_create_block(p, "same_ptr");
 	lbBlock *block_diff_ptr = lb_create_block(p, "diff_ptr");
@@ -277,28 +282,20 @@ lbValue lb_get_equal_proc_for_type(lbModule *m, Type *type) {
 lbValue lb_simple_compare_hash(lbProcedure *p, Type *type, lbValue data, lbValue seed) {
 	GB_ASSERT_MSG(is_type_simple_compare(type), "%s", type_to_string(type));
 
-	i64 sz = type_size_of(type);
-
-	if (1 <= sz && sz <= 16) {
-		char name[20] = {};
-		gb_snprintf(name, 20, "default_hasher%d", cast(i32)sz);
-
-		auto args = array_make<lbValue>(permanent_allocator(), 2);
-		args[0] = data;
-		args[1] = seed;
-		return lb_emit_runtime_call(p, name, args);
-	}
-
 	auto args = array_make<lbValue>(permanent_allocator(), 3);
 	args[0] = data;
 	args[1] = seed;
 	args[2] = lb_const_int(p->module, t_int, type_size_of(type));
-	return lb_emit_runtime_call(p, "default_hasher_n", args);
+	return lb_emit_runtime_call(p, "default_hasher", args);
 }
 
-lbValue lb_get_hasher_proc_for_type(lbModule *m, Type *type) {
+void lb_add_callsite_force_inline(lbProcedure *p, lbValue ret_value) {
+	LLVMAddCallSiteAttribute(ret_value.value, LLVMAttributeIndex_FunctionIndex, lb_create_enum_attribute(p->module->ctx, "alwaysinline"));
+}
+
+lbValue lb_hasher_proc_for_type(lbModule *m, Type *type) {
 	type = core_type(type);
-	GB_ASSERT(is_type_valid_for_keys(type));
+	GB_ASSERT_MSG(is_type_valid_for_keys(type), "%s", type_to_string(type));
 
 	Type *pt = alloc_type_pointer(type);
 
@@ -310,8 +307,8 @@ lbValue lb_get_hasher_proc_for_type(lbModule *m, Type *type) {
 
 	static u32 proc_index = 0;
 
-	char buf[16] = {};
-	isize n = gb_snprintf(buf, 16, "__$hasher%u", ++proc_index);
+	char buf[32] = {};
+	isize n = gb_snprintf(buf, 32, "__$hasher%u", ++proc_index);
 	char *str = gb_alloc_str_len(permanent_allocator(), buf, n-1);
 	String proc_name = make_string_c(str);
 
@@ -320,16 +317,20 @@ lbValue lb_get_hasher_proc_for_type(lbModule *m, Type *type) {
 	lb_begin_procedure_body(p);
 	defer (lb_end_procedure_body(p));
 
+	lb_add_attribute_to_proc(m, p->value, "readonly");
+	lb_add_attribute_to_proc(m, p->value, "nounwind");
+
 	LLVMValueRef x = LLVMGetParam(p->value, 0);
 	LLVMValueRef y = LLVMGetParam(p->value, 1);
 	lbValue data = {x, t_rawptr};
 	lbValue seed = {y, t_uintptr};
 
-	LLVMAttributeRef nonnull_attr = lb_create_enum_attribute(m->ctx, "nonnull");
-	LLVMAddAttributeAtIndex(p->value, 1+0, nonnull_attr);
+	lb_add_proc_attribute_at_index(p, 1+0, "nonnull");
+	lb_add_proc_attribute_at_index(p, 1+0, "readonly");
 
 	if (is_type_simple_compare(type)) {
 		lbValue res = lb_simple_compare_hash(p, type, data, seed);
+		lb_add_callsite_force_inline(p, res);
 		LLVMBuildRet(p->builder, res.value);
 		return {p->value, p->type};
 	}
@@ -343,7 +344,7 @@ lbValue lb_get_hasher_proc_for_type(lbModule *m, Type *type) {
 			GB_ASSERT(type->Struct.offsets != nullptr);
 			i64 offset = type->Struct.offsets[i];
 			Entity *field = type->Struct.fields[i];
-			lbValue field_hasher = lb_get_hasher_proc_for_type(m, field->type);
+			lbValue field_hasher = lb_hasher_proc_for_type(m, field->type);
 			lbValue ptr = lb_emit_ptr_offset(p, data, lb_const_int(m, t_uintptr, offset));
 
 			args[0] = ptr;
@@ -356,11 +357,12 @@ lbValue lb_get_hasher_proc_for_type(lbModule *m, Type *type) {
 
 		if (is_type_union_maybe_pointer(type)) {
 			Type *v = type->Union.variants[0];
-			lbValue variant_hasher = lb_get_hasher_proc_for_type(m, v);
+			lbValue variant_hasher = lb_hasher_proc_for_type(m, v);
 
 			args[0] = data;
 			args[1] = seed;
 			lbValue res = lb_emit_call(p, variant_hasher, args);
+			lb_add_callsite_force_inline(p, res);
 			LLVMBuildRet(p->builder, res.value);
 		}
 
@@ -379,7 +381,7 @@ lbValue lb_get_hasher_proc_for_type(lbModule *m, Type *type) {
 			Type *v = type->Union.variants[i];
 			lbValue case_tag = lb_const_union_tag(p->module, type, v);
 
-			lbValue variant_hasher = lb_get_hasher_proc_for_type(m, v);
+			lbValue variant_hasher = lb_hasher_proc_for_type(m, v);
 
 			args[0] = data;
 			args[1] = seed;
@@ -397,7 +399,7 @@ lbValue lb_get_hasher_proc_for_type(lbModule *m, Type *type) {
 		lb_addr_store(p, pres, seed);
 
 		auto args = array_make<lbValue>(permanent_allocator(), 2);
-		lbValue elem_hasher = lb_get_hasher_proc_for_type(m, type->Array.elem);
+		lbValue elem_hasher = lb_hasher_proc_for_type(m, type->Array.elem);
 
 		auto loop_data = lb_loop_start(p, cast(isize)type->Array.count, t_i32);
 
@@ -418,7 +420,7 @@ lbValue lb_get_hasher_proc_for_type(lbModule *m, Type *type) {
 		lb_addr_store(p, res, seed);
 
 		auto args = array_make<lbValue>(permanent_allocator(), 2);
-		lbValue elem_hasher = lb_get_hasher_proc_for_type(m, type->EnumeratedArray.elem);
+		lbValue elem_hasher = lb_hasher_proc_for_type(m, type->EnumeratedArray.elem);
 
 		auto loop_data = lb_loop_start(p, cast(isize)type->EnumeratedArray.count, t_i32);
 
@@ -439,12 +441,14 @@ lbValue lb_get_hasher_proc_for_type(lbModule *m, Type *type) {
 		args[0] = data;
 		args[1] = seed;
 		lbValue res = lb_emit_runtime_call(p, "default_hasher_cstring", args);
+		lb_add_callsite_force_inline(p, res);
 		LLVMBuildRet(p->builder, res.value);
 	} else if (is_type_string(type)) {
 		auto args = array_make<lbValue>(permanent_allocator(), 2);
 		args[0] = data;
 		args[1] = seed;
 		lbValue res = lb_emit_runtime_call(p, "default_hasher_string", args);
+		lb_add_callsite_force_inline(p, res);
 		LLVMBuildRet(p->builder, res.value);
 	} else {
 		GB_PANIC("Unhandled type for hasher: %s", type_to_string(type));
@@ -454,6 +458,279 @@ lbValue lb_get_hasher_proc_for_type(lbModule *m, Type *type) {
 }
 
 
+lbValue lb_map_get_proc_for_type(lbModule *m, Type *type) {
+	GB_ASSERT(build_context.use_static_map_calls);
+	type = base_type(type);
+	GB_ASSERT(type->kind == Type_Map);
+
+
+	lbProcedure **found = map_get(&m->map_get_procs, type);
+	if (found) {
+		GB_ASSERT(*found != nullptr);
+		return {(*found)->value, (*found)->type};
+	}
+	static u32 proc_index = 0;
+
+	char buf[32] = {};
+	isize n = gb_snprintf(buf, 32, "__$map_get-%u", ++proc_index);
+	char *str = gb_alloc_str_len(permanent_allocator(), buf, n-1);
+	String proc_name = make_string_c(str);
+
+	lbProcedure *p = lb_create_dummy_procedure(m, proc_name, t_map_get_proc);
+	map_set(&m->map_get_procs, type, p);
+	lb_begin_procedure_body(p);
+	defer (lb_end_procedure_body(p));
+
+	LLVMSetLinkage(p->value, LLVMInternalLinkage);
+	lb_add_attribute_to_proc(m, p->value, "readonly");
+	lb_add_attribute_to_proc(m, p->value, "nounwind");
+	if (build_context.ODIN_DEBUG) {
+		lb_add_attribute_to_proc(m, p->value, "noinline");
+	}
+
+	LLVMValueRef x = LLVMGetParam(p->value, 0);
+	LLVMValueRef y = LLVMGetParam(p->value, 1);
+	LLVMValueRef z = LLVMGetParam(p->value, 2);
+	lbValue map_ptr = {x, t_rawptr};
+	lbValue h       = {y, t_uintptr};
+	lbValue key_ptr = {z, t_rawptr};
+
+	lb_add_proc_attribute_at_index(p, 1+0, "nonnull");
+	lb_add_proc_attribute_at_index(p, 1+0, "noalias");
+	lb_add_proc_attribute_at_index(p, 1+0, "readonly");
+
+	lb_add_proc_attribute_at_index(p, 1+2, "nonnull");
+	lb_add_proc_attribute_at_index(p, 1+2, "noalias");
+	lb_add_proc_attribute_at_index(p, 1+2, "readonly");
+
+	lbBlock *loop_block = lb_create_block(p, "loop");
+	lbBlock *hash_block = lb_create_block(p, "hash");
+	lbBlock *probe_block = lb_create_block(p, "probe");
+	lbBlock *increment_block = lb_create_block(p, "increment");
+	lbBlock *hash_compare_block = lb_create_block(p, "hash_compare");
+	lbBlock *key_compare_block = lb_create_block(p, "key_compare");
+	lbBlock *value_block = lb_create_block(p, "value");
+	lbBlock *nil_block = lb_create_block(p, "nil");
+
+	map_ptr = lb_emit_conv(p, map_ptr, t_raw_map_ptr);
+	lbValue map = lb_emit_load(p, map_ptr);
+
+	lbValue length = lb_map_len(p, map);
+
+	lb_emit_if(p, lb_emit_comp(p, Token_CmpEq, length, lb_const_nil(m, t_int)), nil_block, hash_block);
+	lb_start_block(p, hash_block);
+
+	key_ptr = lb_emit_conv(p, key_ptr, alloc_type_pointer(type->Map.key));
+	lbValue key = lb_emit_load(p, key_ptr);
+
+	lbAddr pos = lb_add_local_generated(p, t_uintptr, false);
+	lbAddr distance = lb_add_local_generated(p, t_uintptr, true);
+	lbValue capacity = lb_map_cap(p, map);
+	lbValue mask = lb_emit_conv(p, lb_emit_arith(p, Token_Sub, capacity, lb_const_int(m, t_int, 1), t_int), t_uintptr);
+
+	{
+		auto args = array_make<lbValue>(heap_allocator(), 2);
+		args[0] = map;
+		args[1] = h;
+		lb_addr_store(p, pos, lb_emit_runtime_call(p, "map_desired_position", args));
+	}
+	lbValue zero_uintptr = lb_const_int(m, t_uintptr, 0);
+	lbValue one_uintptr = lb_const_int(m, t_uintptr, 1);
+
+	lbValue ks = lb_map_data_uintptr(p, map);
+	lbValue vs = lb_map_cell_index_static(p, type->Map.key, ks, capacity);
+	lbValue hs = lb_map_cell_index_static(p, type->Map.value, vs, capacity);
+
+	ks = lb_emit_conv(p, ks, alloc_type_pointer(type->Map.key));
+	vs = lb_emit_conv(p, vs, alloc_type_pointer(type->Map.value));
+	hs = lb_emit_conv(p, hs, alloc_type_pointer(t_uintptr));
+
+	lb_emit_jump(p, loop_block);
+	lb_start_block(p, loop_block);
+
+	lbValue element_hash = lb_emit_load(p, lb_emit_ptr_offset(p, hs, lb_addr_load(p, pos)));
+	{
+		// if element_hash == 0 { return nil }
+		lb_emit_if(p, lb_emit_comp(p, Token_CmpEq, element_hash, zero_uintptr), nil_block, probe_block);
+	}
+
+	lb_start_block(p, probe_block);
+	{
+		auto args = array_make<lbValue>(heap_allocator(), 3);
+		args[0] = map;
+		args[1] = element_hash;
+		args[2] = lb_addr_load(p, pos);
+		lbValue probe_distance = lb_emit_runtime_call(p, "map_probe_distance", args);
+		lbValue cond = lb_emit_comp(p, Token_Gt, lb_addr_load(p, distance), probe_distance);
+		lb_emit_if(p, cond, nil_block, hash_compare_block);
+	}
+
+	lb_start_block(p, hash_compare_block);
+	{
+		lb_emit_if(p, lb_emit_comp(p, Token_CmpEq, element_hash, h), key_compare_block, increment_block);
+	}
+
+	lb_start_block(p, key_compare_block);
+	{
+		lbValue element_key = lb_map_cell_index_static(p, type->Map.key, ks, lb_addr_load(p, pos));
+		element_key = lb_emit_conv(p, element_key, ks.type);
+		lbValue cond = lb_emit_comp(p, Token_CmpEq, lb_emit_load(p, element_key), key);
+		lb_emit_if(p, cond, value_block, increment_block);
+	}
+
+	lb_start_block(p, value_block);
+	{
+		lbValue element_value = lb_map_cell_index_static(p, type->Map.value, vs, lb_addr_load(p, pos));
+		element_value = lb_emit_conv(p, element_value, t_rawptr);
+		LLVMBuildRet(p->builder, element_value.value);
+	}
+
+	lb_start_block(p, increment_block);
+	{
+		lbValue pp = lb_addr_load(p, pos);
+		pp = lb_emit_arith(p, Token_Add, pp, one_uintptr, t_uintptr);
+		pp = lb_emit_arith(p, Token_And, pp, mask, t_uintptr);
+		lb_addr_store(p, pos, pp);
+		lb_emit_increment(p, distance.addr);
+	}
+	lb_emit_jump(p, loop_block);
+
+	lb_start_block(p, nil_block);
+	{
+		lbValue res = lb_const_nil(m, t_rawptr);
+		LLVMBuildRet(p->builder, res.value);
+	}
+
+
+	return {p->value, p->type};
+}
+
+void lb_debug_print(lbProcedure *p, String const &str) {
+	auto args = array_make<lbValue>(heap_allocator(), 1);
+	args[0] = lb_const_string(p->module, str);
+	lb_emit_runtime_call(p, "print_string", args);
+}
+
+lbValue lb_map_set_proc_for_type(lbModule *m, Type *type) {
+	GB_ASSERT(build_context.use_static_map_calls);
+	type = base_type(type);
+	GB_ASSERT(type->kind == Type_Map);
+
+
+	lbProcedure **found = map_get(&m->map_set_procs, type);
+	if (found) {
+		GB_ASSERT(*found != nullptr);
+		return {(*found)->value, (*found)->type};
+	}
+	static u32 proc_index = 0;
+
+	char buf[32] = {};
+	isize n = gb_snprintf(buf, 32, "__$map_set-%u", ++proc_index);
+	char *str = gb_alloc_str_len(permanent_allocator(), buf, n-1);
+	String proc_name = make_string_c(str);
+
+	lbProcedure *p = lb_create_dummy_procedure(m, proc_name, t_map_set_proc);
+	map_set(&m->map_set_procs, type, p);
+	lb_begin_procedure_body(p);
+	defer (lb_end_procedure_body(p));
+
+	LLVMSetLinkage(p->value, LLVMInternalLinkage);
+	lb_add_attribute_to_proc(m, p->value, "nounwind");
+	if (build_context.ODIN_DEBUG) {
+		lb_add_attribute_to_proc(m, p->value, "noinline");
+	}
+
+	lbValue map_ptr      = {LLVMGetParam(p->value, 0), t_rawptr};
+	lbValue hash         = {LLVMGetParam(p->value, 1), t_uintptr};
+	lbValue key_ptr      = {LLVMGetParam(p->value, 2), t_rawptr};
+	lbValue value_ptr    = {LLVMGetParam(p->value, 3), t_rawptr};
+	lbValue location_ptr = {LLVMGetParam(p->value, 4), t_source_code_location_ptr};
+
+	map_ptr = lb_emit_conv(p, map_ptr, alloc_type_pointer(type));
+	key_ptr = lb_emit_conv(p, key_ptr, alloc_type_pointer(type->Map.key));
+
+	lb_add_proc_attribute_at_index(p, 1+0, "nonnull");
+	lb_add_proc_attribute_at_index(p, 1+0, "noalias");
+
+	lb_add_proc_attribute_at_index(p, 1+2, "nonnull");
+	if (!are_types_identical(type->Map.key, type->Map.value)) {
+		lb_add_proc_attribute_at_index(p, 1+2, "noalias");
+	}
+	lb_add_proc_attribute_at_index(p, 1+2, "readonly");
+
+	lb_add_proc_attribute_at_index(p, 1+3, "nonnull");
+	if (!are_types_identical(type->Map.key, type->Map.value)) {
+		lb_add_proc_attribute_at_index(p, 1+3, "noalias");
+	}
+	lb_add_proc_attribute_at_index(p, 1+3, "readonly");
+
+	lb_add_proc_attribute_at_index(p, 1+4, "nonnull");
+	lb_add_proc_attribute_at_index(p, 1+4, "noalias");
+	lb_add_proc_attribute_at_index(p, 1+4, "readonly");
+
+	////
+	lbValue found_ptr = {};
+	{
+		lbValue map_get_proc = lb_map_get_proc_for_type(m, type);
+
+		auto args = array_make<lbValue>(permanent_allocator(), 3);
+		args[0] = lb_emit_conv(p, map_ptr, t_rawptr);
+		args[1] = hash;
+		args[2] = key_ptr;
+
+		found_ptr = lb_emit_call(p, map_get_proc, args);
+	}
+
+
+	lbBlock *found_block      = lb_create_block(p, "found");
+	lbBlock *check_grow_block = lb_create_block(p, "check-grow");
+	lbBlock *grow_fail_block  = lb_create_block(p, "grow-fail");
+	lbBlock *insert_block     = lb_create_block(p, "insert");
+
+	lb_emit_if(p, lb_emit_comp_against_nil(p, Token_NotEq, found_ptr), found_block, check_grow_block);
+	lb_start_block(p, found_block);
+	{
+		lb_mem_copy_non_overlapping(p, found_ptr, value_ptr, lb_const_int(m, t_int, type_size_of(type->Map.value)));
+		LLVMBuildRet(p->builder, lb_emit_conv(p, found_ptr, t_rawptr).value);
+	}
+	lb_start_block(p, check_grow_block);
+
+
+	lbValue map_info = lb_gen_map_info_ptr(p->module, type);
+
+	{
+		auto args = array_make<lbValue>(permanent_allocator(), 3);
+		args[0] = lb_emit_conv(p, map_ptr, t_rawptr);
+		args[1] = map_info;
+		args[2] = lb_emit_load(p, location_ptr);
+		lbValue grow_err = lb_emit_runtime_call(p, "__dynamic_map_check_grow", args);
+
+		lb_emit_if(p, lb_emit_comp_against_nil(p, Token_NotEq, grow_err), grow_fail_block, insert_block);
+
+		lb_start_block(p, grow_fail_block);
+		LLVMBuildRet(p->builder, LLVMConstNull(lb_type(m, t_rawptr)));
+	}
+
+	lb_start_block(p, insert_block);
+	{
+		auto args = array_make<lbValue>(permanent_allocator(), 5);
+		args[0] = lb_emit_conv(p, map_ptr, t_rawptr);
+		args[1] = map_info;
+		args[2] = hash;
+		args[3] = lb_emit_conv(p, key_ptr,   t_uintptr);
+		args[4] = lb_emit_conv(p, value_ptr, t_uintptr);
+
+		lbValue result = lb_emit_runtime_call(p, "map_insert_hash_dynamic", args);
+
+		lb_emit_increment(p, lb_map_len_ptr(p, map_ptr));
+
+		LLVMBuildRet(p->builder, lb_emit_conv(p, result, t_rawptr).value);
+	}
+
+	return {p->value, p->type};
+}
+
+
 lbValue lb_generate_anonymous_proc_lit(lbModule *m, String const &prefix_name, Ast *expr, lbProcedure *parent) {
 	lbProcedure **found = map_get(&m->gen->anonymous_proc_lits, expr);
 	if (found) {
@@ -500,51 +777,60 @@ lbValue lb_generate_anonymous_proc_lit(lbModule *m, String const &prefix_name, A
 	return value;
 }
 
-lbValue lb_gen_map_header_table_internal(lbProcedure *p, Type *map_type) {
-	lbModule *m = p->module;
-
-	map_type = base_type(map_type);
-	GB_ASSERT(map_type->kind == Type_Map);
 
-	lbAddr *found = map_get(&m->map_header_table_map, map_type);
+lbValue lb_gen_map_cell_info_ptr(lbModule *m, Type *type) {
+	lbAddr *found = map_get(&m->map_cell_info_map, type);
 	if (found) {
-		return lb_addr_load(p, *found);
+		return found->addr;
 	}
 
-	GB_ASSERT(map_type->Map.entry_type->kind == Type_Struct);
-	i64 entry_size   = type_size_of  (map_type->Map.entry_type);
-	i64 entry_align  = type_align_of (map_type->Map.entry_type);
+	i64 size = 0, len = 0;
+	map_cell_size_and_len(type, &size, &len);
+
+	LLVMValueRef const_values[4] = {};
+	const_values[0] = lb_const_int(m, t_uintptr, type_size_of(type)).value;
+	const_values[1] = lb_const_int(m, t_uintptr, type_align_of(type)).value;
+	const_values[2] = lb_const_int(m, t_uintptr, size).value;
+	const_values[3] = lb_const_int(m, t_uintptr, len).value;
+	LLVMValueRef llvm_res =  llvm_const_named_struct(m, t_map_cell_info, const_values, gb_count_of(const_values));
+	lbValue res = {llvm_res, t_map_cell_info};
+
+	lbAddr addr = lb_add_global_generated(m, t_map_cell_info, res, nullptr);
+	lb_make_global_private_const(addr);
+
+	map_set(&m->map_cell_info_map, type, addr);
 
-	i64 key_offset = type_offset_of(map_type->Map.entry_type, 2);
-	i64 key_size   = type_size_of  (map_type->Map.key);
+	return addr.addr;
+}
+lbValue lb_gen_map_info_ptr(lbModule *m, Type *map_type) {
+	map_type = base_type(map_type);
+	GB_ASSERT(map_type->kind == Type_Map);
 
-	i64 value_offset = type_offset_of(map_type->Map.entry_type, 3);
-	i64 value_size   = type_size_of  (map_type->Map.value);
+	lbAddr *found = map_get(&m->map_info_map, map_type);
+	if (found) {
+		return found->addr;
+	}
 
-	Type *key_type = map_type->Map.key;
-	Type *val_type = map_type->Map.value;
-	gb_unused(val_type);
+	GB_ASSERT(t_map_info != nullptr);
+	GB_ASSERT(t_map_cell_info != nullptr);
 
-	Type *st = base_type(t_map_header_table);
-	GB_ASSERT(st->Struct.fields.count == 7);
+	LLVMValueRef key_cell_info   = lb_gen_map_cell_info_ptr(m, map_type->Map.key).value;
+	LLVMValueRef value_cell_info = lb_gen_map_cell_info_ptr(m, map_type->Map.value).value;
 
-	LLVMValueRef const_values[7] = {};
-	const_values[0] = lb_get_equal_proc_for_type(m, key_type)    .value;
-	const_values[1] = lb_const_int(m, t_int,        entry_size)  .value;
-	const_values[2] = lb_const_int(m, t_int,        entry_align) .value;
-	const_values[3] = lb_const_int(m, t_uintptr,    key_offset)  .value;
-	const_values[4] = lb_const_int(m, t_int,        key_size)    .value;
-	const_values[5] = lb_const_int(m, t_uintptr,    value_offset).value;
-	const_values[6] = lb_const_int(m, t_int,        value_size)  .value;
+	LLVMValueRef const_values[4] = {};
+	const_values[0] = key_cell_info;
+	const_values[1] = value_cell_info;
+	const_values[2] = lb_hasher_proc_for_type(m, map_type->Map.key).value;
+	const_values[3] = lb_equal_proc_for_type(m, map_type->Map.key).value;
 
-	LLVMValueRef llvm_res = llvm_const_named_struct(m, t_map_header_table, const_values, gb_count_of(const_values));
-	lbValue res = {llvm_res, t_map_header_table};
+	LLVMValueRef llvm_res = llvm_const_named_struct(m, t_map_info, const_values, gb_count_of(const_values));
+	lbValue res = {llvm_res, t_map_info};
 
-	lbAddr addr = lb_add_global_generated(m, t_map_header_table, res, nullptr);
+	lbAddr addr = lb_add_global_generated(m, t_map_info, res, nullptr);
 	lb_make_global_private_const(addr);
 
-	map_set(&m->map_header_table_map, map_type, addr);
-	return lb_addr_load(p, addr);
+	map_set(&m->map_info_map, map_type, addr);
+	return addr.addr;
 }
 
 lbValue lb_const_hash(lbModule *m, lbValue key, Type *key_type) {
@@ -602,7 +888,7 @@ lbValue lb_gen_map_key_hash(lbProcedure *p, lbValue key, Type *key_type, lbValue
 
 	lbValue hashed_key = lb_const_hash(p->module, key, key_type);
 	if (hashed_key.value == nullptr) {
-		lbValue hasher = lb_get_hasher_proc_for_type(p->module, key_type);
+		lbValue hasher = lb_hasher_proc_for_type(p->module, key_type);
 
 		auto args = array_make<lbValue>(permanent_allocator(), 2);
 		args[0] = key_ptr;
@@ -615,42 +901,68 @@ lbValue lb_gen_map_key_hash(lbProcedure *p, lbValue key, Type *key_type, lbValue
 
 lbValue lb_internal_dynamic_map_get_ptr(lbProcedure *p, lbValue const &map_ptr, lbValue const &key) {
 	Type *map_type = base_type(type_deref(map_ptr.type));
+	GB_ASSERT(map_type->kind == Type_Map);
 
+	lbValue ptr = {};
 	lbValue key_ptr = {};
-	auto args = array_make<lbValue>(permanent_allocator(), 4);
-	args[0] = lb_emit_conv(p, map_ptr, t_rawptr);
-	args[1] = lb_gen_map_header_table_internal(p, map_type);
-	args[2] = lb_gen_map_key_hash(p, key, map_type->Map.key, &key_ptr);
-	args[3] = key_ptr;
+	lbValue hash = lb_gen_map_key_hash(p, key, map_type->Map.key, &key_ptr);
+
+	if (build_context.use_static_map_calls) {
+		lbValue map_get_proc = lb_map_get_proc_for_type(p->module, map_type);
 
-	lbValue ptr = lb_emit_runtime_call(p, "__dynamic_map_get", args);
+		auto args = array_make<lbValue>(permanent_allocator(), 3);
+		args[0] = lb_emit_conv(p, map_ptr, t_rawptr);
+		args[1] = hash;
+		args[2] = key_ptr;
+
+		ptr = lb_emit_call(p, map_get_proc, args);
+	} else {
+		auto args = array_make<lbValue>(permanent_allocator(), 4);
+		args[0] = lb_emit_transmute(p, map_ptr, t_raw_map_ptr);
+		args[1] = lb_gen_map_info_ptr(p->module, map_type);
+		args[2] = hash;
+		args[3] = key_ptr;
 
+		ptr = lb_emit_runtime_call(p, "__dynamic_map_get", args);
+	}
 	return lb_emit_conv(p, ptr, alloc_type_pointer(map_type->Map.value));
 }
 
-void lb_insert_dynamic_map_key_and_value(lbProcedure *p, lbValue const &map_ptr, Type *map_type,
-                                         lbValue const &map_key, lbValue const &map_value, Ast *node) {
+void lb_internal_dynamic_map_set(lbProcedure *p, lbValue const &map_ptr, Type *map_type,
+                                 lbValue const &map_key, lbValue const &map_value, Ast *node) {
 	map_type = base_type(map_type);
 	GB_ASSERT(map_type->kind == Type_Map);
 
 	lbValue key_ptr = {};
-	lbValue key_hash = lb_gen_map_key_hash(p, map_key, map_type->Map.key, &key_ptr);
+	lbValue hash = lb_gen_map_key_hash(p, map_key, map_type->Map.key, &key_ptr);
+
 	lbValue v = lb_emit_conv(p, map_value, map_type->Map.value);
+	lbValue value_ptr = lb_address_from_load_or_generate_local(p, v);
 
-	lbAddr value_addr = lb_add_local_generated(p, v.type, false);
-	lb_addr_store(p, value_addr, v);
+	if (build_context.use_static_map_calls) {
+		lbValue map_set_proc = lb_map_set_proc_for_type(p->module, map_type);
 
-	auto args = array_make<lbValue>(permanent_allocator(), 6);
-	args[0] = lb_emit_conv(p, map_ptr, t_rawptr);
-	args[1] = lb_gen_map_header_table_internal(p, map_type);
-	args[2] = key_hash;
-	args[3] = key_ptr;
-	args[4] = lb_emit_conv(p, value_addr.addr, t_rawptr);
-	args[5] = lb_emit_source_code_location_as_global(p, node);
-	lb_emit_runtime_call(p, "__dynamic_map_set", args);
+		auto args = array_make<lbValue>(permanent_allocator(), 5);
+		args[0] = lb_emit_conv(p, map_ptr, t_rawptr);
+		args[1] = hash;
+		args[2] = lb_emit_conv(p, key_ptr, t_rawptr);
+		args[3] = lb_emit_conv(p, value_ptr, t_rawptr);
+		args[4] = lb_emit_source_code_location_as_global(p, node);
+
+		lb_emit_call(p, map_set_proc, args);
+	} else {
+		auto args = array_make<lbValue>(permanent_allocator(), 6);
+		args[0] = lb_emit_conv(p, map_ptr, t_raw_map_ptr);
+		args[1] = lb_gen_map_info_ptr(p->module, map_type);
+		args[2] = hash;
+		args[3] = lb_emit_conv(p, key_ptr, t_rawptr);
+		args[4] = lb_emit_conv(p, value_ptr, t_rawptr);
+		args[5] = lb_emit_source_code_location_as_global(p, node);
+		lb_emit_runtime_call(p, "__dynamic_map_set", args);
+	}
 }
 
-void lb_dynamic_map_reserve(lbProcedure *p, lbValue const &map_ptr, isize const capacity, TokenPos const &pos) {
+lbValue lb_dynamic_map_reserve(lbProcedure *p, lbValue const &map_ptr, isize const capacity, TokenPos const &pos) {
 	GB_ASSERT(!build_context.no_dynamic_literals);
 
 	String proc_name = {};
@@ -660,10 +972,10 @@ void lb_dynamic_map_reserve(lbProcedure *p, lbValue const &map_ptr, isize const
 
 	auto args = array_make<lbValue>(permanent_allocator(), 4);
 	args[0] = lb_emit_conv(p, map_ptr, t_rawptr);
-	args[1] = lb_gen_map_header_table_internal(p, type_deref(map_ptr.type));
-	args[2] = lb_const_int(p->module, t_int, capacity);
+	args[1] = lb_gen_map_info_ptr(p->module, type_deref(map_ptr.type));
+	args[2] = lb_const_int(p->module, t_uint, capacity);
 	args[3] = lb_emit_source_code_location_as_global(p, proc_name, pos);
-	lb_emit_runtime_call(p, "__dynamic_map_reserve", args);
+	return lb_emit_runtime_call(p, "__dynamic_map_reserve", args);
 }
 
 
@@ -688,6 +1000,8 @@ lbProcedure *lb_create_startup_type_info(lbModule *m) {
 	p->is_startup = true;
 	LLVMSetLinkage(p->value, LLVMInternalLinkage);
 
+	lb_add_attribute_to_proc(m, p->value, "nounwind");
+
 	lb_begin_procedure_body(p);
 
 	lb_setup_type_info_data(p);
@@ -712,6 +1026,7 @@ lbProcedure *lb_create_objc_names(lbModule *main_module) {
 	}
 	Type *proc_type = alloc_type_proc(nullptr, nullptr, 0, nullptr, 0, false, ProcCC_CDecl);
 	lbProcedure *p = lb_create_dummy_procedure(main_module, str_lit("__$init_objc_names"), proc_type);
+	lb_add_attribute_to_proc(p->module, p->value, "nounwind");
 	p->is_startup = true;
 	return p;
 }
@@ -1198,6 +1513,14 @@ WORKER_TASK_PROC(lb_llvm_function_pass_worker_proc) {
 		lbProcedure *p = m->hasher_procs.entries[i].value;
 		lb_run_function_pass_manager(default_function_pass_manager, p);
 	}
+	for_array(i, m->map_get_procs.entries) {
+		lbProcedure *p = m->map_get_procs.entries[i].value;
+		lb_run_function_pass_manager(default_function_pass_manager, p);
+	}
+	for_array(i, m->map_set_procs.entries) {
+		lbProcedure *p = m->map_set_procs.entries[i].value;
+		lb_run_function_pass_manager(default_function_pass_manager, p);
+	}
 
 	return 0;
 }
diff --git a/src/llvm_backend.hpp b/src/llvm_backend.hpp
index a8ff1571c..72dfdda54 100644
--- a/src/llvm_backend.hpp
+++ b/src/llvm_backend.hpp
@@ -144,6 +144,8 @@ struct lbModule {
 
 	PtrMap<Type *, lbProcedure *> equal_procs;
 	PtrMap<Type *, lbProcedure *> hasher_procs;
+	PtrMap<Type *, lbProcedure *> map_get_procs;
+	PtrMap<Type *, lbProcedure *> map_set_procs;
 
 	u32 nested_type_name_guid;
 
@@ -160,7 +162,8 @@ struct lbModule {
 	StringMap<lbAddr> objc_classes;
 	StringMap<lbAddr> objc_selectors;
 
-	PtrMap<Type *, lbAddr> map_header_table_map;
+	PtrMap<Type *, lbAddr> map_cell_info_map; // address of runtime.Map_Info
+	PtrMap<Type *, lbAddr> map_info_map;      // address of runtime.Map_Cell_Info
 };
 
 struct lbGenerator {
@@ -422,8 +425,6 @@ lbValue lb_dynamic_array_elem(lbProcedure *p, lbValue da);
 lbValue lb_dynamic_array_len(lbProcedure *p, lbValue da);
 lbValue lb_dynamic_array_cap(lbProcedure *p, lbValue da);
 lbValue lb_dynamic_array_allocator(lbProcedure *p, lbValue da);
-lbValue lb_map_entries(lbProcedure *p, lbValue value);
-lbValue lb_map_entries_ptr(lbProcedure *p, lbValue value);
 lbValue lb_map_len(lbProcedure *p, lbValue value);
 lbValue lb_map_cap(lbProcedure *p, lbValue value);
 lbValue lb_soa_struct_len(lbProcedure *p, lbValue value);
@@ -447,10 +448,12 @@ String lb_get_const_string(lbModule *m, lbValue value);
 lbValue lb_generate_local_array(lbProcedure *p, Type *elem_type, i64 count, bool zero_init=true);
 lbValue lb_generate_global_array(lbModule *m, Type *elem_type, i64 count, String prefix, i64 id);
 lbValue lb_gen_map_key_hash(lbProcedure *p, lbValue key, Type *key_type, lbValue *key_ptr_);
+lbValue lb_gen_map_cell_info_ptr(lbModule *m, Type *type);
+lbValue lb_gen_map_info_ptr(lbModule *m, Type *map_type);
 
 lbValue lb_internal_dynamic_map_get_ptr(lbProcedure *p, lbValue const &map_ptr, lbValue const &key);
-void    lb_insert_dynamic_map_key_and_value(lbProcedure *p, lbValue const &map_ptr, Type *map_type, lbValue const &map_key, lbValue const &map_value, Ast *node);
-void    lb_dynamic_map_reserve(lbProcedure *p, lbValue const &map_ptr, isize const capacity, TokenPos const &pos);
+void    lb_internal_dynamic_map_set(lbProcedure *p, lbValue const &map_ptr, Type *map_type, lbValue const &map_key, lbValue const &map_value, Ast *node);
+lbValue lb_dynamic_map_reserve(lbProcedure *p, lbValue const &map_ptr, isize const capacity, TokenPos const &pos);
 
 lbValue lb_find_procedure_value_from_entity(lbModule *m, Entity *e);
 lbValue lb_find_value_from_entity(lbModule *m, Entity *e);
@@ -461,8 +464,8 @@ lbValue lb_emit_source_code_location_const(lbProcedure *p, String const &procedu
 
 lbValue lb_handle_param_value(lbProcedure *p, Type *parameter_type, ParameterValue const &param_value, TokenPos const &pos);
 
-lbValue lb_get_equal_proc_for_type(lbModule *m, Type *type);
-lbValue lb_get_hasher_proc_for_type(lbModule *m, Type *type);
+lbValue lb_equal_proc_for_type(lbModule *m, Type *type);
+lbValue lb_hasher_proc_for_type(lbModule *m, Type *type);
 lbValue lb_emit_conv(lbProcedure *p, lbValue value, Type *t);
 
 LLVMMetadataRef lb_debug_type(lbModule *m, Type *type);
diff --git a/src/llvm_backend_const.cpp b/src/llvm_backend_const.cpp
index a8b66a0ea..dff5298c5 100644
--- a/src/llvm_backend_const.cpp
+++ b/src/llvm_backend_const.cpp
@@ -283,19 +283,28 @@ lbValue lb_emit_source_code_location_const(lbProcedure *p, Ast *node) {
 	return lb_emit_source_code_location_const(p, proc_name, pos);
 }
 
-lbValue lb_emit_source_code_location_as_global(lbProcedure *p, String const &procedure, TokenPos const &pos) {
+
+lbValue lb_emit_source_code_location_as_global_ptr(lbProcedure *p, String const &procedure, TokenPos const &pos) {
 	lbValue loc = lb_emit_source_code_location_const(p, procedure, pos);
 	lbAddr addr = lb_add_global_generated(p->module, loc.type, loc, nullptr);
 	lb_make_global_private_const(addr);
-	return lb_addr_load(p, addr);
+	return addr.addr;
 }
 
 
-lbValue lb_emit_source_code_location_as_global(lbProcedure *p, Ast *node) {
+lbValue lb_emit_source_code_location_as_global_ptr(lbProcedure *p, Ast *node) {
 	lbValue loc = lb_emit_source_code_location_const(p, node);
 	lbAddr addr = lb_add_global_generated(p->module, loc.type, loc, nullptr);
 	lb_make_global_private_const(addr);
-	return lb_addr_load(p, addr);
+	return addr.addr;
+}
+
+lbValue lb_emit_source_code_location_as_global(lbProcedure *p, String const &procedure, TokenPos const &pos) {
+	return lb_emit_load(p, lb_emit_source_code_location_as_global_ptr(p, procedure, pos));
+}
+
+lbValue lb_emit_source_code_location_as_global(lbProcedure *p, Ast *node) {
+	return lb_emit_load(p, lb_emit_source_code_location_as_global_ptr(p, node));
 }
 
 
diff --git a/src/llvm_backend_debug.cpp b/src/llvm_backend_debug.cpp
index 8a98b7f39..e69424929 100644
--- a/src/llvm_backend_debug.cpp
+++ b/src/llvm_backend_debug.cpp
@@ -671,7 +671,8 @@ void lb_debug_complete_types(lbModule *m) {
 				break;
 
 			case Type_Map:
-				bt = bt->Map.internal_type;
+				GB_ASSERT(t_raw_map != nullptr);
+				bt = base_type(t_raw_map);
 				/*fallthrough*/
 			case Type_Struct:
 				if (file == nullptr) {
diff --git a/src/llvm_backend_expr.cpp b/src/llvm_backend_expr.cpp
index 05a9fdfbf..034682855 100644
--- a/src/llvm_backend_expr.cpp
+++ b/src/llvm_backend_expr.cpp
@@ -2215,7 +2215,7 @@ lbValue lb_compare_records(lbProcedure *p, TokenKind op_kind, lbValue left, lbVa
 		args[2] = lb_const_int(p->module, t_int, type_size_of(type));
 		res = lb_emit_runtime_call(p, "memory_equal", args);
 	} else {
-		lbValue value = lb_get_equal_proc_for_type(p->module, type);
+		lbValue value = lb_equal_proc_for_type(p->module, type);
 		auto args = array_make<lbValue>(permanent_allocator(), 2);
 		args[0] = lb_emit_conv(p, left_ptr, t_rawptr);
 		args[1] = lb_emit_conv(p, right_ptr, t_rawptr);
@@ -4131,7 +4131,8 @@ lbAddr lb_build_addr_compound_lit(lbProcedure *p, Ast *expr) {
 		}
 		GB_ASSERT(!build_context.no_dynamic_literals);
 
-		lb_dynamic_map_reserve(p, v.addr, 2*cl->elems.count, pos);
+		lbValue err = lb_dynamic_map_reserve(p, v.addr, 2*cl->elems.count, pos);
+		gb_unused(err);
 
 		for_array(field_index, cl->elems) {
 			Ast *elem = cl->elems[field_index];
@@ -4139,7 +4140,7 @@ lbAddr lb_build_addr_compound_lit(lbProcedure *p, Ast *expr) {
 
 			lbValue key   = lb_build_expr(p, fv->field);
 			lbValue value = lb_build_expr(p, fv->value);
-			lb_insert_dynamic_map_key_and_value(p, v.addr, type, key, value, elem);
+			lb_internal_dynamic_map_set(p, v.addr, type, key, value, elem);
 		}
 		break;
 	}
diff --git a/src/llvm_backend_general.cpp b/src/llvm_backend_general.cpp
index 87f8afa05..f36dc1842 100644
--- a/src/llvm_backend_general.cpp
+++ b/src/llvm_backend_general.cpp
@@ -67,6 +67,8 @@ void lb_init_module(lbModule *m, Checker *c) {
 	map_init(&m->function_type_map, a);
 	map_init(&m->equal_procs, a);
 	map_init(&m->hasher_procs, a);
+	map_init(&m->map_get_procs, a);
+	map_init(&m->map_set_procs, a);
 	array_init(&m->procedures_to_generate, a, 0, 1024);
 	array_init(&m->missing_procedures_to_check, a, 0, 16);
 	map_init(&m->debug_values, a);
@@ -75,7 +77,8 @@ void lb_init_module(lbModule *m, Checker *c) {
 	string_map_init(&m->objc_classes, a);
 	string_map_init(&m->objc_selectors, a);
 
-	map_init(&m->map_header_table_map, a, 0);
+	map_init(&m->map_info_map, a, 0);
+	map_init(&m->map_cell_info_map, a, 0);
 
 }
 
@@ -725,7 +728,7 @@ void lb_addr_store(lbProcedure *p, lbAddr addr, lbValue value) {
 
 		return;
 	} else if (addr.kind == lbAddr_Map) {
-		lb_insert_dynamic_map_key_and_value(p, addr.addr, addr.map.type, addr.map.key, value, p->curr_stmt);
+		lb_internal_dynamic_map_set(p, addr.addr, addr.map.type, addr.map.key, value, p->curr_stmt);
 		return;
 	} else if (addr.kind == lbAddr_Context) {
 		lbAddr old_addr = lb_find_or_generate_context_ptr(p);
@@ -1931,38 +1934,8 @@ LLVMTypeRef lb_type_internal(lbModule *m, Type *type) {
 
 	case Type_Map:
 		init_map_internal_types(type);
-		{
-			Type *internal_type = type->Map.internal_type;
-			GB_ASSERT(internal_type->kind == Type_Struct);
-
-			m->internal_type_level -= 1;
-			defer (m->internal_type_level += 1);
-
-			unsigned field_count = cast(unsigned)(internal_type->Struct.fields.count);
-			GB_ASSERT(field_count == 2);
-			LLVMTypeRef *fields = gb_alloc_array(temporary_allocator(), LLVMTypeRef, field_count);
-
-			LLVMTypeRef entries_fields[] = {
-				lb_type(m, t_rawptr), // data
-				lb_type(m, t_int), // len
-				lb_type(m, t_int), // cap
-				lb_type(m, t_allocator), // allocator
-			};
-
-			fields[0] = lb_type(m, internal_type->Struct.fields[0]->type);
-			fields[1] = LLVMStructTypeInContext(ctx, entries_fields, gb_count_of(entries_fields), false);
-			
-			{ // Add this to simplify things
-				lbStructFieldRemapping entries_field_remapping = {};
-				slice_init(&entries_field_remapping, permanent_allocator(), gb_count_of(entries_fields));
-				for_array(i, entries_field_remapping) {
-					entries_field_remapping[i] = cast(i32)i;
-				}
-				map_set(&m->struct_field_remapping, cast(void *)fields[1], entries_field_remapping);
-			}
-			
-			return LLVMStructTypeInContext(ctx, fields, field_count, false);
-		}
+		GB_ASSERT(t_raw_map != nullptr);
+		return lb_type_internal(m, t_raw_map);
 
 	case Type_Struct:
 		{
diff --git a/src/llvm_backend_proc.cpp b/src/llvm_backend_proc.cpp
index ae8236a71..7c83125ca 100644
--- a/src/llvm_backend_proc.cpp
+++ b/src/llvm_backend_proc.cpp
@@ -586,6 +586,7 @@ void lb_begin_procedure_body(lbProcedure *p) {
 					//                 defer x = ... // defer is executed after the `defer`
 					//                 return // the values returned should be zeroed
 					//         }
+					// NOTE(bill): REALLY, don't even bother.
 					lbAddr res = lb_add_local(p, e->type, e);
 					if (e->Variable.param_value.kind != ParameterValue_Invalid) {
 						lbValue c = lb_handle_param_value(p, e->type, e->Variable.param_value, e->token.pos);
@@ -2319,10 +2320,17 @@ lbValue lb_build_builtin_proc(lbProcedure *p, Ast *expr, TypeAndValue const &tv,
 
 
 	case BuiltinProc_type_equal_proc:
-		return lb_get_equal_proc_for_type(p->module, ce->args[0]->tav.type);
+		return lb_equal_proc_for_type(p->module, ce->args[0]->tav.type);
 
 	case BuiltinProc_type_hasher_proc:
-		return lb_get_hasher_proc_for_type(p->module, ce->args[0]->tav.type);
+		return lb_hasher_proc_for_type(p->module, ce->args[0]->tav.type);
+
+	case BuiltinProc_type_map_info:
+		return lb_gen_map_info_ptr(p->module, ce->args[0]->tav.type);
+
+	case BuiltinProc_type_map_cell_info:
+		return lb_gen_map_cell_info_ptr(p->module, ce->args[0]->tav.type);
+
 
 	case BuiltinProc_fixed_point_mul:
 	case BuiltinProc_fixed_point_div:
diff --git a/src/llvm_backend_stmt.cpp b/src/llvm_backend_stmt.cpp
index bd622d411..c8f244181 100644
--- a/src/llvm_backend_stmt.cpp
+++ b/src/llvm_backend_stmt.cpp
@@ -354,16 +354,6 @@ void lb_build_range_indexed(lbProcedure *p, lbValue expr, Type *val_type, lbValu
 		}
 		break;
 	}
-	case Type_Map: {
-		lbValue entries = lb_map_entries_ptr(p, expr);
-		lbValue elem = lb_emit_struct_ep(p, entries, 0);
-		elem = lb_emit_load(p, elem);
-		lbValue entry = lb_emit_ptr_offset(p, elem, idx);		
-		idx = lb_emit_load(p, lb_emit_struct_ep(p, entry, 2));
-		val = lb_emit_load(p, lb_emit_struct_ep(p, entry, 3));
-
-		break;
-	}
 	case Type_Struct: {
 		GB_ASSERT(is_type_soa_struct(expr_type));
 		break;
@@ -380,6 +370,129 @@ void lb_build_range_indexed(lbProcedure *p, lbValue expr, Type *val_type, lbValu
 	if (done_) *done_ = done;
 }
 
+lbValue lb_map_cell_index_static(lbProcedure *p, Type *type, lbValue cells_ptr, lbValue index) {
+	i64 size, len;
+	i64 elem_sz = type_size_of(type);
+	map_cell_size_and_len(type, &size, &len);
+
+	index = lb_emit_conv(p, index, t_uintptr);
+
+	if (size == len*elem_sz) {
+		lbValue elems_ptr = lb_emit_conv(p, cells_ptr, alloc_type_pointer(type));
+		return lb_emit_ptr_offset(p, elems_ptr, index);
+	}
+
+	lbValue cell_index = {};
+	lbValue data_index = {};
+
+	lbValue size_const = lb_const_int(p->module, t_uintptr, size);
+	lbValue len_const = lb_const_int(p->module, t_uintptr, len);
+
+	if (is_power_of_two(len)) {
+		u64 log2_len = floor_log2(cast(u64)len);
+		cell_index = log2_len == 0 ? index : lb_emit_arith(p, Token_Shr, index, lb_const_int(p->module, t_uintptr, log2_len), t_uintptr);
+		data_index = lb_emit_arith(p, Token_And, index, lb_const_int(p->module, t_uintptr, len-1), t_uintptr);
+	} else {
+		cell_index = lb_emit_arith(p, Token_Quo, index, len_const, t_uintptr);
+		data_index = lb_emit_arith(p, Token_Mod, index, len_const, t_uintptr);
+	}
+
+	lbValue elems_ptr = lb_emit_conv(p, cells_ptr, t_uintptr);
+	lbValue cell_offset = lb_emit_arith(p, Token_Mul, size_const, cell_index, t_uintptr);
+	elems_ptr = lb_emit_arith(p, Token_Add, elems_ptr, cell_offset, t_uintptr);
+
+	elems_ptr = lb_emit_conv(p, elems_ptr, alloc_type_pointer(type));
+
+	return lb_emit_ptr_offset(p, elems_ptr, data_index);
+}
+
+void lb_map_kvh_data_static(lbProcedure *p, lbValue map_value, lbValue *ks_, lbValue *vs_, lbValue *hs_) {
+	lbValue capacity = lb_map_cap(p, map_value);
+	lbValue ks = lb_map_data_uintptr(p, map_value);
+	lbValue vs = {};
+	lbValue hs = {};
+	if (ks_) *ks_ = ks;
+	if (vs_) *vs_ = vs;
+	if (hs_) *hs_ = hs;
+}
+
+lbValue lb_map_hash_is_valid(lbProcedure *p, lbValue hash) {
+	// N :: size_of(uintptr)*8 - 1
+	// (hash != 0) & (hash>>N == 0)
+
+	u64 top_bit_index = cast(u64)(type_size_of(t_uintptr)*8 - 1);
+	lbValue shift_amount = lb_const_int(p->module, t_uintptr, top_bit_index);
+	lbValue zero = lb_const_int(p->module, t_uintptr, 0);
+
+	lbValue not_empty = lb_emit_comp(p, Token_NotEq, hash, zero);
+
+	lbValue not_deleted = lb_emit_arith(p, Token_Shr, hash, shift_amount, t_uintptr);
+	not_deleted = lb_emit_comp(p, Token_CmpEq, not_deleted, zero);
+
+	return lb_emit_arith(p, Token_And, not_deleted, not_empty, t_uintptr);
+}
+
+void lb_build_range_map(lbProcedure *p, lbValue expr, Type *val_type,
+                        lbValue *val_, lbValue *key_, lbBlock **loop_, lbBlock **done_) {
+	lbModule *m = p->module;
+
+	Type *type = base_type(type_deref(expr.type));
+	GB_ASSERT(type->kind == Type_Map);
+
+	lbValue idx = {};
+	lbBlock *loop = nullptr;
+	lbBlock *done = nullptr;
+	lbBlock *body = nullptr;
+	lbBlock *hash_check = nullptr;
+
+
+	lbAddr index = lb_add_local_generated(p, t_int, false);
+	lb_addr_store(p, index, lb_const_int(m, t_int, cast(u64)-1));
+
+	loop = lb_create_block(p, "for.index.loop");
+	lb_emit_jump(p, loop);
+	lb_start_block(p, loop);
+
+	lbValue incr = lb_emit_arith(p, Token_Add, lb_addr_load(p, index), lb_const_int(m, t_int, 1), t_int);
+	lb_addr_store(p, index, incr);
+
+	hash_check = lb_create_block(p, "for.index.hash_check");
+	body = lb_create_block(p, "for.index.body");
+	done = lb_create_block(p, "for.index.done");
+
+	lbValue map_value = lb_emit_load(p, expr);
+	lbValue capacity = lb_map_cap(p, map_value);
+	lbValue cond = lb_emit_comp(p, Token_Lt, incr, capacity);
+	lb_emit_if(p, cond, hash_check, done);
+	lb_start_block(p, hash_check);
+
+	idx = lb_addr_load(p, index);
+
+	lbValue ks = lb_map_data_uintptr(p, map_value);
+	lbValue vs = lb_emit_conv(p, lb_map_cell_index_static(p, type->Map.key, ks, capacity), alloc_type_pointer(type->Map.value));
+	lbValue hs = lb_emit_conv(p, lb_map_cell_index_static(p, type->Map.value, vs, capacity), alloc_type_pointer(t_uintptr));
+
+	// NOTE(bill): no need to use lb_map_cell_index_static for that hashes
+	// since it will always be packed without padding into the cells
+	lbValue hash = lb_emit_load(p, lb_emit_ptr_offset(p, hs, idx));
+
+	lbValue hash_cond = lb_map_hash_is_valid(p, hash);
+	lb_emit_if(p, hash_cond, body, loop);
+	lb_start_block(p, body);
+
+
+	lbValue key_ptr = lb_map_cell_index_static(p, type->Map.key, ks, idx);
+	lbValue val_ptr = lb_map_cell_index_static(p, type->Map.value, vs, idx);
+	lbValue key = lb_emit_load(p, key_ptr);
+	lbValue val = lb_emit_load(p, val_ptr);
+
+	if (val_)  *val_  = val;
+	if (key_)  *key_  = key;
+	if (loop_) *loop_ = loop;
+	if (done_) *done_ = done;
+}
+
+
 
 void lb_build_range_string(lbProcedure *p, lbValue expr, Type *val_type,
                             lbValue *val_, lbValue *idx_, lbBlock **loop_, lbBlock **done_) {
@@ -749,9 +862,7 @@ void lb_build_range_stmt(lbProcedure *p, AstRangeStmt *rs, Scope *scope) {
 			if (is_type_pointer(type_deref(map.type))) {
 				map = lb_emit_load(p, map);
 			}
-			lbValue entries_ptr = lb_map_entries_ptr(p, map);
-			lbValue count_ptr = lb_emit_struct_ep(p, entries_ptr, 1);
-			lb_build_range_indexed(p, map, val1_type, count_ptr, &val, &key, &loop, &done);
+			lb_build_range_map(p, map, val1_type, &val, &key, &loop, &done);
 			break;
 		}
 		case Type_Array: {
diff --git a/src/llvm_backend_type.cpp b/src/llvm_backend_type.cpp
index 4abf674c5..307d9304b 100644
--- a/src/llvm_backend_type.cpp
+++ b/src/llvm_backend_type.cpp
@@ -666,7 +666,7 @@ void lb_setup_type_info_data(lbProcedure *p) { // NOTE(bill): Setup type_info da
 				}
 
 				if (is_type_comparable(t) && !is_type_simple_compare(t)) {
-					vals[3] = lb_get_equal_proc_for_type(m, t).value;
+					vals[3] = lb_equal_proc_for_type(m, t).value;
 				}
 
 				vals[4] = lb_const_bool(m, t_bool, t->Union.custom_align != 0).value;
@@ -702,7 +702,7 @@ void lb_setup_type_info_data(lbProcedure *p) { // NOTE(bill): Setup type_info da
 				vals[6] = is_raw_union.value;
 				vals[7] = is_custom_align.value;
 				if (is_type_comparable(t) && !is_type_simple_compare(t)) {
-					vals[8] = lb_get_equal_proc_for_type(m, t).value;
+					vals[8] = lb_equal_proc_for_type(m, t).value;
 				}
 
 
@@ -788,15 +788,11 @@ void lb_setup_type_info_data(lbProcedure *p) { // NOTE(bill): Setup type_info da
 		case Type_Map: {
 			tag = lb_const_ptr_cast(m, variant_ptr, t_type_info_map_ptr);
 			init_map_internal_types(t);
-			
-			lbValue gst = lb_type_info(m, t->Map.internal_type);
 
-			LLVMValueRef vals[5] = {
+			LLVMValueRef vals[3] = {
 				lb_type_info(m, t->Map.key).value,
 				lb_type_info(m, t->Map.value).value,
-				gst.value,
-				lb_get_equal_proc_for_type(m, t->Map.key).value,
-				lb_get_hasher_proc_for_type(m, t->Map.key).value
+				lb_gen_map_info_ptr(p->module, t).value
 			};
 
 			lbValue res = {};
diff --git a/src/llvm_backend_utility.cpp b/src/llvm_backend_utility.cpp
index a54171b51..101b9dbfb 100644
--- a/src/llvm_backend_utility.cpp
+++ b/src/llvm_backend_utility.cpp
@@ -203,26 +203,19 @@ lbValue lb_emit_transmute(lbProcedure *p, lbValue value, Type *t) {
 	if (is_type_uintptr(src) && is_type_internally_pointer_like(dst)) {
 		res.value = LLVMBuildIntToPtr(p->builder, value.value, lb_type(m, t), "");
 		return res;
-	}
-	if (is_type_internally_pointer_like(src) && is_type_uintptr(dst)) {
+	} else if (is_type_internally_pointer_like(src) && is_type_uintptr(dst)) {
 		res.value = LLVMBuildPtrToInt(p->builder, value.value, lb_type(m, t), "");
 		return res;
-	}
-
-	if (is_type_integer(src) && is_type_internally_pointer_like(dst)) {
+	} else if (is_type_integer(src) && is_type_internally_pointer_like(dst)) {
 		res.value = LLVMBuildIntToPtr(p->builder, value.value, lb_type(m, t), "");
 		return res;
 	} else if (is_type_internally_pointer_like(src) && is_type_integer(dst)) {
 		res.value = LLVMBuildPtrToInt(p->builder, value.value, lb_type(m, t), "");
 		return res;
-	}
-
-	if (is_type_internally_pointer_like(src) && is_type_internally_pointer_like(dst)) {
+	} else if (is_type_internally_pointer_like(src) && is_type_internally_pointer_like(dst)) {
 		res.value = LLVMBuildPointerCast(p->builder, value.value, lb_type(p->module, t), "");
 		return res;
-	}
-
-	if (is_type_simd_vector(src) && is_type_simd_vector(dst)) {
+	} else if (is_type_simd_vector(src) && is_type_simd_vector(dst)) {
 		res.value = LLVMBuildBitCast(p->builder, value.value, lb_type(p->module, t), "");
 		return res;
 	} else if (is_type_array_like(src) && is_type_simd_vector(dst)) {
@@ -239,9 +232,11 @@ lbValue lb_emit_transmute(lbProcedure *p, lbValue value, Type *t) {
 		ap = lb_emit_conv(p, ap, alloc_type_pointer(value.type));
 		lb_emit_store(p, ap, value);
 		return lb_addr_load(p, addr);
-	}
-
-	if (lb_is_type_aggregate(src) || lb_is_type_aggregate(dst)) {
+	} else if (is_type_map(src) && are_types_identical(t_raw_map, t)) {
+		res.value = value.value;
+		res.type = t;
+		return res;
+	} else if (lb_is_type_aggregate(src) || lb_is_type_aggregate(dst)) {
 		lbValue s = lb_address_from_load_or_generate_local(p, value);
 		lbValue d = lb_emit_transmute(p, s, alloc_type_pointer(t));
 		return lb_emit_load(p, d);
@@ -990,14 +985,13 @@ lbValue lb_emit_struct_ep(lbProcedure *p, lbValue s, i32 index) {
 		}
 	} else if (is_type_map(t)) {
 		init_map_internal_types(t);
-		Type *itp = alloc_type_pointer(t->Map.internal_type);
+		Type *itp = alloc_type_pointer(t_raw_map);
 		s = lb_emit_transmute(p, s, itp);
 
-		Type *gst = t->Map.internal_type;
-		GB_ASSERT(gst->kind == Type_Struct);
 		switch (index) {
-		case 0: result_type = get_struct_field_type(gst, 0); break;
-		case 1: result_type = get_struct_field_type(gst, 1); break;
+		case 0: result_type = get_struct_field_type(t_raw_map, 0); break;
+		case 1: result_type = get_struct_field_type(t_raw_map, 1); break;
+		case 2: result_type = get_struct_field_type(t_raw_map, 2); break;
 		}
 	} else if (is_type_array(t)) {
 		return lb_emit_array_epi(p, s, index);
@@ -1130,10 +1124,10 @@ lbValue lb_emit_struct_ev(lbProcedure *p, lbValue s, i32 index) {
 	case Type_Map:
 		{
 			init_map_internal_types(t);
-			Type *gst = t->Map.internal_type;
 			switch (index) {
-			case 0: result_type = get_struct_field_type(gst, 0); break;
-			case 1: result_type = get_struct_field_type(gst, 1); break;
+			case 0: result_type = get_struct_field_type(t_raw_map, 0); break;
+			case 1: result_type = get_struct_field_type(t_raw_map, 1); break;
+			case 2: result_type = get_struct_field_type(t_raw_map, 2); break;
 			}
 		}
 		break;
@@ -1439,34 +1433,47 @@ lbValue lb_dynamic_array_allocator(lbProcedure *p, lbValue da) {
 	return lb_emit_struct_ev(p, da, 3);
 }
 
-lbValue lb_map_entries(lbProcedure *p, lbValue value) {
-	Type *t = base_type(value.type);
-	GB_ASSERT_MSG(t->kind == Type_Map, "%s", type_to_string(t));
-	init_map_internal_types(t);
-	i32 index = 1;
-	lbValue entries = lb_emit_struct_ev(p, value, index);
-	return entries;
+lbValue lb_map_len(lbProcedure *p, lbValue value) {
+	GB_ASSERT_MSG(is_type_map(value.type) || are_types_identical(value.type, t_raw_map), "%s", type_to_string(value.type));
+	lbValue len = lb_emit_struct_ev(p, value, 1);
+	return lb_emit_conv(p, len, t_int);
 }
-
-lbValue lb_map_entries_ptr(lbProcedure *p, lbValue value) {
-	Type *t = base_type(type_deref(value.type));
-	GB_ASSERT_MSG(t->kind == Type_Map, "%s", type_to_string(t));
-	init_map_internal_types(t);
-	i32 index = 1;
-	lbValue entries = lb_emit_struct_ep(p, value, index);	
-	return entries;
+lbValue lb_map_len_ptr(lbProcedure *p, lbValue map_ptr) {
+	Type *type = map_ptr.type;
+	GB_ASSERT(is_type_pointer(type));
+	type = type_deref(type);
+	GB_ASSERT_MSG(is_type_map(type) || are_types_identical(type, t_raw_map), "%s", type_to_string(type));
+	return lb_emit_struct_ep(p, map_ptr, 1);
 }
 
-lbValue lb_map_len(lbProcedure *p, lbValue value) {
-	lbValue entries = lb_map_entries(p, value);
-	return lb_dynamic_array_len(p, entries);
+lbValue lb_map_cap(lbProcedure *p, lbValue value) {
+	GB_ASSERT_MSG(is_type_map(value.type) || are_types_identical(value.type, t_raw_map), "%s", type_to_string(value.type));
+	lbValue zero = lb_const_int(p->module, t_uintptr, 0);
+	lbValue one = lb_const_int(p->module, t_uintptr, 1);
+
+	lbValue mask = lb_const_int(p->module, t_uintptr, MAP_CACHE_LINE_SIZE-1);
+
+	lbValue data = lb_emit_struct_ev(p, value, 0);
+	lbValue log2_cap = lb_emit_arith(p, Token_And, data, mask, t_uintptr);
+	lbValue cap = lb_emit_arith(p, Token_Shl, one, log2_cap, t_uintptr);
+	lbValue cmp = lb_emit_comp(p, Token_CmpEq, data, zero);
+	return lb_emit_conv(p, lb_emit_select(p, cmp, zero, cap), t_int);
 }
 
-lbValue lb_map_cap(lbProcedure *p, lbValue value) {
-	lbValue entries = lb_map_entries(p, value);
-	return lb_dynamic_array_cap(p, entries);
+lbValue lb_map_data_uintptr(lbProcedure *p, lbValue value) {
+	GB_ASSERT(is_type_map(value.type) || are_types_identical(value.type, t_raw_map));
+	lbValue data = lb_emit_struct_ev(p, value, 0);
+	u64 mask_value = 0;
+	if (build_context.word_size == 4) {
+		mask_value = 0xfffffffful & ~(MAP_CACHE_LINE_SIZE-1);
+	} else {
+		mask_value = 0xffffffffffffffffull & ~(MAP_CACHE_LINE_SIZE-1);
+	}
+	lbValue mask = lb_const_int(p->module, t_uintptr, mask_value);
+	return lb_emit_arith(p, Token_And, data, mask, t_uintptr);
 }
 
+
 lbValue lb_soa_struct_len(lbProcedure *p, lbValue value) {
 	Type *t = base_type(value.type);
 	bool is_ptr = false;
diff --git a/src/main.cpp b/src/main.cpp
index b75137613..3b0a599db 100644
--- a/src/main.cpp
+++ b/src/main.cpp
@@ -638,6 +638,7 @@ enum BuildFlagKind {
 	BuildFlag_StrictStyleInitOnly,
 	BuildFlag_ForeignErrorProcedures,
 	BuildFlag_DisallowRTTI,
+	BuildFlag_UseStaticMapCalls,
 
 	BuildFlag_Compact,
 	BuildFlag_GlobalDefinitions,
@@ -814,6 +815,8 @@ bool parse_build_flags(Array<String> args) {
 
 	add_flag(&build_flags, BuildFlag_DisallowRTTI,            str_lit("disallow-rtti"),             BuildFlagParam_None,    Command__does_check);
 
+	add_flag(&build_flags, BuildFlag_UseStaticMapCalls,       str_lit("use-static-map-calls"),      BuildFlagParam_None,    Command__does_check);
+
 
 	add_flag(&build_flags, BuildFlag_Compact,                 str_lit("compact"),                   BuildFlagParam_None,    Command_query);
 	add_flag(&build_flags, BuildFlag_GlobalDefinitions,       str_lit("global-definitions"),        BuildFlagParam_None,    Command_query);
@@ -1414,6 +1417,9 @@ bool parse_build_flags(Array<String> args) {
 						case BuildFlag_DisallowRTTI:
 							build_context.disallow_rtti = true;
 							break;
+						case BuildFlag_UseStaticMapCalls:
+							build_context.use_static_map_calls = true;
+							break;
 						case BuildFlag_DefaultToNilAllocator:
 							build_context.ODIN_DEFAULT_TO_NIL_ALLOCATOR = true;
 							break;
diff --git a/src/types.cpp b/src/types.cpp
index f9470ce2b..b7bfe1b0f 100644
--- a/src/types.cpp
+++ b/src/types.cpp
@@ -226,8 +226,6 @@ struct TypeProc {
 	TYPE_KIND(Map, struct {                                   \
 		Type *key;                                        \
 		Type *value;                                      \
-		Type *entry_type;                                 \
-		Type *internal_type;                              \
 		Type *lookup_result_type;                         \
 	})                                                        \
 	TYPE_KIND(Struct,  TypeStruct)                            \
@@ -685,13 +683,18 @@ gb_global Type *t_allocator_error                = nullptr;
 gb_global Type *t_source_code_location           = nullptr;
 gb_global Type *t_source_code_location_ptr       = nullptr;
 
-gb_global Type *t_map_hash                       = nullptr;
-gb_global Type *t_map_header                     = nullptr;
-gb_global Type *t_map_header_table               = nullptr;
+gb_global Type *t_map_info                       = nullptr;
+gb_global Type *t_map_cell_info                  = nullptr;
+gb_global Type *t_raw_map                        = nullptr;
+gb_global Type *t_map_info_ptr                   = nullptr;
+gb_global Type *t_map_cell_info_ptr              = nullptr;
+gb_global Type *t_raw_map_ptr                    = nullptr;
 
 
 gb_global Type *t_equal_proc  = nullptr;
 gb_global Type *t_hasher_proc = nullptr;
+gb_global Type *t_map_get_proc = nullptr;
+gb_global Type *t_map_set_proc = nullptr;
 
 gb_global Type *t_objc_object   = nullptr;
 gb_global Type *t_objc_selector = nullptr;
@@ -1926,7 +1929,7 @@ bool is_type_valid_for_keys(Type *t) {
 	if (is_type_untyped(t)) {
 		return false;
 	}
-	return is_type_comparable(t);
+	return type_size_of(t) > 0 && is_type_comparable(t);
 }
 
 bool is_type_valid_bit_set_elem(Type *t) {
@@ -3333,8 +3336,6 @@ Selection lookup_field_with_selection(Type *type_, String field_name, bool is_ty
 			}
 		}
 	} else if (type->kind == Type_DynamicArray) {
-		// IMPORTANT TODO(bill): Should these members be available to should I only allow them with
-		// `Raw_Dynamic_Array` type?
 		GB_ASSERT(t_allocator != nullptr);
 		String allocator_str = str_lit("allocator");
 		gb_local_persist Entity *entity__allocator = alloc_entity_field(nullptr, make_token_ident(allocator_str), t_allocator, false, 3);
@@ -3345,15 +3346,12 @@ Selection lookup_field_with_selection(Type *type_, String field_name, bool is_ty
 			return sel;
 		}
 	} else if (type->kind == Type_Map) {
-		// IMPORTANT TODO(bill): Should these members be available to should I only allow them with
-		// `Raw_Map` type?
 		GB_ASSERT(t_allocator != nullptr);
 		String allocator_str = str_lit("allocator");
-		gb_local_persist Entity *entity__allocator = alloc_entity_field(nullptr, make_token_ident(allocator_str), t_allocator, false, 3);
+		gb_local_persist Entity *entity__allocator = alloc_entity_field(nullptr, make_token_ident(allocator_str), t_allocator, false, 2);
 
 		if (field_name == allocator_str) {
-			selection_add_index(&sel, 1);
-			selection_add_index(&sel, 3);
+			selection_add_index(&sel, 2);
 			sel.entity = entity__allocator;
 			return sel;
 		}
@@ -3798,11 +3796,12 @@ i64 type_size_of_internal(Type *t, TypePath *path) {
 	case Type_Map:
 		/*
 			struct {
-				hashes:  []int,               // 2 words
-				entries: [dynamic]Entry_Type, // 5 words
+				data:      uintptr,           // 1 word
+				size:      uintptr,           // 1 word
+				allocator: runtime.Allocator, // 2 words
 			}
 		*/
-		return (2 + (3 + 2))*build_context.word_size;
+		return (1 + 1 + 2)*build_context.word_size;
 
 	case Type_Tuple: {
 		i64 count, align, size;