10 ms·

Static search trees: faster than binary search

656 points by atombender 2y ago

westurner 2y ago
suffix-array-searching/static-search-tree/src/s_tree.rs: https://github.com/RagnarGrootKoerkamp/suffix-array-searching/blob/master/static-search-tree/src/s_tree.rs https://github.com/RagnarGrootKoerkamp/suffix-array-searchin... partitioned_s_tree.rs: https://github.com/RagnarGrootKoerkamp/suffix-array-searching/blob/master/static-search-tree/src/partitioned_s_tree.rs https://github.com/RagnarGrootKoerkamp/suffix-array-searchin...
ryao 2y ago
This would have been easier for a larger number of people to read if it had been in C or Python.
- kubb 2y ago
  Maybe, but should the author really cater to people who can’t overcome a language barrier? They probably won’t understand the concept anyway.
  - ryao 2y ago
    The ACM for a time only accepted code examples in ALGOL because it was felt that there should be a standard language that everyone understood. ALGOL eventually gave way to C and others, but there is definite value in ensuring things are accessible to the largest possible audience.
    - dxbydt 2y ago
      usaco explicitly nudges you towards C++ on the first page itself. problems are graded on running time, even with moderately large datasets, Python simply doesn’t make the cut. So most high schoolers end up using C++ for usaco, and Java for AP Comp Science.
    - kubb 2y ago
      You're free to use ALGOL in your posts if you want. It reads like pseudocode used in algorithmic books, and should be familiar to anyone who used the Pascal family. 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.
      - ryao 2y ago
        The point was that examples should be in widely understood languages. The niche languages you list do not qualify as widely understood. Estne melius scribere exempla latine?
    - mplanchard 2y ago
      This is someone’s blog, not an ACM publication. Why hold it to the same standard? They can write in whatever they like. I have a hard time reading Haskell, but I don’t sit and kvetch about it anytime someone wants to use it in a blog post.
  - mangamadaiyan 2y ago
    Erm, the concepts that you're referring to are independent of the language being used. The author is free to use whatever language they want. The GP (I think) was merely trying to make a point about making the article accessible to a wider audience that is capable of appreciating the concepts involved.
    - kubb 2y ago
      If you can't understand the code snippets in this post, the concepts will most likely be lost on you, no matter what other language would be used for the code.
      - deleted 2y ago
        [deleted]
      - mangamadaiyan 2y ago
        Isn't that precisely the point that the GP was trying to make, about the accessibility of the article? 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.
    - ryao 2y ago
      You are correct.
- Rendello 2y ago
  I wonder what percentage of Rust users have significant experience with C. The difficulty curve of Rust was too high for me when I was coming from Python, but after doing HolyC and Zig, I find it fairly straightforward to conceptualize, though still difficult. 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.
- barbegal 2y ago
  Neither of those languages gives you portable SIMD. Rust is rapidly becoming the language of choice for high performance code.
  - npalli 2y ago
    google has a mature C++ library for portable SIMD. The original article seems to be a translation of the excellent algorithmica site which had it in C++. https://github.com/google/highway https://github.com/google/highway
    - ryao 2y ago
      You can do portable SIMD in GNU C/C++ using the vector extension: https://gcc.gnu.org/onlinedocs/gcc/Vector-Extensions.html https://gcc.gnu.org/onlinedocs/gcc/Vector-Extensions.html
      - swiftcoder 2y ago
        I'm not sure that "portable" and "only works on one specific compiler vendor" are very compatible concepts
        bigpingo 2y ago
        gcc is available on and targets more platforms than rust. So if GNU C is not considered portable you can forget about 'portable rust'.
        swiftcoder 2y ago
        Portability in the C and C++ worlds generally means across standard-conforming compilers, not just across platforms
- wolfgangK 2y ago
  I don't think that Python would be the right language for such low-level performance maxxing endeavor. I would have picked C++ but t was eye opening for me to see how rust enabled such low level optimization, so I'm grateful for the choice.
  - curiouscoding 2y ago
    Yeah, I don't think python is the right tool here. C++ definitely would be an option though. Anyway very happy that this is also showing off what rust can do
    - ryao 2y ago
      As far as I can tell, the community is largely divided into three major groups. Those that can read C, those that can read Python and those that can read both. Using either of them would have dodged criticism that your code examples are not accessible to much of the community. 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.
    - oguz-ismail 2y ago
      > this is also showing off what rust can do To people who already know Rust, yes. To others, not so much
  - ryao 2y ago
    C would be useful to the broadest audience. C++ programmers can read C while C programmers cannot always read C++, especially when the newer language constructs are used. I mentioned Python because of its popularity. Interesting, the Algorithmica article the author cited is in C: https://en.algorithmica.org/hpc/data-structures/s-tree/ https://en.algorithmica.org/hpc/data-structures/s-tree/
    - npalli 2y ago
      C++ not C. The author explains his choices elsewhere in the site.
