Hacker News Reader

Comment by amluto | Hacker News Reader

Binary search is a pretty bad algorithm. Sure, it runs in O(log n) time and it's more or less the best you can do to solve the general problem of finding something in a sorted list, but that does not mean it's a good way to create an immutable list of things that can be searched using comparisons.

In particular, binary search has awful cache locality. Until you get very close to your target, you are essentially hitting a random cache line (and maybe even a random page for large lists) for every comparison. This is bad. A B-tree-like structure that is never modified is very easy to make, and it will be much faster.

This came up with the ORC unwinder in Linux. We got something like a 4x speedup by changing from binary search to something a bit more clever to find unwind entries in the table.

View on HN

> In particular, binary search has awful cache locality.

That makes me think of an idea which I'm certain can't be original, but I can't think of the jargon for what it's called.

Suppose you have a fixed-length sorted array, and its binary-search can be visualized as a tree. Traverse that tree in level-order and pop it into a helper-array, arranged much like a heap: The midpoint is first and all left and right children are proceed from there at offsets that you can predict.

So the original array [A,B,C,D,E,F,G] has a data-structure for searching of [(D,3), (B,1), (F,5), (A,0), (C,2), (E,4), (G,6)]

While the high-indexed items will get spread out, the most common and sequential activity occurs all together near the lower indexes, minimizing large jumps. Since each entry has the original index stored, you can always switch back to the initial array when a different strategy (e.g. linear scan) becomes preferable.

Here is a writeup of the idea and some numbers.

http://bannalia.blogspot.com/2015/06/cache-friendly-binary-s...

Take a look at ARRAY LAYOUTS FOR COMPARISON-BASED SEARCHING. TL;DR there are schemes like this called "Eytzinger" and "van Emde Boas".

https://arxiv.org/ftp/arxiv/papers/1509/1509.05053.pdf

The topic of arranging keys like this within index pages (or maybe elsewhere) has come up on the pgsql-hackers mailing list before:

https://www.postgresql.org/message-id/flat/3B774C9E-01E8-46A...

Yes this is a nice trick. You can use all kinds of implicit search trees for this. See also my comment to a sibling with a link to a paper evaluating the performance of this, including the time it takes to compute that new layout: https://news.ycombinator.com/item?id=18881938

Actually cache locality might not be quite as bad as you think: the first few levels of the "pivot tree" will definitely be cached (although wasting a whole cache line on a single element is certainly not optimal use of the cache). To get better locality one could use a breadth-first layout of the implicit binary search tree, like a binary heap. One compromise could be to duplicate the first few levels of pivots at the beginning of the array, in breadth-first order, while storing the array in the usual sorted order. See "Array Layouts for Comparison-Based Search" for more details.

I came across this last night (http://dtrace.org/blogs/bmc/2018/09/28/the-relative-performa...) and went down the rabbit hole of Rust and its BTreeSet (http://cglab.ca/~abeinges/blah/rust-btree-case/). They came to a very similar conclusion. It all makes me wonder if there's low hanging fruit in a lot of languages/libraries to simply swap out red black trees for B-trees (though I'm guessing the higher constant time cost of B-trees would make it necessary to swap between tree implementations for a truly general case).

> It all makes me wonder if there's low hanging fruit in a lot of languages/libraries to simply swap out red black trees for B-trees

I think the short answer is "yes." Although maybe not quite as low hanging as we'd hope.

The nice thing about RB trees and Splay trees is that they are embeddable at relatively low memory bloat (3 pointers and a color for RB, and 2 pointers for splay) to the object they link into an ordered index.

Embedding list and tree pointers has a variety of advantages for operating system and similar code:

1. The memory is already allocated; you can avoid allocating memory in paths with locks held, which prevents deadlocks / hangs.

2. You can put a single object on multiple lists or indices. I.e., maybe your cached file page is on a eligible-for-reclamation linked list but also indexed by offset into the file (to simplify somewhat).

B-trees are not as trivially embeddable in the same way. As wikipedia points out[0], RB-trees are a kind of low-order B-tree, and it's possible to increase the width to something more like a traditional database B-tree. But this increases the overhead of embedding tree metadata in your object.

I suspect that you're right — dropping in a B-tree of branching factor >2 in place of existing BSTs would improve performance for some indices on some platforms, at the cost of additional memory. But I suspect evaluating where it makes sense would require some profiling or insight into a particular use case. I don't think universal replacement is a slam dunk, at least in low level systems code.

It makes a lot of sense for Rust because their lifetime checker basically prevents the kind of multi-list ownership I've described above. It may make sense for other high level languages for the same reason.

[0]: https://en.wikipedia.org/wiki/Red%E2%80%93black_tree#Analogy...

My friend is working on the paper which shows how to do intrusive data structure (I think that's what you meant by multi-list ownership) in Rust. I've seen the draft, and it's surprising and beautiful. Stay tuned...

Well, there is this (requires nightly): https://github.com/Amanieu/intrusive-rs

Of course, my friends (and I) already know about this and the paper improves upon it.

Yes, intrusive data structure is exactly the correct word for it. I was trying to remember it but couldn't recall it for my comment. Thanks! I'm curious to see how it will work in Rust.

Yes, you probably shouldn't use any kind of binary trees. This has been a sort of open secret for years. I first learned about it from phk(Poul-Henning Kamp)'s 2010 article, "You're doing it wrong". See http://phk.freebsd.dk/B-Heap/queue.html.

AKA how to reinvent cache-oblivious data structures, poorly.

Yes, I don't think the article is very good, but it was where I first learned whole IO complexity thing, and I think it was widely read and effective in popularizing the idea.

What would you recommend as a good book on Virtual Memory ? I learned about the insides of computers during school days more than 20 yers ago and I would like to refresh/update my knowledge.

That's exactly what phk wrote about: theoretically perfect algorithms such as binary search are never practically perfect, because they never account for real life things like disk latency and memory pressure. This has lead to developers come up with inefficient softwares.

This is uninformed. The problem is plain binary search over ordered array.

Binary search with heap order is cache friendly and much faster. And can speed up with SIMD. Like Intel’s FAST algorithm.

Very true. Here's a paper from last year that measures the performance of searches on several implicit search tree layouts on CPU and GPU: https://algoparc.ics.hawaii.edu/pubs/18-ipdps.pdf. You can see the results in figures 7 and 9 (pages 9 and 10).

tl;dr: in an array of 500 million elements, if you're doing more than ~5 million queries (1%), it pays off to spend the time to construct a more efficient representation of the data and search on that. On a GPU, you need ~15 million queries (3%).

Reply on news.ycombinator.com