3 ms·

A High Throughput B+tree for SIMD Architectures (2020) [pdf]

133 points by mfiguiere 3y ago

rurban 3y ago
This, Harmonia, is 3 years old. Code is here: https://github.com/JustKshitijD/Harmonia_for_B_plus_trees https://github.com/JustKshitijD/Harmonia_for_B_plus_trees
- chokolad 3y ago
  [flagged]
- dboreham 3y ago
  Quite a while since I saw a file named a.out !
Const-me 3y ago
I once needed that thing (with 32-bit integer keys, and either FP32 or FP64 values), but I didn’t want to spend too much time designing novel data structures. I have copy-pasted B+ tree from TLX https://github.com/tlx/tlx https://github.com/tlx/tlx (Boost license), and then I did some local changes to improve the performance for my specific keys and value types. I have used AVX2 intrinsics to improve search within nodes, and I also implemented a few more simple tricks. After these changes, the performance became satisfactory for my application.
- slashdev 3y ago
  That was smart. I once did a similar thing, but I built it from scratch. A good learning experience, but man it was a lot of work. I changed from SIMD to branchless though. Branchless binary search inside a node, plus branchless search through the tree (with a fixed max height.) The only branch was to test if the item was found or not at the end. And that’s predictable usually, depending on the workload. I wanted to combine multiple searches over multiple trees using SIMD to batch the execution, but I never got around to that.
- kolbe 3y ago
  I've gone through a similar exercises with other trees, but I learned that much of the improvement I attributed to AVX was actually due to exploiting the idea that non-blocking operations done on data in the register are essentially free. The nice thing about AVX was that it forced me to write the code that way, but the bulk of the improvement was actually due to writing code in an unintuitive, but machine-optimal way.
  - cmrdporcupine 3y ago
    I found this, too. Spent a bunch of time optimizing with SIMD intrinsics only to find that the real win was the array-oriented-style I made along the way. Also a lot of assumptions from the past start to erode with the memory architecture and cache performance we have today. Things where one would reach for binary search or hash table before end up getting outperformed by linear scan, as long as the set of data fits roughly in a cache line, etc. It's possible that in this day and age we'd all just be better off writing actually performance critical stuff in an APL offshoot, with the language forcing one to steer away from branching and dispatch whenever possible and deal with data in declared, bulk, array/vector-type operations.
    - kolbe 3y ago
      In my experience, linear can outperform even on larger sizes. This looks like a pretty robust analysis comparing linear and binary search: https://dirtyhandscoding.github.io/posts/performance-comparison-linear-search-vs-binary-search.html https://dirtyhandscoding.github.io/posts/performance-compari...
      - jeeeb 3y ago
        In my experience using linear search it’s easy to introduce accidental O(n^2) time complexity into a function, which can really come back to bite you. The benchmark linked looks like the best case for linear search - searching a packed array of ints. Even then from the results after just 256 elements binary search starts to win out (comparing the optimised implementations of both). By 1024 elements the difference between O(log N) and O(N) complexity is clearly starting to dominate the results. For more complex comparison functions, and pointer indirections (e.g. searching arrays of heap allocated objects), I’d assume the lower time complexity of binary search would dominate results even more.

133 points by mfiguiere 3y ago

This, Harmonia, is 3 years old. Code is here: https://github.com/JustKshitijD/Harmonia_for_B_plus_trees https://github.com/JustKshitijD/Harmonia_for_B_plus_trees

chokolad 3y ago
[flagged]
dboreham 3y ago
Quite a while since I saw a file named a.out !

Const-me 3y ago

I once needed that thing (with 32-bit integer keys, and either FP32 or FP64 values), but I didn’t want to spend too much time designing novel data structures. I have copy-pasted B+ tree from TLX https://github.com/tlx/tlx https://github.com/tlx/tlx (Boost license), and then I did some local changes to improve the performance for my specific keys and value types. I have used AVX2 intrinsics to improve search within nodes, and I also implemented a few more simple tricks. After these changes, the performance became satisfactory for my application.

slashdev 3y ago
That was smart. I once did a similar thing, but I built it from scratch. A good learning experience, but man it was a lot of work. I changed from SIMD to branchless though. Branchless binary search inside a node, plus branchless search through the tree (with a fixed max height.) The only branch was to test if the item was found or not at the end. And that’s predictable usually, depending on the workload. I wanted to combine multiple searches over multiple trees using SIMD to batch the execution, but I never got around to that.
kolbe 3y ago
I've gone through a similar exercises with other trees, but I learned that much of the improvement I attributed to AVX was actually due to exploiting the idea that non-blocking operations done on data in the register are essentially free. The nice thing about AVX was that it forced me to write the code that way, but the bulk of the improvement was actually due to writing code in an unintuitive, but machine-optimal way.
- cmrdporcupine 3y ago
  I found this, too. Spent a bunch of time optimizing with SIMD intrinsics only to find that the real win was the array-oriented-style I made along the way. Also a lot of assumptions from the past start to erode with the memory architecture and cache performance we have today. Things where one would reach for binary search or hash table before end up getting outperformed by linear scan, as long as the set of data fits roughly in a cache line, etc. It's possible that in this day and age we'd all just be better off writing actually performance critical stuff in an APL offshoot, with the language forcing one to steer away from branching and dispatch whenever possible and deal with data in declared, bulk, array/vector-type operations.
  - kolbe 3y ago
    In my experience, linear can outperform even on larger sizes. This looks like a pretty robust analysis comparing linear and binary search: https://dirtyhandscoding.github.io/posts/performance-comparison-linear-search-vs-binary-search.html https://dirtyhandscoding.github.io/posts/performance-compari...
    - jeeeb 3y ago
      In my experience using linear search it’s easy to introduce accidental O(n^2) time complexity into a function, which can really come back to bite you. The benchmark linked looks like the best case for linear search - searching a packed array of ints. Even then from the results after just 256 elements binary search starts to win out (comparing the optimised implementations of both). By 1024 elements the difference between O(log N) and O(N) complexity is clearly starting to dominate the results. For more complex comparison functions, and pointer indirections (e.g. searching arrays of heap allocated objects), I’d assume the lower time complexity of binary search would dominate results even more.