8 ms·

Binary Trees are optimal except when they’re not

75 points by jjgreen 5y ago

riggsdk 5y ago
Basically algorithmic complexity analysis often ignores the cost of accessing data because the underlying storage is sometimes unknown - be it in memory, on a spinning disc or on magnetic tape. Unfortunately that gives suboptimal algorithms because that basic practically is ignored. You then end up with a bunch of algorithms that look worse “on paper” but still outperforms the theoretically optimal ones. Often the number of items is also ignored. If you want to implement a set-like feature but you’ll be using less than X elements, you can often get better performance just using a linear search through an array than use a full fledged hashed set.
- jsmith45 5y ago
  Agreed. There are plenty of cases where an asymptotically "worse" algorithm performs better than a "better" one for all practical sizes. Like it is very very much possible that the asymptotically "better" algorithms have coeffcients so high that the break even point takes like week or more of computation. There are not many programs where users will tolerate using it with so much data that operations take that long.
- munificent 5y ago
  This reads like a criticism of complexity analysis, but really you're just describing it. By definition and by design, algorithmic complexity analysis only shows you how an algorithm behaves asymptotically. That means it's often not the right tool for selecting an algorithm with optimal real-world performance, but I think that's less a fault of the tool than it is a fault of the tool selector. Saying, "complexity analysis ignores constant factors and small-data size performance" is sort of like saying "hammers ignore the threading on screws".
  - Retric 5y ago
    Saying something is a poor fit in the real world is a perfectly valid criticism. Arguably complexity analysis is such a poor fit programmers should never actually use it, but vastly simplifying problems can make for a good first approximation.
    - alex_smart 5y ago
      Saying "why do we teach programmers complexity analysis in a word RAM model, there are no idealized RAM machines that behave like that in the real world" is no better than saying "why do we teach people Euclidean geometry, there are no such idealized geometrical systems in the real world". The point is that: 1. The analysis is useful and instructive. 2. It teaches you how to analyse computing models, starting from a simple one, so that when you need to, you can build and analyse more complex models specific to your domain.
      - Retric 5y ago
        In the real world spacetime is very close to Euclidean geometry near earth. Complexity analysis on the other hand can be wrong by literal orders of magnitude. If carpenters needed to worry about the internal angles of a triangle a ding up to between 9,672 and 1.72 degrees then I think people would consider Euclidean geometry a waste of time, but 180 +/- 0.0000001 is fine.
        alex_smart 5y ago
        You are responding to an argument I never made. You don't teach children Euclidean because they would actually ever need to calculate the area of a triangle. You teach them geometry because it is a good exercise in working with logic, proofs and mathematical models. >Complexity analysis on the other hand can be wrong by literal orders of magnitude. Seeing how complexity analysis only applies to the asymptotic behavior of an algorithm, I don't even know how to make any semantic sense of that statement. It is not even wrong.
        Retric 5y ago
- MatteoFrigo 5y ago
  What you are saying may be a valid criticism of basic undergraduate algorithms courses, but it is a bit unfair as an absolute criticism of the field. There exists a huge literature that studies algorithms under various models of the memory hierarchy, and under various models of I/O. Even Knuth's venerable The Art of Computer Programming from 50 years ago studied the problem of optimal sorting assuming that the data is on tape and one has six tape drives available (for some value of six that I forgot).
  - svat 5y ago
    Not many people realize that the literature you mention is the field of "analysis of algorithms", which is a sub-field of (or, in practice, somewhat different from) computational complexity theory / theory of algorithms. Robert Sedgewick (CS professor at Princeton, and an early PhD student of Knuth) has a great book with Flajolet on Analysis of Algorithms [1], and in one of the lectures from his course [2] makes a distinction between the complexity analysis usually taught in basic undergraduate algorithms courses (he calls O-notation not the scientific method, in a certain context in the lecture) and AofA (which involves saying "Running time is ~aN^c" instead of saying "Running time is O(N^c)", and also actually measuring against real programs) — watch the video or read the slides; it's an interesting distinction. And the Purdue website [3] is even better at giving a sense of the field. [1]: https://aofa.cs.princeton.edu https://aofa.cs.princeton.edu [2]: https://aofa.cs.princeton.edu/online/slides/AA01-AofA.pdf https://aofa.cs.princeton.edu/online/slides/AA01-AofA.pdf / https://www.coursera.org/learn/analysis-of-algorithms/lecture/LAXjA/a-scientific-approach https://www.coursera.org/learn/analysis-of-algorithms/lectur... [3]: https://aofa.cs.purdue.edu https://aofa.cs.purdue.edu
