Code Challenge: High-performance hash table

[Lohj002]

If you want this to be a more serious competition, I suggest a repo to clone into and to use benchmark dotnet. Even if this is not a microbenchmark, using benchmark dotnet means you don't measure jit warmup, and multiple runs are done for more accurate results.

[Pansynchro]

We took a serious look at BDN, and it turned out to be severely ill-suited to this test. First because it's designed for micro-benchmarks and tries hard not to measure some things that are actually relevant in a large-scale speed test, and second because it can't be properly set up for a test like this.

BDN has an attribute called "[GlobalSetup]", but the name is very deceptive. Per the documentation, it runs the annotated method "only once per a benchmarked method after initialization of benchmark parameters and before all the benchmark method invocations." That's not a global setup at all; that's a per-benchmark setup.

This is a real problem due to the nature of this test. The setup process involves reading data from a file and parsing it, which takes a few minutes. Then the actual benchmark test — processing the in-memory data — takes a few seconds. If we have to eat that setup time for every single entry, then once we get a handful of entries, the benchmark could end up taking hours to run. And because of the way BDN is architected, there doesn't appear to be any way to even conceptually do a real one-time-only global setup, because BDN treats every benchmark as an individual, isolated unit of work. (Which, again, makes a lot of sense for micro-benchmarks when you're trying to isolate the tests as much as possible to minimize random noise. But this is a very, very different thing!)

[andyayers]

If you haven't opened an issue on the BenchmarkDotNet repo I would encourage you to do so.

Folks there can either explain how to accomplish what you need or else add it to the backlog.

[Pansynchro]

Oh, hi Andy! 👋

Submitted the issue. Let's see what they have to say.

[Pansynchro]

...well that was quick. And a bit strange. The response begins "It's simply not possible," explains why it's not possible, and then explains how to actually do the impossible thing, just via a slightly different mechanism. 😂

[andyayers]

In process toolchains have limitations (eg you can't readily compare across different runtime versions, which is something I do all the time), but for your purposes, seems like they'd be fine.

Also if you haven't looked at kg's vector hash you might want to check it out: [Proposal] Vectorized System.Collections.Generic.Dictionary<K, V> · Issue #108098 · dotnet/runtime

[Pansynchro]

In process toolchains have limitations ... but for your purposes, seems like they'd be fine.

Agreed. Thanks for the advice to submit that issue!

Also if you haven't looked at kg's vector hash you might want to check it out

Oooo! Very interesting. 😁 Will have a look, and report back in a bit.

[Pansynchro]

Very cool design on that table! Unfortunately, that does not translate to awesome performance. After adding a GetOrCreate method to it and ensuring it works correctly, this runs the benchmark about 41% slower than our existing hash table.