> If we use standard libraries, we can benefit from extreme optimization
I did a quick test[0] about that since it is a common thing people claim ("use the standard library, it has been battle tested and optimized to heavens", etc). Since the article is mainly just about the hash part of the hash table, i only tried with hash sets instead of full hash maps, though the difference is trivial.
I generated a 256MB file with 67108864 32bit unique random integers and tried to use both C++'s unordered_set as well as a custom set built using the method described in the site (i also used the 32bit integer hash from a link in the article). I used C++ because it is the closest to C that has a standard library that provides a hash set.
The results on my machine (Ryzen 3700X, Linux, GCC 12.1.1) are:
std version: 19504ms
custom version: 3979ms
The "std version" is almost five times slower than the custom purpose-built version. Note that this is the "best case" scenario where i specify a number of buckets to minimize resizing - without that the std version needs 41382ms instead (i.e. a naive use of unordered_set would be almost twice as slow as with providing the bucket count and about 10 times slower than the custom version).
So yeah, i don't think the days of writing your own data structures are left behind, at least as far as purpose built structures for improving performance are concerned. Of course sometimes you just want to replace a very simple/naive algorithm with an at least theoretically faster one (i.e. replacing a linear search in a big unordered array with some map) so having the language provide some reusable data structures is convenient. But if that doesn't solve the performance problem you may have and the problem is in the data structure you can most likely do better than the generic structures the language has - after all you know your data and your code at a better and higher level than the compiler ever will.
It would be worth somebody gathering real world numbers from systems, to find out where people use std::unordered_map, how much are they leaving on the table, versus where people use say Folly F14, how small is the gain they're getting with their real workload.
I would guess there are a lot of maps out there which in practice have a dozen things in them and so it doesn't matter how it works, a naive linear search would be fine too. But I genuinely have no idea, maybe it's 99% maybe it's 1%.
30ns per lookup is ok. I think you could do around 6ns per lookup (maybe less?) without changing the hash algorithm, using huge pages, reordering the lookups, or dropping the requirement that it be a hash table.
Note that the time is for both insertion and lookup, i didn't actually check lookup alone, just how general "use" compares between the two.
Pure lookup is
std version: 8563ms
custom version: 1660ms
(i.e. std version is ~5.1 times slower, again with the preallocated buckets - without preallocating the buckets it is 15298ms)
That puts lookup to ~24.8ns.
> I think you could do around 6ns per lookup (maybe less?) without changing the hash algorithm, using huge pages, reordering the lookups, or dropping the requirement that it be a hash table.
Yeah, considering this is just a "set of 32bit numbers" i could just as easily use a bitmap - a simple implementation with a bitmap array had it at ~6.3ns per lookup - but the discussion was on hash maps/sets and i wanted to keep it as close to the article.
I'm not sure what you refer to with "huge pages" though. Can you elaborate or provide some info?
Also about reordering the lookups you mean changing the order of the values i check? I wanted to have a random lookup since this was a test for how well arbitrary lookups would perform, this is why i generated a file with unique random numbers ahead of time.
You specify the number of buckets but it can still affect how they're built and thus how they are used. This is a guess TBH since i don't know exactly what G++'s unordered_set does.
You are right about execution order, not sure what is going on since both are isolated (i literally just swapped the code around) but doing that almost doubled the std version performance :-/ - the custom one didn't change at all though.
Perhaps the optimizer somehow interferes with both tests since the code is next to each and they use the same source data - a way to work around that might be to implement the lookup tests in separate shared objects with the "fill set" and "lookup set" to be in separate functions. I might do that at some point later.
Oh I see, how many did you choose for the bucket numbers?
( I assumed pre-allocate was a capacity allocation rather than bucket parameter )
I'd recommend 82139 which is the closest prime above 82137 which is Sqrt(Pi/2 * 2^32) which is the expected number of items before a collision.
I'd also be interested to hear the performance under the hash function:
hash(x) = x
This is the CLR and JRE's prefered int32 hash. It's a poor hash for cryptographic purposes or wanting random bits but it has stellar performance for the most part.
I linked the source above. The bucket count is a bit highter than 82139... just 101473717 :-P. Changing it with 82139 does make it twice as slow though. I used 101473717 because that was the number i got from bucket_count() after running it with the default buckets.
About hash(x)=x, that is interesting, i never thought to just use x itself as the hash :-P. The performance is actually a tiny bit better (~17%) for checking if a number is in the set.
I was informally referring to the insert and the much later lookup as "2 lookups."
> I'm not sure what you refer to with "huge pages" though. Can you elaborate or provide some info?
CPUs for servers and desktops made within my lifetime (?) use what's called a translation lookaside buffer (TLB) to cache some of the most recently used mappings from virtual pages to physical pages. Page sizes on commonly used CPUs are 4KB except for Apple Silicon which uses 16KB pages. Since at least 1996[0], consumer CPUs have shipped with the ability to use 2MB (or larger) pages in addition the default page size. This capability is awkwardly exposed on Linux. Linux users can either use transparent huge pages, which will slowly replace 2MB-aligned 2MB regions allocated by long-running programs with huge pages, or they can use hugetlbfs to directly request huge pages when calling mmap. Windows nominally supports this feature and calls it "large pages," but in practice users can either run their program as administrator right after booting the machine and then never close it or give up. macOS supports this feature since 2016 and calls it "superpages." I haven't used that so I can't comment on how usable it is in practice.
A lot of the runtime of a program like this is TLB misses. So you can just have way, way fewer TLB misses, like >99% fewer, if you use 2MB pages instead of 4KB pages. The mmap man page[1] says how to ask for huge pages when you call mmap. Here are some other[2] pages[3] about setting up hugetlbfs, which you must do before calling mmap in this way will work.
> Also about reordering the lookups you mean changing the order of the values i check? I wanted to have a random lookup since this was a test for how well arbitrary lookups would perform, this is why i generated a file with unique random numbers ahead of time.
I just wanted to be specific, like maybe a program could compute the set and then check that the set was computed correctly more quickly by partially sorting the input. No sorting allowed!
I see, i was vaguely aware of them but not to the extent described here. Sadly it seems you need to configure the OS for them - might work for something like a server under your control, but it isn't something you can rely on in general use.
I tried to use posix_memalign + madvice MADV_HUGEPAGE to allocate the memory for use in the test program (if i understood the documentation correctly, the "transparent huge page support" that madvice relies on doesn't need any system setup) but didn't see any difference from just using malloc (perhaps the advice was ignored). Either way, both were much slower than just statically allocating the data like in the test program.
Okay but now the argument has switched from "Use your standard library, because its datastructures have been optimized to the extreme and are better than anything than you'd make yourself" to "use your standard library because it's fast enough, you probably don't spend enough time in hash table algorithms for that 5x performance improvement to be worth it".
C++'s `std::unordered_[map|set]` has a requirement that the addresses of objects in the map don't change on a reallocation -- this forces it to use buckets with linked lists under the hood. Try absl::flat_hash_set (https://github.com/abseil/abseil-cpp/blob/master/absl/contai...) and see how it goes.
I did a quick test[0] about that since it is a common thing people claim ("use the standard library, it has been battle tested and optimized to heavens", etc). Since the article is mainly just about the hash part of the hash table, i only tried with hash sets instead of full hash maps, though the difference is trivial.
I generated a 256MB file with 67108864 32bit unique random integers and tried to use both C++'s unordered_set as well as a custom set built using the method described in the site (i also used the 32bit integer hash from a link in the article). I used C++ because it is the closest to C that has a standard library that provides a hash set.
The results on my machine (Ryzen 3700X, Linux, GCC 12.1.1) are:
The "std version" is almost five times slower than the custom purpose-built version. Note that this is the "best case" scenario where i specify a number of buckets to minimize resizing - without that the std version needs 41382ms instead (i.e. a naive use of unordered_set would be almost twice as slow as with providing the bucket count and about 10 times slower than the custom version).So yeah, i don't think the days of writing your own data structures are left behind, at least as far as purpose built structures for improving performance are concerned. Of course sometimes you just want to replace a very simple/naive algorithm with an at least theoretically faster one (i.e. replacing a linear search in a big unordered array with some map) so having the language provide some reusable data structures is convenient. But if that doesn't solve the performance problem you may have and the problem is in the data structure you can most likely do better than the generic structures the language has - after all you know your data and your code at a better and higher level than the compiler ever will.
[0] http://xtra.runtimeterror.com/snippets/dir?ci=tip&name=hash/...