Static search trees: faster than binary search
curiouscoding.nl
curiouscoding.nl
And, well the language choice doesn't really matter for the core subject here. I could follow this post fine even though I don't really know Rust (just like I assume a Rust programmer could follow a well written algorithms deep dive with examples in C with a bit of dedication). EDIT okok that was a lie, I could follow the first half of this post, ish, and then it got way too deep for me.
But anyway, standardize on Rust, I like it. I'd love if a bit more Zig was thrown into the mix here but either of them feel like a better default than C at this point to me. After decades of C being The Standard for this stuff, I love that this is finally changing.
Still, Zig seems somewhat more intuitive to me, even though I’ve used it as little as Rust thus far.
A nice write up on the topic Zig and Rust: https://matklad.github.io/2023/03/26/zig-and-rust.html
edit: typos
Which is totally fine, there's a reason C++ never completely subsumed C; both are valid avenues.
What in particular do you see lacking in Rust that you can do in C++?
Runtime exceptions is what I consider a bad practice and it's spread everywhere in Java... Also the language evolutions are not really that good. So bringing errors/exception to the compilation time is a safety net.
Despite the fact that languages with managed memory safety bring a lot of potential for abusively high memory consumption, random GC stop the world situations and worse like oom.
Whenever I had to analyze a memory issue with an application it was no fun at all, despite the challenge.
The jvm specifications are so flawed considering security... Creating classes at runtime from a stream using reflections, which is totally spec compliant gave us log4shell. Why even load serialized classes from remote?! Fail by design.
So safety is still context sensitive and depends on the requirements. If you write bad software you can ignore some of the mentioned aspects, though it still lacks of 'security'
Just my 2 cents here
In the end of the day, C# had the same ideas of isolating unsafety that Rust has, and provides many safe wrappers around good libs, like Skia (SkiaSharp, very famous and widely used) for example. So those ideas are kinda market proven as well.
Then there are build systems that natively support Rust in addition to other languages and know how to plug them together [2] [3] [4]. If you're already using one of these existing tools, then you don't need to roll your own, you can plug it into your existing project.
Of course if you really are using Makefiles in C you're already living in the wild west, so it's on you to figure out how to add Rust to your projects in that case (or switch to a better build system).
[1]: https://doc.rust-lang.org/cargo/reference/build-scripts.html
[2]: https://bazelbuild.github.io/rules_rust/
Often a new language in a project would define an application boundary. So those would be different containers or services. I may deploy via container images, or an OS specific installer, etc. If we aren't crossing an application boundary I may use FFI. Sometimes I use https://rust-lang.github.io/rust-bindgen/ to smooth that over for C dependencies. There is also a nice concept called a build.rs file: https://doc.rust-lang.org/cargo/reference/build-script-examp.... There's also tools like: https://github.com/casey/just and https://sagiegurari.github.io/cargo-make/
I rarely use multiple languages with Rust. A lot of interpreted languages have bindings through crates and can go in to a project through Cargo (python, etc). If it involves JS/TS on desktop, I'm usually using Tauri for that. Guess it depends on the system?
Hopefully that helps. You can also still use a Makefile if you want I just haven't dealt with one in a long time.
[0]: https://jacko.io/object_soup.html
[1]: https://crates.io/
> Learn Rust With Entirely Too Many Linked Lists
> In this series I will teach you basic and advanced Rust programming entirely by having you implement 6 linked lists. In doing so, you should learn:
* The following pointer types: &, &mut, Box, Rc, Arc, *const, *mut, NonNull(?)
* Ownership, borrowing, inherited mutability, interior mutability, Copy
* All The Keywords: struct, enum, fn, pub, impl, use, ...
* Pattern matching, generics, destructors
* Testing, installing new toolchains, using miri
* Unsafe Rust: raw pointers, aliasing, stacked borrows, UnsafeCell, variance
- From the perspective of e.g. C++, I don't think it's reinventing the heap. We often prefer to use indexes into a std::vector or similar, even when putting everything in std::shared_ptr is an option, because the dense layout of the vector gives us the blazing fast cache performance we crave. It also avoids memory leaks from reference cycles.
- From the perspective of e.g. Python, yeah it's reinventing the heap. Unless you need to serialize the whole collection into JSON or something, it's much less convenient. But (almost) no one uses Rust instead of Python just for the convenience. (There are dozens of us! Dozens!)
Perhaps this is the reason performance oriented articles prefer Rust. In allows to skip a lot of memory allocation while still catching memory-safety bugs, which is a hard problem with C++.
- Working with resizeable collections like std::vector in any non-GC language, where resizing invalidates pointers.
- Serialization. If your objects contain indexes to each other, it's easy to turn them into e.g. JSON. But if they contain pointers to each other, it's tricky.
Despite this, it's one of the fastest regex engines around: https://github.com/BurntSushi/rebar#summary-of-search-time-b...
Here's a related but more isolated analysis: https://github.com/burntsushi/rsc-regexp
Those are fairly straightforward to implement if you are ok using a reference counted type (along with weak references), although that will hurt performance. That would be similar to using a shared_pointer in c++.
And you can implement code similar to what you would in c or c++ if you use raw pointers and unsafe code.
Where you run into difficulties is if you want something that is fast and safe. And then you need a more complicated design that probably involves using indices into a Vec instead of pointers.
The `splat(q)` constructor is just saying, "populate each lane with `q`." That is, the value is "splatted" across every lane in the vector.
The main idea of SIMD is simple: you represent multiple points of data in the same register and use specialized CPU instructions to operate on those points simultaneously. The difficulty of SIMD is coming up with clever algorithms that use the available instructions in an efficient way.
Ah so splat is like a memset for the entire vector to the same value. OK makes sense, I bet that wasn't actually a Rust-ism at all, just basic SIMD lingo I didn't know. Thanks again!
(For the uninitiated: Burntsushi of ripgrep fame.)
Scientific stuff (scipy) and now all the ML stuff too
In theory, with an infinitely large amount of input queries you will never have to do an out-of-cache lookup, it can be completely amortized away into linear scans.
That said, you now end up with a bunch of results that need to be put back into the correct output order, which likely makes it not worth it. But if the operation can be fused into a reduction (e.g. find the sum of the binary search results) or the output order does not matter in some other way then all of a sudden it might make sense.
I implemented this method in Dyalog 18.0 with BlockQuicksort-like partitioning, using vectorized comparison with bit-boolean output. It's faster than you'd expect, maybe twice as slow as regular binary search when searched values are in cache, and better once they fall out of L2. But Dyalog reverted to 17.1 for later versions so you won't see it in a new download. It'll probably make it into CBQN eventually, perhaps with radix partitioning. Note that both quicksort and radix partitioning can be done and undone in a cache-friendly way.
Unlike quicksort, there's no issue of pivot selection since you always choose the midpoint of the searched values. However, there's a complementary issue of memory if the partitions become unbalanced, because the larger partition can require saved memory of roughly the depth times the number of elements. With a bit per comparison it's bounded by the size of the input.
I also looked a bit into radix and distribution sort at some point over the past year, but in the end high performance sorting is actually too big of a thing to just do quickly on the side, as your post well shows :") In fact I wasn't aware of the associativity issues for radix sort. That's definitely something to keep in mind and investigate.
Will definitely refer back to it once I'm looking at sorting again in more detail at some point!
Email in my Github profile, feel free to contact me any time if you'd like to talk about algorithms!
32-bit radix sort: https://github.com/dzaima/CBQN/blob/v0.8.0/src/builtins/grad... plus https://github.com/dzaima/CBQN/blob/v0.8.0/src/builtins/radi...
And it works much better than pure compacting (i.e. the leveldb lineage), because you avoid lock contention at the root on multithreaded update workloads, and the compaction/resort is much lower overhead when it fits in l2.
incidentally, there's a filesystem that uses this technique.
BetrFS?
At one level you could just be saving the results into a hashtable to bubble them out again, but at the extreme end the lookup is actually spread across multiple machines in a cluster, so it’s more like throwing the query to the proper one with the right chunk of the index, along with instructions about where the final RPC is supposed to go with the result.
The (data size / cache size) ratio and queries local (in time) dispersion are key.
Also (radix) sorting is very memory bound usually, and we probably need to sort in at 16^2=256 buckets or so to get sufficient reusing of the higher layers, but I don't have the numbers of what a round of radix sort takes. (My guess is order 1ns per query? Maybe I'll find time to investigate and add it to the post.)
1. For merge sort of N elements, you have to perform log(N)/log(R) passes
2. For sample sort - C*log(N)/log(R), where С depends on the distribution of your data, there are no strict guarantees
3. For radix sort of K-byte elements exactly K passes (indeed, 256 ways is optimal according to my tests), which is usually larger than the previous value
While Mergesort looks preferable since it uses the least and fixed amount of passes, the merging code itself is less efficient - there are not much independent CPU operations, making it slower than samplesort and especially radix sort for small inputs.
So, it seems that the best strategy combines two different levels - for larger blocks you absolutely need to minimize the amount of passes [over memory] and employ multithreading, while for smaller blocks we need to minimize the amount of CPU operations and increase ILP.
Today two well-recognized algos are IPS4O for larger blocks and Google's SIMD QuickSort for smaller ones.
Walk the larger tree, using the smaller tree.
That's not terribly common.
Doing this stuff in Rust is absolutely possible, and I'd do it again since my C++ days are now past me, but the endless transmuting between portable-simd types, plain rust arrays, and intrinsic types is quite annoying.
Also rust is not made for convenient raw pointer arithmetic. There plain C would be much more to the point.
The next level would be to keep track of how many prefix bits are implied by the parents, so leaf nodes could perhaps also only use 8/12/16 bits, if the the higher bits are implied by the parent. or instead of bit masks, use offsets (i.e. leaves store k bits offset from parent value).
That may screw around with the branch predictor, and may work very good with evenly distributed data vs uneven data.
On the other hand, most of the latency is in the last few layers, and probably there isn't as much to be saved there.
The biggest problem might be that the bottom layer will anyway have to store full-width numbers, since we must be sure to have the low-order bits somewhere in case they weren't covered yet in earlier layers. Or we could have variable width encoding per node maybe (instead of per layer) but that does sound a bit iffy on the branch predictor.
In the end I guess I kinda like the simplicity and hence reliability of the 'just do the full tree and the first layers are cheap anyway' approach. Probably another factor 2 speedup is possible on specific datasets, but anything beyond this may not be reliably good on worst case inputs (like is the issue for the prefix partitioning methods).
It kind of comes down to how to deal with bad distribution of values, like large differences between adjacent values. One could for example deal with this by deliberately leaving „gaps“ in the tree, like using a 59-ary node on places (make the last values in the array large, so they will never get visited). With dynamic programming, perhaps an optimal distribution of the leaf level could be had - although it requires more bookkeeping bits of one needs to have the index of the found value, not just whether the value is in the tree.
The question could also be whether it could be interesting to store delta valeues, so that 63 8-bit valeues gives a larger numeric range - this means computing some sort of cumulative sum on on the 63 values, not sure whether there is a simd instruction for that.
One more thought: if there is different ways different layers of the tree are stored, but they are always the same for each layer, the code be unrolled, with every layer having different code to deal with it.
Last thought: if the index is not important to know, just whether the value is in the set or not, one could use a bitmap as a data structure. It would require 256MB for the 32bit space, but large spans of zeros imply empty pages.
But when I tested this even Eytzinger was too slow.
indeed, highway is the popularity leader, it implements lots of SIMD operations and supports lots of hardware including SVE/RVV with runtime SIMD width, although IMHO it has a bit longer learning curve
This is useful if your primary keystore is a normal sorted set of keys - easier to work with - you then don't need to store explicit pointers.
Also, he didn't mention that with eytzinger you can prefetch multiple loop iterations in advance - use 1-based indexing so that sibling nodes line up nicely on cachelines.
In fact, I'm pretty sure a similar formula could be made to work for higher branching factors, although it would surely be slower. (Probably it depends on the number of times 17 divides the final index it so, which is not great, but with B=15 it would be the number of factors of 16 which is easy again.) The more annoying issue with not storing everything in the final layer is that we have to keep a running-answer for each query as we go down the tree, which I suspect will add measurable runtime overhead. But maybe that's a tradeoff one is willing to make to avoid the 6.25% overhead.
it's interesting that the wins for batching start diminishing at 8. I'm curious then how the subsequent optimizations fare with batch size 8 (rather than 128).
smaller batch sizes are nice since it determines how much request throughput we'd need to saturate this system. at batch size 8, we need 1s / ~30ns * 8 = 266M searches per second to fully utilize this algorithm.
the multithreading results are also interesting -- going from 1 to 6 threads only improves overhead by 4x. curious how this fares on a much higher core count machine.
I suspect that at higher core counts, we can still saturate the full RAM bandwidth with only 4-5 cores, so that the marginal gains with additional cores will be very small. That's good though, because that gives CPU time to work on the bigger problem to determine the right queries, and to deal with the outputs (as long as that is not too memory bound in itself, although it probably is).
As a general purpose data structure, I would look at roaring bitmaps for this purpose, which has good trade-offs with great performance for most use-cases.
If only simple lookups are needed over a static set, then it's worth looking at minimal perfect hash functions (https://sux.di.unimi.it).
There's also the extreme of simply storing the answer for each possible query as a u32 and just index the array, but there the overhead is much larger.
Rank-select is also interesting, but I doubt it comes anywhere close in performance.
I happen to also be working on a minimal perfect hashing project that has way higher throughput than other methods (mostly because batching), see https://curiouscoding.nl/posts/ptrhash-paper/ and the first post linked from there.
There are a lot of interesting variants of rank/select and other succinct data structures which has interesting tradeoffs. Maybe most useful when compression is critical. At least my own data structures can’t compete with the query performance you are showing, but they are great when the memory footprint matters.
Whenever I read about super low-level optimisation, my immediate feeling is that of gratitude to the author for spending so much time shaving off nanoseconds which the entire SE community gets to enjoy.
I wonder how much time humanity has collectively saved simply as a result of how all these optimisations stack up.
But yes, as new technologies stack up, we achieve exponential growth in throughput in the end, which usually enables new science :)
Edit: Also, 1.3 figure 1: Should the y-axis label be "Inverse throughput" to match later figures?
And yeah, maybe I should just label all of then with throughout for consistency.
For 32 bits, using the first few or even a lot (16? 20?) bits to index an array and then chasing down the remaining bits somehow (adaptively depending on size of that partition?) seems like it could work.
In this direction, and with really impressive asymptotic performance, there’s the van Emde Boas tree and its variants.
I found this to really detract from an otherwise interesting post.
And since DNA sequencers are still increasing there throughput and accuracy, it's always good to have faster algorithms as well.
Use case is to query hundreds of gigabytes of data in tens of milliseconds.
(Skiplists is also used by some search engines.)
You can replace string with any data structure you can hash or index really.
But what would a range over strings even represent?
Perhaps if you e.g. use string indices into an array of sorted strings (by length, by prefix or whatever), you could use it for something. Depends on the application I guess :)
For such prefix queries, I think a radix-tree/Trie or ordered collections are more useful (than the index-based collection I initially mentioned).
Thanks for following up :)
Then again, Eytzinger looks like binary heaps.
What is the point?
The final goal is to index DNA, say a human genome, or a bunch of them, and this is static data.
Then as new DNA comes in (eg is read by a DNA sequencer) we can efficiently query against the index built on the reference genome, and this reference is often fixed.
I wonder when the next such malicious algorithm(s) passes under our noses, and what its hidden purpose might be.
Such a good and detailed article that packed with techniques that are applicable everywhere yet the complaints are: “but rust”.
Regarding Python, how could such optimizations be implemented in Python? Generating LLVM bytecodes directly aside.
`&[u32; P]` is similarly something like `std::span<const uint32_t, P>`.
`[u32; P]` (no `&`) is essentially `std::array<uint32_t, P>`.
`Vec<u32>` is essentially `std::vector<uint32_t>`, yes.
Vec<u32> is pretty much like std::vector compared to them, yeah.
This could be addressed if I just learned Rust (much like my difficulty with Italian could be addressed by studying Italian). However, I already know at least 10 programming languages. I am unwilling to learn the latest fashionable language unless it can promise me that the language will not change and there will never be another fashionable language for me to learn. Given that Rust rejected the standardization process that C and C++ embraced, and Zig is expected to replace Rust one day, I doubt Rust can make such assurances.
As for Python, it is often used for teaching CS and everything except the assembly code is doable in it. Using low level assembly from Python would require using the FFI. Also, Python has nothing to do with LLVM.
I didn’t say python has anything to do with LLVM, it’s just a technique, read about it, or not.
That's a bold prediction considering that Zig is unsafe and Rust is safe.
If Zig's idioms make it safe, then modern C++ is safe too.
It otherwise solves basically nobodies problems in the real world and is just a love letter to C. It's cute, kinda, but that's about it.
This is true of every single programming language.
Yeah, don’t you think they might be perhaps just slightly biased? I have some news for you about your average technology enthusiast…
Anyone who claims Zig is going to replace Rust knows nothing about either Zig, Rust, or both. Zig is designed to solve none of the problems that Rust solves. Trillion-dollar corporations are rewriting things in Rust because it solves problems that really matter to them.
The US government strongly recommends writing all new mission-critical code in memory-safe languages. Guess which one of Rust and Zig is memory-safe?
I have nothing against Zig, it looks like a very nice better C, and the comptime stuff is both cool and useful. But its priorities are not Rust’s priorities.
Which is good. Programming is an open field, ideas are constantly popping in and out and you sometimes need to reinvent things to prove that they are worth it. More languages is a good thing, the bizarre tribalism around them is dangerous, but it is not possible to prevent it, people gotta be people.
And also so more readable, ie. maintainable
You don't. You instead use your favorite Python extension system (regular Python modules, Cython, Numba, whatever) to implement this tree algorithm and expose it to Python already shaped into a container.
Interesting, the Algorithmica article the author cited is in C:
Anyway very happy that this is also showing off what rust can do
That said, you are right that Python is not the best language to use when you need to use intrinsics, as you would be writing it in another language and using the Python FFI to access it.
To people who already know Rust, yes. To others, not so much
So realistically, this is just the other half of the coin for all the articles where the code examples were written in C and everyone who didn’t really read C just had to put up with it.
It's a good article.
If Heinlein were in our industry, he might write this:
A programmer should be able to write a shell, parse binary data, design a protocol (and reverse engineer one too), authenticate a password, not fumble multi-code-point graphemes, wrangle semaphores, plug memory leaks, compress data, migrate databases, automate builds, git rebase a tree, profile tail latency, write a simple design doc for a complex system, draw a triangle, multiply tensors, and do fizzbuzz in every popular language on GitHub. Specialization is for insects.
* C
* C++
* Java
* JavaScript
* Python
https://www.tiobe.com/tiobe-index/
Rust is not very high on the TIOBE index. It has rank 14 with a 1.29% rating. That is not much higher than COBOL.
Your description would be better applied to C, C++ and Python. That is what the majority of popular software uses and people having challenging conversations are often using one of those languages.
Servo is pretty notable and visible. ripgrep, influxdb, wasmer, deno. uv and ruff in the python ecosystem are written in rust.
AWS, Cloudflare, Discord (iirc), and Microsoft have all adopted Rust extensively.
As of late 2023 there are committed drivers in the Linux kernel written in rust. (Linux is pretty popular.) prior to those, only C and assembly were allowed.
You may be surprised to learn, Python's `cryptography` project is written (EDIT: maybe not primarily, it's hard to compare given dependencies) in Rust, and saw around 8.1 million downloads from PyPI yesterday. That puts it close to the top 20 (the 20th project comes in at 8.5m).
Source?
ALGOL gave way to C, and C is now giving way to Rust, Zig and others. You're playing the role of the people who wanted to keep the example snippets in ALGOL.
Estne melius scribere exempla latine?
Edit: Eytzinger layout, Cache lines, SIMD, et cetera are independent of the particular language used in the article. They're just as valid in C, for example. I don't understand your point about them being tied to Rust.
I've been working with real C today and have been having fun, but it's very different for me to step back into the C world again after working with more modern tools.
At the end of the day rust is just another imperative programming language. You shouldn't need to know the language at all to understand the very simple examples written in rust.
Also the other comment saying that "psuedocode is not concerned with intrinsics" is false. You can get "great" theoretical speedups (the shaveoffs are tiny but hey, they're better) with "simple" intrinsic operations - that's my roommate's entire research lol. The external memory model, for example, formalizes caching and allows all these low level optimizations to flourish. I'm not sure how intrinsics tied into it, but he's published so I'm not gonna question it :)
---
Speaking of which, I noticed that you did competitive programming. How does CP compare to research? I loved data structure manipulation problems in CP when they were clever - often because they involved noticing that you can take a "common" model, but then optimize it significantly because you only needed to support a subset of the operations through a clever mathematical proof based on the structure of the problem - but as I got to the higher levels it felt more and more that a lot of them became really obscure "support 413 operations on a tree, and yes, you really need to support all 413 operations on a tree" and that's kind of my opinion of data structure research unfortunately as well :( I guess because solving broad general instances is more important. I'd love to hear your perspective though.
Indeed I did a bunch of competitive programming! But actually there my favourite topics are combinatorics, graph theory, and number theory. I'd usually leave the datastructure (read segtree) problems to my teammates.
I super enjoyed that, and indeed was looking for a PhD where I could do similar things (because my time at Google was boring in comparison -- mostly just software engineering), on the intersection of new theory and practical fast code. I decided on bioinformatics, because this is exactly a field that has a lot of data, and the amount of data is growing fast, so that fast algorithms&code are needed, both in theory (big-O) and practice. Generally I've been super excited working on various problems in this domain, and I'd say it quite closely matches my compprog experience :)
Don't see it as a problem, see it as an opportunity.
But no, this is actually part of my PhD research. The next step will be to use this in a fast suffix-array search algorithm.
It was great while computers were not really a thing yet, but these days it's often so meaningless. We see papers with 2x speedup with a lot of novel algorithmic stuff that sell better than 10x speedup just by exploiting CPUs to the fullest.
Even myself I kinda think theoretical contributions are cooler, and we really need to get rid of that (slightly exaggerating).
https://github.com/openzfs/zfs/commit/677c6f8457943fe5b56d7a...
There are two ways to look at this Big O wise. One is that insertions and deletions would be asymptomatically faster since memmove() is a linear operation while bubble up/down are logarithmic operations. Look ups would not be any different asymptotically, but the constant factor might improve from being able to do prefetch. The other way is that the N is bounded, such that it is all O(1) and the difference is how big the constant factor is.
I imagine I could implement it and benchmark it. However, my intuition is that the end result have lookups be marginally faster to the point of splitting hairs while insertions and deletions would be slower. While memmove() is a technically a linear time operation, it is a sequential operation that has a very low constant factor. The bubble up and bubble down operations needed to do insertions and deletions in a Eytzinger ordered array are technically random access, which has a higher constant factor. At some point, the Eytzinger ordered array operations should win, but that point is likely well beyond the size of a b-tree node.
My reason for saying this is to say that Big O notation still matters, but understanding when the constant factor is significant is important.
Video about this that was very interesting to follow and somewhat related to what you're doing: https://www.youtube.com/watch?v=5rb0vvJ7NCY
Who do you think is behind this? The government?
Definitely going to use this for our next round of interviews.
Fun aside, asking someone to work through a problem with you is fine, but when it diverges so much from the actual work then it just becomes ridiculous.