Store sub item as pointer or deref

Help
,
1

I got a little question which might be obvious for long-term devs, but I’m still unsure. And because so many of those explanation stuff in the web is LLM-generated these days, I would prefer replies from some of you experienced (Zig)devs :slightly_smiling_face:

The scenario: I have a larger main data structure which holds a hash map of smaller substructs with key a u32 id and value a single substruct item (e.g. as kind of cache). Now, one of those cached substructs is always kind of “active”, because its the main source for the ongoing internal operations and thus should be stored in a field of the main structure. Because the active substructure item could be edited, it can’t be const; plus the cache needs to get those updates too, because the program is a long-running process and the active item can change several times (and also back to former already active items).

Now the main question to me is: is it preferable to store this active substruct as pointer into the hash map or as dereferenced item of the pointer into the hash map.

Here as pseudo code:

const MainStruct = struct {
    // Either the dereferenced item:
    active_item: SubStruct,
    // OR the pointer to the item:
    active_item: *SubStruct,
    // Here is the cache list
    item_cache: std.AutoHashMap(u32, SubStruct),
    // ... imagine several more fields to follow ...
};

const SubStruct = struct {
    number: u32,
    string: []const u8,
};

fn setActiveStruct() !void {
    // ... MainStruct and SubStruct's already have been created and the latter added
    // to the HashMap using random ID's (123654, 346562, 8867563 ...)

    // Not I want to set the MainStruct.active to the SubStruct stored at ID 346562

    // Either this one to receive pointer to SubStruct (*SubStruct)
    main_struct.active_item = main_struct.item_cache.getPtr(346562).?;

    // Or this to receive dereferenced item SubStruct
    main_struct.active_item = main_struct.item_cache.getPtr(346562).?.*;

    // ... changes to main_struct.active_item are possible and likely. An item which has been
    // active before could become active again in a later turn of the main event loop
}

Both cases work, thats not the thing. I just want to know what is “better” regarding to performance, memory management, robustness etc.; or what the pros and cons are for each version.

Since my experience regarding those low level things is not very deep (though, still evolving, thanks mainly to Zig), I’m happy for some feedback or even to get taught a lesson because the whole approach is bullshit :grin:

2

if you care about performance benchmark.

regarding memory management/robustness, holding a long term pointer into an unstable collection is ill-advised, which a hashmap could be depending on how you use it.

related to that is: have you tried/able to use a handle instead of a pointer?

3

I haven’t found a good way to benchmark this. But tbh performance should be a minor problem.

The items stored in the hash map have a unique u32 as key which is very very unlikely to match a duplicate. To be precise the keys are directory inodes (which in theory could be reused, but not during the runtime of the program). To make sure, I always update/create an entry with:

const cache = try cache_map.getOrPut(inode);
if (cache.found_existing) {
    cache.value_ptr.*.deinit();
    cache.value_ptr.* = new_item;
} else {
    cache.value_ptr.* = new_item
}

Sorry for the maybe dumb question, but what do you mean by “handles” in this case?

4

andrew has a talk on the subject Video: Programming without pointers

5

Yeah, indeed I watched the video multiple times, but am not sure how I could apply this to my code. But if thats a preferred way I might have to wrap my head around this even more :smile:

However, since this approach is something different, I would assume that there is no real difference between using active_item = cache.getPtr(inode).? and active_item = cache.getPtr(inode).?.* for the case I outlined above

6

This is dangerous in a non-obvious way. Only do this, if you are absolutely sure nothing will write to item_cache while you hold the reference to the value. Any change to the hashmap can invalidate the pointer and you get hard-to-debug crashes.

If you want a safe option, dereference it and store a cope in active_item. For one u32 and slice, that seems like the best option. Storing the pointer would only make sense if you need to actively update the struct, which doesn’t seem to be case for you.

7

Thanks. However, the SubStruct is only an example. The original “substruct” has several more fields containing different types (strings, integers, other structs). And as stated it has to be updated while it is active. E.g. for the used example the SubStruct.string value could be changed and this change has to be present also in the hash map holding the items.

