wvwwvwwv
commented
2 years ago Implementing Clone is not as simple as it seems. It's true that the data structures are full of ebr::Arc for reference counting, but the unit of memory allocation is not a single key-value entry, instead a fixed number of entries sharing the same memory chunk. That brings about a problematic situation where an entry is removed if we are to implement Clone. Currently, the vacancy of each entry slot in a memory chunk is checked using a bit-vector that's located at the head of the memory chunk. Removing an entry means marking a flag on the bit-vector, and if a cloned instance shares the same memory chunk, that also gets to see the removal; that is definitely undesirable. In order to fix this, the bit-vector field must be separated from the data area by either 1. the one that owns the ebr::Arc manages the bit-vector directly, or 2. use a separate heap memory region for the bit-vector. The latter is not quite a good solution as it doubles the average count of heap memory allocation. The former is also bad in terms of memory usage, for instance, HashMap is a two-level data structure that the first level is an array of ebr::Arc, and the second level is the aforementioned array of entries with a bit-vector field; the first level array embedding bit-vectors of the second-level array means almost 4-times larger than the current scheme, and it is really a waste of heap memory in case the HashMap is sparse.
So, in short, in order for HashMap or TreeIndex (the situation is similar, the leaf node is a single memory chunk of multiple entries embedding metadata) to implement Clone, we have to compromise the performance, or the memory usage efficiency. I'll think about what would be the best approach.
It would be handy to easily
.clone()aHashMaporTreeIndexinstance that contains a bunch of Arc's. I'm a bit hazy on the internals, but I'm assuming copy-on-write semantics could be possible for memory efficiency, at least in theTreeIndexcase.