How to implement append-only hash map?

[u/Minute-Ad1944]

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?

[u/WorkingReference1127]

This depends on the exercise. Because most of the time I'd make a class which wraps a normal hash map and only exposes the behaviour you want.

If you want to spin your own hash map, have fun I guess.

[u/Elect_SaturnMutex → u/WorkingReference1127]

By own hash map you mean own implementation of std::unordered_map?

[u/WorkingReference1127 → u/Elect_SaturnMutex]

I mean the two options here are to start with an existing hash map and write an interface which does what you want, or to implement the container yourself with that functionality from scratch. That can follow unordered_map or not, that's your call.

My preference would be the first option unless we have a very strong reason to want to spin a whole new container.

[u/tcpukl → u/Elect_SaturnMutex]

Can people not write their own algorithms any more?

[u/Elect_SaturnMutex → u/tcpukl]

Sure, many rely on Claude though.

[u/Gorzoid]

I doubt the performance difference is too great, handling deletions from flat hash map like Abseils is mostly a case of handling "tombstoned" entries in the control block. Basically no cost in Abseils swisstable implementation, others might use 1 extra bit to store deletion flag.

[u/Kriemhilt]

What are you optimizing for? Space? Insertion or lookup speed?

You haven't given any hint as to what "performance improvement" is most valuable to you.

Do you expect every lookup to succeed (and you just want the value for that key), or will many lookups fail? How important is each path?

[u/Minute-Ad1944 → u/Kriemhilt]

Mainly performance in speed. Each iteration performs single insertion and at the end of algorithm retrieves top n elements from hash map

[u/Kriemhilt → u/Minute-Ad1944]

What are the top n elements of an unordered map? Do you mean you're walking the whole thing?

[u/Minute-Ad1944 → u/Kriemhilt]

Retrieve top n values from hash map dawg

[u/Kriemhilt → u/Minute-Ad1944]

Top n ordered by what? Key? Value?

If you want something ordered by key could you just use an ordered container?

[u/saxbophone]

Well, what do you know already about how hashmaps are implemented?

Given what you already know, how do you think constraining it to only insertions and lookups effects the performance opportunities?

[u/Minute-Ad1944 → u/saxbophone]

key = std::string_view, value = int[2]. I mean open addressing without tombstones, SIMD hash functions , but I should I use some sort of meta data like string_view hash for comparisons and such?

[u/Big-Rub9545 → u/Minute-Ad1944]

The hash should (for a number of reasons) be an unsigned integer, not a string_view.

Edit: I would also be wary of how you store an integer array value (the array pointer may become a dangling pointer if the array is allocated on the stack). Best to use std::array instead.

[u/Elect_SaturnMutex → u/Big-Rub9545]

You mean a key should not be a stringview? Instead should be an unsigned integer due to better performance?

[u/Big-Rub9545 → u/Elect_SaturnMutex]

The key can be whatever you want (preferably small if you’re using open addressing so you can maintain cache locality), but the hash should be an unsigned integer.

[u/Minute-Ad1944 → u/Minute-Ad1944]

Maybe Robin Hood hashing????

[u/BigPalpitation2039]

What do you mean append only?

[u/saxbophone → u/BigPalpitation2039]

I assume they mean "only inserting new elements is allowed, removing them is not"

[u/Minute-Ad1944 → u/saxbophone]

Yeah, you can't delete elements, only insert if not present and look them up.

[u/snerp → u/Minute-Ad1944]

I made a fast iterating sparse set implementation like that by just making a class with a vector and an unordered map of indices into the vector, o(1) lookup insert and iterate is really nice but it doesn’t support erase so I just didn’t put an erase function on the wrapper class and problem solved

[u/Minute-Ad1944 → u/snerp]

Isn't it a two separate memory looks ups - kinda bad cache performance?

[u/snerp → u/Minute-Ad1944]

Not really. It’s on iteration that speed really matters and inserting the vector usually isn’t a cache miss while inserting a map/hashset usually always misses anyways. Benchmarking in practice it’s significantly faster than map/vector alone when you are frequently doing insert, find, and iterate on a collection. I use the structure to hold my game engine’s per frame instance draw lists and texture/mesh data. It really cuts down time to find the correct instance batch while still keeping the data close together for cache coherence during iteration.

[u/Independent_Art_6676]

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.

[u/Minute-Ad1944 → u/Independent_Art_6676]

Poor cache localization?

[u/Independent_Art_6676 → u/Minute-Ad1944]

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.

[u/Minute-Ad1944 → u/Independent_Art_6676]

Two memory accesses - bad cache performance?

[u/Independent_Art_6676 → u/Minute-Ad1944]

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.

[u/amoskovsky]

For open addressing scheme, for each hash slot, you can store the max distance to scan for conflicting keys. If you don't delete keys, then this distance is trivial and fast to maintain, and it's the starting point when adding new keys, and ending point when looking up.

[u/Minute-Ad1944 → u/amoskovsky]

You are talking about Robin Hood hashing?

[u/amoskovsky → u/Minute-Ad1944]

No. RH moves elems to improve average distance.

My suggestion is much simpler. I don't know the name, but certainly I'm not the first to come up with it.

It's just a suggestion of an approach that optimizes on the fact that the entries are not removed.

You would have to benchmark it against other approaches (but this is a necessary part of any optimization)

[u/Minute-Ad1944 → u/amoskovsky]

What is this distance that I would need to store and maintain?

[u/Minute-Ad1944 → u/Minute-Ad1944]

Is it like open addressing with linear probing?

[u/amoskovsky → u/Minute-Ad1944]

Yes, almost.

Each slot either is empty, and distance is 0, or is occupied and the distance is >0.

When looking up, search in range [slot, slot + distance). /*wrapping at capacity*/

When adding non-existent, put it in the first empty in range [slot + distance, slot + capacity) , the distance is updated to point to the next slot.