8

Then I’d store pointers in the hashmap. But once you bring pointers into the code, you need to think about their lifetime. Since it’s a cache and not concurrently used, it’s probably easy enough to clean up entries once they are no longer needed. In case there are concurrent inserts/update, it gets a lot more complex and you end up needing refcounting, but I don’t expect you need it for your case.

9

Actually, if you really don’t need performance, you might find that always using getPtr when you need to work with the item, and never storing any reference for “quick access”, might be the easiest and safest option and still fast enough, since I don’t expect your hash table to be huge, if it’s for directories.

10

By the way, this is the exact use case for HashMap.lockPointers().

11

Yes, no concurrent usage in the whole code for now. I want to keep it single threaded/non-concurrent if possible. Mainly exactly because I don’t want to deal with the complexity it introduces. However, that might change in the future. If that’ll become the case, the hint by @alanza might be very helpful:

Yes, but that would be cumbersome code-wise. As long as its non-concurrent I’ll stay with the pointer version. If it gets more complex, I’ll overthink the design and have a deeper look into handles/locking etc.

Thanks to all of you for the tipps

12

Maybe you misunderstood something.

The risk of an invalid pointer is not only caused by multi-threading.

If you add items to your map (or remove items), the pointers into the map can become invalid, because the backing array could be resized and move by these operations.

So, you can only use a pointer into the map while the map itself is unchanged. Changing the values is ok.

13

Yes, I understood that, but thanks for clarification. I just mentioned the concurrent stuff explicitly because @lalinsky mentioned it. But while the item is active, nothing is added to the map. That will only happen if the active item is changed too. Maybe it helps to be a bit more detailed: the active item is the dir which is currently worked on. The map will only get a new item when the current active dir is changed to that newly added dir. If an already cached dir is reactivated, nothing will be added to the hash map.

14

Programming without pointers is nice as long as you have a flat structure.

15

Hey, this one keeps preying on my mind.

Thus, I tried to somehow make a little example using the less-pointer approach. However, first of all I’m not sure if thats the correct approach at all. Also I’m unsure if it saves me any of the problems described initially, since I still use a hash map, but this time only for storing integers (id and indices).

Beside this, personally, I find the code better understandable:

Code block 
const std = @import("std");

const DataStruct = struct {
    name: []const u8,
    year: u16,
    content: []const []const u8,
};

const CacheMap = struct {
    gpa: std.mem.Allocator,
    items: std.ArrayList(DataStruct),
    index_map: std.AutoHashMap(u64, usize),

    pub fn add(self: *CacheMap, item: DataStruct, ident: u64) !void {
        const len = self.items.items.len;
        try self.items.append(self.gpa, item);
        try self.index_map.put(ident, len);
    }

    pub fn get(self: *CacheMap, ident: u64) ?DataStruct {
        const idx = self.index_map.get(ident) orelse return null;
        if (idx + 1 <= self.items.items.len) return self.items.items[idx];
        return null;
    }

    pub fn deinit(self: *CacheMap) void {
        self.index_map.deinit();
        self.items.deinit(self.gpa);
    }
};

pub fn main(init: std.process.Init) !void {
    const gpa = init.gpa;

    var cache: CacheMap = .{
        .gpa = gpa,
        .items = .empty,
        .index_map = .init(gpa),
    };
    defer cache.deinit();

    try cache.add(.{
        .name = "first",
        .year = 2026,
        .content = &.{ "some", "strings" },
    }, 12345);

    try cache.add(.{
        .name = "second",
        .year = 2026,
        .content = &.{ "some", "more", "strings" },
    }, 321);

    const first_item = cache.get(12345) orelse return error.NotFound;

    try std.testing.expectEqual("first", first_item.name);
}

Of course, this code is rather simple and therefore has a flat structure as @ericlang pointed out. Thus, it might not be a feasible approach for more complex data structures…

