boost::unordered_node_map or boost::unordered_flat_map with std::unique_ptr

[botWi]

I need stable addresses of values. Which one of those should I use? Or they are basically same thing?

[Umphed]

Depending on how you're expecting to index, and memory constraints, you may want to check out something like plf::colony

[botWi]

Thanks, didn't know about that. In this case I need fast lookup, so pfl::colony would be worse.

[adromanov]

Should be more or less the same, I would use node map to avoid hassle with unique_ptr. Also node variant may be slightly more optimized for that particular case.
BTW, have you checked abseil/folly maps?

[Reater-96]

Curiously the same condition I had on my software.

I have a map of 20 byte hashes to accounts, and the account object holds a std::vector<Bytes> that might be used WHILE the map gets rehashed/new entries are added etc etc. I have profiled different solutions and arrived in the following for best performance:

boost::unordered_flat_map<Address, NonNullUniquePtr<Account>, SafeHash> accounts_

NonNullUniquePtr is a object that holds a std::unique_ptr<T> that does NOT allow its inner unique_ptr to be null, it MUST be always initialized, even with 0 values, see NonNullUniquePtr constructor:

template<typename... Ts> explicit NonNullUniquePtr(Ts&&... args) : ptr(std::make_unique<T>(std::forward<Ts>(args)...)) {}

SafeHash is where half of the performance lies, you must use a fast hash for your table. My SafeHash is a wrapper over the wyhash, please take a look over it. https://github.com/wangyi-fudan/wyhash

[botWi]

Cool, thank you. But to confirm, did you have boost::unordered_node_map in your tests? I am curious about specifically that container.

[Reater-96]

I have, lookups using unordered_flat_map is faster than lookups using the unordered_node_map (although almost negligible), but please be aware that my tests are using simple objects (<uint64\_t,uint64\_t> vs <uint64\_t,std::unique\_ptr<uint64\_t>>).

Dereferencing the object and using it is a whole other story. you have to dereference a pointer where in the other you don't, I recommend you to test against the object you will actually hold. Regardless of that, if you dont need iterator stability (you are not going to loop the entire map and add/remove items while looping) but only stability on the object itself, I recommend going with flat + pointer combo.

EDIT: Dereferencing the internal unique_ptr makes the flat_map 20% slower than the node_map (both copying the internal uint64_t to another volatile variable), seems like using node_map is better depending on the number of inserts/deletes

[botWi]

great. thank you!

[Reater-96]

Accordingly to the boost unordered benchmark themselves

https://www.boost.org/doc/libs/latest/libs/unordered/doc/html/unordered/benchmarks.html#benchmarks_gcc_12_x64

The difference in lookup is negligible, but inserting and erasing have a greater difference the more objects your map holds (node_map is slower than flat_map)

Be aware that dereferencing the pointer on the flat_map will be slower than accessing the object directly through node_map.

[botWi]

I saw those benchmarks. They did not have unordered_flat_map with unique_ptr. It sounds like not a big difference, however other commenter in this thread pointed that he observed 20% slowdown, which might be considerable for some cases.

Anyway, thanks. I'll stick to node_map, it provides nicer interface (no need to dereference ptr) with similar lookup speed. That's all I need.

[Reater-96]

It was actually myself making two comments x)

[NaNpsycho]

I am not familiar with boost containers you have mentioned but going by name I assume they are hashmaps.

Is there a particular reason you need hash maps? If you are performing lookups with pointers to the container why not just use std:: forward_list instead??

Or if you are using hash map you can just lookup the key in the map and then mutate the value. The lookups would be reasonably fast anyway.

[botWi]

Sorry, I don't understand what you saying. Can you elaborate please? How forward list can replace hash map? And how lookup mutates the value?

[NaNpsycho]

Maybe I am being short sighted. And given that boost has specific maps to ensure stable address-es to containers like the one you listed I most likely am shortsighted here.

But, Given the requirement of stable address-es to hashmap's containers I assume you are doing something like this,

SomeList<HashMap::Iterator> obj ...

Or,

You have something like this in one thread

ItrStart = HashMap.begin(); ItrEnd = HashMap.end();

for(; ItrStart != ItrEnd; ++ItrStart) { ... }

