4 ms·
The article looks great but a doubling of speed actually seems kind of disappointing (What I'd like to see is would something like "big O" improvement). I have
by joe_the_user 9y ago
The article looks great but a doubling of speed actually seems kind of disappointing (What I'd like to see is would something like "big O" improvement).
I have been investigating cache-oblivious data structures for a while. They're impressive, complex and a bit difficult to fathom (for a cache-oblivious tree, you have to consider both relational structure created by pointers and the layout of all the pointer in memory - the article seems like it gives a nice overview compared to academic articles I've looked at).
The thing is, in most of the large applications I've tried to optimize, you could squeeze several speed doublings out of fairly easy inner-loop rewrites as soon as you started profiling the app. After that, you got more marginal results from optimizing this and that. Consider; if 25% of the time is spent retrieving data, a halving of time to do this results in a 12.5% increase in performance. Is that 12.5% worth the complexity of implementing a cache oblivious structure? Even if you application is a full database, I'm not sure if the trade-offs are worth it.
- rusbus 9y agoIt actually may be an order as you suggest -- the difference gets bigger as the tree gets bigger. I just stopped benchmarking at about 300MB of data where the perf was almost 2x. If you run it on a 1GB tree it might be 4x
- joe_the_user 9y agoSure, maybe. The problem is that doesn't seem enough to necessarily compensate for the added complexity. The thing is a self-balancing binary tree is so much faster than the alternatives for large chunks of data that you really have to use it. Here, I'm not so sure. Anyway, thinking about this lead me to this discussion about fractal trees and LSM trees. https://www.quora.com/What-are-the-major-differences-between-LSM-trees-used-in-BigTable-etc-and-Fractal-Trees-used-in-TokuDB?share=1 https://www.quora.com/What-are-the-major-differences-between... Another question here is how will this play out if the high-performance DB is going to be moving to a GPU where cache levels and scans would be quite different.
- dspillett 9y ago> Sure, maybe. The problem is that doesn't seem enough to necessarily compensate for the added complexity. A 50% improvement could be massively significant if processing a huge data-set on thousands of nodes and it is still taking days/weeks/more of wall-clock time. Given the choice between waiting longer, buying more computer power, or using a more complex algorithm, the best of those choices will depend a lot on the circumstances of the project. If it is a one-off then waiting or paying for power will likely win out. Of course in some circumstances paying for more power won't help: you can only get so much out of each node and for some processes factors like interconnect throughput & latency might eat into the ROI significantly as the number of nodes grow. In some cases a 10% or less boost might be worth the extra complexity. And if the algorithm can be generalised and packages as a library, you aren't actually having to deal with that complexity each time the method is useful.
- vvanders 9y agoCache friendly algorithms tend to be on the order of 10-50x speed improvement so they're definitely worth it, the problem is that once you've already built your app you've already locked yourself into an architecture that can't be changed enough to take advantage of them. Dig up some of posts around "Data oriented design" from the gamedev space if you want to see it done proper.
- chongli 9y agoThe advantage of squeezing more performance out of data structures is that you can package them up in standard libraries and provide that performance for potentially thousands of applications out there. Inner-loop rewrites are great but they are tied to a specific application.