- pxmpxm 2y ago
  I suspect like 9/10 of these type of articles are really just meant to be PR for rust. Like someone that wants to write Bart Simpsonensque "rust is great" over and over, but have to hide it into something more interesting.
  - curiouscoding 2y ago
    Rust is great :") 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.
    - jackschultz 2y ago
      Great stuff. We get told O notation is what matters for data structures / algorithms, but improvements low level with memory and storage with things like rust is much more where improves can be made. These types of tricks for anctual run times are so valuable, and interesting to follow.
      - curiouscoding 2y ago
        Ohh yeah, don't get me started in big-O... 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).
        Andys 2y ago
        You're really just exploiting hidden O(?) implementations inside the CPU, so it still applies, just less visibly.
        ryao 2y ago
        He is improving the constant factor in big O notation. University algorithm classes tend to ignore cases where the constant factor difference is significant enough to favor a asymptomatically slower algorithm. Matrix multiplication is the quintessential example of this, since a good implementation of the O(n^3) algorithm will outperform asymptotically faster algorithms, such as the famous O(n^2 * log(n) * log(log(n))) one that uses the FFT. At least, it outperforms it on matrix multiplications people actually do in practice.
- plasticeagle 2y ago
  As a computer science article, it should have mostly been pseudocode. Concrete implementations can be given in an appendix, where they belong.
  - curiouscoding 2y ago
    The problem with pseudocode is that it's completely underspecified. And how would I ever write intrinsics in pseudocode? Much easier to do a proper language directly so people can actually Google things and read their official documentation.
    - deleted 2y ago
      [deleted]
    - sigbottle 2y ago
      My former roommate works in a similar domain; https://dl.acm.org/doi/pdf/10.1145/3448016.3452841 https://dl.acm.org/doi/pdf/10.1145/3448016.3452841 is an example of a paper implementing intrinsics in pseudocode. They "unroll" the intrinsics with a comment saying that this is implemented with an intrinsic. Of course though, your blog isn't a paper, don't know why people are getting up in arms about it. 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.
- quotemstr 2y ago
  Rust is now common enough in the industry that everyone should be expected to at least read it, just like every programmer should be able to fizzbuzz in Python and JavaScript just as a matter of general technical literacy. There's no advanced Rust here and no concepts specific to the language. 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.
  - ryao 2y ago
    Here is a list of languages people can be generally expected to be able to read: * C * C++ * Java * JavaScript * Python It is the top 6 of the TIOBE index, minus C#: https://www.tiobe.com/tiobe-index/ 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.
    - quotemstr 2y ago
      Rust is where the action is though. It's not just about cumulative SLOC weight, but about mindshare among the "movers and shakers" of the industry. Think of it as a prestige language, an acrolect, you should at least vaguely know so that you can participate in the most challenging conversations in the field.
      - ryao 2y ago
        That is an interesting perspective. Here is my perspective. There are no popular projects that use Rust as a primary language. The current fashionable area of computers is machine learning. As far as high level languages go, you will see a mix of Python, C++ and perhaps a tiny bit of C there. Rust is nowhere to be seen. 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.
- deleted 2y ago
  [deleted]
- unrealhoang 2y ago
  What a weird thing to complain about. The Rust code in TFA are purely arithmetic and imperative function calls. Any C developer that is good enough to care about the algorithm mentioned will have no issue reading such Rust code, heck, they could even throw the code to chatgpt to translate for them no problem. 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.
  - quotemstr 2y ago
    > Regarding Python, how could such optimizations be implemented in Python? Generating LLVM bytecodes directly aside. 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.
  - ryao 2y ago
    I have not studied Rust and find its syntax alien. It looks like a cross between a functional language and C++. Trying to read it is like forcing myself to read Italian. I don’t know Italian, but have studied Spanish and Latin. I can sort of figure things out if I put in effort, but there is always uncertainty when I do. That is the problem with reading Rust. 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.
    - quotemstr 2y ago
      > Zig is expected to replace Rust one day 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.
- FridgeSeal 2y ago
  I have a far easier time reading Rust than C. Probably because it’s been years since I’ve had to do C, and I find some of the syntax and patterns quite C-specific and confusing. Python also does not express some of the important implementation details well enough in its standard syntax IMO: there’s no obvious delineation between references and pass by value in Python, borrowing, etc. 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.
  - ryao 2y ago
    The TIOBE index suggests that you are in a much smaller group than those who have difficulty reading Rust: https://www.tiobe.com/tiobe-index/ https://www.tiobe.com/tiobe-index/
    - coliveira 2y ago
      Yes, he is in a bubble.
- bawolff 2y ago
  I've never programmed in rust and i can understand find. 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.
- peutetre 2y ago
  Well, you can do the C implementation then. Don't see it as a problem, see it as an opportunity.
- tmtvl 2y ago
  Oh no, it would've been better if it was written using the most readable language: Scheme.
wolfgangK 2y ago
Amazingly thorough ! I love how the author leaves no stone unturned. I had no idea you could do the kind of low level efficiency shaving in Rust. I wonder how a C++ implementation with https://github.com/jfalcou/eve https://github.com/jfalcou/eve would compare.
- secondcoming 2y ago
  Have you used Eve successfully for anything? It’s very confusing, it took me far too long to uppercase a string with it.
  - wolfgangK 2y ago
    Just played a bit with it. Were you working with ASCII ? This example didn't work for you ? https://github.com/jfalcou/eve/blob/a141ba93048bb2916c2157a9dea3d36cbabb5666/examples/algorithms/using_existing/case_insensitive_equals.cpp#L42 https://github.com/jfalcou/eve/blob/a141ba93048bb2916c2157a9...
