Binary Trees are optimal except when they’re not
hbfs.wordpress.com
hbfs.wordpress.com
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.
The author’s other writings seem to show that they do indeed know of B-trees.
If you have to go to disk, a combination of: splay tree, batching and append-only log structure are your best bet.
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.
You should be inserting a new level whenever you add an element to the highest. I like skiplists, they're fun to teach but I'd say the part that irks me the most is their O(log n) is through "amortization", or sometimes its a long search, sometimes its a short search, so it "averages out in the end".
From a purely academic side, its difficult to explain why you'd use one data structure over another. We can say THIS structure has an O() for THIS operation, but its often at the tradeoff of another operation. Then it comes down to ease of implementation, where I'd say skiplists have a harder time explaining vs. hashing.
Or leveldb's: https://github.com/google/leveldb/blob/master/db/skiplist.h
Not an implementation, but a very fun explanation, that you could definitely implement if desired.
One way to look at treaps is to start with a skip list. A skip list has variable-size nodes, which is kind of annoying. If you transform the variable-size node into a linked list, you end up with something that is essentially a binary tree, but now you have redundant information in multiple tree nodes. If you remove all redundancy you get the treap. This is not how one usually thinks of treaps, and it is not how they were invented, but it's good to be aware of the correspondence.
For a given set of keys and hash function, the treap is effectively unique (unlike binary search trees) irrespective of the insertion order, which is sometimes a good property to have.
Anyone actually use this combo (I don't know much about this) that show is good?
---
If I were to build a rdbms today, and not for OLAP but OLTP, is this a good combination? I have imagine building my relational language about this stuff, and have wondered if building a paged "columnar" layout could be the best:
DeletedBitArray(00100100...)
Page1(SizeOfBlock) =
col1 = 1, 2, 3,
col2 = "hello" "cruel" "world"
Page2(SizeOfBlock) =
col1 = 1, 2, 3,
col2 = "hello" "cruel" "world"
All you have to do to keep an item alive is to access it using a splay tree. Cleanup is as simple as deciding how many older log segment files to chop.
In practical use cases you generally don't even have to worry about potential downsides. The sequential integer insert thing giving you log(N) is so rare. Most live systems are touching tons of items in arbitrary order so the probabilities work themselves out.
This is already happening as a natural part of the utilization patterns. Just looking at something in a splay tree will cause it to be relocated to the root (the most live part of the log). That is the dynamic part of the data structure. You are doing a huge part of the GC effort simply by reading the database.
There are clearly applications where this would not be a good fit (i.e. data warehousing where you want to keep old shit on purpose). Even with the natural cleanup mechanism, you may still need to save stuff you haven't accessed in a while. Linked list nodes built on top being an example of an area that would need careful attention to avoid chopping up data structures unexpectedly.
>That'd have horrific write amplification.
This is precisely why I recommend batching as part of the approach in my original post above. With batching, you can take a total rewrite of all nodes in a linked list and squeeze them into a single I/O operation that flows into exactly the # of storage blocks required. In implementations without batching, you are talking about block I/O per linked list node that needs updating. Clearly this is a total non-starter for drive lifetime & performance.
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.
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.
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".
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.
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.
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.
This is false, complex analysis is vastly more than just Big O, other resources like memory usage are also considered as are exact results.
Ex: Suppose you are allocating memory for a growing array. It’s allocated (+) and deallocated (-) in sequence. So +1000, then +1001, -1000, creating a (1000 wide gap at the start) but your next +1002 doesn’t fit in the gap. you now have 1001 bytes of allocated but due to fragmentation in effect 2001 are used up. This one isn’t that bad the second time around you you have a 2001 byte wide free space, but in more complex situations you can run out of memory vastly sooner than expected.
On PC’s virtual memory mapping generally means you don’t need to worry about this, but it used to be a huge pain and it can still be an issue for embedded systems.
PS: Not that this is 100% solved on PC’s, it’s still possible to run out of physical RAM much sooner than expected just significantly less likely.
I've never once felt that way in my career. I've often found that the insight I get from an algorithm's complexity is not a complete picture of its worthiness for a particular problem, but it is almost always a necessary piece of the puzzle.
I would never feel confident using an algorithm that I'd only empirically measured on some number of hand-chosen datasets because then who knows how it will behave when a user throws something unexpected at it.
And the Purdue website [3] is even better at giving a sense of the field.
[1]: https://aofa.cs.princeton.edu
[2]: https://aofa.cs.princeton.edu/online/slides/AA01-AofA.pdf / https://www.coursera.org/learn/analysis-of-algorithms/lectur...
[1] http://soliton.vm.bytemark.co.uk/pub/jjg/en/code/librtree/
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.
However, something like std::less can be accidentally exponential on deeply-nested objects like trees: 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.
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
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.
``` // Traits for the operations you want to perform... trait Map<K,V> { ... operations ... } trait List<K,V> { ... operations ... }
// Functions which dispatch for your data/operation distribution fn gimme_map<K, V>(data: DataDistribution, op: OperationDistribution) -> impl Map<K, V> { .. }
enum DataDistribution { ... } enum OperationDistribution { ... } ```
E.g. this has three nodes:
dog
/ \
ant fly
ant -> 61 6E 74 -> 011000010110111001110100
dog -> 64 6f 67 -> 011001000110111101100111
fly -> 66 6C 79 -> 011001100110110001111001
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)
Consider the characters. Is the "g" character in "dog" the parent of the "a" in "ant"? We can "explode" the original tree like this:
[ L | R | S ]
/ \
[L | R | S ] [0] -> 'd'
\ [1] -> 'o'
"ant" [2] -> 'g'
[3] -> 0 // null-terminated C string :)
What the binary search tree is doing is representing the sequence { "ant", "dog", "fly" }. It captures that this sequence has three elements, which are in that order.
The fact that "dog" is a parent of "ant" is not relevant in a search tree; it's just an artifact of how the tree is balanced. In the following tree, it is a child of "ant", yet it is an equivalent search tree:
ant
\
dog
\
fly
I believe "trie tree" is the specific name for these un-compacted ones... So, a "bitwise trie" here.