Store static search data

Vladimir Sakharuk • • 2 min read
programming

How to store static search data in the application? I got such a question in an interview.

My first suggestion was a hash map. Second was storing the binary tree in an array where the root of the tree goes into 0 slots, 1,2 indexes occupied by root children etc. I quickly realized that the expected solution involves regularly sorted arrays with plain binary search. Which, as a general method, is very convenient given standard libraries in many languages.

I want to talk about my logic in more detail and how it differs from the traditional method.The layout I proposed is named Eytzinger (a.k.a. BFS) . It is very friendly for CPU cache and supports prefetching.

The tree:

text 
    4
    / \
   2  6
  / \ / \
 1 3  5 7

will be placed in array as:

cpp 
[4, 2, 6, 1, 3, 5, 7]

The access of children for any node ‘i’ would be:

cpp 
Left   = i*2 +1;
Right = i*2 +2;

Here is a sample function illustrating branchless binary search in Eytzinger layout, with CMOV instruction utilization.

cpp 
template<typename T, typename Index>
Index branch_free_search(T value, const std::vector<T>& values)
{
    Index n = values.size();
    Index i = 0;
    while (i < n)
    {
        i = (value <= values[i])? (2*i + 1) : (2*i + 2);
    }
    Index j = (i+1) >> __builtin_ffs(~(i+1));
    return (j == 0) ? n : j-1;
}

The key improvement is that the left and right children are in addresses next to each other and on the same or adjusted cache lines.

The recursive construction of the layout from the sorted array:

cpp 
template<typename T>
void build_eytzinger(
    const std::vector<T>& sorted,
    std::vector<T>& result,
    size_t index,
    size_t& source)
{
    if (index >= a.size()) return;
    // process left
    build_eytzinger(sorted, result, 2*index + 1, source);
    // process node
    result[index] = sorted[source++];
    // process right
    build_eytzinger(sorted, result, 2*index + 2, source);
}

// Usage:
size_t source = 0;
build_eytzinger(sorted, result, 0, source);

Yes there are b-trees and s-trees, but those folks are for big data not HFT.

Eytzinger layout beats or is on par with the stored array solution due to CPU cache friendly data storage and no branching. It is extremely handy in instrument lookup during a busy pass in HFT trading.