New Rust hash table leads Benchmarks Game
&gt; Some language implementations have hash tables built-in; some provide a hash table as part of a collections library; some use a third-party hash table library. (For example, use either khash or CK_HT for C language k-nucleotide programs.) The hash table algorithm implemented is likely to be different in different libraries.<p>&gt; Please don&#x27;t implement your own custom &quot;hash table&quot; - it will not be accepted.<p>&gt; The work is to use the built-in or library hash table implementation to accumulate count values - lookup the count for a key and update the count in the hash table.<p>The C++ implementation is thereby testing an old version of a non-standard extension of libstdc++ that I had never heard of and which was likely contributed once by IBM and never really looked at again (by either maintainers <i>or users</i> ;P), while the C implementation is testing the specified khash library, which is apparently something a number of people actively contribute to and attempt to optimize, giving it some notoriety.<p>If I were to do this in C++, and I wasn&#x27;t allowed to use my hash table, I would almost certainly not be using __gnu_pbds::cc_hash_table&lt;&gt;. If I were to just want to use something &quot;included&quot;, I would use the C++11 std::unordered_map&lt;&gt; (note that this code is compiled already as C++11). But we all know the STL is designed for flexibility and predictability, not performance, and the culture of C++ is &quot;that&#x27;s OK, as if you actually care about performance no off-the-shelf data structure is going to be correct&quot;. If I decided I wanted speed, I know I&#x27;d want to check out Folly, and I might even end up using khash.<p>Reading other comments, what happened here is the Rust version is now using some &quot;experimental&quot; hash table based on ongoing work to optimize the Python 3000 dict implementation. This is just not a useful benchmark. What we are benchmarking is &quot;how maintained is the implementation&#x27;s built in hash table and is it tunable for this particular workload&quot;.<p>That&#x27;s why you should not be surprised to see Java doing so well: the code actually being written here is just some glue... your programming language has to be incompetent to do poorly at this benchmark (especially as many commenters here are using a &quot;within a power of 2&quot; rule of thumb). There are even multiple listings for the Java one, and the one that is faster is using it.unimi.dsi.fastutil.longs.Long2IntOpenHashMap?!?<p>What we really should be asking here is: why is <i>any</i> language doing &quot;poorly&quot; in this benchmark? It just isn&#x27;t surprising that Rust is competitive with C&#x2F;C++, nor is it surprising that Java is also; what <i>is</i> surprising is that Swift, Go, Haskell, and C# are not, and so I bet the issue is something (such as &quot;is allocating memory for a thing which is not required&quot;) that can be trivially fixed for each (though by the rules of engagement, it might... or might not :&#x2F; as Java &quot;cheated&quot;, right? ;P... require a minor fix upstream).<p>I mean, since the &quot;work&quot; explicitly is not &quot;write a hash table using nothing but primitives from this language&quot;,  there is no particular reason why Perl and Python (which is using a non-destructive array .replace, which is likely <i>brutal</i>... again: I bet this is almost always a benchmark of ancillary memory allocations) should be doing as poorly as they are: if we all made &quot;optimize for this benchmark&quot; a top priority for a weekend hackathon, I bet we could get every open source language to nail this under 25s. But do we care?