- curiouscoding 2y ago
  Thanks! It's somewhat tiring to not have loose ends, but I agree it pays off :) 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.
  - ant6n 2y ago
    You kind of lost me towards the end, so I’m not sure whether you attempted it, but I was wondering whether it would be possible for the internal nodes to store only the upper 8/16 bits (that are nonzero for the current subtree). This implies that one 64 byte cache line stores 32 or 64 entries instead of 16 (or better: 31 or 62/63, since u may need some bookkeeping dat). 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.
estebarb 2y ago
Recently I tried to optimize a set implementation and found that interpolation search works quite well, being competitive with HashSet in C# (both single digit ns for my use case), with zero memory overhead. Unfortunately, it only works well with uniform data, so I guess I'll give static search trees a try. This explanation was clear and extremelly well detailed.
- curiouscoding 2y ago
  At some point I was playing around with interpolation search on the human genome dataset, and it was really really terrible. It had some very bad worst case behaviour when the input data has big plateaus and you're searching for something around the edges of the plateau. This can be fixed by only using interpolation for the first few iterations and doing binary search for as long as needed afterwards, but that kills a lot of the predictability of the current approach. So while I really like it in theory, in practice I'm not quite convinced it can be made to work efficiently.
  - estebarb 2y ago
    There are tricks: if you need to find uniformly distributed data it is unbeatable: guaranteed to work in 5 hops or less. After 5 hops, is better to use binary search. If data is not uniformly distributed one trick is to sort by hash of the element (store the hash with the element or calculate on the fly). But yeah, without those adjustments it has a worst case of O(n).
koverstreet 2y ago
Nifty thing about eytzinger trees is that there's a formula for converting from a node index to its position in an inorder traversal. 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.
- curiouscoding 2y ago
  You're right. While I wasn't very explicit about this (because algorithmica and the linked paper spend plenty of words on it already), the code snippet for Eytzinger does indeed do both the prefetching and the formula. 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.
sujayakar 2y ago
this is unbelievably cool. ~27ns overhead for searching for a u32 in a 4GB set in memory is unreal. 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.
- curiouscoding 2y ago
  Just fyi: the throughput numbers with batching are per _query_, not per _batch_, so I think the *8 is too optimistic ") 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).
- Bulat_Ziganshin 2y ago
  with m/t, the algorithm is memory-bound, so the performance should be determined strictly by the memory throughput
orlp 2y ago
One dimension that is not explored is partitioning the queries in batches. The primary cost is doing lookups on the out-of-cache table, so if you have a sufficiently large amount of queries you can resolve a couple layers of the tree in one step while those layers are in cache, grouping them based on where they land deeper in the tree, and then resolving all those queries that touch the same deeper part of the tree in one batch as well. 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.
- mikepurvis 2y ago
  Interesting stuff, definitely the kind of real world optimization that happens when you’re able to look at actual access characteristics rather highly abstracted models. 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.
- koverstreet 2y ago
  That presumes there's both locality in your queries, and it's not an online system - result latency doesn't matter much. That's not terribly common.
- tmyklebu 2y ago
  There are theory papers on "buffer trees"---B-trees where each node is augmented with an O(B)-length array of pending updates and queries. I believe there were also some attempts at building SQL databases based on them. It sounds like you're reaching for the same trick.
  - 2y ago
NooneAtAll3 2y ago
I wish graph did not show 2 values with the same blue color
- jasonjmcghee 2y ago
  It wasn't only the one graph - there's another graph that has a whole spectrum of blue colors - nearly impossible to tell which is which without going in with an eye drop tool. I found this to really detract from an otherwise interesting post.
  - curiouscoding 2y ago
    You're absolutely right. At some point I spent so long working on the plotting code that I really couldn't be bothered anymore to make it prettier. Hopefully I eventually find some motivation to fix this.
owenthejumper 2y ago
Elastic Binary Trees https://wtarreau.blogspot.com/2011/12/elastic-binary-trees-ebtree.html?m=1 https://wtarreau.blogspot.com/2011/12/elastic-binary-trees-e...
purple-leafy 2y ago
cant understand the comp sci stuff yet, but love the way this site looks
- curiouscoding 2y ago
  Thanks! I did spend some time fiddling with CSS to make the yellow highlights so that the titles stand out a bit more, and to improve the code blocks, but otherwise it's a relatively common theme for Hugo. (I think it's linked in the footer.)
shawn_w 2y ago
All this nattering about rust and C++, and then there's me thinking about how to do it in Common Lisp, possibly keeping the simd bits.
- wk_end 2y ago
  FWIW, I’d love to read a blog post about that, too.
  - shawn_w 2y ago
    I'm not up to that, but I have a working S-Tree builder and basic AVX2-using `lower-bound` for it (as described in the Algorithmica article linked to in the post) up and running in SBCL. Haven't played with any of the fancier optimizations yet, much less done any benchmarking. Should put it up in a gist or paste site to share...
colesantiago 2y ago
This is a great new interview question for junior and senior software engineering candidates. Definitely going to use this for our next round of interviews.
- butterlettuce 2y ago
  Please don’t. Just test us on how to center a div.
  - animal531 2y ago
    "Go ahead Junior, please implement this world class work and explain it to me as you go along. Oh, starting salary? No no, this is an unpaid 6 month internship." 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.
