SAsamsquire·Jun 13, 2023
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 ) 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 str
Read the rest
ucture. 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.