Benchmarking C++ Sets
constantsmatter.com
constantsmatter.com
In a realistic application (with cache pressure) you may find an array performs even better because the CPU can trivially predict and pipeline the entire operation vs jumping around to random locations in memory.
Another approach is a B-tree with lots of nodes stored at the leaves. This can get you the array's linear performance for small datasets, while preserving other big-O benefits of sets/trees (eg insertion time).
As the side of your dataset grows, there is a performance cliff at L1, L2, and L3 cache size. For very large datasets, creating data structures with predictable access patterns often trumps Big-O entirely. If following a linked list thrashes the cache it turns out the constant factor can and does dominate.
So again, always measure with your application on your intended hardware. Be sure you measure with realistic loads and access patterns.
Std::Array is expected to have almost identical performance characteristics.
The author is generating random strings of length 64. They then generate N random string and search for them. The probability of finding a match is effectively zero.
> Interestingly, up to about 75 elements, the vector actually outperforms both sets.
No way. The unordered_set will perform one hash, one lookup, and return false. That is not going to be slower than SEVENTY FIVE string comparisons.
Looking at the code I _think_ that randString() for each of the N search strings is included in the timing code. That, uh, is not good? Line 29: https://github.com/akshaynanavati/benchmarks/blob/master/ben...
I don't know how Google Benchmark works. So I wrote my own simple test. I could not find any combination of string length and num searches where a vector was faster than an unordered_set.
https://pastebin.com/raw/mfBmGa5B
Example results:
String length: 8 Num Elements: 75 Num Searches: 10000 Gen Time: 1.94252 Vec Time: 4.12721 Set Time: 0.144987 Num Found: 0
I suspect the author made critical mistakes too.
If you are actually hitting a match or do many operations with warmed cache, vector may actually win big time even compared to unordered_set as there may be no pointer chasing involved. (since both all keys and all values are in cache) The vector scan essentially boils down to a memcmp for a sufficiently smart compiler. Computing the hash may or may not be faster than this.
In my testing unordered_map is faster so long as numberOfStrings > stringLength. This true for any size string greater than roughly 4. As stringLength grows the unordered_set advantage grows.
Original post says vector is faster until 75 elements. By my test the unordered_set is 4x faster with 64 char strings/75 elements. At 250 numberOfStrings its ~10x faster.
Sorted vectors + binary search are very very good though. Author said vector faster until 20,000 elements. My testing finds the numberOfStrings > stringLength limit is still basically true. But the unordered_set's advantage grows only to 1.9x by 20,000 numberOfStrings.
This advantage will grow as number of matches / near-matches grows. Random strings are not a great test case. Data sets matter!
Author is fixing a couple of bugs and will be updating their post. Curious to see if his updated results match mine. :)
Nitpick: that is (almost certainly) true for strings of length 64 on any system, but not necessarily so.
On existing systems, it isn’t true for short strings (with ‘short’ being implementation dependent), due to “short string optimization” (See https://stackoverflow.com/a/10319672, https://stackoverflow.com/a/28003328).
There’s nothing in the standard that forbids putting extra room in the base object to accommodate larger strings (but of course, it would surprise many users, possibly lead to stack overflows in lots of code, etc)
Using one of the policy-based data structures instantly gets you about an order magnitude of speedup (for accesses).
Hopefully in the future mistakes of these sort will be avoided, but that might be asking for too much (certainly std::optional opted to break compat with boost's (`std::optional<T&>` is disallowed) so there's some hope).
- Compiler, c++ library, compilation options, and platform are missing
- The author doesn't benchmark vector and unordered_map insertions with reserve()
- If I read correctly, the author benchmarks up to 32,768 items. This is way too low. There should be tests with millions of entries.
- Random string/numbers isn't a realistic scenario and very favourable to unordered_map. I would use data from real life examples, e.g. list of cities, list of people, etc.
- Ordered arrays are missing from the benchmark (e.g. boost::container::flat_set), it's a very powerful data structure. Why just do a sorted vector at the end?
- Vector outperforms unordered_set probably because of the hashing function used.
You have to draw the line somewhere, and this post is very interesting as it is.
One way to speed up set's usually appalling performance is to give it a custom allocator so that instead of N calls to allocate tiny tree nodes all over the heap, you get all your tree nodes on an arena. This can dramatically speed up short-lived sets (for example you are trying to build the unique set of some non-unique input).
Pedantic: comparing 64 character strings is O(1).
I highly doubt std::string takes advantage of them.
> (rather than comparing strings which requires O(n) cycles and memory reads)
A better algorithm is called "radix quicksort with a three-way partition." Rather than the classical qsort < and >= partition, you maintain three regions of <, =, and >. Crucially, at each step, you sort based only on a single character: the whole range via the first char, then the = region via the second char, then that = region via the third char, etc. This allows for super-fast comparisons without re-walking prefixes.
All of these data structures (std::binary_search, std::set, and and set::unordered_set) are quite sub-optimal. The design of unordered_set with closed-hashing separately-allocated buckets is especially distressing.
For a much more efficient take, see LLVM's DenseSet which does NOT separately allocate buckets. This burdens the client with finding two values to represent empty and tombstone entries, but if perf is a concern that's much better than additional mallocs.
From these charts, isn’t unordered_set clearly the best all-rounder? Which is exactly as I’d expect. Am I missing something?
Sure, a simple vector might be a bit faster for 10 or 100 or 1000 elements, but after a certain point performance is awful.
By writing my own implementation (to avoid boost dependency) I kinda understood why they aren't standard: iterators have different invalidation rules and some special sorted-vector-derived useful properties, the map/multimap keys can't be const as in other standard associative containers, etc.
Likewise for a hash table with separate chaining, wouldn't one better-than `std::unordered_set` way to do it be to keep the separate chains as a `std::vector` that is kept sorted, and then use `std::lower_bound` (or the above better version of it) to probe the table? Those separate tables are O(1) in size, so lookup and insertion are still O(1) on average. Worst case goes to O(n log n), but that doesn't seem too bad.
Related: Is there a widely-used "frozen set" C++ data structure? I'm picturing something that is constructed from a sequence but that internally is a sorted `std::vector<T>` that provides a set-like API but that uses `std::lower_bound` to find data. It's easy enough to write, but it seems like it should be in the standard or at least Boost.
[0] https://scottmeyers.blogspot.com/2015/09/should-you-be-using...
C++ sets define the interfaces and not the implementation.
https://github.com/sparsehash/sparsehash
I read a while ago that it beat all the competitors at almost every size.
Also does that allocate a new string every call?
Allocating a new string simulates heap fragmentation.
set @ 4096: 10.80
set @ 32768: 1.31
I would be interested in comparing an stack based array with integers to the sets as well.