- Bulat_Ziganshin 2y ago
  it's how Google managed to convince young people all over the world to start reading those crappy A&DS books
openquery 2y ago
This is really interesting and a thorough write up. Thanks to the author for sharing their work. 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.
- curiouscoding 2y ago
  Assuming this is going to save someone 10ns per query in the end and I spent 150h on coding and writing this up, we only(?) need around 10^14 queries to make it worth it! But yes, as new technologies stack up, we achieve exponential growth in throughput in the end, which usually enables new science :)
DerSaidin 2y ago
I think there is an error in 1.7 figure 3: Layer 1 should have a 10 instead of a 12. Edit: Also, 1.3 figure 1: Should the y-axis label be "Inverse throughput" to match later figures?
- curiouscoding 2y ago
  You're right about the mistake in the figure. Will fix soon, thanks :) And yeah, maybe I should just label all of then with throughout for consistency.
vlovich123 2y ago
Is binary search on su ch large integer data sets common? I guess maybe time series data. But I would think that this isn’t amenable to representing strings?
- throw-qqqqq 2y ago
  Hash the string to convert to integer -> double hash or truncate to lowest 32 bits and this technique works for strings as well. You can replace string with any data structure you can hash or index really.
  - vlovich123 2y ago
    Ah but this then absolutely fails for range queries but makes sense if you want to build an index for point lookups.
    - throw-qqqqq 2y ago
      Definitely! If the integers are (truncated) hashes, ranges are completely meaningless. 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 :)
      - vlovich123 2y ago
        Range queries over strings are extremely common. For example, databases like cockroachdb and yuggabytedb use the table name as a prefix which then requires a range query to narrow down queries against a specific table.
        throw-qqqqq 2y ago
        Ah, I misunderstood what you meant by range :) 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 :)
swiftcoder 2y ago
Absolutely love the level of detail here! Not often you see the process of optimising something spelled out in so much depth
astronautas 2y ago
Cool! Thanks for the investigation.
starlite-5008 2y ago
[dead]
topbanana 2y ago
Interesting. If you need to support occasional writes, you could have a large static search tree and a small writable tree that you check afterwards. The when you have enough changes, you could occasionally ship those changes into a new version of the static tree
skrebbel 2y ago
Totally off topic, but I've started to notice that more and more algorithmic low-ish level content assumes Rust by default. My entire life I've been used to anything algorithmic being either written in sciency pseudocode (invariably in latex-generated PDFs), or plain old C(++), the vulgar latin of computer programming. I know C and I don't really know Rust but nevertheless I love that this is changing! I'd never advise a new programmer interested in low-level/fast stuff to begin with C now, so much good content is written around Rust. Like the old C examples, the post doesn't even say "this is Rust". You're expected to expect it to be Rust. 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.
- uecker 2y ago
  This assumes that Rust is actually a better language. IMHO it isn't.
  - norman784 2y ago
    I would argue that in some sense it is, just because of the enforced safety and correctness.
    - peoplefromibiza 2y ago
      So it's Ada since 1980, before C++ was even created.
      - sroussey 2y ago
        I wrote my first optimizing compiler for Ada in C++ around 1990.
gorset 2y ago
The number of unique int32 values is not that great, and a full bitset would only be 512MB. Hard to bit a dense bitset in performance. 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 https://sux.di.unimi.it).
- curiouscoding 2y ago
  Hmm, bitmaps is an interesting idea! If the data is dense enough, then yeah I guess a quick linear scan would work. 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/ https://curiouscoding.nl/posts/ptrhash-paper/ and the first post linked from there.
  - gorset 2y ago
    Nice work! I love the care and discussion around low level optimizations, as such things are often ignored. 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.
deleted 2y ago
[deleted]
jules 2y ago
Nice post. Would the larger amount of code result in different performance in a scenario where other code is being run as well, or would the instruction cache be large enough to make this a non-issue?
nielsole 2y ago
I've never had the use case for this amount of throughput. What are use-cases for this. From the website I presume this is gene-matching related?
- curiouscoding 2y ago
  Jup. I've added to the future work section now that the plan is to use this to speed up suffix array searching. Suffix arrays are pretty regularly used to build indices over say a human genome, that can then be queried. And since DNA sequencers are still increasing there throughput and accuracy, it's always good to have faster algorithms as well.
- marginalia_nu 2y ago
  I'm using a variant of static search trees in my search engine index though in this scenario the main bottleneck is block reads from disk, but the thinking is relatively similar to cache lines. Use case is to query hundreds of gigabytes of data in tens of milliseconds. (Skiplists is also used by some search engines.)
- Bulat_Ziganshin 2y ago
  JOIN SQL operation is another usecase
jokoon 2y ago
so a tree when the data cannot be updated? What is the point?
- curiouscoding 2y ago
  I've added a little motivation section on this :) 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.
xpe 2y ago
I predict that more and more of these kinds of optimized algorithms will be designed / written / assisted by machines. I wonder when the next such malicious algorithm(s) passes under our noses, and what its hidden purpose might be.
anamax 2y ago
This looks like something that patricia trees would be good for. Then again, Eytzinger looks like binary heaps.
amluto 2y ago
Given the fact that the keys are fixed-size integers with a not-too-terrible distribution, I would consider chasing the partitioning idea a bit harder, and possibly even removing all the fancy S-tree parts. Some ideas: 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.

