boost::histogram::axis::variant, allow users to choose between sorted_array+std::lower_bound and eytzinger_layout+eytzinger_binary_search
- Dominant language
- C++
- Stars
- 334
- Forks
- 76
- PR merge metrics
- No merged PRs in 30d
Description
According to the test,
- When input follows normal distribution, sorted_array+std::lower_bound is faster;
- When input follows uniform distribution, eytzinger_layout+eytzinger_binary_search is faster;
[Eytzinger Binary Search - Algorithmica](https://algorithmica.org/en/eytzinger)
[Static B-Trees: up to 15x faster than std::lower_bound : cpp](https://www.reddit.com/r/cpp/comments/sv012b/static_btrees_up_to_15x_faster_than_stdlower_bound/)
(`boost::histogram::axis::variant` is currently using `std::upper_bound`.)
[comparison (x86-64 gcc (trunk), -std=c++23 -O3 -Wall -pedantic -pthread)](https://godbolt.org/#z:OYLghAFBqd5QCxAYwPYBMCmBRdBLAF1QCcAaPECAMzwBtMA7AQwFtMQByARg9KtQYEAysib0QXACx8BBAKoBnTAAUAHpwAMvAFYTStJg1DIApACYAQuYukl9ZATwDKjdAGFUtAK4sGe1wAyeAyYAHI%2BAEaYxCAA7ACspAAOqAqETgwe3r56KWmOAkEh4SxRMQm2mPYFDEIETMQEWT5%2BXJXVGXUNBEVhkdF6CvWNzTltQ929JWUSAJS2qF7EyOwc5gDMScRMwCxMANQA4m5u%2B6hJjix4AF6YEOZmAPLrD7MmGgCCG8HI3lj7JnWbgihAUAHohuhTJZrAA6BCA7DvL6fNAMIaYVRbfZpW4AfQI%2BwYAPWABF9hAuIC3NSzBo3usrKiBBiscQcTdMAT9hFaKhkABrPG4zAk8kANkk%2BzBHNuqCoEGCBAZFmlMsBEqlMqlGv2omQCC5tGCXJF0tlmHlisEb0%2BYjwwGYCggktm%2ByV%2ByYJniFgY3tJpB53t91ip8VJgKZKI%2BaNZ2JF3IAjl5ogBPPFoLyCDWU6m0%2BmR5Ee4bATAEBTB5NpjOLbPhwufD3ETAKLy0ct4zCpgjXYKl4iVlPEdOZusRxlFwT7Zut9sKPF8gDu0TxEVr6EH1dHBH9DejHq7Pb70WthLwYv2GkDCcJAovXDdJliUf2r/dVApd7zZKJj%2BfyLfQD3QvQ9eyME88EDMx9gAKn2AUVQAoDXwiYMBX9C8vR9PBrFw%2BsJ0%2BZDX3PXVQOPYhFSg2D4IBSx9gfPdAKfCNCLfZsCCWYkcIIr5YhY/cpyUBoDVPfZVD/F83xvGjdSpHjAMXBA6FFCAvyBXUGAkpDkLxVcvDoRwGDxLZMCoMsRIiWjVTvODeX5IURUQ1jkLU8loLgr86IgVCfXQ8MSVOcTGLfZjtJk9YkQi3VdIifT22CPEqCoZ0AD8EOC192M4%2BC91Cz5J0JPZgggW1eMk19IRAEBtgYdBUBYPEsAANzwFZpw3RlXzBMEAHU6FoHlRS8JR0H2Igzgiepgk9HFMEwUb%2BHZAhDWnQw6pYIl%2BnZRhgBNMLKpAFgCC4ABOE71lifZSwYCBiHQEqVTVLpaoaUa2GIJQGBCAlFzwDFiE7IwTVm%2Bb5v2X7lvakr9oIdAqqzPBFoapVGr%2BghiDwWKam/bB9nwIYMYiCADoYHxolahc8CuctqSVREqquG75hxWGqtJ96KeNamKyBOmIoZphVAejL9kWilpJIn8NEjYCwDADSZdwyw8FKpj/2coCsIsHD8NJA7iHXCB8fRzHoEYWYnI%2BNX%2BMAg6FBIAhidZkAol2m6mHmA7XAgD3LbCsjwIov2NbF4nOW5SXyWlzrzzl3Uq2HGssx3Tqle11WQvVq2iJLMsK2w3cyX1w3jcJs3NMt63kTCp9ys1rxxomRoLwOg0DYYVAqoxJh0BHPlBTZ1BF2h%2BSiNDiWL2j1VY/ln8E5HWsU9VNOVbCtW66I6cWzbDsA/7YMdfHPXMGEhAIFzmmC/DSuiLy7PkKYBvUH2VwW%2BdtuBE7kBu97jN%2B4FQew8b7IVbggduX90BLCYNjIEdUvC8kwIiF%2BBgkgjWFJgNE6AFAgVqgAWibkvNeUl36LEJN%2BU4DwqhMFQWDS47BaLQXIcg6haClCYIULCbcJUArUgYfnNwfozBmBFnfdeRDXyP0bsMMhP5QHgK7gQE%2Bv9fj2UASPDeb5x7hzPJPGWM945DgXsnRWMJlYZ2QrXcRQEZw73nEuFca4swbivkfA69iAaONqk7OGLtMBux9p7Z23sPakAvvnbW/pZj4Odq7YqHsRZVw1oBSRz9X66jkZ/BRSi%2B6qJAB3IBCTiE%2BI/h3KqkDtgwLcHAhBSCqE0PQOg9hOD0DRO6IUiqJCG48KBAwupI0xpU3oQ8bppw%2BnzUaQILBnDF7cKYQ8fhgjhGj1fKIzRJBxbaOArqKestZ7knnknbMqdTHpxrlnTeTAFBKEaD7YMNi5wLiHg49cB9dy6w1D5Cw9zd7djAvvFxkSZYrI1nfO%2BHB5i0E4PEXgfgOBaFIJ3DgNITk4kWMsUUGweChM0OC%2BYAD4hXkhRwSQvAWAgElLCAAHBoSl6xxRmDpedC6J1KWkFhfCxFvAFAgCvAQHF8w4CwCQGgFgSRlJkAoBAEVYr6AxGAAoZgqCECoAIKQZqrVMAADU8CYEXI8JIjBOBYpoO2aI3LvI4tICCZgw4jW8BFWwQQjwGC0FTJarAewjDiDhbwfAzYHB4Cai2S1mIMEN1WFipUVRLXGgiNsYcHgsCWpNmS7g4K%2BAGHldq3V%2BrDVppkIIEQYh2BSALfIJQahLW6DaAYIwKA076ExtyyA8xzg1G5RwaJHVSTQisJYBl%2BxcHPEHT1MQA1cEGvQIYRwyBB0XDAUorlVQME1BcLVUYrRSCBBNNMAYbQ8jpAEBu3IqRD0MCmFtQYy6A0CC6CMTwLQr0dFvdIi9pQ922Gkce8Yr6d2XofAsJYKw5j6ChTCy1iKxKUvFLgyUV1kCzvPsQLMCEKS4EIOszFsxeB8p9QKpAobkBPwlZQBo8rlCGCqEIZVi5YVYulXQaBGQKMhFoNRoe7L7X1RlQMeViqFDKtVQx2VjwG7sdoyG1QGCPjEHlZwXghG6j4FhbwfghbRDiFLWp8tKh1A%2BtINW/QhhjANtjc2kqCKLgZA7V2jUvbrADqHesEdY653zWna1Ody1mw9y5Wi4DP7lMsaozRujOHmwRt4IubYSQ7UQrA2yiDnBsBSaI0QdkqhoOwalMABDFJ0YobdBAZFfabD7HQ%2Bl2i6wHw4f5fMQ0PcBgWaJSS0gZL1jxFhKdLg4oLq9Y0OKelGgzCJf05y2wehcNaAtqQABXANCEs4OscDY35PYrw/MINH0MggEkEAA):
```C++
#pragma GCC optimize("O3")
#include
constexpr size_t n = (1<<20);
constexpr size_t block_size = 64 / sizeof(int); // = 64 / 4 = cache_line_size / sizeof(int)
alignas(64) int a[n], b[n+1];
constexpr size_t query_count=(1<<20);
int targets[query_count];
int results_eytzinger[query_count];
int results_lower_bound[query_count];
int eytzinger(int i = 0, size_t 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) {
size_t k = 1;
while (k <= n) {
__builtin_prefetch(b + k * block_size);
k = 2 * k + (b[k] < x);
}
k >>= __builtin_ffs(~k);
return k;
}
int main()
{
std::random_device rd; //Will be used to obtain a seed for the random number engine
std::mt19937 gen(rd()); //Standard mersenne_twister_engine seeded with rd()
std::uniform_int_distribution<> distrib(std::numeric_limits::min(), std::numeric_limits::max());
for (size_t i = 0; i != n; ++i)
{
a[i]=std::round(distrib(gen));
}
std::sort(std::begin(a),std::end(a));
eytzinger();
for (size_t i = 0; i != query_count; ++i)
{
targets[i]=std::round(distrib(gen));
}
{
auto start = std::chrono::steady_clock::now();
for (size_t i = 0; i != query_count; ++i)
{
results_eytzinger[i]=search(targets[i]);
}
auto end = std::chrono::steady_clock::now();
std::chrono::duration elapsed_seconds = end-start;
std::cout << "elapsed time: " << elapsed_seconds.count() << "s\n";
}
{
auto start = std::chrono::steady_clock::now();
for (size_t i = 0; i != query_count; ++i)
{
results_lower_bound[i]=std::lower_bound(std::begin(a),std::end(a),targets[i])-std::begin(a);
}
auto end = std::chrono::steady_clock::now();
std::chrono::duration elapsed_seconds = end-start;
std::cout << "elapsed time: " << elapsed_seconds.count() << "s\n";
}
for (size_t i = 0; i != query_count; ++i)
{
assert(a[results_lower_bound[i]]==b[results_eytzinger[i]]);
}
}
```

Contributor guide
Assessment
This issue has not been assessed yet.