Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Exploring the design space of binary search trees

rtheunissen.github.io

Post reply on HN
Print view View original

21–30 of 31 posts

Re: Exploring the design space of binary search trees

#21

Post by emmanueloga_ »

Some feedback on readability: the article utilizes the term "logarithmic weight-balance" 6 times without explaining what it is (and several more times after). On the 7th mention, it links to a paper: "Frias[40] published top-down logarithmic weight-balance trees in 2005, under advice from Roura." But the referenced paper doesn't mention logarithmic weight-balance even once, I think [40] calls them "Logarithmic binary search trees", and links to "Roura S., 2001, A new method for balancing binary search trees".

After reading the last paragraph:

"Any current red-black tree implementation in practice can be replaced by a logarithmic weight-balance tree to achieve better balance, better performance, and get positional access as a bonus, all with a simpler algorithm."

... it is clear the article is advocating for these, and the title should hence be something like "Advantages of logarithmic weight-balanced Trees over other balanced trees", or something like that, immediately followed by an explanation of what these are, and what other people call them.

The repository linked at the top includes a lot of stuff and makes it hard to find a logarithmic weight-balance tree implementation, lost in all other kinds of trees in there. Would be helpful to see a separated logarithmic weight-balanced tree go module for people looking forward studying its source code.

40: L. Frias, Extending STL maps using LBSTs, 2005.

Re: Exploring the design space of binary search trees

#22

Post by jiggawatts »

JonChesterfield wrote: post #18
jiggawatts wrote: post #15

Earlier quoted context omitted.

> 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…

The variation is not smooth in real systems, but just like you’ve noticed: it’s right there in the L1->L2->L3->RAM->Disk hierarchy.

Each one is physically bigger, further away, and higher latency.

We might one day have 1 PB memory systems with 1 TB of on-chip cache… but the larger memory will still need more space and be further away…

Re: Exploring the design space of binary search trees

#23

Post by rtheunissen »

emmanueloga_ wrote: post #21

Some feedback on readability: the article utilizes the term "logarithmic weight-balance" 6 times without explaining what it is (and several more times after). On the 7th mention, it links to a paper: "Frias[40] published top-down logarithmic weight-balance trees in 2005, under advice from Roura." But the referenced paper doesn't mention logarithmic weight-balance even once, I think [40] calls them "Logarithmic binary…

Part 2 defines that "a node is logarithmically weight-balanced if the binary log of the weights of its subtrees differ by no more than 1" and references Roura directly there. Roura uses the acronym LBST, which corresponds to the file trees/lbst.go in the repository. I hoped that this would be intuitive enough to follow.

They are definitely part of the class of weight-balanced trees, using the exact same algorithms as BB[a] trees, which are the classic weight-balanced trees.

When I started this project, it was unclear that the conclusion would advocate for them. In fact, I did not even know about them when I started. My intention was to focus on the exploration more than the conclusion. I'm in the process of writing another conclusion around relaxed balance as a concept, which could just as well be the title.

I appreciate this feedback very much. Perhaps the paper could mention specifically that Roura and Frias call the logarithmic binary search trees, abbreviated as LBST. The repository's README could also provide an index to each tree in the source.

For reference: the weight-balanced algorithms can be found in [1], [2] and [3]. The logarithmic weight-balance rules are defined in [4].

[1] https://github.com/rtheunissen/bst/blob/main/trees/wbst_bott...

[2] https://github.com/rtheunissen/bst/blob/main/trees/wbst_topd...

[3] https://github.com/rtheunissen/bst/blob/main/trees/wbst_rela...

[4] https://github.com/rtheunissen/bst/blob/main/trees/lbst.go

Re: Exploring the design space of binary search trees

#24

Post by emmanueloga_ »

rtheunissen wrote: post #23
emmanueloga_ wrote: post #21