656 points by atombender 2y ago

suffix-array-searching/static-search-tree/src/s_tree.rs: https://github.com/RagnarGrootKoerkamp/suffix-array-searching/blob/master/static-search-tree/src/s_tree.rs https://github.com/RagnarGrootKoerkamp/suffix-array-searchin... partitioned_s_tree.rs: https://github.com/RagnarGrootKoerkamp/suffix-array-searching/blob/master/static-search-tree/src/partitioned_s_tree.rs https://github.com/RagnarGrootKoerkamp/suffix-array-searchin...

ryao 2y ago

This would have been easier for a larger number of people to read if it had been in C or Python.

kubb 2y ago
Maybe, but should the author really cater to people who can’t overcome a language barrier? They probably won’t understand the concept anyway.
- ryao 2y ago
  The ACM for a time only accepted code examples in ALGOL because it was felt that there should be a standard language that everyone understood. ALGOL eventually gave way to C and others, but there is definite value in ensuring things are accessible to the largest possible audience.
  - dxbydt 2y ago
    usaco explicitly nudges you towards C++ on the first page itself. problems are graded on running time, even with moderately large datasets, Python simply doesn’t make the cut. So most high schoolers end up using C++ for usaco, and Java for AP Comp Science.
  - kubb 2y ago
    You're free to use ALGOL in your posts if you want. It reads like pseudocode used in algorithmic books, and should be familiar to anyone who used the Pascal family. 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.
    - ryao 2y ago
      The point was that examples should be in widely understood languages. The niche languages you list do not qualify as widely understood. Estne melius scribere exempla latine?
  - mplanchard 2y ago
    This is someone’s blog, not an ACM publication. Why hold it to the same standard? They can write in whatever they like. I have a hard time reading Haskell, but I don’t sit and kvetch about it anytime someone wants to use it in a blog post.
- mangamadaiyan 2y ago
  Erm, the concepts that you're referring to are independent of the language being used. The author is free to use whatever language they want. The GP (I think) was merely trying to make a point about making the article accessible to a wider audience that is capable of appreciating the concepts involved.
  - kubb 2y ago
    If you can't understand the code snippets in this post, the concepts will most likely be lost on you, no matter what other language would be used for the code.
    - deleted 2y ago
      [deleted]
    - mangamadaiyan 2y ago
      Isn't that precisely the point that the GP was trying to make, about the accessibility of the article? 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.
  - ryao 2y ago
    You are correct.
Rendello 2y ago
I wonder what percentage of Rust users have significant experience with C. The difficulty curve of Rust was too high for me when I was coming from Python, but after doing HolyC and Zig, I find it fairly straightforward to conceptualize, though still difficult. 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.
barbegal 2y ago
Neither of those languages gives you portable SIMD. Rust is rapidly becoming the language of choice for high performance code.
- npalli 2y ago
  google has a mature C++ library for portable SIMD. The original article seems to be a translation of the excellent algorithmica site which had it in C++. https://github.com/google/highway https://github.com/google/highway
  - ryao 2y ago
    You can do portable SIMD in GNU C/C++ using the vector extension: https://gcc.gnu.org/onlinedocs/gcc/Vector-Extensions.html https://gcc.gnu.org/onlinedocs/gcc/Vector-Extensions.html
    - swiftcoder 2y ago
      I'm not sure that "portable" and "only works on one specific compiler vendor" are very compatible concepts
      - bigpingo 2y ago
        gcc is available on and targets more platforms than rust. So if GNU C is not considered portable you can forget about 'portable rust'.
        swiftcoder 2y ago
        Portability in the C and C++ worlds generally means across standard-conforming compilers, not just across platforms
wolfgangK 2y ago
I don't think that Python would be the right language for such low-level performance maxxing endeavor. I would have picked C++ but t was eye opening for me to see how rust enabled such low level optimization, so I'm grateful for the choice.
- curiouscoding 2y ago
  Yeah, I don't think python is the right tool here. C++ definitely would be an option though. Anyway very happy that this is also showing off what rust can do
  - ryao 2y ago
    As far as I can tell, the community is largely divided into three major groups. Those that can read C, those that can read Python and those that can read both. Using either of them would have dodged criticism that your code examples are not accessible to much of the community. 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.
  - oguz-ismail 2y ago
    > this is also showing off what rust can do To people who already know Rust, yes. To others, not so much
- ryao 2y ago
  C would be useful to the broadest audience. C++ programmers can read C while C programmers cannot always read C++, especially when the newer language constructs are used. I mentioned Python because of its popularity. Interesting, the Algorithmica article the author cited is in C: https://en.algorithmica.org/hpc/data-structures/s-tree/ https://en.algorithmica.org/hpc/data-structures/s-tree/
  - npalli 2y ago
    C++ not C. The author explains his choices elsewhere in the site.
