2 ms·
All node-based trees with a small branching factor of 2-3 have the same performance problems on modern hardware, irrespective of the theoretical big-O algorithm
by jiggawatts 7y ago
All node-based trees with a small branching factor of 2-3 have the same performance problems on modern hardware, irrespective of the theoretical big-O algorithmic complexity.
They all have poor memory locality, high overheads, and high indirection. This is kryptonite for typical x86 or ARM CPUs. Unless you're only developing for some tiny embedded CPU with no cache, no branch predictor, and low frequency, such algorithms belong in the dustbin of history.
Practically always, you get better actual performance when using array-based structures such as hashtables, B-Trees, or the like.
Features like snapshotting can be implemented using virtual memory tricks, but is a gimmick rarely used outside of pure functional languages. You might find that simply copying an array when needed for a snapshot is faster than a fancy tree with sharing as a native capability. The exception would be certain dynamic programming scenarios where cloning is very common.
- afc 7y agoThank you for your reply. Interesting points. I guess I'll implement an analogous immutable B-Tree structure and run some benchmarks. I suspect you're probably right. I'll probably experiment with different branching factors and tree sizes. I rely a lot on the trivial (i.e., zero cost) snapshotting for feeding work to background threads. For my workload, having to do deep copies constantly would be prohibitively expensive (and I'd rather not deal with the complexity of explicit locking). That said, I'm now curious to see whether using immutable B-Trees will yield significantly better performance. I suspect they likely will. Exciting. :-) Thanks again!
- magicalhippo 7y agoThe traditional ZFS implementation(s) use AVL trees as the in-memory data structure for allocating space (ie finding free disk space). However the performance limitations of them have started to show, so there's been work done to switch to B-trees[1]. [1]: https://www.youtube.com/watch?v=LZpaTGNvalE https://www.youtube.com/watch?v=LZpaTGNvalE