[jackschultz]

Great stuff. We get told O notation is what matters for data structures / algorithms, but improvements low level with memory and storage with things like rust is much more where improves can be made. These types of tricks for anctual run times are so valuable, and interesting to follow.

[curiouscoding]

Ohh yeah, don't get me started in big-O...

It was great while computers were not really a thing yet, but these days it's often so meaningless. We see papers with 2x speedup with a lot of novel algorithmic stuff that sell better than 10x speedup just by exploiting CPUs to the fullest.

Even myself I kinda think theoretical contributions are cooler, and we really need to get rid of that (slightly exaggerating).

[ryao]

Your article led me to wonder if our b-trees would be faster if I switched the intra node operations to use Eytzinger ordered arrays:

https://github.com/openzfs/zfs/commit/677c6f8457943fe5b56d7a...

There are two ways to look at this Big O wise. One is that insertions and deletions would be asymptomatically faster since memmove() is a linear operation while bubble up/down are logarithmic operations. Look ups would not be any different asymptotically, but the constant factor might improve from being able to do prefetch. The other way is that the N is bounded, such that it is all O(1) and the difference is how big the constant factor is.

I imagine I could implement it and benchmark it. However, my intuition is that the end result have lookups be marginally faster to the point of splitting hairs while insertions and deletions would be slower. While memmove() is a technically a linear time operation, it is a sequential operation that has a very low constant factor. The bubble up and bubble down operations needed to do insertions and deletions in a Eytzinger ordered array are technically random access, which has a higher constant factor. At some point, the Eytzinger ordered array operations should win, but that point is likely well beyond the size of a b-tree node.

My reason for saying this is to say that Big O notation still matters, but understanding when the constant factor is significant is important.

[jackschultz]

Same with async and throwing threads at a problem. People love do those and think it's the right answer, but you can do a ton with smarter memory management and actually looking at what the code is doing lower level rather than abstractions.

Video about this that was very interesting to follow and somewhat related to what you're doing: https://www.youtube.com/watch?v=5rb0vvJ7NCY

[Andys]

You're really just exploiting hidden O(?) implementations inside the CPU, so it still applies, just less visibly.

[ryao]

He is improving the constant factor in big O notation. University algorithm classes tend to ignore cases where the constant factor difference is significant enough to favor a asymptomatically slower algorithm. Matrix multiplication is the quintessential example of this, since a good implementation of the O(n^3) algorithm will outperform asymptotically faster algorithms, such as the famous O(n^2 * log(n) * log(log(n))) one that uses the FFT. At least, it outperforms it on matrix multiplications people actually do in practice.