pxmpxm 2y ago
I suspect like 9/10 of these type of articles are really just meant to be PR for rust. Like someone that wants to write Bart Simpsonensque "rust is great" over and over, but have to hide it into something more interesting.
- curiouscoding 2y ago
  Rust is great :") 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.
  - jackschultz 2y ago
    Great stuff. We get told O notation is what matters for data structures / algorithms, but improvements low level with memory and storage with things like rust is much more where improves can be made. These types of tricks for anctual run times are so valuable, and interesting to follow.
    - curiouscoding 2y ago
      Ohh yeah, don't get me started in big-O... 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).
      - Andys 2y ago
        You're really just exploiting hidden O(?) implementations inside the CPU, so it still applies, just less visibly.
        ryao 2y ago
        He is improving the constant factor in big O notation. University algorithm classes tend to ignore cases where the constant factor difference is significant enough to favor a asymptomatically slower algorithm. Matrix multiplication is the quintessential example of this, since a good implementation of the O(n^3) algorithm will outperform asymptotically faster algorithms, such as the famous O(n^2 * log(n) * log(log(n))) one that uses the FFT. At least, it outperforms it on matrix multiplications people actually do in practice.
plasticeagle 2y ago
As a computer science article, it should have mostly been pseudocode. Concrete implementations can be given in an appendix, where they belong.
- curiouscoding 2y ago
  The problem with pseudocode is that it's completely underspecified. And how would I ever write intrinsics in pseudocode? Much easier to do a proper language directly so people can actually Google things and read their official documentation.
  - deleted 2y ago
    [deleted]
  - sigbottle 2y ago
    My former roommate works in a similar domain; https://dl.acm.org/doi/pdf/10.1145/3448016.3452841 https://dl.acm.org/doi/pdf/10.1145/3448016.3452841 is an example of a paper implementing intrinsics in pseudocode. They "unroll" the intrinsics with a comment saying that this is implemented with an intrinsic. Of course though, your blog isn't a paper, don't know why people are getting up in arms about it. 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.
quotemstr 2y ago
Rust is now common enough in the industry that everyone should be expected to at least read it, just like every programmer should be able to fizzbuzz in Python and JavaScript just as a matter of general technical literacy. There's no advanced Rust here and no concepts specific to the language. 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.
- ryao 2y ago
  Here is a list of languages people can be generally expected to be able to read: * C * C++ * Java * JavaScript * Python It is the top 6 of the TIOBE index, minus C#: https://www.tiobe.com/tiobe-index/ 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.
  - quotemstr 2y ago
    Rust is where the action is though. It's not just about cumulative SLOC weight, but about mindshare among the "movers and shakers" of the industry. Think of it as a prestige language, an acrolect, you should at least vaguely know so that you can participate in the most challenging conversations in the field.
    - ryao 2y ago
      That is an interesting perspective. Here is my perspective. There are no popular projects that use Rust as a primary language. The current fashionable area of computers is machine learning. As far as high level languages go, you will see a mix of Python, C++ and perhaps a tiny bit of C there. Rust is nowhere to be seen. 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.
deleted 2y ago
[deleted]
unrealhoang 2y ago
What a weird thing to complain about. The Rust code in TFA are purely arithmetic and imperative function calls. Any C developer that is good enough to care about the algorithm mentioned will have no issue reading such Rust code, heck, they could even throw the code to chatgpt to translate for them no problem. 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.
- quotemstr 2y ago
  > Regarding Python, how could such optimizations be implemented in Python? Generating LLVM bytecodes directly aside. 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.
- ryao 2y ago
  I have not studied Rust and find its syntax alien. It looks like a cross between a functional language and C++. Trying to read it is like forcing myself to read Italian. I don’t know Italian, but have studied Spanish and Latin. I can sort of figure things out if I put in effort, but there is always uncertainty when I do. That is the problem with reading Rust. 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.
  - quotemstr 2y ago
    > Zig is expected to replace Rust one day 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.
FridgeSeal 2y ago
I have a far easier time reading Rust than C. Probably because it’s been years since I’ve had to do C, and I find some of the syntax and patterns quite C-specific and confusing. Python also does not express some of the important implementation details well enough in its standard syntax IMO: there’s no obvious delineation between references and pass by value in Python, borrowing, etc. 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.
- ryao 2y ago
  The TIOBE index suggests that you are in a much smaller group than those who have difficulty reading Rust: https://www.tiobe.com/tiobe-index/ https://www.tiobe.com/tiobe-index/
  - coliveira 2y ago
    Yes, he is in a bubble.
bawolff 2y ago
I've never programmed in rust and i can understand find. 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.
peutetre 2y ago
Well, you can do the C implementation then. Don't see it as a problem, see it as an opportunity.
tmtvl 2y ago
Oh no, it would've been better if it was written using the most readable language: Scheme.

wolfgangK 2y ago

Amazingly thorough ! I love how the author leaves no stone unturned. I had no idea you could do the kind of low level efficiency shaving in Rust. I wonder how a C++ implementation with https://github.com/jfalcou/eve https://github.com/jfalcou/eve would compare.

secondcoming 2y ago
Have you used Eve successfully for anything? It’s very confusing, it took me far too long to uppercase a string with it.
- wolfgangK 2y ago
  Just played a bit with it. Were you working with ASCII ? This example didn't work for you ? https://github.com/jfalcou/eve/blob/a141ba93048bb2916c2157a9dea3d36cbabb5666/examples/algorithms/using_existing/case_insensitive_equals.cpp#L42 https://github.com/jfalcou/eve/blob/a141ba93048bb2916c2157a9...
