4 ms·

I think you could achieve something close to (I haven't sat down and thought about it) O(logN) with sorted arrays? You'd have the downside of inserting things i

I think you could achieve something close to (I haven't sat down and thought about it) O(logN) with sorted arrays? You'd have the downside of inserting things in the middle, but I think that would be lost in cache efficiency elsewhere for many use cases.

amluto 3y ago
A sorted array to less inefficiently iterate children of a node? This is getting ridiculous. The “no pointers” thing is cache efficient for three reasons: 1. Indices can be smaller than pointers. 2. The data is packed in memory. This means that cachelines will be full of relevant data, and adjacent cache lines (which are a bit faster than faraway lines) get used. 3. SOA form is more or less cache efficient depending on what you’re doing with it. And that’s it. If you need child pointers, use child pointers. If you want a cache-efficient tree, use a cache-efficient tree, e.g. a B-tree or an appropriate variant.
- alexchamberlain 3y ago
  Sorted arrays can be navigated like a tree. For sufficiently randomised data, the middle element is approximately the middle of your data. You can use binary search. You can implement range iteration very efficiently. It's not wholly ridiculous.
  - amluto 3y ago
    Binary search into a sorted array is slow. Intro algorithms classes might count operations, and you discover that about log_2(n) operations are needed, which is optimal in a certain sense. But those operations are horrible operations. Until you are log_2(cache line size / element size) steps from the leaves, you are hitting a different cache line each time, and you’re doing a branch such that the next cache line you want depends on the branch result. So this is like log_2(n)-3 serial (cache miss, compare, branch, compute address operations). (Assume 8-byte entries — it’s much worse with bigger entries.) This not even close to optimal. You will find that, for reasonably large data sets (maybe a few hundred elements or more?), any cache-optimized searchable data structure will beat binary search by a large factor. And for small arrays (or the last stage of an optimized large structure), you want a vectorized linear search. Binary search is mostly nice because sorted arrays are elegant and binary search can be implemented in very little code. And it’s easy to explain and analyze.
    - senderista 3y ago
      Eytzinger ("heap") layout packs the pivots as efficiently as possible, so cache misses are confined to the lower levels of the tree. But ordered iteration is slower, and of course it only works for static data. I agree that for dynamic structures I have yet to find anything more cache-efficient than a B-tree.
    - GrumpySloth 3y ago
      Measurements suggest that binary search is at least competitive with linear search and is often the winner, so it’s a reasonable default[1]. But naive binary search can also be improved upon by dividing the searched space into 3 subranges instead of 2[2]. [1]: <https://www.pvk.ca/Blog/2012/07/03/binary-search-star-eliminates-star-branch-mispredictions/ https://www.pvk.ca/Blog/2012/07/03/binary-search-star-elimin...> [2]: <https://www.pvk.ca/Blog/2012/07/30/binary-search-is-a-pathological-case-for-caches/ https://www.pvk.ca/Blog/2012/07/30/binary-search-is-a-pathol...>
      - amluto 3y ago
        To clarify, I’m not saying that binary search is a bad way to search a sorted array. I’m saying that, if you have a bunch of data, you intend to preprocess that data and then search it repeatedly, that sorting it and binary searching is not a great solution.

amluto 3y ago

A sorted array to less inefficiently iterate children of a node? This is getting ridiculous. The “no pointers” thing is cache efficient for three reasons: 1. Indices can be smaller than pointers. 2. The data is packed in memory. This means that cachelines will be full of relevant data, and adjacent cache lines (which are a bit faster than faraway lines) get used. 3. SOA form is more or less cache efficient depending on what you’re doing with it. And that’s it. If you need child pointers, use child pointers. If you want a cache-efficient tree, use a cache-efficient tree, e.g. a B-tree or an appropriate variant.

alexchamberlain 3y ago
Sorted arrays can be navigated like a tree. For sufficiently randomised data, the middle element is approximately the middle of your data. You can use binary search. You can implement range iteration very efficiently. It's not wholly ridiculous.
- amluto 3y ago
  Binary search into a sorted array is slow. Intro algorithms classes might count operations, and you discover that about log_2(n) operations are needed, which is optimal in a certain sense. But those operations are horrible operations. Until you are log_2(cache line size / element size) steps from the leaves, you are hitting a different cache line each time, and you’re doing a branch such that the next cache line you want depends on the branch result. So this is like log_2(n)-3 serial (cache miss, compare, branch, compute address operations). (Assume 8-byte entries — it’s much worse with bigger entries.) This not even close to optimal. You will find that, for reasonably large data sets (maybe a few hundred elements or more?), any cache-optimized searchable data structure will beat binary search by a large factor. And for small arrays (or the last stage of an optimized large structure), you want a vectorized linear search. Binary search is mostly nice because sorted arrays are elegant and binary search can be implemented in very little code. And it’s easy to explain and analyze.
  - senderista 3y ago
    Eytzinger ("heap") layout packs the pivots as efficiently as possible, so cache misses are confined to the lower levels of the tree. But ordered iteration is slower, and of course it only works for static data. I agree that for dynamic structures I have yet to find anything more cache-efficient than a B-tree.
  - GrumpySloth 3y ago
    Measurements suggest that binary search is at least competitive with linear search and is often the winner, so it’s a reasonable default[1]. But naive binary search can also be improved upon by dividing the searched space into 3 subranges instead of 2[2]. [1]: <https://www.pvk.ca/Blog/2012/07/03/binary-search-star-eliminates-star-branch-mispredictions/ https://www.pvk.ca/Blog/2012/07/03/binary-search-star-elimin...> [2]: <https://www.pvk.ca/Blog/2012/07/30/binary-search-is-a-pathological-case-for-caches/ https://www.pvk.ca/Blog/2012/07/30/binary-search-is-a-pathol...>
    - amluto 3y ago
      To clarify, I’m not saying that binary search is a bad way to search a sorted array. I’m saying that, if you have a bunch of data, you intend to preprocess that data and then search it repeatedly, that sorting it and binary searching is not a great solution.