gistfile1.txt

package workbench

      import "core:/sys/win32"

      import "core:mem"
      import "core:hash"
using import "core:fmt"

using import "../logging"

Hashtable :: struct(Key: typeid, Value: typeid) {
	indices: []Key_Index(Key),
	values:  []Key_Value(Value),
	free_places: int,
	collisions: int,
}

Key_Index :: struct(Key: typeid) {
	filled: bool,
	key: Key,
	index: int,
}

Key_Value :: struct(Value: typeid) {
	filled: bool,
	value: Value,
}

next_power_of_2 :: proc(n: int) -> int {
	if (n <= 0) {
		return 0;
	}
	n := n;
	n -= 1;
	n |= n >> 1;
	n |= n >> 2;
	n |= n >> 4;
	n |= n >> 8;
	n |= n >> 16;
	n |= n >> 32;
	n += 1;
	return n;
}

insert :: proc(using table: ^Hashtable($Key, $Value), key: Key, value: Value) #no_bounds_check {
	if f64(free_places) <= f64(len(indices))*0.25 {
		old_indices := indices;
		old_values  := values;
		old_length  := len(indices);

		INITIAL_SIZE :: 32;
		new_len := next_power_of_2(INITIAL_SIZE + old_length);
		indices     = make([]Key_Index(Key),   new_len);
		values      = make([]Key_Value(Value), new_len);
		free_places = len(indices);

		for index in old_indices {
			if index.filled {
				value := old_values[index.index];
				insert(table, index.key, value.value);
			}
		}

		delete(old_indices);
		delete(old_values);
	}

	key, value := key, value;

	key_idx_pair: ^Key_Index(Key);
	collided := false;
	{
		key_bytes := mem.slice_ptr(cast(^byte)&key, size_of(Key));
		h := hash.fnv64(key_bytes);
		idx := h % cast(u64)len(indices);
		first_idx := idx;
		for {
			pair := &indices[idx];
			if !pair.filled {
				key_idx_pair = pair;
				break;
			}
			collided = true;
			idx = (idx + 1) % cast(u64)len(indices);
			if idx == first_idx {
				break;
			}
		}
		assert(key_idx_pair != nil, "indices array was full.");
	}
	if collided do collisions += 1;

	value_idx: int = -1;
	for value, idx in values {
		if !value.filled {
			value_idx = idx;
			break;
		}
	}
	assert(value_idx != -1, "values array was full");

	values[value_idx] = {true, value};
	key_idx_pair^ = {true, key, value_idx};
	free_places -= 1;
}

get :: proc(using table: ^Hashtable($Key, $Value), key: Key) -> Value {
	key := key;
	key_bytes := mem.slice_ptr(cast(^byte)&key, size_of(Key));
	h := hash.fnv64(key_bytes);
	idx := h % cast(u64)len(indices);
	first_idx := idx;
	key_idx_pair: ^Key_Index(Key);
	for {
		pair := &indices[idx];
		if !pair.filled {
			continue;
		}
		if pair.key == key {
			key_idx_pair = pair;
			break;
		}
		idx = (idx + 1) % cast(u64)len(indices);
		if idx == first_idx {
			panic(tprint("couldn't find key", key));
			break;
		}
	}
	assert(key_idx_pair != nil, tprint("couldn't find key ", key));
	return values[key_idx_pair.index].value;
}

main :: proc() {
	freq := get_freq();

	NUM_ELEMS :: 1024 * 10;

	my_table: Hashtable(int, int);
	{
		insert_start := get_time();
		for i in 0..NUM_ELEMS {
			insert(&my_table, i, i * 3);
		}
		insert_end := get_time();
		logln("My map inserting ", NUM_ELEMS, " elements:   ", (insert_end-insert_start)/freq, "s");
		// logln("collisions: ", my_table.collisions);
	}

	odin_table: map[int]int;
	{
		insert_start := get_time();
		for i in 0..NUM_ELEMS {
			odin_table[i] = i * 3;
		}
		insert_end := get_time();
		logln("Odin map inserting ", NUM_ELEMS, " elements: ", (insert_end-insert_start)/freq, "s");
	}

	logln("free_places: ", my_table.free_places, ", len(indices): ", len(my_table.indices));

	{
		lookup_start := get_time();
		for i in 0..NUM_ELEMS {
			val := get(&my_table, i);
		}
		lookup_end := get_time();
		logln("My map retrieving ", NUM_ELEMS, " elements:   ", (lookup_end-lookup_start)/freq, "s");
	}

	{
		lookup_start := get_time();
		for i in 0..NUM_ELEMS {
			val := odin_table[i];
		}
		lookup_end := get_time();
		logln("Odin map retrieving ", NUM_ELEMS, " elements: ", (lookup_end-lookup_start)/freq, "s");
	}
}

get_time :: inline proc() -> f64 {
	res: i64;
	win32.query_performance_counter(&res);
	return cast(f64)res;
}

get_freq :: inline proc() -> f64 {
	freq: i64;
	win32.query_performance_frequency(&freq);
	return cast(f64)freq;
}