Generic chess hash table

Help
,
1

For my chess I have some hashtables for different elements.
These work with an indexing scheme based on key % len, which is the usual thing in chess programs.
The 3 hashtables I have can then be wrappers around this one below.
If people see optimizations, let me know!!

(Too bad the empty_element is not doable with std.mem.zeroes() because of unions and enums inside the Elements).

fn HashTable(Element: type) type {
    return struct {
        const Self = @This();

        const elementsize: usize = @sizeOf(Element);
        const empty_element: Element = get_empty_element();

        /// Array allocated on the heap.
        data: []Element,

        fn init(size_in_bytes: usize) !Self {
            const len: usize = size_in_bytes / elementsize;
            return .{
                .data = try create_data(len),
            };
        }

        fn deinit(self: *Self) void {
            ctx.galloc.free(self.data);
        }

        fn clear(self: *Self) void {
            clear_data(self.data);
        }

        fn resize(self: *Self, size_in_bytes: usize) !void {
            const len: usize = size_in_bytes / elementsize;
            self.data = try ctx.galloc.realloc(self.data, len);
            self.clear();
        }

        fn put(self: *Self, key: u64, value: Element) void {
            self.data[key % self.data.len] = value;
        }

        fn get(self: *Self, key: u64) *Element {
            return &self.data[key % self.data.len];
        }

        fn create_data(len: usize) ![]Element {
            const data: []Element = try ctx.galloc.alloc(Element, len);
            clear_data(data);
            return data;
        }

        fn clear_data(data: []Element) void {
            @memset(data, empty_element);
        }

        fn get_empty_element() Element {
            return switch (Element) {
                Entry => Entry.empty,
                EvalEntry => EvalEntry.empty,
                PawnEntry => PawnEntry.empty,
                else => @compileError("invalid type"),
            };
        }
    };
}
2

This seems more like a cache data structure that overwrites other entries whenever there is a collision, under the name ‘hash table’ I would expect something that doesn’t lose elements that have been inserted.

Or how do you manage hash collisions?

1 Like
3

Collisions are handled by storing the 64 bits key.
EDIT: and some depth tricks.

4

I would be surprised, this seems like you only show a fraction of the relevant code (did you intend to link or show more code?), this is basically how it seems to me:

500×407 65 KB

https://knowyourmeme.com/memes/how-to-draw-an-owl

What do you actually want to accomplish in this topic?
Do you want improvements/tips for your data-structure design, pointers to other solutions etc.?

I think it would help the reader if you added a question or description what you want and a bit more context. Not everyone is familiar with tricks used in chess programming, so I think it would help if you describe how this is actually used, or add some links that do.

1 Like
5

It is just about the little isolated piece of code only… How to draw an owl #1.

To be more specific:
Is it possible to allocate directly an empty array?
Is the create_data function copying the result?
Is it possible to make get_empty_element function generic for each struct type?

6

An empty array doesn’t have memory, you actually can allocate it like the following code demonstrates, but it is unnecessary, the same applies to empty slices which I think you actually meant.

const std = @import("std");

pub fn main() !void {
    var gpa = std.heap.DebugAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    const EmptyArray = [0]u32;
    const data = EmptyArray{};
    std.debug.print("data: {any}\n", .{data});
    std.debug.print("sizeOf: {}\n", .{@sizeOf(@TypeOf(data))});

    const allocated_empty_array = try allocator.create(EmptyArray);
    defer allocator.destroy(allocated_empty_array);
    std.debug.print("data: {any}\n", .{allocated_empty_array.*});

    const allocated_empty_slice = try allocator.alloc(u32, 0);
    defer allocator.free(allocated_empty_slice);
    std.debug.print("slice data: {any}\n", .{allocated_empty_slice});

    const simple_empty_slice: []u32 = &.{};
    std.debug.print("slice data: {any}\n", .{simple_empty_slice});
}

An empty array is just a zero sized type which doesn’t need any memory and an empty slice is a slice where the pointer can point anywhere (except to zero, unless it is an allowzero slice) and the length is 0.

And you can create it by using something like: const my_slice:[]u32 = &.{};

It allocates a slice sets all elements to empty_element and then returns the slice.
The slice itself is copied, but not the contents it points to.
A slice is a fat pointer (a pointer and the length), so those two parts get copied.

You should be able to remove the get_empty_element function and just use decl-literal syntax and write:

const empty_element: Element = .empty;

At least that works if every struct type you want to use defines the empty public constant.

Or you also could directly use Element.empty.

If the type is zero sized and you try to allocate it then the Allocator.create function calculates a pointer with the right alignment for you (but no memory is actually being allocated):

if (@sizeOf(T) == 0) {
    const ptr = comptime std.mem.alignBackward(usize, math.maxInt(usize), @alignOf(T));
    return @ptrFromInt(ptr);
}
1 Like
7

Thank you! I forgot we can use .empty. Strange but useful!
With an empty array i meant an array with length but all directly filled with .empty, (instead of creating and then filling).

8 
var array: [n]Element = @splat(.empty);

should work

EDIT: for runtime-known size you’ll have to use an alloc function with @memset(slice, .empty)

2 Likes