Understanding the StaticStringMap implementation

Explain
1

I was reading the Zig standard library and stumbled across this piece of code in the StaticStringMap implementation:

struct {
    kvs: *const KVs = &empty_kvs,
    …

    const KVs = struct {
        keys: [*]const []const u8,
        values: [*]const V,
        len: u32,
    };
    …

I was reading the Zig standard library and stumbled into this piece of code in the StaticStringMap implementation:

struct {
    kvs: *const KVs = &empty_kvs,
    …

    const KVs = struct {
        keys: [*]const []const u8,
        values: [*]const V,
        len: u32,
    };
    …

From what I can see, KVs has a known size (two pointers and a u32), so what I’m struggling to understand is why kvs is a pointer. In the runtime init() function it’s allocated on the heap, which seems like a waste of resources, since it could be allocated statically on the stack. Am I missing something here?

1 Like
2

It is a comptime structure type (constant data), and is does not live on the stack or in the heap, but compiled directly into program memory wherever the compiler decides to place it, hence you use a pointer to wherever that static memory resides.

EDIT:
To offer an example that is analoguous, think of it like const declaration for a string:

pub const MyType {

    pub const foo = "Hello World";
};

The type of foo is *const [11:0]u8, a pointer to where those bytes were statically compiled into the program binary. They are not heap-allocated, nor exist on the stack of a function call. You can use a hex-editor to find this string within the binary itself, which is where the pointer is pointing to. It is the same case for the StaticStringMap.

1 Like
3

it’s a comptime structure type if we use the initComptime() function, but we also have a runtime constructor (init()), which clearly allocates memory for that known-sized struct:

pub fn init(kvs_list: anytype, allocator: mem.Allocator) !Self {
    ...
    const kvs = try allocator.create(KVs);
    errdefer allocator.destroy(kvs);
    ...
}

/// this method should only be used with init() and not with initComptime().
pub fn deinit(self: Self, allocator: mem.Allocator) void {
    ...
    allocator.destroy(self.kvs);
}

source code

4

Yes, but it still requires it to be a pointer, otherwise the initComptime variant would no longer work or make sense (where would the memory be stored?). There is std.StringHashMap if you want to use a similar structure that can live on the stack, and eliminate one degree of redirection, though its contents will still obviously be heap-allocated. Although it isn’t restricted to only comptime, the primary purpose of the StaticStringMap is its comptime features, as allocating (as far as I know) cannot be done using a generic Allocator interfaces at comptime, a requirement for “traditional” hashmaps in the standard library.

5

KVs contains pointers to the actual data, itself being used through a pointer, is unnecessary. Though it does reduce the size of the struct.

FYI, there is a pr to optimise StaticStingMap that changes the struct to contain only a slice of KV, the rest of the data is calculated at comptime in the respective functions, so it won’t exist unless needed and is prone to more optimisations.

1 Like