4 ms·
Thank you for this article. I have been working on trying to design a contiguous hash table data structure that has these two mutual requirements: a) allows d
by samsquire 3y ago
Thank you for this article.
I have been working on trying to design a contiguous hash table data structure that has these two mutual requirements:
a) allows deep clones (due to contiguous memory copyable with memcpy)
b) supports arbitrarily nestable hash tables
The closest library I know about is smolworld ( https://github.com/snej/smol_world https://github.com/snej/smol_world ) but I don't know how easy it can be cloned.
These requirements rules out multiple mallocs: I do one single malloc and expect that to be enough for the entire hashmap.
I'm not sure if these constraints might also force a fixed number of buckets and a fixed capacity.
The clonable property requires interior mutability be limited, because if you memcpy pointers they would cause structure sharing, that I'm trying to avoid, hence a deep clone.
Rationale: these are the use cases I have for such a data structure. The first is cheap copy on write. I also have a left-right concurrency control hashmap, but I feel the properties of this data structure are even better. The first is a sharding in multithreading design: do a cheap memcpy for each thread and shard the processing and merge at the end, without any synchronization cost while the threads are working. I know that deep cloning is slow in Java and presumably C if you do it with loops rather than memcpy. Another use case is efficient serialization for network.
In other words, a protobuf but easily deep clonable without loops.
- teo_zero 3y agoIf you pre-allocate a large enough buffer, you can keep a pointer to mark the boundary between the part where you have already stored data and the part still empty. Then re-implement malloc() to just move such pointer. Of course you must check for running out of allocated memory, etc. This simple approach assumes that you seldom delete entries, because it never reclaims the room occupied by deleted entries.
- williamcotton 3y agoHere's a simple example of the bump allocator part of this! https://gist.github.com/williamcotton/99ab6e8efa3c4b6c07a149d1262dfccf https://gist.github.com/williamcotton/99ab6e8efa3c4b6c07a149...
- Gibbon1 3y ago> because if you memcpy pointers they would cause structure sharing, that I'm trying to avoid, hence a deep clone. I'm probably that guy that pipes up when he doesn't know what he's talking about but. You can store offsets instead of pointers. You can then just memcpy the whole thing and it'll just work as long as everything is self contained.
- samsquire 3y agoThanks for your reply, you're right. You know what you're talking about. This is what smol_world does, it uses 32 bit indexes. I really like the idea of smol_world, I just don't know if you can easily .clone() it.