Some feedback on readability: the article utilizes the term "logarithmic weight-balance" 6 times without explaining what it is (and several more times after). On the 7th mention, it links to a paper: "Frias[40] published top-down logarithmic weight-balance trees in 2005, under advice from Roura." But the referenced paper doesn't mention logarithmic weight-balance even once, I think [40] calls them "Logarithmic binary…

Part 2 defines that "a node is logarithmically weight-balanced if the binary log of the weights of its subtrees differ by no more than 1" and references Roura directly there. Roura uses the acronym LBST, which corresponds to the file trees/lbst.go in the repository. I hoped that this would be intuitive enough to follow. They are definitely part of the class of weight-balanced trees, using the exact same algorithms as…

I'm glad it is helpful! Why not just calling them LBSTs as the papers do? Catchier than LWBT I think... (gotta think of the marketing side too) :-p

Thanks for the extra pointers!

Re: Exploring the design space of binary search trees

#25

Post by rtheunissen »

emmanueloga_ wrote: post #24
rtheunissen wrote: post #23

Earlier quoted context omitted.

Part 2 defines that "a node is logarithmically weight-balanced if the binary log of the weights of its subtrees differ by no more than 1" and references Roura directly there. Roura uses the acronym LBST, which corresponds to the file trees/lbst.go in the repository. I hoped that this would be intuitive enough to follow. They are definitely part of the class of weight-balanced trees, using the exact same algorithms as…

I'm glad it is helpful! Why not just calling them LBSTs as the papers do? Catchier than LWBT I think... (gotta think of the marketing side too) :-p Thanks for the extra pointers!

Haha true, that's a good point. There's also WAVL and RAVL for weak AVL and relaxed AVL, but no equivalent acronyms for the red-black variants. RRB is the same as Relaxed Radix-Balanced! In my notes I found it easier to avoid acronyms, and then "logarithmic binary search tree" became ambiguous because "aren't they all logarithmic (in height and complexity)?" I found that grouping them as part of the weight-balanced class of trees is the most intuitive, and I wish the original paper did the same, but that's okay.

What I'll do for now is mention specifically that the literature refer to them as LBSTs, and I'll add an index to each tree in the repository to make them easier to navigate. Thanks again.

Re: Exploring the design space of binary search trees

#26

Post by rtheunissen »

frfl wrote: post #20

No 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

I was inspired by Stick & Rudder, which is a very easy book to recommend to most people in this community. I'm sure I'll keep coming back to make adjustments, but the end result is what I hoped to achieve.

The Charter font was a particularly good find as part of the "transitional" system font stack. I'll definitely use it for other projects in the future.

Re: Exploring the design space of binary search trees

#27

Post by frfl »

rtheunissen wrote: post #26
frfl wrote: post #20

No 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

I was inspired by Stick & Rudder , which is a very easy book to recommend to most people in this community. I'm sure I'll keep coming back to make adjustments, but the end result is what I hoped to achieve. The Charter font was a particularly good find as part of the "transitional" system font stack. I'll definitely use it for other projects in the future.

Really one of the most beautiful pages on the web. A prime example of what content on the web could look like. No bloat, fast, beautiful typography, SVG graphics not unnecessary jpegs/pngs.

You have my respect for making this and setting an example which I will definitely strive towards moving forward for my own stuff.

Re: Exploring the design space of binary search trees

#28

Post by cb321 »

If you like this article then you might also be interested in: https://github.com/c-blake/bst

It's ANSI C with a bespoke macro generics system not Go, does not cover as many balancing rules, and is not written up as nicely. It does do something only weakly represented in your Go impls, AFAICT - "binary symmetry" - the reflection about left-right intrinsic to most ideas in this area. (Mehlhorn has a book that does this, but that is the only other source I know.) It also has API considerations like seek-edit separation and how to handle in-tree duplicate keys (FIFO/LIFO/etc. as opposed to values which are also collections).

