Implementations of fast containers
I've participated in some discussions on fast containers on the SG14 mailing list. Now I'm wondering what production quality open source implementations are there of different fast containers? I'm aware of the following:
- Boost Flatmap
- Google Sparse/Dense hash
- HashMap (my own project)
I've not had any success using Google's implementation, but I've used flatmap and my own HashMap in production and achieved nice performance boosts. It would be nice to compare std::map and flatmap with some good implementations of cache-oblivious search trees (http://supertech.csail.mit.edu/cacheObliviousBTree.html) and in-memory btrees.
My own HashMap implementation has similar drawbacks as Google densehash in terms of standards compliance, but if you are willing to sacrifice 4 or 8 bytes (depending upon alignment) it's possible to create a 99% standards compliant std::unordered_map that is using open addressing with linear probing. Each bucket would be defined as:
struct {
uint32_t hash;
std::aligned_storage<sizeof(T)> value;
};
Hash value 0 is reserved for empty buckets. Values are inserted by placement new into an array of buckets. The only standards breakage is that T would need to be either std::nothrow_copy_assignable or std::nothrow_move_assignable to implement erase().
What are your fast containers?
17 comments · 77% upvoted · other discussions
'Fast' really depends on the context.
You mention getting a performance increase with flat_map. This almost certainly because you're looking things up, or in-order traversing far more often than inserting. If your usage was different, where you are altering the container frequently, a std::map might be better.
My point is that there are no magic 'fast' containers, but there are containers that are optimized for different use cases. The boost flat* containers are one example of these, the Google hash containers are another.
Further consideration also needs to be given to iterator and reference stability. For example, it's not valid to cache pointers to objects that live in a boost flat_map (because it's an array, so it might reallocate). For a std::map this is ok though, so here again the flat_map might be faster to look things up, but you might need to look things up more frequently because you can't cache pointers.
rigtorp [OP] 2 points · Apr 2016
Good points. I generally have lots of insertions and deletions (millions per second) of small objects either to a single big hash table or spread over thousands of maps. My hash table and flat_map is much faster since they reduce cache misses and they don't do any allocs if sized properly. You are right open addressing hash tables with inplace storage invalidate all iterators on any modifying operation, but if you are fine with the alloc overhead you can store std::unique_ptr to the values instead and get iterators that don't invalidate (traversal would still be an issue).
I think using btrees might be faster than the red-black trees of std::map in almost all use cases where std:map is used. It would be interesting to see benchmarks on that.
tavianator 3 points · Apr 2016
This is true (don't have any benchmarks off the top of my head though). It's difficult to meet the iterator invalidation guarantees of
std::mapwith a B-tree though, so it's not quite a drop-in replacement.rigtorp [OP] 2 points · Apr 2016
Yes, that's also an issue with open addressing hash tables. It's a shame really that the spec constrains the design so much.
[deleted] 1 points · Apr 2016
If you don't care about the keys, a slot map might benefit you. It has O(1) random access, insert, and remove, at the cost of dictating what your values key will be instead of letting you choose.