3 ms·
This article demonstrates why performance intensive software systems (like database engines) implement many of their own data structures and algorithms, often n
by jandrewrogers 12y ago
This article demonstrates why performance intensive software systems (like database engines) implement many of their own data structures and algorithms, often not even reusing those implementations internally, and avoid standard libraries for many use cases. The suboptimality of any particular use case can be quite large relative to a purpose-built implementation for that spot in the software. It is a lot more work but it can also dramatically improve real-world throughput and variance because you have visibility into exactly what the access pattern will be.
If you measure these things at large scales you will see surprisingly smooth and regular constructive interference patterns that emerge from the interaction of boundary constants in the software and hardware. This is a difficult type of variance to eliminate. That obvious solution is to inject pseudo-randomization into scheduling and boundary constants. This dampens the patterns but even if you turn the randomization knobs pretty high the patterns do not go away! And you can't go too crazy because that randomization has its own performance costs as the algorithms move further away from their theoretical optimum.
Some latency hiding computing architectures, like barrel processors, actually hash memory addressing in hardware to eliminate locality so that you do not see these kinds of locality and aliasing effects. However, most modern CPUs are specifically designed to exploit locality so this technique generalizes poorly.