2 ms·
Binary Search Tree with SIMD
- rgovostes 2y agoThis 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 https://doi.org/10.1145/1807167.1807206) if this is of interest.
- dragontamer 2y agoThis 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?