Skimming through, I didn't see any discussion of AA trees which I have seen discussed as similar to red black trees but simpler to implement and have been interested in exploring for learning purposes. Any reason you didn't look specifically at AA trees, or were they covered somewhere that I missed?
Exploring the design space of binary search trees
11–20 of 31 posts
Re: Exploring the design space of binary search trees
#12Empty page with noscript. And with Javascript enabled just text!
This is tragic! Supporting noscript was a primary design goal but I forgot to only enable the knuth/plass justification in print media. The math expressions I'm moving to build time now. So sorry.
Re: Exploring the design space of binary search trees
#13Skimming through, I didn't see any discussion of AA trees which I have seen discussed as similar to red black trees but simpler to implement and have been interested in exploring for learning purposes. Any reason you didn't look specifically at AA trees, or were they covered somewhere that I missed?
You are correct, they have not been covered yet. I've added a note in the "work in progress" section.
There are also LLRB trees that would be interesting to see compared within this framework. All the red-black trees are implemented as rank-balanced trees, so there is no concept of "color" exactly, but the authors do mention the left-leaning 2-3 rule and the left-leaning red-black rule -- I just haven't implemented those yet.
See Pg. 5 of https://citeseerx.ist.psu.edu/document?type=pdf&doi=52330eed...
Re: Exploring the design space of binary search trees
#14Empty page with noscript. And with Javascript enabled just text!
This has now been fixed, thank you for reminding me.
Re: Exploring the design space of binary search trees
#15This looks like a thorough treatment of the subject. But my intuition is that B-trees are better than BSTs in almost every context. A good B-tree implementation is more cache-friendly, so faster to insert, delete, traverse. In my previous job I used to replace STL map uses with a btree implementation. It was always faster.
That is true, but in a persistent setting they likely also copy more data, and iterator invalidation might be a concern in some cases when moving values around within a B-tree node. The motivation was not really to come up with the best tree structure or to even consider memory hierarchy at all. Instead, within just the scope of binary search trees specifically, what cool things might we uncover by taking a closer lo…
> caches so large and advanced that the best practices of today might not apply all the same.
All trends are going in the wrong direction for binary trees to ever become useful again, and some of those limits are physics, not design.
- Branch predictors hate binary trees.
- CPU pipelines hate pointer chasing.
- Larger caches work less efficiently with binary trees than alternatives, such as "cache-oblivious" algorithms.
- Operations wasted per cache-miss due to memory latency has been going up, not down.
Etc...
> even consider memory hierarchy at all.
There's an often overlooked physics aspect here: physical memory requires physical space. As you add "N" bytes of memory, the layout of the circuits needs to expand into space. If deployed in a flat plane as is done typically, then this is a shape with radius roughly proportional to √N. For a space-filling volumetric design, at best it is ∛N.
Access to a piece of data requires a round-trip that takes time proportional to the distance taken through the computer. This is a simple consequence of the speed of light.
This means that unpredictable or random memory access time scales as ∛N to √N, not the constant "1" as typically assumed in big O analysis!
This is inescapable for computers made from physical components instead of pencil & paper abstractions.
If you add in this additional term, a lot of algorithms traditionally considered to be efficient suddenly look much worse. Conversely, algorithms preferred by developers with a knack for performance tuning don't get such a big penalty.
Re: Exploring the design space of binary search trees
#16If you'd like to get more attention from academics, you could try submitting a journal paper of the work. The ACM Computing Surveys journal may be a good venue: https://dl.acm.org/journal/csur
Re: Exploring the design space of binary search trees
#17Earlier quoted context omitted.
That is true, but in a persistent setting they likely also copy more data, and iterator invalidation might be a concern in some cases when moving values around within a B-tree node. The motivation was not really to come up with the best tree structure or to even consider memory hierarchy at all. Instead, within just the scope of binary search trees specifically, what cool things might we uncover by taking a closer lo…
> caches so large and advanced that the best practices of today might not apply all the same. All trends are going in the wrong direction for binary trees to ever become useful again, and some of those limits are physics , not design. - Branch predictors hate binary trees. - CPU pipelines hate pointer chasing. - Larger caches work less efficiently with binary trees than alternatives, such as "cache-oblivious" algorit…
I would not disregard that direction. Architectures that do well on pointer chasing have been attempted in the past (e.g. Cray XMT) and are cropping up in prototypes (PIUMA https://arxiv.org/abs/2010.06277) and startups. The caveat is that latency is hidden with massive amounts of parallelism.
edit: To be clear, I agree with the sentiment that the paper abstract machine models are inadequate in most practical cases. There are workloads where you're dealing with asymptotically large datasets, such as genome assembly and analysis. Even there, the RAM model is abstracting away the bottlenecks of modern computer systems.
Re: Exploring the design space of binary search trees
#18Earlier quoted context omitted.
That is true, but in a persistent setting they likely also copy more data, and iterator invalidation might be a concern in some cases when moving values around within a B-tree node. The motivation was not really to come up with the best tree structure or to even consider memory hierarchy at all. Instead, within just the scope of binary search trees specifically, what cool things might we uncover by taking a closer lo…
> caches so large and advanced that the best practices of today might not apply all the same. All trends are going in the wrong direction for binary trees to ever become useful again, and some of those limits are physics , not design. - Branch predictors hate binary trees. - CPU pipelines hate pointer chasing. - Larger caches work less efficiently with binary trees than alternatives, such as "cache-oblivious" algorit…
Interesting idea. I'm not confident it holds, access time to memory is often described as some count of cycles. E.g. 3 cycles to L1, some number of hundreds to somewhere else in the hierarchy.
Memory also positioned at some distance from the CPU (or whatever silicon is doing the arithmetic), where copying from one place to another involves copying into and then back out of the CPU.
More memory is slower, but within a given level of the cache hierarchy, I'd guess access time to any memory to be constant. How much variation is there in latency as a function of physical address, within say system level ddr4?
Re: Exploring the design space of binary search trees
#19Earlier quoted context omitted.
That is true, but in a persistent setting they likely also copy more data, and iterator invalidation might be a concern in some cases when moving values around within a B-tree node. The motivation was not really to come up with the best tree structure or to even consider memory hierarchy at all. Instead, within just the scope of binary search trees specifically, what cool things might we uncover by taking a closer lo…
> caches so large and advanced that the best practices of today might not apply all the same. All trends are going in the wrong direction for binary trees to ever become useful again, and some of those limits are physics , not design. - Branch predictors hate binary trees. - CPU pipelines hate pointer chasing. - Larger caches work less efficiently with binary trees than alternatives, such as "cache-oblivious" algorit…
What if some future technology or material breakthrough provides a sort of self-adjusting liquid memory that provides true constant time access to any address? I'm not being entirely serious of course, as I dream about sequences across nodes on planets through other solar systems.
Focusing on fundamental algorithms in the abstract provides a fun playground to explore and learn and teach, before you learn about memory hierarchy when all your hopes and dreams of the ideal data structure fades away.
I don't think there is any time wasted exploring the fundamental. Who knows what technology might see renaissance in the future as hardware continues to change. Analog computers, binary search trees, who knows.
It's fun to dream and take a break from reality sometimes, digging deep into a simple concept with a rich design space and complex analysis.
Re: Exploring the design space of binary search trees
#20No one else has mentioned it, so I'll be the first. I love the typography and layout. Looks like a proper book. I'll definitely be coming back to this for future reference for style and layout