Static search trees: faster than binary search
Static search trees are presented as a way to outperform binary search on large, read‑only sets of integers by exploiting CPU caches, SIMD instructions and batched queries, with applications in areas like bioinformatics indexes and search engines. Commenters praise the unusually detailed, low-level performance analysis while debating how much big‑O complexity still matters when constant‑factor and memory‑hierarchy optimizations can yield 10x speedups. A major side thread argues over the choice of Rust for the implementation—its safety, ecosystem and readability versus C/C++ or pseudocode—highlighting broader tensions around language accessibility and evolving “standard” systems languages.
Overall reception
- Many commenters found the write‑up unusually thorough and appreciated seeing low‑level optimization work laid out step by step.
- Some readers admitted the later SIMD and micro-optimizations were beyond their comfort zone but still valued the earlier conceptual parts.
- A few people explicitly linked this kind of work to real-world speedups that, in aggregate, save large amounts of human time.
Language choice and accessibility
- Large subthread on whether Rust was a good choice for examples.
- One side: C (or C++) is more universally readable; Python is popular for teaching; pseudocode is more language‑neutral.
- Other side: blog authors can pick any language; Rust is now common enough that developers should at least be able to read it; the code is mostly straightforward imperative logic.
- Some argued Python is not suitable for intrinsics and cache-level tuning; C/C++ or Rust are more appropriate.
- Debate over pseudocode: some want high-level pseudocode plus implementation appendix; others say pseudocode is too underspecified, especially for SIMD and cache-line details.
Rust vs other systems languages
- Rust praised for:
- Portable SIMD in the standard ecosystem.
- Tooling (cargo, build scripts) and safety model compared with C++.
- Counterpoints:
- Claims that C/C++ already have portable SIMD via libraries or compiler extensions.
- Concerns about Rust’s popularity (e.g., TIOBE rank) and long-term stability vs yet‑newer languages like Zig.
- Worries that relying on many third‑party crates is a security and legal risk.
- Discussion of how hard certain data structures (graphs, doubly‑linked lists) are in Rust’s ownership model unless using indices or reference counting.
Algorithmic and performance discussion
- Strong focus on constant‑factor speedups vs asymptotic big‑O; several note that practical wins often dwarf “better” theoretical algorithms.
- Comparisons with:
- Interpolation search (fast on uniform data, bad worst‑case behavior).
- Eytzinger layout and cache‑aware trees, prefetching, batching queries, and SIMD vectorization.
- B‑trees, buffer/fractal trees, compacting B‑tree variants, and static vs dynamic trees.
- Bitmap/bitset approaches, roaring bitmaps, rank/select structures, minimal perfect hashing.
- Ideas for further work: query partitioning and sorting, radix‑based schemes, compressed node representations, and van Emde Boas–style structures.
Use cases and practicality
- Mentioned applications: DNA/suffix‑array indexing, search engines, SQL joins, and static indexes with occasional writes via a small mutable overlay.
- Some skepticism about using such advanced material as interview questions; concern about mismatch with typical job work.
Presentation feedback
- Several complaints about graph color choices making lines hard to distinguish; author acknowledges this as a to‑do.