- jjgreen 5y ago
  I recently had occasion to re-implement the R-tree structure [1] which I based on the original code by Guttman. There, each set of child nodes were stored in a (hard-coded 1k) page of memory, but there was a macro which allowed n sets of child-nodes in a page, but that value was set to 1. I assumed that this was an experiment which turned out to not work, hence the hard-coded 1 to disable it. As the code was nearing completion I experimented with values other than 1, and found a 3-fold increase in speed for a value of n=8 (IIRC) against a 4k memory page. It's always worth testing your assumptions :-) [1] http://soliton.vm.bytemark.co.uk/pub/jjg/en/code/librtree/ http://soliton.vm.bytemark.co.uk/pub/jjg/en/code/librtree/
valbaca 5y ago
Author seems to have just backed into rediscovering B-trees https://en.wikipedia.org/wiki/B-tree https://en.wikipedia.org/wiki/B-tree > To conclude, binary trees are optimal when we ignore the cost of accessing a node, but they aren’t when it becomes costly to access a node. When we access the nodes on disk, with a high cost, it becomes interesting to bundles many keys in a node, and we gave the optimal solution. However, the problem is often solved quite more directly. We just fit as many keys as possible in an I/O block. Disks operates on small blocks of (typically) 512 bytes, but file systems operate in somewhat larger, but fixed-sized blocks, something like 4 or 8k. A good strategy is therefore to fit as many keys as possible in that block, since even if the number of comparisons is large, it will still be faster than bringing that block into main memory.
- jwdunne 5y ago
  I didn’t get that impression. I got the impression the author knew full well what B-trees are and is alluding to them. The author’s other writings seem to show that they do indeed know of B-trees.
bob1029 5y ago
Skiplists are my favorite data structure. There are a few use cases that they can't satisfy, but for the typical memory-bound key-value store application, it's a very simple & effective approach. If you have to go to disk, a combination of: splay tree, batching and append-only log structure are your best bet.
- valbaca 5y ago
  I'm sure online resources abound...but do you have a favorite descriptor or implementation of them? Or a particular use-case?
  - bob1029 5y ago
    I've used indexed skiplist implementations in DIY database projects. The idea was to first build a super fast K/V store (i.e. to memory+disk), and then build skiplists on top of that for tying together collections of indexed data. The problem with skiplists is that they kinda suck when used directly with mutable block storage. There is no way to do incremental updates like with a splay tree where you can write just the diff (a modified sub-tree and a new root node) to the end of a contiguous log file.
- codr7 5y ago
  Links to efficient implementations would be much appreciated. I've played around with the idea but eventually settled on binary searched arrays for the small stuff and red/black trees for the rest. One thing that bothers me about skiplists is having a static number of levels, which will either be too few or too many for most situations.
  - bob1029 5y ago
    You can do probabilistic inserts which should ensure the # of levels scales appropriately with the quantity of data. The probability factor can be a simple constant or some linear function of the quantity and/or index #.
  - tsumnia 5y ago
