[HN Gopher] A High Throughput B+tree for SIMD Architectures (202...
___________________________________________________________________
A High Throughput B+tree for SIMD Architectures (2020) [pdf]
Author : mfiguiere
Score : 116 points
Date : 2023-09-17 06:30 UTC (16 hours ago)
(HTM) web link (www.ece.lsu.edu)
(TXT) w3m dump (www.ece.lsu.edu)
| rurban wrote:
| This, Harmonia, is 3 years old.
|
| Code is here:
| https://github.com/JustKshitijD/Harmonia_for_B_plus_trees
| chokolad wrote:
| [flagged]
| dboreham wrote:
| Quite a while since I saw a file named a.out !
| Const-me wrote:
| 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
| (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.
| kolbe wrote:
| 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 wrote:
| 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 wrote:
| 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-
| compari...
| slashdev wrote:
| 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.
___________________________________________________________________
(page generated 2023-09-17 23:01 UTC)