optimization: batch XOR operations 12% faster IBD #31144

Depends on #31551.

The descriptions and stats will be updated after the dependent PRs are already merged, but so far it seems that the 3 PRs combined can achieve a 12% IBD speedup.

The recently merged XOR obfuscation introduced a minor serialization cost (seen during IBD benchmarking). This PR is meant to alleviate that.

Summary

The obfuscation’s effect on IBD seems’ to be about ~4% when it still has to be applied, and ~9% when it’s turned off, see:

• #31144 (comment)
• #31144 (comment)

Changes in testing, benchmarking and implementation

• Added new tests comparing randomized inputs against a trivial implementation and performing roundtrip checks with random chunks.
• Updated the benchmark to reflect realistic scenarios by capturing every call of util::Xor for the first 860k blocks, creating a model with the same data distribution. An additional benchmark checks the effect of short-circuiting XOR when the key is zero, ensuring no speed regression occurs when the obfuscation feature is disabled.
• Optimized the Xor function to process in batches (64/32/16/8 bits instead of per-byte).
• Migrated remaining std::vector<std::byte>(8) values to uint64_t.

Reproducer and assembly

Memory alignment is handled via std::memcpy, optimized out on tested platforms (see https://godbolt.org/z/GGYcedjzY):

• Clang (x86-64) - 32 bytes/iter using SSE vector operations
• GCC (x86-64) - 16 bytes/iter using unrolled 64-bit XORs
• RISC-V (32-bit) - 8 bytes/iter using load/XOR/store sequence
• s390x (big-endian) - 64 bytes/iter with unrolled 8-byte XORs

Endianness

The only endianness issue was with bit rotation, intended to realign the key if obfuscation halted before full key consumption. Elsewhere, memory is read, processed, and written back in the same endianness, preserving byte order. Since CI lacks a big-endian machine, testing was done locally via Docker.

0brew install podman pigz
1softwareupdate --install-rosetta
2podman machine init
3podman machine start
4docker run --platform linux/s390x -it ubuntu:latest /bin/bash
5    apt update && apt install -y git build-essential cmake ccache pkg-config libevent-dev libboost-dev libssl-dev libsqlite3-dev && \
6    cd /mnt && git clone https://github.com/bitcoin/bitcoin.git && cd bitcoin && git remote add l0rinc https://github.com/l0rinc/bitcoin.git && git fetch --all && git checkout l0rinc/optimize-xor && \
7    cmake -B build && cmake --build build --target test_bitcoin -j$(nproc) && \
8    ./build/src/test/test_bitcoin --run_test=streams_tests

Performance

0   cmake -B build -DBUILD_BENCH=ON -DCMAKE_BUILD_TYPE=Release \
1&& cmake --build build -j$(nproc) \
2&& build/src/bench/bench_bitcoin -filter='XorHistogram|AutoFileXor' -min-time=10000

The 860k block profile contains a lot of very big arrays (96'233 separate sizes, biggest was 3'992'470 bytes long) - a big departure from the previous 400k and 700k blocks (having 1500 sizes, biggest was 9319 bytes long).

The performance characteristics are also quite different, now that we have more and bigger byte arrays:

C++ compiler …………………….. AppleClang 16.0.0.16000026

Before:

After:

i.e. ~11/5.5x (disabled/enabled) faster with Clang at processing the data with representative histograms.

C++ compiler …………………….. GNU 13.2.0

Before:

After:

i.e. ~3.2/3.5x faster (disabled/enabled) with GCC at processing the data with representative histograms.

Before:

After:

Also visible on https://corecheck.dev/bitcoin/bitcoin/pulls/31144

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Code Coverage & Benchmarks

For details see: https://corecheck.dev/bitcoin/bitcoin/pulls/31144.

Reviews

See the guideline for information on the review process.

If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.

Conflicts

Reviewers, this pull request conflicts with the following ones:

• #31551 (optimization: bulk reads(27%)/writes(290%) in [undo]block [de]serialization, 6% faster IBD by l0rinc)
• #31539 (optimization: buffer reads(23%)/writes(290%) in [undo]block [de]serialization, 6% faster IBD by l0rinc)
• #31519 (refactor: Use std::span over Span by maflcko)
• #30965 (kernel: Move block tree db open to block manager by TheCharlatan)
• #29641 (scripted-diff: Use LogInfo over LogPrintf [WIP, NOMERGE, DRAFT] by maflcko)
• #29307 (util: explicitly close all AutoFiles that have been written by vasild)
• #27006 (reduce cs_main scope, guard block index ’nFile’ under a local mutex by furszy)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

I think your example may be a bit skewed? It shows how much time is spent when deserializing a CScript from a block file. However, block files contain full blocks, where many (most?) of the writes are single bytes (or 4 bytes), see #30833 (comment). Thus, it would be useful to know what the overall end-to-end performance difference is. Also taking into account the utxo db.

If you want the micro-benchmark to be representative, I’d presume you’d have to mimic the histogram of the sizes of writes. Just picking one (1024, or 1004), which is never hit in reality, and then optimizing for that may be misleading.

where many (most?) of the writes are single bytes (or 4 bytes)

Thanks, I’ve extended your previous benchmarks with both Autofile serialization and very small vectors. I will also run a reindex of 400k blocks before and after to see if the effect is measurable or not.

It would be good to explain the jpegs in the description, or even remove them. They will be excluded from the merge commit and aren’t shown, unless GitHub happens to be reachable and online. Are they saying that IBD was 4% faster? Also, I think they were created with the UB version of this pull, so may be outdated either way?

I did a quick check on my laptop and it seems the XorSmall (1+4 bytes) is slower with this pull. The Xor (modified to check 40 bytes) was twice as fast. Overall, I’d expect it to be slower on my machine, due to the histogram of real data showing more small byte writes than long ones, IIRC.

I can try to bench on another machine later, to see if it makes a difference.

Can you clarify what type of machine you tested this on?

Are they saying that IBD was 4% faster?

That’s what I’m measuring currently, but I don’t expect more than 2% difference here.

Also, I think they were created with the UB version of this pull, so may be outdated either way?

Benchmarks indicated that the 64 bit compiled result was basically the same.

Overall, I’d expect it to be slower on my machine, due to the histogram of real data showing more small byte writes than long ones, IIRC.

I’ll investigate, thanks.

Posting the perf here for reference: Reindexing until 300k blocks reveals that XOR usage was reduced:

Concept ACK a3dc138798e2f2c7aa1c9b37633c16c1b523a251

Operating on CPU words rather than individual bytes. :+1:

Not entirely clear to me from #31144 (review) whether the optimizer is able to use SIMD. Guess picking through the binary of a GUIX-build would give a definitive answer.

The verbosity of std::memcpy hurts readability but alignment issues are real.

🚧 At least one of the CI tasks failed. Debug: https://github.com/bitcoin/bitcoin/runs/32109998785

Try to run the tests locally, according to the documentation. However, a CI failure may still happen due to a number of reasons, for example:

• Possibly due to a silent merge conflict (the changes in this pull request being incompatible with the current code in the target branch). If so, make sure to rebase on the latest commit of the target branch.

• A sanitizer issue, which can only be found by compiling with the sanitizer and running the affected test.

• An intermittent issue.

Leave a comment here, if you need help tracking down a confusing failure.

🚧 At least one of the CI tasks failed. Debug: https://github.com/bitcoin/bitcoin/runs/32217592364

Try to run the tests locally, according to the documentation. However, a CI failure may still happen due to a number of reasons, for example:

• Possibly due to a silent merge conflict (the changes in this pull request being incompatible with the current code in the target branch). If so, make sure to rebase on the latest commit of the target branch.

• A sanitizer issue, which can only be found by compiling with the sanitizer and running the affected test.

• An intermittent issue.

Leave a comment here, if you need help tracking down a confusing failure.

The CI failure in https://github.com/bitcoin/bitcoin/runs/32217592364 might come from a bad rebase reconciliation with master?

0[12:44:30.723] Duplicate include(s) in src/bench/xor.cpp:
1[12:44:30.723] #include <cstddef>
2[12:44:30.723] #include <span.h>
3[12:44:30.723] #include <streams.h>
4[12:44:30.723] #include <random.h>
5[12:44:30.723] #include <vector>
6[12:44:30.723] #include <bench/bench.h>
7[12:44:30.723] 
8[12:44:30.728] ^---- ⚠️ Failure generated from lint-includes.py

The CI failure in bitcoin/bitcoin/runs/32217592364 might come from a bad rebase reconciliation with master?

That’s an old build, right? Latest Lint seems fine

Taking a step back, I wonder if this is worth it. IIRC it gives a +1% speedup when run on spinning storage, so it seems a higher speedup is possibly visible on faster, modern storage. However, it would be good if any IO delay was taken out of IBD completely, so that the speed of storage and the speed of XOR is largely irrelevant.

I haven’t looked, but this may be possible by asking the next block the be read into memory in the background, as soon as work on the current block begins.

Something similar is done in net_processing, where the (presumed) current block is read into memory, and kept there, to avoid having to read it from storage again in validation. See https://github.com/bitcoin/bitcoin/blob/f07a533dfcb172321972e5afb3b38a4bd24edb87/src/net_processing.cpp#L823

Taking a step back, I wonder if this is worth it. IIRC it gives a +1% speedup

That’s not the main point, rather that we’re storing the key in a value that can be short-circuited easily so that when key is 0 (i.e. xor is NOOP), we can skip it. Previously this would have only been possible by checking each byte of the key. It’s also a lot cleaner to store it in a primitive instead, which supports xor natively. Xor comes up in every profiling I do, we shouldn’t have a regression because of #28207 - this PR solves that.

we shouldn’t have a regression because of #28207 - this PR solves that.

It is not possible to do XOR without any cost at all. There will always be an overhead and I think calling #28207 a regression and this change a “fix” is not entirely accurate. This change reduces the overhead, according to the benchmarks.

That’s not the main point

The pull request title starts with “optimization”, so I got the impression that a speedup is the main point.

The reason that std::vector was picked is that switching to larger sizes is possible. However, if there was a need to do that, XOR would likely not be sufficient anyway. So limiting to 8 bytes fixed at compile time seems reasonable.

I am mostly saying that any speedup here may not be visible at all if IO is completely taken out of the critical path, but I haven’t looked into that in detail.

change a “fix” is not entirely accurate

when xor is disabled we’re not xor-ing now at all. Previously we did xor, so this change brings back the previous behavior when xor is not needed.

The pull request title starts with “optimization”, so I got the impression that a speedup is the main point.

Yes, please see the updated description with the benchmarks: #31144#issue-2610689777

may not be visible at all if IO is completely taken out of the critical path

I’d argue the current implementation is slightly simpler (i.e. xor is stored and performed natively and can be disabled) and faster (2x for a representative dataset).

(Reviewed a5cad729c76cafa047a2b1897595669ae9b2b0d5)

Since my previous Concept ACK, the PR was changed to switch the xor key more completely to uint64_t. Before the PR, we were already using fixed-size of 8 bytes for the obfuscation value in the file formats, so changing the type to uint64_t shouldn’t be noticeable to users. :+1:

Even if we could move reading and XOR-ing out of the hot path as suggested by maflcko, we might as well make use the CPU architectures we have. I would expect larger-sized XOR operations to have less overhead and energy waste (less heat).

We could have used ReadLE64 to unify the byte order for keys and writable values, but that shouldn’t be necessary, since both have the same endianness locally that shouldn’t be affected by a byte-by-byte xor.

The s390x unit tests fail:

 0./src/test/streams_tests.cpp(40): error: in "streams_tests/xor_bytes": check { expected.begin(), expected.end() } == { actual.begin(), actual.end() } has failed. 
 1Mismatch at position 0: � != |
 2Mismatch at position 1: Y != �
 3Mismatch at position 2: � != �
 4Mismatch at position 3: � != �
 5Mismatch at position 4: w != �
 6Mismatch at position 5: C != �
 7Mismatch at position 6:  != x
 8Mismatch at position 7: � != �
 9Mismatch at position 8: � != C
10Mismatch at position 9: Y != �
11Mismatch at position 10: � != �
12Mismatch at position 11: , != �
13Mismatch at position 12: � != R
14Mismatch at position 13: 8 != �
15Mismatch at position 14: � != �
16Mismatch at position 15: � != �
17Mismatch at position 16: � != l
18Mismatch at position 17: � != n
19Mismatch at position 18: � != �
20Mismatch at position 19: t != B
21Mismatch at position 20: ; != �
22Mismatch at position 21: != �
23Mismatch at position 22: � != �
24Mismatch at position 23: � != �
25Mismatch at position 24: k != �
26Mismatch at position 25: � != Z
27Mismatch at position 26: � != �
28Mismatch at position 27: � != �
29Mismatch at position 28: � != #
30Mismatch at position 29: 8 != �
31Mismatch at position 30: � != �
32Mismatch at position 31: � != �
33Mismatch at position 32: g != �
34Mismatch at position 33: � != ^
35Mismatch at position 34: � != �
36ismatch at position 36: � != k
37Mismatch at position 37: * != �
38Mismatch at position 38: q != 
39Mismatch at position 39: � != �
40Mismatch at position 40: � != �
41Mismatch at position 41: r != e
42Mismatch at position 42: � != �

The s390x unit tests fail:

I don’t know how to access that, is it part of CI? Does the test suite pass on it otherwise or was it just curiosity? Do you know the reason it fails, is my assumption incorrect that endianness should apply to both parts (key and value) the same way? Is the test wrong or the xor, should I change the test such that xor-ing twice should reveal the original data instead (while the intermediary part should not)?

I don’t know how to access that, is it part of CI?

It needs to be run manually. See https://github.com/bitcoin/bitcoin/tree/master/ci#running-a-stage-locally. (podman run --rm --privileged docker.io/multiarch/qemu-user-static --reset -p yes may be required to setup qemu-s390x, depending on your setup). Then something like MAKEJOBS="-j$(nproc)" FILE_ENV="./ci/test/00_setup_env_s390x.sh" ./ci/test_run_all.sh should run it.

Does the test suite pass on it otherwise or was it just curiosity?

Yes, it should pass on s390x. If not, that is a bug somewhere.

Thanks for the hints @maflcko, I was under the impression that big-endian tests were run automatically.

Fix

It seem that that std::rotr doesn’t take endianness into account, so the fix basically looks like:

0size_t key_rotation = 8 * key_offset;
1if constexpr (std::endian::native == std::endian::big) key_rotation *= -1;
2return std::rotr(key, key_rotation);

I’ve emulated the s390x behavior locally like this:

0brew install podman pigz
1softwareupdate --install-rosetta
2podman machine init
3podman machine start
4docker run --platform linux/s390x -it ubuntu:22.04 /bin/bash
5    apt update && apt install -y git build-essential cmake ccache pkg-config libevent-dev libboost-dev libssl-dev libsqlite3-dev && \
6    cd /mnt && git clone https://github.com/bitcoin/bitcoin.git && cd bitcoin && git remote add l0rinc https://github.com/l0rinc/bitcoin.git && git fetch --all && git checkout l0rinc/optimize-xor && \
7    cmake -B build && cmake --build build --target test_bitcoin -j$(nproc) && \
8    ./build/src/test/test_bitcoin --run_test=streams_tests

Changes

• The change also includes an updated benchmarking suite with 700k blocks inspected for all usages of utils::Xor to make the benchmark representative:

• Changed AutoFileXor benchmark to measure the regression of turning off obfuscation.

• I’ve also updated all key derivations to vector-to-uint64 instead of generating the 64 bit key directly (it’s more consistent, more representative and helps with endianness).

• Added a xor roundtrip test which applies the xor in random chunks, asserts that it differs from the original and reapplies it in different random chunks and asserts that it’s equivalent to the original.

See the complete diff: https://github.com/bitcoin/bitcoin/compare/a5cad729c76cafa047a2b1897595669ae9b2b0d5..af778c5bdea4175f84e82b41f3b51c7f453d8c7e

Updated the benchmark to 860k blocks (September 2024):

This one contains a lot of very big arrays (96'233 separate sizes, biggest was 3'992'470 bytes long) - a big departure from the previous 400k and 700k blocks (having 1500 sizes, biggest was 9319 bytes long).

The performance characteristics are also quite different, now that we have more and bigger byte arrays:

C++ compiler …………………….. AppleClang 16.0.0.16000026

Before:

After:

i.e. ~35x faster with Clang at processing the data with representative histograms.

C++ compiler …………………….. GNU 13.2.0

Before:

After:

i.e. ~10x faster with GCC at processing the data with representative histograms.

Edit: note that I couldn’t use random byte generation for each benchmark value since it timed out on CI. I have replaced it with getting subsets of a single big random vector.

🚧 At least one of the CI tasks failed. Debug: https://github.com/bitcoin/bitcoin/runs/32549559124

Try to run the tests locally, according to the documentation. However, a CI failure may still happen due to a number of reasons, for example:

• Possibly due to a silent merge conflict (the changes in this pull request being incompatible with the current code in the target branch). If so, make sure to rebase on the latest commit of the target branch.

• A sanitizer issue, which can only be found by compiling with the sanitizer and running the affected test.

• An intermittent issue.

Leave a comment here, if you need help tracking down a confusing failure.

I ran a reindex-chainstate until 860k blocks (SSD, i7 CPU), before and after this change, 2 runs per commit. As stated in the previous comment, the latter blocks (>700k) seem to contain a lot of very big vectors where the new algorithm shines.

0hyperfine   \
1--runs 2   \
2--export-json /mnt/my_storage/reindex-chainstate-obfuscation-overhead.json  \
3--parameter-list COMMIT 866f4fa521f6932162570d6531055cc007e3d0cd,3efc72ff7cbdfb788b23bf4346e29ba99362c120,08db1794647c37f966c525411f931a4a0f6b6119 \
4--prepare 'git checkout {COMMIT} && git clean -fxd && git reset --hard && cmake -B build -DCMAKE_BUILD_TYPE=Release -DBUILD_UTIL=OFF -DBUILD_TX=OFF -DBUILD_TESTS=OFF -DENABLE_WALLET=OFF -DINSTALL_MAN=OFF && cmake --build build -j$(nproc)' \
5'COMMIT={COMMIT} ./build/src/bitcoind -datadir=/mnt/my_storage/BitcoinData -stopatheight=860000 -dbcache=10000 -printtoconsole=0 -reindex-chainstate'

Which indicates that this change speeds up IBD (or at least reindex-chainstate) by roughly ~3% (i.e. reverts the regression):

• 866f4fa521f6932162570d6531055cc007e3d0cd - baseline
• 3efc72ff7cbdfb788b23bf4346e29ba99362c120 - end-to-end vector to uint64
• 08db1794647c37f966c525411f931a4a0f6b6119 - dummy commit that forces obfuscation keys to be 0 to ignore xor operations (since -blocksxor=0 doesn’t affect dbwrapper), to see how xor affects speed in general

Benchmark 1: COMMIT=866f4fa521f6932162570d6531055cc007e3d0cd ./build/src/bitcoind -datadir=/mnt/my_storage/BitcoinData -stopatheight=860000 -dbcache=10000 -printtoconsole=0 -reindex-chainstate

Time (mean ± σ): 20846.396 s ± 72.227 s [User: 22353.773 s, System: 2563.864 s] Range (min … max): 20795.323 s … 20897.468 s 2 runs

Benchmark 2: COMMIT=3efc72ff7cbdfb788b23bf4346e29ba99362c120 ./build/src/bitcoind -datadir=/mnt/my_storage/BitcoinData -stopatheight=860000 -dbcache=10000 -printtoconsole=0 -reindex-chainstate

Time (mean ± σ): 20308.036 s ± 100.345 s [User: 21745.076 s, System: 2591.459 s] Range (min … max): 20237.081 s … 20378.991 s 2 runs

Benchmark 3: COMMIT=08db1794647c37f966c525411f931a4a0f6b6119 ./build/src/bitcoind -datadir=/mnt/my_storage/BitcoinData -stopatheight=860000 -dbcache=10000 -printtoconsole=0 -reindex-chainstate

Time (mean ± σ): 20293.227 s ± 9.923 s [User: 21711.799 s, System: 2588.886 s] Range (min … max): 20286.210 s … 20300.244 s 2 runs

0Summary
1'COMMIT=08db1794647c37f966c525411f931a4a0f6b6119 ./build/src/bitcoind -datadir=/mnt/my_storage/BitcoinData -stopatheight=860000 -dbcache=10000 -printtoconsole=0 -reindex-chainstate' ran
2 1.00 ± 0.00 times faster than 'COMMIT=3efc72ff7cbdfb788b23bf4346e29ba99362c120 ./build/src/bitcoind -datadir=/mnt/my_storage/BitcoinData -stopatheight=860000 -dbcache=10000 -printtoconsole=0 -reindex-chainstate'
3 1.03 ± 0.00 times faster than 'COMMIT=866f4fa521f6932162570d6531055cc007e3d0cd ./build/src/bitcoind -datadir=/mnt/my_storage/BitcoinData -stopatheight=860000 -dbcache=10000 -printtoconsole=0 -reindex-chainstate'

Reviewed a1232973189126cfc9526713011461709685fcc8

git range-diff master a5cad72 a123297

The awk script in the comment in c671dd17dced0d51845dc8d2148f288c4c44ecb2 doesn’t add the ' separators…?

Care to explain the scaling_factor value?

XorHistogram claims to use 8 GB of RAM. Could be a bit much if we want to be able to also run benchmarks on low-end devices.

 0diff --git a/src/bench/xor.cpp b/src/bench/xor.cpp
 1index 2ba8b17f08..bb193c7fcf 100644
 2--- a/src/bench/xor.cpp
 3+++ b/src/bench/xor.cpp
 4@@ -96269,18 +96269,13 @@ static void XorHistogram(benchmark::Bench& bench)
 5 
 6         total_bytes += scaled_count * size;
 7         for (size_t j{0}; j < scaled_count; ++j) {
 8-            std::vector<std::byte> ret;
 9-            ret.reserve(size);
10-            ret.insert(ret.end(), pattern.begin(), pattern.begin() + size);
11-            test_data.push_back(std::move(ret));
12+            test_data.emplace_back(pattern.begin(), pattern.begin() + size);
13         }
14     }
15     assert(total_bytes == 8'129'394'848); // ~8 GB of data
16     std::shuffle(test_data.begin(), test_data.end(), rng); // Make it more realistic & less predictable
17 
18-    std::vector key_bytes{rng.randbytes<std::byte>(8)};
19-    uint64_t key;
20-    std::memcpy(&key, key_bytes.data(), 8);
21+    const uint64_t key{rng.rand64()};
22 
23     size_t offset{0};
24     bench.batch(total_bytes).unit("byte").run([&] {
25@@ -96296,9 +96291,7 @@ static void AutoFileXor(benchmark::Bench& bench)
26     FastRandomContext rng{/*fDeterministic=*/true};
27     auto data{rng.randbytes<std::byte>(1'000'000)};
28 
29-    std::vector<std::byte> empty_key_bytes(8, std::byte{0}); // Test disabled xor
30-    uint64_t empty_key;
31-    std::memcpy(&empty_key, empty_key_bytes.data(), 8);
32+    uint64_t empty_key{0};
33 
34     const fs::path test_path = fs::temp_directory_path() / "xor_benchmark.dat";
35     AutoFile f{fsbridge::fopen(test_path, "wb+"), empty_key};

The awk script in the comment in https://github.com/bitcoin/bitcoin/commit/c671dd17dced0d51845dc8d2148f288c4c44ecb2 doesn’t add the ’ separators…?

I’ve added them manually.

Care to explain the scaling_factor value?

The values in the histogram (i.e. total bytes streamed through xor) add up to 92gb, but 1 byte values occupy half of that. (edit: this is only true for the first row, in other cases we would need to multiply by the first column)

Since we have thousands of big values that represent vector of that size, we have to include all of those into the test set at least once. I had to scale down the histogram such that the lower values, having a few hundred occurrences aren’t flattened out completely - to make the histogram still representative. Do you have a better idea?

XorHistogram claims to use 8 GB of RAM. Could be a bit much if we want to be able to also run benchmarks on low-end devices.

Yes, but if I scale it down more, more values will be equal in the histogram and it won’t reflect real usage. That’s why I’ve set it to low priority, we don’t have to run these for every execution.

Edit: pushed some nits to git range-diff 866f4fa521f6932162570d6531055cc007e3d0cd..a1232973189126cfc9526713011461709685fcc8 866f4fa521f6932162570d6531055cc007e3d0cd..57caa965b5ae284e501f892415d60fcb536f4c0e

Care to explain the scaling_factor value?

The values in the histogram (i.e. total bytes streamed through xor) add up to ~92gb, but 1 byte values occupy half of that. I had to scale down the histogram such that the lower values, having a few hundred occurrences aren’t flattened out completely - to make the histogram still representative. Do you have a better idea?

So raw_histogram really is the raw data?

Added:

0    uint64_t raw_total_bytes{0};
1    for (size_t i{0}; i < std::size(raw_histogram); i += 2) {
2        const uint64_t size = raw_histogram[i];
3        const uint64_t count = raw_histogram[i + 1];
4        raw_total_bytes += size * count;
5    }
6    printf("raw_total_bytes: %ld", raw_total_bytes);

Got:

0raw_total_bytes: 1'277'637'746'542 # "'" added manually

So something like 1.28TB instead of 92GB, but I can’t seem to get my head screwed on right today.

If I re-understood correctly what the code was doing with the scaling - it’s doing only 1'000'000 XOR-passes for the most common size (1 byte) instead of 47'584'838'861, and scaling down the number of XOR-passes for the others by the same factor.

Thought the following would be slightly faster:

 0diff --git a/src/bench/xor.cpp b/src/bench/xor.cpp
 1index 2ba8b17f08..5e933d74ea 100644
 2--- a/src/bench/xor.cpp
 3+++ b/src/bench/xor.cpp
 4@@ -96253,7 +96253,7 @@ static void XorHistogram(benchmark::Bench& bench)
 5     };
 6 
 7     const auto max_count{static_cast<double>(raw_histogram[1])}; // 1 byte is the most common
 8-    const auto scaling_factor{1'000'000U};
 9+    const auto scaling_factor{1'000'000.0 / max_count};
10 
11     FastRandomContext rng{/*fDeterministic=*/true};
12     const size_t pattern_size = raw_histogram[std::size(raw_histogram) - 2];
13@@ -96265,7 +96265,7 @@ static void XorHistogram(benchmark::Bench& bench)
14     for (size_t i{0}; i < std::size(raw_histogram); i += 2) {
15         const uint64_t size = raw_histogram[i];
16         const uint64_t count = raw_histogram[i + 1];
17-        const size_t scaled_count{static_cast<size_t>(std::ceil((static_cast<double>(count) / max_count) * scaling_factor))};
18+        const size_t scaled_count{static_cast<size_t>(std::ceil(static_cast<double>(count) * scaling_factor))};
19 
20         total_bytes += scaled_count * size;
21         for (size_t j{0}; j < scaled_count; ++j) {

Still passes the total_bytes == 8'129'394'848-assert unmodified, but seems slightly slower in my measurements (including for posterity).

Reviewed 57caa965b5ae284e501f892415d60fcb536f4c0e

git range-diff master a123297 57caa96

• Applied most of my nits that were still valid.

I understand you were burned by endianness but I disagree that it’s worth sacrificing readability where endianness is a non-issue.

For cases where endianness is a concern, I suggest the following pattern:

0uint64_t xor_key;
1constexpr std::array<uint8_t, sizeof xor_key> xor_pat{std::to_array<uint8_t>({0xff, 0x00, 0xff, 0x00, 0xff, 0x00, 0xff, 0x00})};
2std::memcpy(&xor_key, xor_pat.data(), sizeof xor_key);

1. Declare the uint64_t first so sizeof can be used in place of magic 8.
2. Use constexpr std::array instead of const std::vector to constrain the size.
3. Use to_array initialization since regular brace-initialization will only complain if too many elements are given, not too few.
4. Use uint8_t in favor of std::byte to improve readability.
5. Use sizeof <target> for the memcpy call since it is good practice to avoid writing out of bounds and also avoids the magic 8.

Use ~0ULL to express a uint64_t with all bits set, ensuring one doesn’t forget an f.

 0diff --git a/src/bench/xor.cpp b/src/bench/xor.cpp
 1index f94a1a6f96..fdf41b3696 100644
 2--- a/src/bench/xor.cpp
 3+++ b/src/bench/xor.cpp
 4@@ -96275,10 +96275,7 @@ static void XorHistogram(benchmark::Bench& bench)
 5     assert(total_bytes == 8'129'394'848); // ~8 GB of data
 6     std::shuffle(test_data.begin(), test_data.end(), rng); // Make it more realistic & less predictable
 7 
 8-    std::vector key_bytes{rng.randbytes<std::byte>(8)};
 9-    uint64_t key;
10-    std::memcpy(&key, key_bytes.data(), 8);
11-
12+    const uint64_t key{rng.rand64()};
13     size_t offset{0};
14     bench.batch(total_bytes).unit("byte").run([&] {
15         for (auto& data : test_data) {
16@@ -96293,10 +96290,7 @@ static void AutoFileXor(benchmark::Bench& bench)
17     FastRandomContext rng{/*fDeterministic=*/true};
18     auto data{rng.randbytes<std::byte>(1'000'000)};
19 
20-    std::vector<std::byte> empty_key_bytes(8, std::byte{0}); // Test disabled xor
21-    uint64_t empty_key;
22-    std::memcpy(&empty_key, empty_key_bytes.data(), 8);
23-
24+    const uint64_t empty_key{0}; // Test disabled xor
25     const fs::path test_path = fs::temp_directory_path() / "xor_benchmark.dat";
26     AutoFile f{fsbridge::fopen(test_path, "wb+"), empty_key};
27     bench.batch(data.size()).unit("byte").run([&] {
28diff --git a/src/test/streams_tests.cpp b/src/test/streams_tests.cpp
29index 5e9b607b3a..ac51eb3e51 100644
30--- a/src/test/streams_tests.cpp
31+++ b/src/test/streams_tests.cpp
32@@ -77,9 +77,9 @@ BOOST_AUTO_TEST_CASE(xor_file)
33     auto raw_file{[&](const auto& mode) { return fsbridge::fopen(xor_path, mode); }};
34     const std::vector<uint8_t> test1{1, 2, 3};
35     const std::vector<uint8_t> test2{4, 5};
36-    const std::vector xor_pat{std::byte{0xff}, std::byte{0x00}, std::byte{0xff}, std::byte{0x00}, std::byte{0xff}, std::byte{0x00}, std::byte{0xff}, std::byte{0x00}};
37     uint64_t xor_key;
38-    std::memcpy(&xor_key, xor_pat.data(), 8);
39+    constexpr std::array<uint8_t, sizeof xor_key> xor_pat{std::to_array<uint8_t>({0xff, 0x00, 0xff, 0x00, 0xff, 0x00, 0xff, 0x00})};
40+    std::memcpy(&xor_key, xor_pat.data(), sizeof xor_key);
41 
42     {
43         // Check errors for missing file
44@@ -293,12 +293,8 @@ BOOST_AUTO_TEST_CASE(streams_serializedata_xor)
45     in.push_back(std::byte{0xf0});
46 
47     {
48-        const std::vector xor_pat{std::byte{0xff}, std::byte{0xff}, std::byte{0xff}, std::byte{0xff}, std::byte{0xff}, std::byte{0xff}, std::byte{0xff}, std::byte{0xff}};
49-        uint64_t xor_key;
50-        std::memcpy(&xor_key, xor_pat.data(), 8);
51-
52         DataStream ds{in};
53-        ds.Xor(xor_key);
54+        ds.Xor(~0ULL);
55         BOOST_CHECK_EQUAL("\xf0\x0f"s, ds.str());
56     }
57 
58@@ -307,9 +303,9 @@ BOOST_AUTO_TEST_CASE(streams_serializedata_xor)
59     in.push_back(std::byte{0x0f});
60 
61     {
62-        const std::vector xor_pat{std::byte{0xff}, std::byte{0x0f}, std::byte{0xff}, std::byte{0x0f}, std::byte{0xff}, std::byte{0x0f}, std::byte{0xff}, std::byte{0x0f}};
63         uint64_t xor_key;
64-        std::memcpy(&xor_key, xor_pat.data(), 8);
65+        constexpr std::array<uint8_t, sizeof xor_key> xor_pat{std::to_array<uint8_t>({0xff, 0x0f, 0xff, 0x0f, 0xff, 0x0f, 0xff, 0x0f})};
66+        std::memcpy(&xor_key, xor_pat.data(), sizeof xor_key);
67 
68         DataStream ds{in};
69         ds.Xor(xor_key);

Thanks @fanquake, I thought of that, can you please help me understand the constraints? Wouldn’t that require a cmake generation step from binary to header which would basically produce the exact same lines as what we have now? Would it help if I simply extracted it to a separate header file instead?

So something like 1.28TB instead of 92GB, but I can’t seem to get my head screwed on right today.

Yeah, I’ve edited that part since, my napkin calculations were only true for the first row, in other cases we would need to multiply by the first column - like you did. But the point is that it’s a lot of data that we have to scale down.

but seems slightly slower in my measurements

I thought of that as well, but wanted to avoid floating point conversion (likely the reason for the slowness in your example)

Wouldn’t that require a cmake generation step from binary to header which would basically produce the exact same lines as what we have now?

Yes. See bench/data/block413567.raw & bench/data/block413567.raw.h, where at build time a header file of ~125'000 lines is produced.

Would it help if I simply extracted it to a separate header file instead?

I don’t think so. The point is more to not add 100'000s of lines of “data” to this repo, which doesn’t scale across many benchmarks, creates unusable diffs, leaves (source) files unviewable on GH etc.

I understand you were burned by endianness but I disagree that it’s worth sacrificing readability where endianness is a non-issue.

Thanks @hodlinator for the suggestions, I tried them all, but in the end decided that I value consistency more than coming up with a separate solution for each test case. These are ugly, I agree, but at least they’re testing the setup we’re using in prod. I did however change the hard-coded 8 values to sizeof xor_key (for memcpy) or sizeof(uint64_t) for vector inits.

The point is more to not add 100'000s of lines of “data” to this repo

I have stored the sorted diffs in the end (since the lines are correlated, i.e. more likely to have similar neighbours) and compressed them using .tar.gz (added the generator python script as a gist, please verify) - this way the histogram data is ~100 kb instead of 1.7 MB (thanks for the hint @fanquake). I’ve extended GenerateHeaderFromRaw.cmake with compression support (adjusting GenerateHeaders.cmake to trim the suffix from the header name) and added more safety asserts to make sure the data read back is the same as before.

Code reviewed f2fd1f7c043a2782cb2bf3c9fe7e2f94c17728b5

0₿ git range-diff master 57caa96 f2fd1f7
1₿ git show e314bb7e00 > old
2₿ git show 91a8fde051 > new
3₿ meld old new

Thanks for using more constexpr std::arrays and clearer sizeofs!

Nice that block data could be compressed to such a large extent.

nit: Would prefer the *.cmake changes where broken out into their own commit, keeping only src/bench/CMakeLists.txt as part of the benchmark change.

Concept ACK, but curious for more feedback from @maflcko about this PR. The actual code changes here do not seem too complicated but maybe they make the code less generic. I wonder if you think there are concrete downsides to this PR, or if the changes are ok but possibly not be worth the review effort (as #31144 (comment) seems to suggest)

I’m happy to spend time reviewing this if it improves performance and doesn’t cause other problems.

this way the histogram data is ~100 kb instead of 1.7 MB

Current approach seems ok to me, but wondering it it might be better to just use a sampling of the most common write sizes instead of including the entire histogram. It seems like if you take the top 50 sizes it covers 99.6% of the writes, and might make the test more maintainable and PR easier to understand without changing results too much.

using histogram from https://gist.github.com/l0rinc/a44da845ad32ec89c30525507cdd28ee

 0    cut = 50
 1    hist_count = rest_count = 0
 2    histogram.sort(key=lambda h: (-h[1]*h[0]))
 3    for i, (size, count) in enumerate(histogram):
 4        if i < cut:
 5           print(f"{size=}, {count=}")
 6           hist_count += count
 7        else:
 8           rest_count += count
 9
10    print()
11    print(f"{hist_count=} {hist_count/(hist_count+rest_count)*100:.1f}%")
12    print(f"{rest_count=} {rest_count/(hist_count+rest_count)*100:.1f}%")

 0size=32, count=5369404406
 1size=106, count=1193555153
 2size=71, count=1763349816
 3size=107, count=1064027363
 4size=25, count=2705183236
 5size=33, count=2025696499
 6size=4, count=14983070199
 7size=72, count=827712501
 8size=23, count=2357347372
 9size=1, count=47584838861
10size=8, count=5939128629
11size=21, count=2019807250
12size=22, count=1616301504
13size=34, count=682781008
14size=139, count=155158814
15size=253, count=83729340
16size=105, count=198656556
17size=64, count=275253628
18size=4096, count=3905157
19size=138, count=112918349
20size=252, count=48105681
21size=254, count=38940977
22size=35, count=269339238
23size=218, count=25918921
24size=140, count=37826769
25size=83, count=53818260
26size=217, count=13625647
27size=219, count=12992432
28size=108, count=24662023
29size=488, count=4909014
30size=27, count=87057844
31size=489, count=4483016
32size=28, count=78184146
33size=40, count=50600412
34size=113, count=17829712
35size=65, count=29197009
36size=128, count=13323530
37size=123, count=12986923
38size=37, count=41467794
39size=114, count=9826401
40size=26, count=35870265
41size=130, count=7111451
42size=29, count=30858682
43size=487, count=1836899
44size=70, count=12772097
45size=131, count=6398914
46size=109, count=7506161
47size=490, count=1380253
48size=95901, count=6384
49size=30, count=19197417
50
51hist_count=91959859913 99.6%
52rest_count=382932220 0.4%

Concept ACK, but curious for more feedback from @maflcko about this PR. The actual code changes here do not seem too complicated but maybe they make the code less generic.

There is a good chance that increasing the size of the vector is insufficient, if there is ever a need to increase it to more than 8 bytes, so a complete rewrite may be needed in that case anyway. However, this is just my guess and only time will tell. So I’d say this change is probably fine for now.

Would still be nice to if there was a way to take all of it out of the hot path (possibly with higher overall benefits), but I don’t know if such a change is possible and will replace this pull.

Would still be nice to if there was a way to take all of it out of the hot path

Can you give me hints on how to do that? Since we have a primitive as a key now, we already skip xor with 0 value now, see https://github.com/bitcoin/bitcoin/pull/31144/files#diff-4020c723bb55e114bdc7ff769086a765dcc7ccfb61da2047a315db16c0c7a8b4R295

but wondering it it might be better to just use a sampling of the most common write sizes @fanquake mentioned that he thinks this benchmark could be useful - if he’s fine with the truncated version as well, I’ll simplify (would solve some of @hodlinator’s cmake concerns as well).

It seems like if you take the top 50 sizes it covers 99.6% of the writes

I had the same thought. Obviously there could be an unlikely problem if the remaining 0.04% of writes accounted for the majority of the time, but that seems unlikely. Other than that, taking only the top N seems preferable.

Would still be nice to if there was a way to take all of it out of the hot path

Since blocks are XOR-ed as well, I can’t meaningfully test it with a reindex(-chainstate), so I did 2 full IBDs until 800k blocks, rebased after #30039 with -blocksxor=0 to test whether we can disable xor completely now.

0hyperfine \
1--runs 2 \
2--export-json /mnt/my_storage/IBD-xor-rebased.json \
3--parameter-list COMMIT e1074081c9f1895a4f629dfee347ceae484a10d3,f2fd1f7c043a2782cb2bf3c9fe7e2f94c17728b5 \
4--prepare 'rm -rf /mnt/my_storage/BitcoinData/* && git checkout {COMMIT} && git clean -fxd && git reset --hard && cmake -B build -DCMAKE_BUILD_TYPE=Release -DBUILD_UTIL=OFF -DBUILD_TX=OFF -DBUILD_TESTS=OFF -DENABLE_WALLET=OFF -DINSTALL_MAN=OFF && cmake --build build -j$(nproc)' \
5'COMMIT={COMMIT} ./build/src/bitcoind -datadir=/mnt/my_storage/BitcoinData -stopatheight=800000 -blocksxor=0 -dbcache=10000 -printtoconsole=0'

0Benchmark 1: COMMIT=e1074081c9f1895a4f629dfee347ceae484a10d3 ./build/src/bitcoind -datadir=/mnt/my_storage/BitcoinData -stopatheight=800000 -blocksxor=0 -dbcache=10000 -printtoconsole=0
1  Time (mean ± σ):     25797.921 s ± 61.629 s    [User: 26803.189 s, System: 1457.936 s]
2  Range (min … max):   25754.343 s … 25841.500 s    2 runs
3 
4Benchmark 2: COMMIT=f2fd1f7c043a2782cb2bf3c9fe7e2f94c17728b5 ./build/src/bitcoind -datadir=/mnt/my_storage/BitcoinData -stopatheight=800000 -blocksxor=0 -dbcache=10000 -printtoconsole=0
5  Time (mean ± σ):     23751.046 s ± 342.376 s    [User: 25322.345 s, System: 1509.236 s]
6  Range (min … max):   23508.949 s … 23993.142 s    2 runs

Which indicates a 9% speedup compared to the baseline:

0Summary
1  COMMIT=f2fd1f7c043a2782cb2bf3c9fe7e2f94c17728b5 ./build/src/bitcoind -datadir=/mnt/my_storage/BitcoinData -stopatheight=800000 -blocksxor=0 -dbcache=10000 -printtoconsole=0 ran
2    1.09 ± 0.02 times faster than COMMIT=e1074081c9f1895a4f629dfee347ceae484a10d3 ./build/src/bitcoind -datadir=/mnt/my_storage/BitcoinData -stopatheight=800000 -blocksxor=0 -dbcache=10000 -printtoconsole=0

Would still be nice to if there was a way to take all of it out of the hot path (possibly with higher overall benefits), but I don’t know if such a change is possible and will replace this pull.

Actually, this change here also affects RPC performance, not just internal validation, so this can be done in a follow-up or separate pull, if it is possible at all.

More context: The previous benchmark was for completely turning off XOR - but we can only do that for new IBD by explicitly setting it to 0. But for the majority of cases we likely want to still to the xor, so this PR is meant to speed it up. I have remeasured it with doing full IBD until 800k blocks (two runs to measure stability, since reindex wouldn’t cover all usages of XOR):

0hyperfine \
1--runs 2 \
2--export-json /mnt/my_storage/IBD-xor-rebased.json \
3--parameter-list COMMIT e1074081c9f1895a4f629dfee347ceae484a10d3,f2fd1f7c043a2782cb2bf3c9fe7e2f94c17728b5 \
4--prepare 'rm -rf /mnt/my_storage/BitcoinData/* && git checkout {COMMIT} && git clean -fxd && git reset --hard && cmake -B build -DCMAKE_BUILD_TYPE=Release -DBUILD_UTIL=OFF -DBUILD_TX=OFF -DBUILD_TESTS=OFF -DENABLE_WALLET=OFF -DINSTALL_MAN=OFF && cmake --build build -j$(nproc)' \
5'COMMIT={COMMIT} ./build/src/bitcoind -datadir=/mnt/my_storage/BitcoinData -stopatheight=800000 -dbcache=10000 -printtoconsole=0'

0Benchmark 1: COMMIT=e1074081c9f1895a4f629dfee347ceae484a10d3 ./build/src/bitcoind -datadir=/mnt/my_storage/BitcoinData -stopatheight=800000 -dbcache=10000 -printtoconsole=0
1  Time (mean ± σ):     25601.461 s ± 65.686 s    [User: 27025.116 s, System: 1586.908 s]
2  Range (min … max):   25555.014 s … 25647.907 s    2 runs
3 
4Benchmark 2: COMMIT=f2fd1f7c043a2782cb2bf3c9fe7e2f94c17728b5 ./build/src/bitcoind -datadir=/mnt/my_storage/BitcoinData -stopatheight=800000 -dbcache=10000 -printtoconsole=0
5  Time (mean ± σ):     24526.781 s ± 389.029 s    [User: 25525.801 s, System: 1552.625 s]
6  Range (min … max):   24251.697 s … 24801.866 s    2 runs

Which indicates that this will speed up IBD by roughly 4% on average (now that 30039 was merged the difference is more obvious):

0Summary
1 COMMIT=f2fd1f7c043a2782cb2bf3c9fe7e2f94c17728b5 ./build/src/bitcoind -datadir=/mnt/my_storage/BitcoinData -stopatheight=800000 -dbcache=10000 -printtoconsole=0 ran
2   1.04 ± 0.02 times faster than COMMIT=e1074081c9f1895a4f629dfee347ceae484a10d3 ./build/src/bitcoind -datadir=/mnt/my_storage/BitcoinData -stopatheight=800000 -dbcache=10000 -printtoconsole=0

Thanks for the reviews and hints, I’ve pushed the following changes:

• Reverted all cmake changes @hodlinator mentioned and histogram archives, and based on the hints of @ryanofsky and @maflcko I’ve kept only the top entries (by frequency, re-sorted by size), making sure that the really big write-vectors are also covered (so kept the first 1000 instead of just the first 50). This enabled putting all the data in the sourcefile.
• Added Assumes to each xor to check that we don’t have any useless calls with 0 keys - making sure we “turn off” the feature when we can.