cakoose 5y ago
Yup, ignoring the costs of memory/storage access (cache, main memory, disk) can hurt an algorithm's real-world performance. Laying your data out in chunks that match the memory/storage blocks sizes (cache line size, disk block size) can yield much better performance. And while having the algorithm be aware of the chunk sizes in every layer of your memory hierarchy is optimal, it can be inconvenient to get all that set up. But what's cool is that you can often lay your data out in a fractal-like pattern, and get pretty good performance no matter what the various chunk sizes are: https://en.wikipedia.org/wiki/Cache-oblivious_algorithm https://en.wikipedia.org/wiki/Cache-oblivious_algorithm
kazinator 5y ago
A binary search tree with string keys is just a compressed version of a binary tree with bit keys, which greatly reduces the number of nodes. E.g. this has three nodes: dog / \ ant fly But: ant -> 61 6E 74 -> 011000010110111001110100 dog -> 64 6f 67 -> 011001000110111101100111 fly -> 66 6C 79 -> 011001100110110001111001 Thus R / 0 \ 1 \ 1 / 0 / 0 / \ ,---' `-------. / \ / \ 0 1 / / \ / ,-------' `---. / / \ 0 0 1 \ / / 1 0 0 / / / 0 0 0 \ \ \ 1 1 1 \ \ \ 1 1 1 / / / 0 0 0 \ \ \ 1 1 1 \ \ \ 1 1 1 \ \ / 1 1 0 / \ / 0 1 0 / / / 0 0 0 \ \ \ 1 1 1 \ \ \ 1 1 1 \ / \ 1 0 1 / / \ 0 0 1 \ \ / 1 1 0 / \ / 0 1 0 / \ \ 0 1 1 (ant) (dog) (fly) :)
crazygringo 5y ago
> The spaceship operator, <=> is C++20’s version of C’s old timey qsort comparison function (it is in fact much better because it also automagically provides all comparison operators). Basically, a<=>b can return <0 if a<b, 0 if they’re equal, and >0 if a>b Wow, had no idea this operator was a thing now. Does anyone here know if <=> actually gives a performance boost over separately checking < and then =, at least for basic things like integers and ASCII strings? A quick search online doesn't seem to provide an obvious answer -- whether it compiles to something more efficient, or whether compilers were already smart enough to compile previous <-then-= checks in the same manner. I'm assuming it's syntactic sugar, or else it would have been introduced for performance reasons long ago... but surely someone here has the definitive answer.
- remram 5y ago
  `<=>` seems to replace `-` not `if`.
  - deleted 5y ago
    [deleted]
  - crazygringo 5y ago
    Only for integers -- you can't subtract strings, but <=> compares them just fine.
- nneonneo 5y ago
  <=> on primitives probably won't be any faster than the binary comparison operators because of compiler optimizations. However, something like std::less can be accidentally exponential on deeply-nested objects like trees: https://news.ycombinator.com/item?id=26344987 https://news.ycombinator.com/item?id=26344987. This is because two separate comparison operations may be performed at each level (< in both directions for std::less), each of which may recurse on the corresponding nodes. <=> does not suffer from this problem as it means that only one (rich) comparison is performed for each node.
anonymoushn 5y ago
If the author fetches an array of 1000 children from disk, what prevents him from using binary search on those?
zanecodes 5y ago
This makes me wish that we had a language (or library, or runtime, take your pick) that abstracted away performance concerns. As an example of how this might work, suppose you want a data structure that provides an ordered collection of items, with the ability to insert, randomly access, remove, and iterate over them. The compiler/library/runtime might be able to supply any of a binary tree, a linked list, or an array. You, the programmer, have some idea of the distribution of the data that will be stored in the collection (e.g. the collection will contain integers between a specific range) and the operations your program will perform on it (e.g. the collection will never be iterated over, insertions will be twice as common as removals, only the first/last elements will ever be accessed at any given time). The compiler knows the performance characteristics of each of the operations over various distributions of data (e.g. linked list insertion has a cost of O(1), random access has a cost of O(n), removal has a cost of O(1)). The language would allow the programmer to provide the compiler with hints about the expected distributions of data and operations, and the compiler would use this to pick the optimal data structure for the use case. Another example might be the compiler picking a sorting algorithm automatically, based on the expected distribution of collection sizes and data (e.g. automatically pick insertion sort of the collections are typically small and already partially sorted, but pick merge sort if they are typically large and unsorted). It would also be interesting if this language/runtime could enable sampling of statistics on the actual observed distributions of data/operations under production workloads, and make it easy to update the programmer's specified distributions to get better performance with minimal effort. Or if the compiler could be given the performance characteristics of the target hardware as well, which could impact its choices. Maybe the program will be reading from an SSD, making the overhead of caching something in memory no longer worth it? More broadly, it would be very cool if program semantics and performance could be decoupled entirely, and the compiler could have the ultimate freedom to pick the optimal data structures and algorithms so long as the program's observed behavior remained the same.
- Svetlitski 5y ago
  This very much sounds like a typical Relational Database (to a degree), with the language thus being SQL.

75 points by jjgreen 5y ago

Basically algorithmic complexity analysis often ignores the cost of accessing data because the underlying storage is sometimes unknown - be it in memory, on a spinning disc or on magnetic tape. Unfortunately that gives suboptimal algorithms because that basic practically is ignored. You then end up with a bunch of algorithms that look worse “on paper” but still outperforms the theoretically optimal ones. Often the number of items is also ignored. If you want to implement a set-like feature but you’ll be using less than X elements, you can often get better performance just using a linear search through an array than use a full fledged hashed set.

jsmith45 5y ago
Agreed. There are plenty of cases where an asymptotically "worse" algorithm performs better than a "better" one for all practical sizes. Like it is very very much possible that the asymptotically "better" algorithms have coeffcients so high that the break even point takes like week or more of computation. There are not many programs where users will tolerate using it with so much data that operations take that long.
munificent 5y ago
This reads like a criticism of complexity analysis, but really you're just describing it. By definition and by design, algorithmic complexity analysis only shows you how an algorithm behaves asymptotically. That means it's often not the right tool for selecting an algorithm with optimal real-world performance, but I think that's less a fault of the tool than it is a fault of the tool selector. Saying, "complexity analysis ignores constant factors and small-data size performance" is sort of like saying "hammers ignore the threading on screws".
- Retric 5y ago
  Saying something is a poor fit in the real world is a perfectly valid criticism. Arguably complexity analysis is such a poor fit programmers should never actually use it, but vastly simplifying problems can make for a good first approximation.
  - alex_smart 5y ago
    Saying "why do we teach programmers complexity analysis in a word RAM model, there are no idealized RAM machines that behave like that in the real world" is no better than saying "why do we teach people Euclidean geometry, there are no such idealized geometrical systems in the real world". The point is that: 1. The analysis is useful and instructive. 2. It teaches you how to analyse computing models, starting from a simple one, so that when you need to, you can build and analyse more complex models specific to your domain.
    - Retric 5y ago
      In the real world spacetime is very close to Euclidean geometry near earth. Complexity analysis on the other hand can be wrong by literal orders of magnitude. If carpenters needed to worry about the internal angles of a triangle a ding up to between 9,672 and 1.72 degrees then I think people would consider Euclidean geometry a waste of time, but 180 +/- 0.0000001 is fine.
      - alex_smart 5y ago
        You are responding to an argument I never made. You don't teach children Euclidean because they would actually ever need to calculate the area of a triangle. You teach them geometry because it is a good exercise in working with logic, proofs and mathematical models. >Complexity analysis on the other hand can be wrong by literal orders of magnitude. Seeing how complexity analysis only applies to the asymptotic behavior of an algorithm, I don't even know how to make any semantic sense of that statement. It is not even wrong.
        Retric 5y ago
MatteoFrigo 5y ago
What you are saying may be a valid criticism of basic undergraduate algorithms courses, but it is a bit unfair as an absolute criticism of the field. There exists a huge literature that studies algorithms under various models of the memory hierarchy, and under various models of I/O. Even Knuth's venerable The Art of Computer Programming from 50 years ago studied the problem of optimal sorting assuming that the data is on tape and one has six tape drives available (for some value of six that I forgot).
- svat 5y ago
  Not many people realize that the literature you mention is the field of "analysis of algorithms", which is a sub-field of (or, in practice, somewhat different from) computational complexity theory / theory of algorithms. Robert Sedgewick (CS professor at Princeton, and an early PhD student of Knuth) has a great book with Flajolet on Analysis of Algorithms [1], and in one of the lectures from his course [2] makes a distinction between the complexity analysis usually taught in basic undergraduate algorithms courses (he calls O-notation not the scientific method, in a certain context in the lecture) and AofA (which involves saying "Running time is ~aN^c" instead of saying "Running time is O(N^c)", and also actually measuring against real programs) — watch the video or read the slides; it's an interesting distinction. And the Purdue website [3] is even better at giving a sense of the field. [1]: https://aofa.cs.princeton.edu https://aofa.cs.princeton.edu [2]: https://aofa.cs.princeton.edu/online/slides/AA01-AofA.pdf https://aofa.cs.princeton.edu/online/slides/AA01-AofA.pdf / https://www.coursera.org/learn/analysis-of-algorithms/lecture/LAXjA/a-scientific-approach https://www.coursera.org/learn/analysis-of-algorithms/lectur... [3]: https://aofa.cs.purdue.edu https://aofa.cs.purdue.edu
jjgreen 5y ago
I recently had occasion to re-implement the R-tree structure [1] which I based on the original code by Guttman. There, each set of child nodes were stored in a (hard-coded 1k) page of memory, but there was a macro which allowed n sets of child-nodes in a page, but that value was set to 1. I assumed that this was an experiment which turned out to not work, hence the hard-coded 1 to disable it. As the code was nearing completion I experimented with values other than 1, and found a 3-fold increase in speed for a value of n=8 (IIRC) against a 4k memory page. It's always worth testing your assumptions :-) [1] http://soliton.vm.bytemark.co.uk/pub/jjg/en/code/librtree/ http://soliton.vm.bytemark.co.uk/pub/jjg/en/code/librtree/

valbaca 5y ago

Author seems to have just backed into rediscovering B-trees https://en.wikipedia.org/wiki/B-tree https://en.wikipedia.org/wiki/B-tree > To conclude, binary trees are optimal when we ignore the cost of accessing a node, but they aren’t when it becomes costly to access a node. When we access the nodes on disk, with a high cost, it becomes interesting to bundles many keys in a node, and we gave the optimal solution. However, the problem is often solved quite more directly. We just fit as many keys as possible in an I/O block. Disks operates on small blocks of (typically) 512 bytes, but file systems operate in somewhat larger, but fixed-sized blocks, something like 4 or 8k. A good strategy is therefore to fit as many keys as possible in that block, since even if the number of comparisons is large, it will still be faster than bringing that block into main memory.

jwdunne 5y ago
I didn’t get that impression. I got the impression the author knew full well what B-trees are and is alluding to them. The author’s other writings seem to show that they do indeed know of B-trees.

bob1029 5y ago

Skiplists are my favorite data structure. There are a few use cases that they can't satisfy, but for the typical memory-bound key-value store application, it's a very simple & effective approach. If you have to go to disk, a combination of: splay tree, batching and append-only log structure are your best bet.

valbaca 5y ago
I'm sure online resources abound...but do you have a favorite descriptor or implementation of them? Or a particular use-case?
- bob1029 5y ago
  I've used indexed skiplist implementations in DIY database projects. The idea was to first build a super fast K/V store (i.e. to memory+disk), and then build skiplists on top of that for tying together collections of indexed data. The problem with skiplists is that they kinda suck when used directly with mutable block storage. There is no way to do incremental updates like with a splay tree where you can write just the diff (a modified sub-tree and a new root node) to the end of a contiguous log file.
codr7 5y ago
Links to efficient implementations would be much appreciated. I've played around with the idea but eventually settled on binary searched arrays for the small stuff and red/black trees for the rest. One thing that bothers me about skiplists is having a static number of levels, which will either be too few or too many for most situations.
- bob1029 5y ago
  You can do probabilistic inserts which should ensure the # of levels scales appropriately with the quantity of data. The probability factor can be a simple constant or some linear function of the quantity and/or index #.
- tsumnia 5y ago

cakoose 5y ago

Yup, ignoring the costs of memory/storage access (cache, main memory, disk) can hurt an algorithm's real-world performance. Laying your data out in chunks that match the memory/storage blocks sizes (cache line size, disk block size) can yield much better performance. And while having the algorithm be aware of the chunk sizes in every layer of your memory hierarchy is optimal, it can be inconvenient to get all that set up. But what's cool is that you can often lay your data out in a fractal-like pattern, and get pretty good performance no matter what the various chunk sizes are: https://en.wikipedia.org/wiki/Cache-oblivious_algorithm https://en.wikipedia.org/wiki/Cache-oblivious_algorithm

kazinator 5y ago

A binary search tree with string keys is just a compressed version of a binary tree with bit keys, which greatly reduces the number of nodes. E.g. this has three nodes: dog / \ ant fly But: ant -> 61 6E 74 -> 011000010110111001110100 dog -> 64 6f 67 -> 011001000110111101100111 fly -> 66 6C 79 -> 011001100110110001111001 Thus R / 0 \ 1 \ 1 / 0 / 0 / \ ,---' `-------. / \ / \ 0 1 / / \ / ,-------' `---. / / \ 0 0 1 \ / / 1 0 0 / / / 0 0 0 \ \ \ 1 1 1 \ \ \ 1 1 1 / / / 0 0 0 \ \ \ 1 1 1 \ \ \ 1 1 1 \ \ / 1 1 0 / \ / 0 1 0 / / / 0 0 0 \ \ \ 1 1 1 \ \ \ 1 1 1 \ / \ 1 0 1 / / \ 0 0 1 \ \ / 1 1 0 / \ / 0 1 0 / \ \ 0 1 1 (ant) (dog) (fly) :)

