benchmark: Improve SipHash_32b accuracy to avoid potential optimization issues

l0rinc commented at 2:05 pm on June 27, 2024: contributor

This PR stems from the discussions in #30317 (review)

The previous benchmark for SipHash was slightly less accurate in representing real-world usage and allowed for potential compiler optimizations that could invalidate the benchmark. This change aims to ensure the benchmark produces more realistic results.

By modifying the initial values and only incrementing the bytes of val, the benchmark should reflects a more typical usage patterns - and prevent the compiler from optimizing away the calculations.

On my M1 processor the benchmark’s speed changed significantly (but the CI seems to produce the same result as before):

cmake -B build -DCMAKE_BUILD_TYPE=Release -DBUILD_BENCH=ON && cmake –build build -j10 && ./build/src/bench/bench_bitcoin –filter=SipHash_32b –min-time=1000

Before:

ns/op	op/s	err%	total	benchmark
43.90	22,780,157.00	0.1%	1.09	`SipHash_32b`
43.92	22,768,946.21	0.0%	1.09	`SipHash_32b`
43.91	22,775,604.29	0.1%	1.09	`SipHash_32b`

After (note, the hash didn’t change, only the benchmark did):

ns/op	op/s	err%	total	benchmark
27.63	36,193,173.27	0.1%	1.09	`SipHash_32b`
27.61	36,220,514.83	0.1%	1.09	`SipHash_32b`
27.64	36,180,519.38	0.1%	1.09	`SipHash_32b`

DrahtBot commented at 2:05 pm on June 27, 2024: contributor

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

Code Coverage

For detailed information about the code coverage, see the test coverage report.

Reviews

See the guideline for information on the review process.

Type	Reviewers
Stale ACK	laanwj, maflcko

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

Conflicts

No conflicts as of last run.

l0rinc renamed this:
~~benchmark: Refactor SipHash_32b to improve accuracy and potential avoid optimization issues~~
refactor: Refactor SipHash_32b to improve accuracy and potential avoid optimization issues
on Jun 27, 2024

DrahtBot added the label Refactoring on Jun 27, 2024

l0rinc renamed this:
~~refactor: Refactor SipHash_32b to improve accuracy and potential avoid optimization issues~~
refactor: Improve SipHash_32b accuracy and potential avoid optimization issues
on Jun 27, 2024

l0rinc renamed this:
~~refactor: Improve SipHash_32b accuracy and potential avoid optimization issues~~
refactor: Improve SipHash_32b accuracy to avoid potential optimization issues
on Jun 27, 2024

maflcko commented at 2:10 pm on June 27, 2024: member

Changing the behavior of something is not a refactor.

l0rinc renamed this:
~~refactor: Improve SipHash_32b accuracy to avoid potential optimization issues~~
benchmark: Improve SipHash_32b accuracy to avoid potential optimization issues
on Jun 27, 2024

maflcko removed the label Refactoring on Jun 27, 2024

DrahtBot added the label CI failed on Jul 22, 2024

DrahtBot commented at 10:17 am on July 22, 2024: contributor

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

Make sure to run all tests locally, according to the documentation.

The failure may 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.

l0rinc force-pushed on Jul 22, 2024

DrahtBot removed the label CI failed on Jul 22, 2024

achow101 requested review from laanwj on Oct 15, 2024

achow101 requested review from josibake on Oct 15, 2024

laanwj added the label Tests on Oct 16, 2024

in src/bench/crypto_hash.cpp:200 in 8c4e14deda outdated