Also, Re: B-trees among several comments here - edit heavy B-trees with very large nodes (driven by IO bandwidth-delay products) need some "mini-scalable" structure for their nodes since shifting (on average) half the entries can cost. That mini-scale could be another B-tree or it could be a binary search tree, perhaps adjusted to have 2-byte sized pointers into the little arena that is a node if 64Knode is enough. I once heard Sybase (now Microsoft SQL Server?) used skip lists. Anyway, this may be a remaining use case for binary trees even in the presence of a B-tree.

Re: Exploring the design space of binary search trees

#29

Post by rtheunissen »

cb321 wrote: post #28

If you like this article then you might also be interested in: https://github.com/c-blake/bst It's ANSI C with a bespoke macro generics system not Go, does not cover as many balancing rules, and is not written up as nicely. It does do something only weakly represented in your Go impls, AFAICT - "binary symmetry" - the reflection about left-right intrinsic to most ideas in this area. (Mehlhorn has a book that does thi…

Thank you for sharing this resource, I was not aware of it. I am happy to see the inclusion of LBSTs there too.

Re: binary symmetry, if I'm understanding correctly, another author that makes use of the symmetry is Ben Pfaff in libavl [1]. At the top of [2], which seems a bit misplaced now, I wrote:

>A choice was made to not unify the symmetric cases using the direction-based technique of Ben Pfaff and others because it makes the logic more difficult to follow even though there would be less code overall.

The choice of Go was to provide implementations that are both reliable to benchmark (though not as robust as C or Rust for example) but also easy to read. I would like to further reduce abstraction by decomposing common parts such that all the strategies are "one-file" references. This is then effectively the opposite of what the macro-based implementation achieves. Both have value, of course.

[1] https://adtinfo.org/libavl.html/BST-Node-Structure.html

[2] https://github.com/rtheunissen/bst/blob/main/trees/avl_botto...

Re: Exploring the design space of binary search trees

#30

Post by cb321 »

rtheunissen wrote: post #29
cb321 wrote: post #28

If you like this article then you might also be interested in: https://github.com/c-blake/bst It's ANSI C with a bespoke macro generics system not Go, does not cover as many balancing rules, and is not written up as nicely. It does do something only weakly represented in your Go impls, AFAICT - "binary symmetry" - the reflection about left-right intrinsic to most ideas in this area. (Mehlhorn has a book that does thi…

Thank you for sharing this resource, I was not aware of it. I am happy to see the inclusion of LBSTs there too. Re: binary symmetry, if I'm understanding correctly, another author that makes use of the symmetry is Ben Pfaff in libavl [1]. At the top of [2], which seems a bit misplaced now, I wrote: >A choice was made to not unify the symmetric cases using the direction-based technique of Ben Pfaff and others because…

LBSTs are pretty rare, too. :) Re: symmetry reasoning troubles, another benefit is that it enforces the symmetry algebraically rather than relying on code edits maintaining it (& multiplying it). As to DRY vs. reducing abstraction aka explicitness, I favor the former but, yeah, people are indeed passionate in both directions. E.g., see Java. :-)

Along that abstraction line, it perhaps bears emphasizing that it is not all subjective. E.g., being able to have 1-byte or 2-byte pointers can really shrink the per node space overhead from 16B to 2..4B, possibly total node size from 20B to 8B for a 4B payload (like a float32) or 2.5x overall space saving, an objective and interesting amount that might well keep a working set resident in faster memory. Indeed, even allowing any number of bits like 20 bits*2 is thinkable. Of course, that limits the number of nodes to the address space of the numbers, but that can be ok (such as inside 1 B-tree node or when populations are elsewise easily bounded). But then you pretty much must abstract "allocation/dereferencing" as done in that generic C package or analogously. (Others elsethread were discussing memory overheads vs. B-trees, but not at this API level and more related to tree/indirection depth in uncached worst cases.)

Anyway, I just thought that package might provide color along some other less traveled roads in this space..was not trying to direct or redirect your own effort. It's a nice write up of what you have so far.

Post reply on HN