5 ms·

If you search for "reciprocal throughput" in the article, the author did do another benchmark with dependencies to compare "real latency".

• ot 5y ago
  Thanks! 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 ago
    By the time I realized it needs correcting, I was already like 15 graphs in and really didn't want to remake them.
    • _0ffh 5y ago
      Somewhat 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 ago
      If 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 ago
        That's because it is in bytes, representing cache sizes. But I agree, a clarification is needed