crazygringo 5y ago

> The spaceship operator, <=> is C++20’s version of C’s old timey qsort comparison function (it is in fact much better because it also automagically provides all comparison operators). Basically, a<=>b can return <0 if a<b, 0 if they’re equal, and >0 if a>b Wow, had no idea this operator was a thing now. Does anyone here know if <=> actually gives a performance boost over separately checking < and then =, at least for basic things like integers and ASCII strings? A quick search online doesn't seem to provide an obvious answer -- whether it compiles to something more efficient, or whether compilers were already smart enough to compile previous <-then-= checks in the same manner. I'm assuming it's syntactic sugar, or else it would have been introduced for performance reasons long ago... but surely someone here has the definitive answer.

remram 5y ago
`<=>` seems to replace `-` not `if`.
- deleted 5y ago
  [deleted]
- crazygringo 5y ago
  Only for integers -- you can't subtract strings, but <=> compares them just fine.
nneonneo 5y ago
<=> on primitives probably won't be any faster than the binary comparison operators because of compiler optimizations. However, something like std::less can be accidentally exponential on deeply-nested objects like trees: https://news.ycombinator.com/item?id=26344987 https://news.ycombinator.com/item?id=26344987. This is because two separate comparison operations may be performed at each level (< in both directions for std::less), each of which may recurse on the corresponding nodes. <=> does not suffer from this problem as it means that only one (rich) comparison is performed for each node.

