benchmark.cpp

#pragma GCC optimize("O3")
#include <bits/stdc++.h>

using namespace std;

const int n = (1<<20), m = (1<<20);
int a[n], q[m], results[m];
alignas(64) int b[n+1];

const int block_size = 16; // = 64 / 4 = cache_line_size / sizeof(int)

int eytzinger(int i = 0, int k = 1) {
    if (k <= n) {
        i = eytzinger(i, 2 * k);
        b[k] = a[i++];
        i = eytzinger(i, 2 * k + 1);
    }
    return i;
}

int search(int x) {
    int k = 1;
    while (k <= n) {
        __builtin_prefetch(b + k * block_size);
        k = 2 * k + (b[k] < x);
    }
    k >>= __builtin_ffs(~k);
    return k;
}

template<typename lambda>
double timeit(string name, lambda f) {
    cout << "> " << name << endl;
    clock_t start = clock();
    f();
    double t = double(clock() - start) / CLOCKS_PER_SEC;
    cout << "time: " << t << endl;
    return t;
}

int main() {
    for (int i = 0; i < n; i++)
        a[i] = rand();
    for (int i = 0; i < m; i++)
        q[i] = rand();
    a[0] = RAND_MAX;

    sort(a, a+n);
    eytzinger();

    double t1 = timeit("std::lower_bound", [&](){
        for (int i = 0; i < m; i++)
            results[i] = *lower_bound(a, a + n, q[i]);
    });

    double t2 = timeit("eytzinger", [&](){
        for (int i = 0; i < m; i++) {
            assert(results[i] == b[search(q[i])]);
        }
    });

    cout << "speedup: " << t1 / t2 << endl;

    return 0;
}