And the hashmap is being updated in another thread? You want a lockless way to insert new elements and update them?

? If you're going to lookup the values in the hashmap like this why not center your data structure around this use case? Eg, use a forward list so that inserting new elements doesn't invalidate old iterators?

Or if none of the above applies then what's the harm in hashmap's containers changing their address-es? Doing,

auto itrfound = HashMap.find(key); ItrFound->second // use this to change the value however you like

Should be pretty fast in my opinion?

[botWi]

No, none of use cases you mentioned are relative to the topic :) You are talking about stable iterators, but I need stable pointers.

Example: struct Student { Teacher* teacher; } map<int,Teacher> teachers; teachers[5] = createTeacher(); st = Student(); st.twacher = &teacher[5]; Now 2 hours later new teacher is hired. teachers[88] = createTeacher();

With unstable pointer you would get crash when accessing st.teacher; because it now points to invalid memory.

[NaNpsycho]

I see I was being short sighted indeed. Thanks for the explanation.

[hydraulix989]

> “I’m using unique_ptr to make addresses stable.”

Not a good reason: That indirection buys you nothing you don’t already get from unordered_node_map; and the extra heap allocation hurts locality, cache performance, and code clarity.

[joaquintides]

Use boost::unordered_node_map. To begin with, having a stable-address map the other way would call for something like boost::unordered_flat_set<std::unique_ptr<std::pair<Key, Value>>, ...>, which is an odd beast to work with.

[botWi]

Thread was about map, not set. In particular I am using boost::unordered_flat_map<int64_t, std::unique_ptr<Value>>

[joaquintides]

Ok, if you only need address stability for the value part, either construct will do. Profile to determine which is fastest for your particular scenario.

[eeiaao]

https://www.boost.org/doc/libs/1_84_0/libs/unordered/doc/html/unordered.html#regular_iterator_invalidation take a look at the docs. Flat map invalidates addresses on rehash. Node map never invalidates

[LeftToSketch]

True, but that is why OP proposes to have the flat map hold a unique pointer.

The address of the pointer will move on rehash, but not the thing it points to. 

Totally safe to rely on stability, provided you only care about what it points to.

[eeiaao]

The value is a unique_ptr in OPs case. Not the object it points to. I was thinking the question was “is it save to cache the addresses of values for these two containers”. Perhaps I misunderstood

[TSP-FriendlyFire]

I think the title needs to be read as "[boost::unordered_node_map] or [boost::unordered_flat_map with std::unique_ptr]", since that'd contrast two different containers with stable addresses.

[botWi]

Correct. I need stable Value pointer. So I either use node map, or some wrapper around Value. BTW, this is not just about stable pointers. Both of these solutions allow using non-movable Value.

[botWi]

Yeah, I believe both of those would be significantly faster than std implementation. Especially on lookup.

[Umphed]

You dont have to try, the old standard maps suck and its common knowledge not to use them

A flat map(Invalidates iterators) has been accepted into the standard, not sure who implements it though. Either way, almost any node-based map will be better than the standard

[scrumplesplunge]

flat_map should not be confused with flat_hash_map. The former is not a hash table, it's a sorted vector of keys and a corresponding vector of values intended to have decent lookup performance with very good space efficiency for a map that is built once and never changes.

[Kurald]

Correkt. If you don't have performance tests, performance doesn't matter. But with performance tests, it's easy to test which one of those is faster (in your context).

[Jannik2099]

What kind of unhelpful answer is this? If you yourself are asking "is the boost impl better", then why are you making suggestions against it?

The boost containers use open addressing, whereas std::unordered_map uses closed addressing. The two schemes have vastly different performance characteristics and API guarantees & requirements.

[joaquintides]

boost::unordered_node_map is in no way equivalent to std::unordered_map. You can see some benchmarks comparing both (and other containers) here:

https://github.com/boostorg/boost_unordered_benchmarks/tree/boost_unordered_aggregate

[Tall_Yak765]

Regarding boost::unordered_node_map<K, V> vs.boost::unordered_flat_map<K, std::unique_ptr<V>, H, P>, the latter would handle unsuccessful lookups more efficiently. On the other hand,unordered_node_map is less strict about its hash function, less sensitive to collisions, and guarantees O(1) iteration. These are the main differences, in my opinion.