anonymoushn 5y ago

If the author fetches an array of 1000 children from disk, what prevents him from using binary search on those?

zanecodes 5y ago

This makes me wish that we had a language (or library, or runtime, take your pick) that abstracted away performance concerns. As an example of how this might work, suppose you want a data structure that provides an ordered collection of items, with the ability to insert, randomly access, remove, and iterate over them. The compiler/library/runtime might be able to supply any of a binary tree, a linked list, or an array. You, the programmer, have some idea of the distribution of the data that will be stored in the collection (e.g. the collection will contain integers between a specific range) and the operations your program will perform on it (e.g. the collection will never be iterated over, insertions will be twice as common as removals, only the first/last elements will ever be accessed at any given time). The compiler knows the performance characteristics of each of the operations over various distributions of data (e.g. linked list insertion has a cost of O(1), random access has a cost of O(n), removal has a cost of O(1)). The language would allow the programmer to provide the compiler with hints about the expected distributions of data and operations, and the compiler would use this to pick the optimal data structure for the use case. Another example might be the compiler picking a sorting algorithm automatically, based on the expected distribution of collection sizes and data (e.g. automatically pick insertion sort of the collections are typically small and already partially sorted, but pick merge sort if they are typically large and unsorted). It would also be interesting if this language/runtime could enable sampling of statistics on the actual observed distributions of data/operations under production workloads, and make it easy to update the programmer's specified distributions to get better performance with minimal effort. Or if the compiler could be given the performance characteristics of the target hardware as well, which could impact its choices. Maybe the program will be reading from an SSD, making the overhead of caching something in memory no longer worth it? More broadly, it would be very cool if program semantics and performance could be decoupled entirely, and the compiler could have the ultimate freedom to pick the optimal data structures and algorithms so long as the program's observed behavior remained the same.

Svetlitski 5y ago
This very much sounds like a typical Relational Database (to a degree), with the language thus being SQL.