195+    auto k0 = rng.rand64(), k1 = rng.rand64();
196+    auto val = rng.rand256();
197     bench.run([&] {
198-        *((uint64_t*)x.begin()) = SipHashUint256(0, ++k1, x);
199+        ankerl::nanobench::doNotOptimizeAway(SipHashUint256(k0, k1, val));
200+        ++k0; ++k1; ++(*val.begin());

laanwj commented at 9:21 am on October 16, 2024:

nit: please put multiple statements on multiple lines, this is pretty hard to read code as-is :sweat_smile:

l0rinc commented at 1:11 pm on October 16, 2024:

Thanks, done

laanwj commented at 9:22 am on October 16, 2024: member

ACK on overall change, small nit

l0rinc force-pushed on Oct 16, 2024

laanwj approved

laanwj commented at 8:05 am on October 17, 2024: member

ACK c49cc30b8185a50b4aa00cf705d313c8aa9482a3

in src/bench/crypto_hash.cpp:198 in c49cc30b81 outdated

196-    uint64_t k1 = 0;
197+    FastRandomContext rng(true);
198+    auto k0 = rng.rand64(), k1 = rng.rand64();
199+    auto val = rng.rand256();
200     bench.run([&] {
201-        *((uint64_t*)x.begin()) = SipHashUint256(0, ++k1, x);

maflcko commented at 10:01 am on October 17, 2024:

Maybe I am wrong, but in theory I think that a byte array has weaker memory alignment requirements than uint64_t. So this is (in a strict sense) undefined behavior anyway. I presume it could be tested by adding a padding byte to uint256 and compile with ubsan, and then run this bench to observe the failure.

laanwj commented at 10:24 am on October 17, 2024:

This is a great point. Instead of the type-pun, we’d likely want to make this safer by assigning the result to a uint64_t then memcpy it in instead. That likely isn’t going to be significantly slower.

Edit: Wait, this code is being removed. Sorry.

maflcko commented at 10:30 am on October 17, 2024:

Edit: Wait, this code is being removed. Sorry.

Yeah, sorry, I was just trying to come up with another reason to change the code here :sweat_smile:

l0rinc commented at 10:48 am on October 17, 2024:

Do you have any concrete recommendation that I could apply here?

maflcko commented at 11:31 am on October 17, 2024:

Sorry again, I am just trying to add useful context that hasn’t been mentioned before. I just have an allergy against undefined behavior, so I wanted to mention that the previous code may have had one.

As a fun fact, I tried it myself and in theory the UB should look like:

 0src/bench/crypto_hash.cpp:198:9: runtime error: store to misaligned address 0x7fffdb31cb81 for type 'uint64_t' (aka 'unsigned long'), which requires 8 byte alignment
 10x7fffdb31cb81: note: pointer points here
 2 00 00 00  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  00 00 00 00 00
 3              ^ 
 4    [#0](/bitcoin-bitcoin/0/) 0x556ee2095df7 in SipHash_32b(ankerl::nanobench::Bench&)::$_0::operator()() const bld-cmake/src/bench/./src/bench/crypto_hash.cpp:198:33
 5    [#1](/bitcoin-bitcoin/1/) 0x556ee2095df7 in ankerl::nanobench::Bench& ankerl::nanobench::Bench::run<SipHash_32b(ankerl::nanobench::Bench&)::$_0>(SipHash_32b(ankerl::nanobench::Bench&)::$_0&&) bld-cmake/src/bench/./src/bench/nanobench.h:1221:13
 6    [#2](/bitcoin-bitcoin/2/) 0x556ee2092fc6 in SipHash_32b(ankerl::nanobench::Bench&) bld-cmake/src/bench/./src/bench/crypto_hash.cpp:197:11
 7
 8...
 9
10SUMMARY: UndefinedBehaviorSanitizer: misaligned-pointer-use ./src/bench/crypto_hash.cpp:198:9

l0rinc commented at 11:39 am on October 17, 2024:

Thank you for checking!

maflcko approved

maflcko commented at 10:02 am on October 17, 2024: member

lgtm ACK c49cc30b8185a50b4aa00cf705d313c8aa9482a3

maflcko added this to the milestone 29.0 on Oct 17, 2024

Refactor SipHash_32b benchmark to improve accuracy and avoid optimization issues

- Modify `SipHash_32b` benchmark to use `FastRandomContext` for generating initial values.
- Cycle through and increment each byte of the `uint256` value to ensure no part of it can be optimized away.

The lack of "recursion" (where the method call overwrites the used inputs partially) and the systematic modification of each input byte makes the benchmark usage more reliable and thorough.

c88b1bde75

in src/bench/crypto_hash.cpp:202 in c49cc30b81 outdated

200     bench.run([&] {
201-        *((uint64_t*)x.begin()) = SipHashUint256(0, ++k1, x);
202+        ankerl::nanobench::doNotOptimizeAway(SipHashUint256(k0, k1, val));
203+        ++k0;
204+        ++k1;
205+        ++(*val.begin());

maflcko commented at 4:25 pm on October 17, 2024:

This fails ubsan:

0src/bench/crypto_hash.cpp:202:9: runtime error: implicit conversion from type 'int' of value 256 (32-bit, signed) to type 'unsigned char' changed the value to 0 (8-bit, unsigned)
1    [#0](/bitcoin-bitcoin/0/) 0x55b763589f3f in SipHash_32b(ankerl::nanobench::Bench&)::$_0::operator()() const bld-cmake/src/bench/./src/bench/crypto_hash.cpp:202:9
2
3
4...
5
6SUMMARY: UndefinedBehaviorSanitizer: implicit-signed-integer-truncation /home/marco/workspace/b-c/src/bench/crypto_hash.cpp:202:9

To reproduce you’ll have to run the bench under ubsan/isan without -sanity-check.

l0rinc commented at 12:26 pm on October 18, 2024:

I couldn’t reproduce the warning locally, but changed it to modify every value in val.data() instead to make sure none of them can be optimized away - would you be so kind and check if this solves the undefined behavior?

laanwj commented at 10:09 am on October 20, 2024:

i’m very confused about this one; begin() returns a unsigned char*, and unsigned values are definitely allowed to overflow within defined behavior. Also, m_data is an array (of fixed size) so by definition [0] will not be out of bounds.

laanwj commented at 11:43 am on October 20, 2024:

a workaround may be to do val.data()[0] = (val.data()[0] + 1) & 0xff; to make the wrap-around explicit, the C++ compiler will almost certainly just optimize it away. It’s also slightly more readable i think.

sipa commented at 11:47 am on October 20, 2024:

This is not UB, but ubsan is explicitly told to warn for certain error-prone but implementation-defined or well-defined behaviors.

If the effect is deliberate, it is possible to add the function name to the ubsan suppressions.

l0rinc commented at 11:48 am on October 20, 2024:

Would you prefer I ‘& 0xFF’ the current implementation?

laanwj commented at 12:56 pm on October 20, 2024:

dunno, i would prefer &0xff to adding a supression (if that works to make the error go away, ofc), it more explicitly defines what is expected

maflcko commented at 2:05 pm on October 23, 2024:

Yeah, this is a bit confusing. UndefinedBehaviorSanitizer is just the name of the tool, not an implication that the issue it found is UB.

If you want to reproduce, you’ll have to compile with the integer sanitizer (yes, to add to the confusion, the tool is called different here). Also, it only works with clang++/clang, so you’ll have to select that as well during cmake -B. Maybe this can be documented in doc/developer-notes.md?

Edit: (reply to &0xff): An alternative to &0xff would be to cast to the underlying type uint8_t(bla), but both are fine and identical.

maflcko commented at 7:31 pm on October 24, 2024:

Maybe this can be documented in doc/developer-notes.md?

(An alternative would be to add the CI configs to the cmake presets file, because the ISan is part of one. )

l0rinc force-pushed on Oct 18, 2024

maflcko removed this from the milestone 29.0 on Oct 24, 2024

benchmark: Improve SipHash_32b accuracy to avoid potential optimization issues #30349

Code Coverage

Reviews

Conflicts