Furthermore, I’m not sure what would be the best approach to edit a value inside the main arraylist holding the DataStruct items:

  • I could return a pointer to it, changing the return value of CacheMap.get() to ?*DataStruct. But then its a pointer again (which isn’t necessarily bad, but I try to program without pointers where possible :grin: )
  • I could edit the returned not-explicit-a-pointer DataStruct and then reassign it to the corresponding index of the arraylist. But that seems to be only a simple solution as long as DataStruct itself is only a simple struct without complex fields.

PS: Since I’m still trying to wrap my head around this, I unmarked the solution for now (no offense to @lalinsky, your input is always really helpful)

16

If you are working with copies, then just store DataStruct directly in the hash map. There is no benefit of the separate array here. If you want to work without pointers, you could imply have this API:

pub fn add(self: *CacheMap, item: DataStruct, ident: u64) !void;
pub fn update(self: *CacheMap, item: DataStruct, ident: u64) !void;
pub fn get(self: *CacheMap, ident: u64) ?DataStruct;

And you just have these fields:

    gpa: std.mem.Allocator,
    index_map: std.AutoHashMap(u64, DataStruct),

If you are going for correctness, not performance, this makes the most sense to me.

17

For the real project there’ll be very likely no way to avoid all pointers in every scenario (and it might also not be a good idea). However, in some cases I’m passing pointers down through several instances/structs and that seems to be at least a likely error source.

Thus, I’m trying to explore ways to reduce the usage of pointers where its possible and makes sense. The feedback here is very valuable for this since for many concepts I’ve a rather incomplete (at best) understanding how they work on the lower levels.

Indeed your update() method approach seems to be very interesting. This way I could just work with a copy as active item and reassign it to the cache if the active items changes. If I get it right, this would reduce the risk of invalidating the pointer into the map while its active and just make sure on reassignement that the correct id is connected with the up-to-date version of the item…

18

I just implemented your suggestion. I like the clean API, although, it’s more or less just a simple wrapper around AutoHashMap:

Updated Code 
const std = @import("std");

const DataStruct = struct {
    name: []const u8,
    year: u16,
    content: []const []const u8,

    pub fn deinit(self: *DataStruct) void {
        // Just dummy deinit() function for demonstration
        _ = self;
    }
};

const CacheMap = struct {
    gpa: std.mem.Allocator,
    index_map: std.AutoHashMap(u64, DataStruct),

    pub fn add(self: *CacheMap, item: DataStruct, ident: u64) !void {
        const put = try self.index_map.getOrPut(ident);
        if (put.found_existing) return error.KeyAlreadyUsed;
        put.value_ptr.* = item;
    }

    pub fn get(self: *CacheMap, ident: u64) ?DataStruct {
        return self.index_map.get(ident);
    }

    pub fn update(self: *CacheMap, item: DataStruct, ident: u64) !void {
        const entry = try self.index_map.getOrPut(ident);
        if (entry.found_existing) {
            entry.value_ptr.*.deinit();
            entry.value_ptr.* = item;
            return;
        }
        return error.UnknownKey;
    }

    pub fn deinit(self: *CacheMap) void {
        self.index_map.deinit();
    }
};

pub fn main(init: std.process.Init) !void {
    const gpa = init.gpa;

    var cache: CacheMap = .{
        .gpa = gpa,
        .index_map = .init(gpa),
    };
    defer cache.deinit();

    try cache.add(.{
        .name = "first",
        .year = 2026,
        .content = &.{ "some", "strings" },
    }, 12345);

    try cache.add(.{
        .name = "second",
        .year = 2026,
        .content = &.{ "some", "more", "strings" },
    }, 321);

    var first_item = cache.get(12345) orelse return error.NotFound;

    try std.testing.expectEqual("first", first_item.name);

    first_item.name = "reborn";
    std.log.debug("Cached item name before update() call: {s}", .{cache.get(12345).?.name});

    std.log.debug("Call update() function with renamed copy as arg", .{});
    try cache.update(12345, first_item);

    std.log.debug("Cached item name after update() call: {s}", .{cache.get(12345).?.name});
}

As soon as I’ll find the time, I’ll try to implement this for my main code to check if it has any serious drawbacks with the more complex nested data structures.