[HN Gopher] Binary Search Tree with SIMD
       ___________________________________________________________________
        
       Binary Search Tree with SIMD
        
       Author : ingve
       Score  : 18 points
       Date   : 2024-07-12 19:06 UTC (5 days ago)
        
 (HTM) web link (clement-jean.github.io)
 (TXT) w3m dump (clement-jean.github.io)
        
       | rgovostes wrote:
       | This article doesn't make a lot of sense to me. It avoids using
       | computer science terminology (like "tree traversal") that would
       | clarify the author's intent here.
       | 
       | I don't follow at all the example of searching for the number 62,
       | deciding that the triplet 41-23-61 contains all numbers greater
       | than 62, and then deciding to "access the 4th child" 73-67-79 --
       | what is the 4th child in a binary tree? How do we determine the
       | index to move to in our flattened array?
       | 
       | It would probably be better to read the original paper "FAST:
       | Fast Architecture Sensitive Tree Search on Modern CPUs and GPUs"
       | (https://doi.org/10.1145/1807167.1807206) if this is of interest.
        
       | dragontamer wrote:
       | This is non-intuitive to me.
       | 
       | I'd expect that the natural SIMD-extension to a binary search
       | tree would be a 4-BTree (assuming 4-elements compared per SIMD
       | unit).
       | 
       | For AVX512, I'd expect a 16-BTree to be used.
       | 
       | ----------
       | 
       | EDIT:
       | 
       | > The paper mentionned at the beginning, propose to have a binary
       | tree layed out like the following:
       | 
       | > And if you take time to understand how this maps back to the
       | binary tree, you will notice that we are storing parent-children
       | triangles. With this, we can now apply SIMD operations on both
       | the parent and the children in order to either dtermine if the
       | data we are looking for is in the triangle, or if we should
       | continue our search.
       | 
       | Hmmmmmmm. So maybe they are making a B-Tree here except not
       | calling it one?
        
       ___________________________________________________________________
       (page generated 2024-07-17 23:03 UTC)