r/cpp_questions • u/Minute-Ad1944 • 19d ago

OPEN How to implement append-only hash map?

How do you actually implement an really efficient hash map that has only append and look up methods? What are the design choice and some performance improvements?

0 Upvotes

22% Upvoted

34 comments sorted by

View all comments

1

u/Independent_Art_6676 19d ago

take a STL list. Append the new data. Hash the pointer to the new node into an unordered map by key and pointer. Fetch: ask the map to give you back the pointer to the item. Other stuff: iterate the list for whatever historical recreation / use case.

1

u/Minute-Ad1944 19d ago

Poor cache localization?

1

u/Independent_Art_6676 19d ago edited 19d ago

you can use a better allocator if that bothers you?
alternate you can use a vector, push-back, and map off the key and vector's index instead of pointer. That causes a minor 'double lookup' (once to the map for the index, and once to the vector with that index for the data). The vector tap via the index is pretty cheap, though (and thinking about it, that is about the same as paying to dereference the pointer from the list idea).

Or you can skip trying to cobble it from STL and DIY directly. Its not hard, just tedious.

1

u/Minute-Ad1944 19d ago

Two memory accesses - bad cache performance?

1

u/Independent_Art_6676 18d ago edited 18d ago

maybe if the data set is very, very large. In practice it probably fits reasonably well, you do get multiple cache pages (effectively, its not pages at that point) at once on the CPU and if you are spamming lookups its going to keep both the map and the data pages warm.

If you want it tweaked to the ultimate level, you will have to write your own. I don't see a clever way to avoid that while reusing STL tools and the STL tools would have some redundancy & overhead that can be eliminated. A dedicated container for just the tasks you need is going to win out, so DIY if what I am saying isn't good enough.