4 ms·
Very interesting post. The best results I knew of for static ordered search [1] were from the 2015 Khuong-Morin paper [2], which is not cited in the article but
by ot 5y ago
Very interesting post. The best results I knew of for static ordered search [1] were from the 2015 Khuong-Morin paper [2], which is not cited in the article but the author cites it in the previous post, and in their benchmarks Eytzinger+prefeching performed best. The improvement on top of that is pretty impressive. At the larger sizes, the latencies are basically 1 cache miss (~50ns).
However, I have some comment on the benchmark, the iterations have no loop dependency on the previous result, so the CPU is allowed to pipeline some loads. This is rarely representative of real workloads, where the key being searched comes from other computations, so this is more a measure of highest possible reciprocal throughput than actual latency. Would be interesting to see what happens if they make the key being searched a function of the result of the previous lookup. (EDIT: as gfd below points out, the article actually discusses this!)
Also some of the tricks only work for 32-bit keys, which allow the vectorized search in nodes. For larger keys, different layouts may still be preferable.
[1] Ordered search is when you need to look up keys that are not in the dataset, and find predecessor/successor. If you only do exact lookups, a hashtable will almost certainly perform better, though it would require a bit more space.
[2] https://arxiv.org/pdf/1509.05053.pdf https://arxiv.org/pdf/1509.05053.pdf
- gfd 5y agoIf you search for "reciprocal throughput" in the article, the author did do another benchmark with dependencies to compare "real latency".
- ot 5y agoThanks! You're right, I missed it because it was in the section "Comparison with std::lower_bound" and I thought there would be just some gloating :) Most published data structure benchmarks have this pitfall, and don't discuss it, then when trying to measure the improvements after plugging into a real workload it turns out that the microbenchmark was not predictive. When I see latencies that top out at 50ns when they clearly have to make more than one causal load I immediately get skeptical. This is one of the very few articles I've seen that clearly explains this, which makes it even more excellent. I only wish it didn't label the other graphs "Latency" too, or at least put an asterisk there.
- sereja 5y agoBy the time I realized it needs correcting, I was already like 15 graphs in and really didn't want to remake them.
- _0ffh 5y agoSomewhat understandable. As I sometimes stumble over comparable situations I have made it a habit to never just make any graphs, I always make a script that makes the graphs. That makes it easy and quick to go back and just re-generate them if you later change your mind about some detail.
- gfd 5y agoIf you ever get around to updating the graphs, there's also a bug with where you're drawing the vertical dotted lines (for example I expect 4M to be at 2^22)
- sereja 5y agoThat's because it is in bytes, representing cache sizes. But I agree, a clarification is needed