boost::histogram::axis::variant, allow users to choose between sorted_array+std::lower_bound and eytzinger_layout+eytzinger_binary_search
Nobody has claimed this yet.
Assessment
- Difficulty
- 5/5
- Estimated time
- Over a week
- Newbie friendliness
- 30/100
- Issue type
- Feature
- Clarity
- Mostly clear
- Activity status
- Stale
- Tech stack
- cpp
- Domain
- performance
Research direction
Start by locating boost::histogram::axis::variant and the test referenced in the issue, then review how it currently uses std::upper_bound. Compare the two proposed search layouts and determine how users would choose between them; done means the choice is exposed without changing existing behavior and the relevant tests or benchmarks cover both options.
Written by the indexing model from the issue text.
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
Static B-Trees: up to 15x faster than std::lower_bound : cpp
(boost::histogram::axis::variant is currently using std::upper_bound.)
comparison (x86-64 gcc (trunk), -std=c++23 -O3 -Wall -pedantic -pthread):
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
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<int>::min(), std::numeric_limits<int>::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<double> 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<double> 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]]);
}
}
- Dominant language
- C++
- Stars
- 334
- Forks
- 76
- PR merge metrics
- No merged PRs in 30d
Getting set up
- No Dockerfile or Docker Compose file
- No pull request template
- Read the contributing guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
More from boostorg/histogram
-
Difficulty 5/5 Over a week Newbie friendliness 28/100
-
Mixed scalar/array `fill` zeroes the whole histogram when a non-inclusive axis drops the first entryOpen
Difficulty 3/5 1-2 days Newbie friendliness 72/100
-
Difficulty 5/5 Over a week Newbie friendliness 35/100
-
Difficulty 4/5 3-5 days Newbie friendliness 35/100
-
Difficulty 4/5 3-5 days Newbie friendliness 42/100
All issues in boostorg/histogram
Similar issues
-
bug chart-audit
Difficulty 1/5 Under an hour Newbie friendliness 92/100
Maintainers usually reply within 1 day
-
HasBacktrace Priority-Critical
Difficulty 2/5 1-3 hours Newbie friendliness 78/100
azerothcore/azerothcore-wotlk#27921 ·
Maintainers usually reply within 1 day
-
Difficulty 1/5 Under an hour Newbie friendliness 88/100
Maintainers usually reply within 1 day
-
Difficulty 2/5 1-3 hours Newbie friendliness 68/100
Maintainers usually reply within 1 day
-
Difficulty 1/5 Under an hour Newbie friendliness 88/100
yhirose/cpp-peglib#344 ·