I thought of eliminating the worst case here (when pa == pb, where it has to do the comparison for every byte) with something like:
return pa != pb &&
std::tie(pa->nChainWork, pb->nSequenceId, pb)
< std::tie(pb->nChainWork, pa->nSequenceId, pa);
But the benchmarks indicate that it's not really faster.
<details><summary>benchmark with pointer duplicates</summary>
// Copyright (c) 2025-present The Bitcoin Core developers
// Distributed under the MIT software license, see the accompanying
// file COPYING or http://www.opensource.org/licenses/mit-license.php.
#include <arith_uint256.h>
#include <bench/bench.h>
#include <chain.h>
#include <node/blockstorage.h>
#include <random.h>
#include <uint256.h>
#include <algorithm>
#include <memory>
#include <vector>
static void CBlockIndexWorkComparator(benchmark::Bench& bench)
{
FastRandomContext rng{/*fDeterministic=*/true};
constexpr size_t n{1'000};
std::vector<std::shared_ptr<CBlockIndex>> blocks;
blocks.reserve(n);
for (size_t i{0}; i < n; ++i) {
auto block{std::make_shared<CBlockIndex>()};
block->nChainWork = UintToArith256(rng.rand256());
block->nSequenceId = int32_t(rng.rand32());
if (i % 10 == 1) {
// Have some duplicates
if (rng.randbool()) {
block = blocks.back();
} else {
if (rng.randbool()) block->nChainWork = blocks.back()->nChainWork;
if (rng.randbool()) block->nSequenceId = blocks.back()->nSequenceId;
}
}
blocks.push_back(std::move(block));
}
std::ranges::shuffle(blocks, rng);
const node::CBlockIndexWorkComparator comparator;
bench.batch(n * n).unit("cmp").run([&] {
for (size_t i{0}; i < n; ++i) {
const auto* lhs{blocks[i].get()};
for (size_t j{0}; j < n; ++j) {
const auto* rhs{blocks[j].get()};
const bool result{comparator(lhs, rhs)};
ankerl::nanobench::doNotOptimizeAway(result);
}
}
});
}
BENCHMARK(CBlockIndexWorkComparator, benchmark::PriorityLevel::HIGH);
</details>
b17504b611 refactor: optimize CBlockIndexWorkComparator with std::tie
|
ns/cmp |
cmp/s |
err% |
ins/cmp |
cyc/cmp |
IPC |
bra/cmp |
miss% |
total |
benchmark |
|
2.13 |
469,485,340.38 |
0.2% |
15.07 |
5.09 |
2.959 |
4.02 |
0.1% |
11.01 |
CBlockIndexWorkComparator |
|
ns/op |
op/s |
err% |
ins/op |
cyc/op |
IPC |
bra/op |
miss% |
total |
benchmark |
|
90,265.10 |
11,078.48 |
0.1% |
637,536.00 |
215,946.18 |
2.952 |
178,844.00 |
0.0% |
10.84 |
CheckBlockIndex |
2b77e567d8 refactor: short-circuit CBlockIndex comparator for equality
|
ns/cmp |
cmp/s |
err% |
ins/cmp |
cyc/cmp |
IPC |
bra/cmp |
miss% |
total |
benchmark |
|
2.60 |
385,002,212.20 |
0.0% |
18.00 |
6.22 |
2.894 |
5.00 |
0.0% |
11.00 |
CBlockIndexWorkComparator |
|
ns/op |
op/s |
err% |
ins/op |
cyc/op |
IPC |
bra/op |
miss% |
total |
benchmark |
|
94,110.53 |
10,625.80 |
0.0% |
682,454.03 |
225,242.05 |
3.030 |
186,486.01 |
0.0% |
11.00 |
CheckBlockIndex |