Static search trees: 40x faster than binary search

This page summarizes the projects mentioned and recommended in the original post on news.ycombinator.com

Nutrient - The #1 PDF SDK Library
Bad PDFs = bad UX. Slow load times, broken annotations, clunky UX frustrates users. Nutrient’s PDF SDKs gives seamless document experiences, fast rendering, annotations, real-time collaboration, 100+ features. Used by 10K+ devs, serving ~half a billion users worldwide. Explore the SDK for free.
nutrient.io
featured
CodeRabbit: AI Code Reviews for Developers
Revolutionize your code reviews with AI. CodeRabbit offers PR summaries, code walkthroughs, 1-click suggestions, and AST-based analysis. Boost productivity and code quality across all major languages with each PR.
coderabbit.ai
featured
  1. eve

    Expressive Vector Engine - SIMD in C++ Goes Brrrr (by jfalcou)

    Just played a bit with it. Were you working with ASCII ? This example didn't work for you ? https://github.com/jfalcou/eve/blob/a141ba93048bb2916c2157a9...

  2. Nutrient

    Nutrient - The #1 PDF SDK Library. Bad PDFs = bad UX. Slow load times, broken annotations, clunky UX frustrates users. Nutrient’s PDF SDKs gives seamless document experiences, fast rendering, annotations, real-time collaboration, 100+ features. Used by 10K+ devs, serving ~half a billion users worldwide. Explore the SDK for free.

    Nutrient logo
  3. zfs

    OpenZFS on Linux and FreeBSD

    Your article led me to wonder if our b-trees would be faster if I switched the intra node operations to use Eytzinger ordered arrays:

    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. 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 O(1) 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.

  4. suffix-array-searching

    High throughput suffix array searching

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

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

  6. highway

    Performance-portable, length-agnostic SIMD with runtime dispatch

    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

  7. crates.io

    The Rust package registry

    I often hear this and am confused; not only are things like ['object soup'](https://jacko.io/object_soup.html) possible and straightforward (putting things in collections and referring to them by indices), I never concretely hear why a graph or doubly-linked list becomes uniquely difficult to implement in Rust (and would genuinely be curious to learn why you feel this way). If you needed such data structures anyway, they're either in the standard library or in the many libraries ('crates' in Rust-lingo) available on [Rust's package registry](https://crates.io/)---using dependencies in Rust is very straightforward & easy.

  8. cargo-make

    Rust task runner and build tool.

    Well, I don't use makefiles to deploy software with Rust. I also have never used lex or yacc, but I bet there are similar tools in the ecosystem, or wrappers for those. That would obviate what I will offer below.

    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. 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.

  9. CodeRabbit

    CodeRabbit: AI Code Reviews for Developers. Revolutionize your code reviews with AI. CodeRabbit offers PR summaries, code walkthroughs, 1-click suggestions, and AST-based analysis. Boost productivity and code quality across all major languages with each PR.

    CodeRabbit logo
  10. just

    🤖 Just a command runner

    Well, I don't use makefiles to deploy software with Rust. I also have never used lex or yacc, but I bet there are similar tools in the ecosystem, or wrappers for those. That would obviate what I will offer below.

    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. 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.

  11. rust-bindgen

    Automatically generates Rust FFI bindings to C (and some C++) libraries.

    Well, I don't use makefiles to deploy software with Rust. I also have never used lex or yacc, but I bet there are similar tools in the ecosystem, or wrappers for those. That would obviate what I will offer below.

    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. 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.

  12. rules_rust

    Rust rules for Bazel

    If you're embedding, say, a C library inside of Rust, you can do so via a so-called "build.rs" script [1]. These run at build time so you can do pretty much whatever you want. They're not necessarily pretty, but given that Cargo isn't going to support other languages natively, it's often a less-evil option.

    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/

    [3]: https://buck.build/rule/rust_library.html

    [4]: https://mesonbuild.com/Rust.html

  13. rebar

    A biased barometer for gauging the relative speed of some regex engines on a curated set of tasks.

    Not easily. But not all use cases require it. The regex crate makes heavy use of this pattern for finite machine states, for example. But this fits nicely with an arena allocation pattern, so everything can just be dropped at once.

    Despite this, it's I've of the fastest regex engines around: https://github.com/BurntSushi/rebar#summary-of-search-time-b...

  14. SingeliSort

    Sorting with Singeli

    I got stuck on sorting too, was working on SingeliSort (https://github.com/mlochbaum/SingeliSort) for a while. The basic performance is there but I need to get serious about testing before using it. But the radix sort and counting sort should be very solid. The approach is about the same as the C code currently used in CBQN, linked below. The main complication is to reduce constant overhead for shorter arrays with a small count type and better prefix sums, interleaved SWAR for SingeliSort since it targets generic architecture and shared SIMD utilities in CBQN.

    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...

  15. CBQN

    a BQN implementation in C

    I got stuck on sorting too, was working on SingeliSort (https://github.com/mlochbaum/SingeliSort) for a while. The basic performance is there but I need to get serious about testing before using it. But the radix sort and counting sort should be very solid. The approach is about the same as the C code currently used in CBQN, linked below. The main complication is to reduce constant overhead for shorter arrays with a small count type and better prefix sums, interleaved SWAR for SingeliSort since it targets generic architecture and shared SIMD utilities in CBQN.

    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...

NOTE: The number of mentions on this list indicates mentions on common posts plus user suggested alternatives. Hence, a higher number means a more popular project.

Suggest a related project

Related posts

  • C Is Not Suited to SIMD

    7 projects | news.ycombinator.com | 27 Jan 2025
  • Similarity Measures on Arm SVE and NEON, x86 AVX2 and AVX-512

    2 projects | /r/simd | 25 Mar 2023
  • Optimizing compilers reload vector constants needlessly

    7 projects | news.ycombinator.com | 6 Dec 2022
  • Vc 1.4.2 released: portable SIMD programming for C++

    3 projects | /r/cpp | 23 Jun 2021
  • Expressive Vector Engine – SIMD in C++

    6 projects | news.ycombinator.com | 5 Jan 2025