Static search trees: 40x faster than binary search (curiouscoding.nl)
from tedu@inks.tedunangst.com to inks@inks.tedunangst.com on 02 Jan 01:18
https://inks.tedunangst.com/l/5137

In this post, we will implement a static search tree (S+ tree) for high-throughput searching of sorted data, as introduced on Algorithmica. We’ll mostly take the code presented there as a starting point, and optimize it to its limits. For a large part, I’m simply taking the ‘future work’ ideas of that post and implementing them. And then there will be a bunch of looking at assembly code to shave off all the instructions we can. Lastly, there will be one big addition to optimize throughput: batching.

https://en.algorithmica.org/hpc/data-structures/s-tree/

#compsci #perf #programming #rust

#compsci #inks #perf #programming #rust