Efficiently Searching In-Memory Sorted Arrays: Revenge of Interpolation Search? [pdf]

• Efficiently-Searching-In-Memory-Sorted-Arrays

  1 26 10.0 C++

  Efficiently Searching In-Memory Sorted Arrays:Revenge of the Interpolation Search?

  

Big fan on your presentation on binary search that amortised multiple concurrent searches. I did several variations on binary search and always compared against the best one. [0] From what I remember, some variations were compiled to a branchless implementation and some were compiled to implementations that used a branch. I had many passes of analysis by pasting into godbolt with identical compilers and flags. Power of 2 binary search did better on small arrays iirc, but are the first to hit conflict misses. For larger arrays, I believe the branchy search algorithms start to do better since half their branches get predicted correctly.

I haven't looked at ITP, and other than being cautious about the cost I've seen of unrelated hybrid algorithms, I would need a substantial amount of time to analyze it enough to comment further. I'm on the BQN discord if you wanted a different form of communication.

[0] https://github.com/UWHustle/Efficiently-Searching-In-Memory-...

• Efficiently-Searching-In-Memory-

  1 - -

Big fan on your presentation on binary search that amortised multiple concurrent searches. I did several variations on binary search and always compared against the best one. [0] From what I remember, some variations were compiled to a branchless implementation and some were compiled to implementations that used a branch. I had many passes of analysis by pasting into godbolt with identical compilers and flags. Power of 2 binary search did better on small arrays iirc, but are the first to hit conflict misses. For larger arrays, I believe the branchy search algorithms start to do better since half their branches get predicted correctly.

I haven't looked at ITP, and other than being cautious about the cost I've seen of unrelated hybrid algorithms, I would need a substantial amount of time to analyze it enough to comment further. I'm on the BQN discord if you wanted a different form of communication.

[0] https://github.com/UWHustle/Efficiently-Searching-In-Memory-...

• InfluxDB

  www.influxdata.com featured

  Power Real-Time Data Analytics at Scale. Get real-time insights from all types of time series data with InfluxDB. Ingest, query, and analyze billions of data points in real-time with unbounded cardinality.

  

Suggest a related project