curiouscoding 2y ago
Thanks! It's somewhat tiring to not have loose ends, but I agree it pays off :) 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.
- ant6n 2y ago
  You kind of lost me towards the end, so I’m not sure whether you attempted it, but I was wondering whether it would be possible for the internal nodes to store only the upper 8/16 bits (that are nonzero for the current subtree). This implies that one 64 byte cache line stores 32 or 64 entries instead of 16 (or better: 31 or 62/63, since u may need some bookkeeping dat). 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.

estebarb 2y ago

Recently I tried to optimize a set implementation and found that interpolation search works quite well, being competitive with HashSet in C# (both single digit ns for my use case), with zero memory overhead. Unfortunately, it only works well with uniform data, so I guess I'll give static search trees a try. This explanation was clear and extremelly well detailed.

curiouscoding 2y ago
At some point I was playing around with interpolation search on the human genome dataset, and it was really really terrible. It had some very bad worst case behaviour when the input data has big plateaus and you're searching for something around the edges of the plateau. This can be fixed by only using interpolation for the first few iterations and doing binary search for as long as needed afterwards, but that kills a lot of the predictability of the current approach. So while I really like it in theory, in practice I'm not quite convinced it can be made to work efficiently.
- estebarb 2y ago
  There are tricks: if you need to find uniformly distributed data it is unbeatable: guaranteed to work in 5 hops or less. After 5 hops, is better to use binary search. If data is not uniformly distributed one trick is to sort by hash of the element (store the hash with the element or calculate on the fly). But yeah, without those adjustments it has a worst case of O(n).

koverstreet 2y ago

Nifty thing about eytzinger trees is that there's a formula for converting from a node index to its position in an inorder traversal. 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.

curiouscoding 2y ago
You're right. While I wasn't very explicit about this (because algorithmica and the linked paper spend plenty of words on it already), the code snippet for Eytzinger does indeed do both the prefetching and the formula. 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.

sujayakar 2y ago

this is unbelievably cool. ~27ns overhead for searching for a u32 in a 4GB set in memory is unreal. 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.

curiouscoding 2y ago
Just fyi: the throughput numbers with batching are per _query_, not per _batch_, so I think the *8 is too optimistic ") 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).
Bulat_Ziganshin 2y ago
with m/t, the algorithm is memory-bound, so the performance should be determined strictly by the memory throughput

orlp 2y ago

One dimension that is not explored is partitioning the queries in batches. The primary cost is doing lookups on the out-of-cache table, so if you have a sufficiently large amount of queries you can resolve a couple layers of the tree in one step while those layers are in cache, grouping them based on where they land deeper in the tree, and then resolving all those queries that touch the same deeper part of the tree in one batch as well. 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.

mikepurvis 2y ago
Interesting stuff, definitely the kind of real world optimization that happens when you’re able to look at actual access characteristics rather highly abstracted models. 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.
koverstreet 2y ago
That presumes there's both locality in your queries, and it's not an online system - result latency doesn't matter much. That's not terribly common.
tmyklebu 2y ago
There are theory papers on "buffer trees"---B-trees where each node is augmented with an O(B)-length array of pending updates and queries. I believe there were also some attempts at building SQL databases based on them. It sounds like you're reaching for the same trick.
- 2y ago

NooneAtAll3 2y ago

I wish graph did not show 2 values with the same blue color

jasonjmcghee 2y ago
It wasn't only the one graph - there's another graph that has a whole spectrum of blue colors - nearly impossible to tell which is which without going in with an eye drop tool. I found this to really detract from an otherwise interesting post.
- curiouscoding 2y ago
  You're absolutely right. At some point I spent so long working on the plotting code that I really couldn't be bothered anymore to make it prettier. Hopefully I eventually find some motivation to fix this.

owenthejumper 2y ago

Elastic Binary Trees https://wtarreau.blogspot.com/2011/12/elastic-binary-trees-ebtree.html?m=1 https://wtarreau.blogspot.com/2011/12/elastic-binary-trees-e...

purple-leafy 2y ago

cant understand the comp sci stuff yet, but love the way this site looks

curiouscoding 2y ago
Thanks! I did spend some time fiddling with CSS to make the yellow highlights so that the titles stand out a bit more, and to improve the code blocks, but otherwise it's a relatively common theme for Hugo. (I think it's linked in the footer.)

shawn_w 2y ago

All this nattering about rust and C++, and then there's me thinking about how to do it in Common Lisp, possibly keeping the simd bits.

wk_end 2y ago
FWIW, I’d love to read a blog post about that, too.
- shawn_w 2y ago
  I'm not up to that, but I have a working S-Tree builder and basic AVX2-using `lower-bound` for it (as described in the Algorithmica article linked to in the post) up and running in SBCL. Haven't played with any of the fancier optimizations yet, much less done any benchmarking. Should put it up in a gist or paste site to share...

colesantiago 2y ago

This is a great new interview question for junior and senior software engineering candidates. Definitely going to use this for our next round of interviews.

butterlettuce 2y ago
Please don’t. Just test us on how to center a div.
- animal531 2y ago
  "Go ahead Junior, please implement this world class work and explain it to me as you go along. Oh, starting salary? No no, this is an unpaid 6 month internship." 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.
Bulat_Ziganshin 2y ago
it's how Google managed to convince young people all over the world to start reading those crappy A&DS books

openquery 2y ago

This is really interesting and a thorough write up. Thanks to the author for sharing their work. 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.

curiouscoding 2y ago
Assuming this is going to save someone 10ns per query in the end and I spent 150h on coding and writing this up, we only(?) need around 10^14 queries to make it worth it! But yes, as new technologies stack up, we achieve exponential growth in throughput in the end, which usually enables new science :)

DerSaidin 2y ago

I think there is an error in 1.7 figure 3: Layer 1 should have a 10 instead of a 12. Edit: Also, 1.3 figure 1: Should the y-axis label be "Inverse throughput" to match later figures?

curiouscoding 2y ago
You're right about the mistake in the figure. Will fix soon, thanks :) And yeah, maybe I should just label all of then with throughout for consistency.

vlovich123 2y ago

Is binary search on su ch large integer data sets common? I guess maybe time series data. But I would think that this isn’t amenable to representing strings?

throw-qqqqq 2y ago
Hash the string to convert to integer -> double hash or truncate to lowest 32 bits and this technique works for strings as well. You can replace string with any data structure you can hash or index really.
- vlovich123 2y ago
  Ah but this then absolutely fails for range queries but makes sense if you want to build an index for point lookups.
  - throw-qqqqq 2y ago
    Definitely! If the integers are (truncated) hashes, ranges are completely meaningless. 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 :)
    - vlovich123 2y ago
      Range queries over strings are extremely common. For example, databases like cockroachdb and yuggabytedb use the table name as a prefix which then requires a range query to narrow down queries against a specific table.
      - throw-qqqqq 2y ago
        Ah, I misunderstood what you meant by range :) 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 :)

swiftcoder 2y ago

Absolutely love the level of detail here! Not often you see the process of optimising something spelled out in so much depth

astronautas 2y ago

Cool! Thanks for the investigation.

starlite-5008 2y ago

[dead]

topbanana 2y ago

Interesting. If you need to support occasional writes, you could have a large static search tree and a small writable tree that you check afterwards. The when you have enough changes, you could occasionally ship those changes into a new version of the static tree

skrebbel 2y ago

Totally off topic, but I've started to notice that more and more algorithmic low-ish level content assumes Rust by default. My entire life I've been used to anything algorithmic being either written in sciency pseudocode (invariably in latex-generated PDFs), or plain old C(++), the vulgar latin of computer programming. I know C and I don't really know Rust but nevertheless I love that this is changing! I'd never advise a new programmer interested in low-level/fast stuff to begin with C now, so much good content is written around Rust. Like the old C examples, the post doesn't even say "this is Rust". You're expected to expect it to be Rust. 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.

uecker 2y ago
This assumes that Rust is actually a better language. IMHO it isn't.
- norman784 2y ago
  I would argue that in some sense it is, just because of the enforced safety and correctness.
  - peoplefromibiza 2y ago
    So it's Ada since 1980, before C++ was even created.
    - sroussey 2y ago
      I wrote my first optimizing compiler for Ada in C++ around 1990.

gorset 2y ago

The number of unique int32 values is not that great, and a full bitset would only be 512MB. Hard to bit a dense bitset in performance. 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 https://sux.di.unimi.it).

curiouscoding 2y ago
Hmm, bitmaps is an interesting idea! If the data is dense enough, then yeah I guess a quick linear scan would work. 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/ https://curiouscoding.nl/posts/ptrhash-paper/ and the first post linked from there.
- gorset 2y ago
  Nice work! I love the care and discussion around low level optimizations, as such things are often ignored. 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.

deleted 2y ago

[deleted]

jules 2y ago

Nice post. Would the larger amount of code result in different performance in a scenario where other code is being run as well, or would the instruction cache be large enough to make this a non-issue?

nielsole 2y ago

I've never had the use case for this amount of throughput. What are use-cases for this. From the website I presume this is gene-matching related?

curiouscoding 2y ago
Jup. I've added to the future work section now that the plan is to use this to speed up suffix array searching. Suffix arrays are pretty regularly used to build indices over say a human genome, that can then be queried. And since DNA sequencers are still increasing there throughput and accuracy, it's always good to have faster algorithms as well.
marginalia_nu 2y ago
I'm using a variant of static search trees in my search engine index though in this scenario the main bottleneck is block reads from disk, but the thinking is relatively similar to cache lines. Use case is to query hundreds of gigabytes of data in tens of milliseconds. (Skiplists is also used by some search engines.)
Bulat_Ziganshin 2y ago
JOIN SQL operation is another usecase

jokoon 2y ago

so a tree when the data cannot be updated? What is the point?

curiouscoding 2y ago
I've added a little motivation section on this :) 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.

xpe 2y ago

I predict that more and more of these kinds of optimized algorithms will be designed / written / assisted by machines. I wonder when the next such malicious algorithm(s) passes under our noses, and what its hidden purpose might be.

anamax 2y ago

This looks like something that patricia trees would be good for. Then again, Eytzinger looks like binary heaps.

amluto 2y ago

Given the fact that the keys are fixed-size integers with a not-too-terrible distribution, I would consider chasing the partitioning idea a bit harder, and possibly even removing all the fancy S-tree parts. Some ideas: 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.