[IBD] precalculate SipHash constant salt calculations #30442

pull l0rinc wants to merge 4 commits into bitcoin:master from l0rinc:paplorinc/siphash changing 7 files +142 −33
  1. l0rinc commented at 3:01 pm on July 12, 2024: contributor

    This change is part of [IBD] - Tracking PR for speeding up Initial Block Download

    Summary

    The in-memory representation of the UTXO set uses (salted) SipHash for avoiding key collision attacks.

    Hashing a uint256 key is done so often that a specialized optimization was extracted to SipHashUint256Extra. The constant salting operations were already extracted in the general case, this PR adjust the main specialization similarly.

    Details

    Previously, only k0 and k1 were stored, causing the constant xor operations to be recomputed in every call to SipHashUint256Extra. This commit adds a dedicated Uint256ExtraSipHasher class that caches the initial state (v0-v3) and to perform the SipHash computation on a uint256 (with an extra parameter), hiding the constant computation details from higher-level code and improving efficiency (as suggested by @sipa in #30442 (comment)).

    Measurements

    cmake -B build -DBUILD_BENCH=ON -DCMAKE_BUILD_TYPE=Release && cmake –build build -j$(nproc) && build/bin/bench_bitcoin -filter=‘SaltedOutpointHasherBench’ -min-time=10000

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

    Before:

    ns/op op/s err% total benchmark
    58.60 17,065,922.04 0.3% 11.02 SaltedOutpointHasherBench_create_set
    11.97 83,576,684.83 0.1% 11.01 SaltedOutpointHasherBench_hash
    14.50 68,985,850.12 0.3% 10.96 SaltedOutpointHasherBench_match
    13.90 71,942,033.47 0.4% 11.03 SaltedOutpointHasherBench_mismatch

    After:

    ns/op op/s err% total benchmark
    57.27 17,462,299.19 0.1% 11.02 SaltedOutpointHasherBench_create_set
    11.24 88,997,888.48 0.3% 11.04 SaltedOutpointHasherBench_hash
    13.91 71,902,014.20 0.2% 11.01 SaltedOutpointHasherBench_match
    13.29 75,230,390.31 0.1% 11.00 SaltedOutpointHasherBench_mismatch

    compared to master:

    0create_set - 17,462,299.19 / 17,065,922.04 - 2.3% faster
1hash       - 88,997,888.48 / 83,576,684.83 - 6.4% faster
2match      - 71,902,014.20 / 68,985,850.12 - 4.2% faster
3mismatch   - 75,230,390.31 / 71,942,033.47 - 4.5% faster

    C++ compiler …………………….. GNU 13.3.0

    Before:

    ns/op op/s err% ins/op cyc/op IPC bra/op miss% total benchmark
    136.76 7,312,133.16 0.0% 1,086.67 491.12 2.213 119.54 1.1% 11.01 SaltedOutpointHasherBench_create_set
    23.82 41,978,882.62 0.0% 252.01 85.57 2.945 4.00 0.0% 11.00 SaltedOutpointHasherBench_hash
    60.42 16,549,695.42 0.1% 460.51 217.04 2.122 21.00 1.4% 10.99 SaltedOutpointHasherBench_match
    78.66 12,713,595.35 0.1% 555.59 282.52 1.967 20.19 2.2% 10.74 SaltedOutpointHasherBench_mismatch

    After:

    ns/op op/s err% ins/op cyc/op IPC bra/op miss% total benchmark
    135.38 7,386,349.49 0.0% 1,078.19 486.16 2.218 119.56 1.1% 11.00 SaltedOutpointHasherBench_create_set
    23.67 42,254,558.08 0.0% 247.01 85.01 2.906 4.00 0.0% 11.00 SaltedOutpointHasherBench_hash
    58.95 16,962,220.14 0.1% 446.55 211.74 2.109 20.86 1.4% 11.01 SaltedOutpointHasherBench_match
    76.98 12,991,047.69 0.1% 548.93 276.50 1.985 20.25 2.3% 10.72 SaltedOutpointHasherBench_mismatch 
    0compared to master:
1create_set -  7,386,349.49 / 7,312,133.16  - 1.0% faster
2hash       - 42,254,558.08 / 41,978,882.62 - 0.6% faster
3match      - 16,962,220.14 / 16,549,695.42 - 2.4% faster
4mismatch   - 12,991,047.69 / 12,713,595.35 - 2.1% faster
  2. DrahtBot commented at 3:01 pm on July 12, 2024: contributor

    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/30442.

    Reviews

    See the guideline for information on the review process.

    Type Reviewers
    Stale ACK laanwj, ismaelsadeeq

    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:

    • #32189 (refactor: Txid type safety (parent PR) by marcofleon)
    • #32128 (Draft: CCoinMap Experiments by martinus)

    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.

  3. l0rinc force-pushed on Jul 12, 2024
  4. l0rinc renamed this:
    Precalculate SipHash constant XOR with k0 and k1 in SaltedOutpointHasher
    optimization: Precalculate SipHash constant XOR with k0 and k1 in SaltedOutpointHasher
    on Jul 12, 2024
  5. l0rinc marked this as ready for review on Jul 13, 2024
  6. l0rinc commented at 12:40 pm on July 14, 2024: contributor
    @andrewtoth, this is another tiny addition to the coincache speedup, your review would be welcome.
  7. andrewtoth commented at 3:36 pm on July 14, 2024: contributor

    I did not see any improvement in the benchmark with this change. Running ./src/bench/bench_bitcoin -filter=.*Out[pP]oint.*

    commit 3b7b82b4b0c39a38538aae2cba10bec3907c5cbf

    0|               ns/op |                op/s |    err% |          ins/op |          cyc/op |         bra/op |   miss% |     total | benchmark
1|--------------------:|--------------------:|--------:|----------------:|----------------:|---------------:|--------:|----------:|:----------
2|                1.31 |      766,241,272.84 |    0.2% |            0.00 |            0.00 |           0.00 |    0.0% |      0.01 | `COutPoint_equality_match`
3|                0.64 |    1,561,309,649.35 |    0.0% |            0.00 |            0.00 |           0.00 |    0.0% |      0.01 | `COutPoint_equality_mismatch`
4|              107.62 |        9,292,298.54 |    1.7% |            0.00 |            0.00 |           0.00 |    0.0% |      0.10 | `SaltedOutpointHasherBenchmark_create_set`
5|               23.36 |       42,799,791.14 |    0.0% |            0.00 |            0.00 |           0.00 |    0.0% |      0.01 | `SaltedOutpointHasherBenchmark_hash`
6|               48.78 |       20,502,210.98 |    0.1% |            0.00 |            0.00 |           0.00 |    0.0% |      0.01 | `SaltedOutpointHasherBenchmark_match`
7|               69.31 |       14,426,956.77 |    0.3% |            0.00 |            0.00 |           0.00 |    0.0% |      0.01 | `SaltedOutpointHasherBenchmark_mismatch`

    commit 7ac4e3aaf345a06fdde463100c45c4295d730820

    0|               ns/op |                op/s |    err% |          ins/op |          cyc/op |         bra/op |   miss% |     total | benchmark
1|--------------------:|--------------------:|--------:|----------------:|----------------:|---------------:|--------:|----------:|:----------
2|                1.30 |      766,440,414.89 |    0.0% |            0.00 |            0.00 |           0.00 |    0.0% |      0.01 | `COutPoint_equality_match`
3|                1.02 |      982,018,502.07 |    0.2% |            0.00 |            0.00 |           0.00 |    0.0% |      0.01 | `COutPoint_equality_mismatch`
4|              108.92 |        9,180,628.87 |    0.9% |            0.00 |            0.00 |           0.00 |    0.0% |      0.10 | `SaltedOutpointHasherBenchmark_create_set`
5|               23.69 |       42,213,365.83 |    0.1% |            0.00 |            0.00 |           0.00 |    0.0% |      0.01 | `SaltedOutpointHasherBenchmark_hash`
6|               47.90 |       20,876,369.10 |    0.1% |            0.00 |            0.00 |           0.00 |    0.0% |      0.01 | `SaltedOutpointHasherBenchmark_match`
7|               70.10 |       14,265,655.03 |    0.1% |            0.00 |            0.00 |           0.00 |    0.0% |      0.01 | `SaltedOutpointHasherBenchmark_mismatch`
  8. l0rinc commented at 5:58 pm on July 14, 2024: contributor
    That’s disappointing, thanks for checking, something’s still off with my compiler, it seems. After I finish benching #28280 (comment), I’ll try this again on the dedicates server instead. I’m also a bit surprised that the ratios are completely different compared to my measurements, e.g. SaltedOutpointHasherBenchmark_match and _mismatch are 40% off, while in my case they’re basically equal. Are compilers this different? Could you please send me the exact command and compiler versions you’ve used? Thanks!
  9. l0rinc marked this as a draft on Jul 15, 2024
  10. andrewtoth commented at 3:55 pm on July 15, 2024: contributor

    Could you please send me the exact command and compiler versions you’ve used?

    gcc version 11.4.0 (Ubuntu 11.4.0-1ubuntu1~22.04)

    I ran ./configure --enable-bench make ./src/bench/bench_bitcoin -filter=.*Out[pP]oint.*

  11. l0rinc commented at 10:15 am on July 16, 2024: contributor

    Now that the other benchmark finished after a few days, I ran this on a gcc (Debian 12.2.0-14) 12.2.0.

    After the first run I got a warning of:

    Warning, results might be unstable:

    • CPU frequency scaling enabled: CPU 0 between 800.0 and 4,200.0 MHz
    • CPU governor is ‘powersave’ but should be ‘performance’
    • Turbo is enabled, CPU frequency will fluctuate

    which I’ve fixed and also ran pyperf system tune. Additionally I set a --min-time=10000, otherwise the results weren’t consistent between runs. I ran each change twice to make sure they’re stable.

    before:

    0./configure --enable-bench
1git checkout 7ac4e3aaf345a06fdde463100c45c4295d730820 && git reset --hard
2make -j$(nproc) && ./src/bench/bench_bitcoin -filter='.*Out[pP]oint.*' --min-time=10000
    ns/op op/s err% ins/op cyc/op IPC bra/op miss% total benchmark
    135.01 7,406,978.51 0.1% 1,060.42 485.49 2.184 120.72 1.1% 11.05 SaltedOutpointHasherBenchmark_create_set
    23.89 41,860,205.94 0.0% 252.01 85.94 2.932 4.00 0.0% 11.00 SaltedOutpointHasherBenchmark_hash
    59.81 16,719,701.99 0.1% 451.14 215.16 2.097 20.83 1.5% 11.00 SaltedOutpointHasherBenchmark_match
    79.21 12,624,726.37 0.0% 566.84 284.97 1.989 20.50 2.3% 10.74 SaltedOutpointHasherBenchmark_mismatch
    ns/op op/s err% ins/op cyc/op IPC bra/op miss% total benchmark
    133.71 7,479,023.41 0.0% 1,060.38 480.97 2.205 120.72 1.1% 11.03 SaltedOutpointHasherBenchmark_create_set
    23.87 41,894,947.89 0.0% 252.01 85.88 2.935 4.00 0.0% 11.00 SaltedOutpointHasherBenchmark_hash
    60.05 16,652,312.90 0.1% 452.20 216.05 2.093 20.86 1.3% 11.00 SaltedOutpointHasherBenchmark_match
    79.90 12,515,491.22 0.1% 566.85 287.46 1.972 20.50 2.3% 10.74

    after:

    0git checkout 3b7b82b4b0c39a38538aae2cba10bec3907c5cbf && git reset --hard
1make -j$(nproc) && ./src/bench/bench_bitcoin -filter='.*Out[pP]oint.*' --min-time=10000
    ns/op op/s err% ins/op cyc/op IPC bra/op miss% total benchmark
    132.60 7,541,596.87 0.0% 1,045.84 476.97 2.193 120.72 1.1% 11.03 SaltedOutpointHasherBenchmark_create_set
    23.43 42,674,820.33 0.0% 246.01 84.29 2.918 4.00 0.0% 11.00 SaltedOutpointHasherBenchmark_hash
    58.90 16,977,444.58 0.0% 444.45 211.91 2.097 20.92 1.3% 11.00 SaltedOutpointHasherBenchmark_match
    78.29 12,773,764.99 0.0% 544.01 281.65 1.932 20.29 2.6% 10.73 SaltedOutpointHasherBenchmark_mismatch
    ns/op op/s err% ins/op cyc/op IPC bra/op miss% total benchmark
    132.75 7,533,102.65 0.0% 1,045.87 477.53 2.190 120.72 1.1% 11.02 SaltedOutpointHasherBenchmark_create_set
    23.44 42,660,977.02 0.0% 246.01 84.33 2.917 4.00 0.0% 11.00 SaltedOutpointHasherBenchmark_hash
    59.05 16,934,798.45 0.0% 444.96 212.44 2.094 20.93 1.3% 11.01 SaltedOutpointHasherBenchmark_match
    76.32 13,103,542.96 0.1% 531.55 274.56 1.936 19.99 2.4% 10.71 SaltedOutpointHasherBenchmark_mismatch

    Resulting in:

    SaltedOutpointHasherBenchmark_create_set: Before Avg = 7443000.96, After Avg = 7537349.76, Increase = 1.27%

    SaltedOutpointHasherBenchmark_hash: Before Avg = 41877576.91, After Avg = 42667898.67, Increase = 1.89%

    SaltedOutpointHasherBenchmark_match: Before Avg = 16686007.45, After Avg = 16956121.52, Increase = 1.62%

    SaltedOutpointHasherBenchmark_mismatch: Before Avg = 12570108.79, After Avg = 12938653.98, Increase = 2.93% @andrewtoth, what do you think, can you try reproducing these results?

  12. l0rinc marked this as ready for review on Jul 18, 2024
  13. andrewtoth commented at 3:24 am on July 25, 2024: contributor
    Based on your benchmark results, I don’t think this can be called an optimization. It seems to be worse for one benchmark, better in another, and roughly the same for the rest. The description also notes that this will not be noticeable by users. In light of that, does the motivation for this PR still hold?
  14. l0rinc closed this on Jul 25, 2024
  15. l0rinc commented at 6:11 pm on July 26, 2024: contributor
    I’ve removed the COutPoint_equality changes and benchmarks (updated the comments to avoid confusion), the SaltedOutpointHasher speed gains remain. I’ll let you decide if it’s worth doing the change or not.
  16. l0rinc reopened this on Jul 26, 2024
  17. l0rinc force-pushed on Jul 26, 2024
  18. l0rinc force-pushed on Jul 26, 2024
  19. DrahtBot commented at 4:18 pm on August 30, 2024: contributor

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

    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.

  20. DrahtBot added the label CI failed on Aug 30, 2024
  21. l0rinc force-pushed on Aug 31, 2024
  22. l0rinc renamed this:
    optimization: Precalculate SipHash constant XOR with k0 and k1 in SaltedOutpointHasher
    optimization: precalculate SipHash constant XOR with k0 and k1 in SaltedOutpointHasher
    on Aug 31, 2024
  23. DrahtBot removed the label CI failed on Aug 31, 2024
  24. DrahtBot added the label CI failed on Oct 13, 2024
  25. l0rinc force-pushed on Oct 15, 2024
  26. achow101 requested review from josibake on Oct 15, 2024
  27. l0rinc force-pushed on Oct 16, 2024
  28. l0rinc commented at 1:15 pm on October 16, 2024: contributor
    @laanwj This is the optimization that relies on #30349, would really appreciate you input on it.
  29. DrahtBot removed the label CI failed on Oct 16, 2024
  30. laanwj requested review from laanwj on Oct 17, 2024
  31. laanwj added the label Utils/log/libs on Oct 17, 2024
  32. l0rinc closed this on Jan 19, 2025
  33. laanwj commented at 9:50 am on January 20, 2025: member

    Sorry for taking so long.

    FWIW, Code review ACK bc959f5ba9a62b41b36cc662aa176b03969be176. Moving the magic numbers to constants seems like a good idea to me. It’s good to add the benchmarks. And although the speed change is neglilible (as would be expected from factoring out ~four xor instructions), it doesn’t complicate the code much either.

  34. l0rinc reopened this on Jan 20, 2025
  35. in src/bench/crypto_hash.cpp:212 in 6ce13a33c6 outdated 
    199@@ -199,6 +200,98 @@ static void SipHash_32b(benchmark::Bench& bench)
200     });
201 }
202 
203+static void SaltedOutpointHasherBenchmark_hash(benchmark::Bench& bench)
204+{
205+    FastRandomContext rng(true);
206+    constexpr size_t size = 1000;
    ismaelsadeeq commented at 9:33 pm on January 23, 2025:

    In “bench: Add COutPoint and SaltedOutpointHasher benchmarks” 6ce13a33c6901d820467b9c24a03ca3861d91640

    You could factor out size as a static global variable and reuse it in the benchmarks to avoid repetition!

    l0rinc commented at 10:01 pm on January 23, 2025:
    I thought of that but they each have different difficulties, so they should be tuned separately (i.e. if something takes 2x as much time per round, we likely want fewer repetitions)
  36. in src/bench/crypto_hash.cpp:240 in 6ce13a33c6 outdated 
    229+    std::vector<COutPoint> value_vector;
230+    values.reserve(size);
231+    value_vector.reserve(size);
232+
233+    for (size_t i = 0; i < size; ++i) {
234+        COutPoint outpoint{Txid::FromUint256(rng.rand256()), rng.rand32()};
    ismaelsadeeq commented at 9:34 pm on January 23, 2025:

    In “bench: Add COutPoint and SaltedOutpointHasher benchmarks” 6ce13a33c6901d820467b9c24a03ca3861d91640

    You could create a helper for inserting random outpoints to reduce duplication.

    l0rinc commented at 10:04 pm on January 23, 2025:
    If I need to edit again, I’ll consider it, thanks
  37. in src/bench/crypto_hash.cpp:223 in 6ce13a33c6 outdated 
    212+
213+    const SaltedOutpointHasher hasher;
214+    bench.batch(size).run([&] {
215+        size_t result = 0;
216+        for (const auto& outpoint : outpoints) {
217+            result ^= hasher(outpoint);
    ismaelsadeeq commented at 9:35 pm on January 23, 2025:

    In “bench: Add COutPoint and SaltedOutpointHasher benchmarks” 6ce13a33c6901d820467b9c24a03ca3861d91640

    Why are you xoring the hashes?

    l0rinc commented at 10:00 pm on January 23, 2025:
    Just to make sure they’re not optimized away - ankerl::nanobench::doNotOptimizeAway is likely more costly than a simple xor. Do you have a better idea?
  38. in src/bench/crypto_hash.cpp:241 in 6ce13a33c6 outdated 
    230+    values.reserve(size);
231+    value_vector.reserve(size);
232+
233+    for (size_t i = 0; i < size; ++i) {
234+        COutPoint outpoint{Txid::FromUint256(rng.rand256()), rng.rand32()};
235+        values.emplace(outpoint);
    ismaelsadeeq commented at 9:38 pm on January 23, 2025:

    In “bench: Add COutPoint and SaltedOutpointHasher benchmarks” 6ce13a33c6901d820467b9c24a03ca3861d91640

    Why aren’t you benching insertion to the unordered map?

    l0rinc commented at 10:03 pm on January 23, 2025:
    I’d be measuring the map’s behavior in that case, not the hashing
    l0rinc commented at 10:04 pm on January 23, 2025:
    But there is a SaltedOutpointHasherBenchmark_create_set which does something similar
  39. ismaelsadeeq commented at 9:44 pm on January 23, 2025: member

    I’ve thoroughly reviewed 6ce13a33c6901d820467b9c24a03ca3861d91640 and lightly reviewed bc959f5ba9a62b41b36cc662aa176b03969be176.

    I’ve noticed a slight increase in performance.

    Moving the magic numbers to constants seems like a good idea to me. It’s good to add the benchmarks.

    Same!

    ACK bc959f5ba9a62b41b36cc662aa176b03969be176

  40. DrahtBot requested review from ismaelsadeeq on Jan 23, 2025
  41. sipa commented at 3:24 pm on February 1, 2025: member

    I’m not convinced about the approach here: it’s leaking a SipHash implementation detail (the way the initial v0..v3 values are computed) into a higher layer (util/hasher.h).

    I would suggest to have a Uint256ExtraSipHasher class instead of the SipHashUint256Extra function, with a constructor that takes k0, k1 like the function current before, and computes the v0..v3 values, and then an uint64_t Uint256ExtraSipHasher::operator()(const uint256& val, uint32_t extra) const noexcept which contains the meat of the computation.

  42. l0rinc force-pushed on Feb 1, 2025
  43. l0rinc force-pushed on Feb 1, 2025
  44. l0rinc commented at 7:42 pm on February 1, 2025: contributor

    Thanks a lot for the review @sipa. The SipHash leaking into the hasher also bothered me a lot (it’s also why I closed it a few weeks ago before @laanwj revived it), but I like the Uint256ExtraSipHasher wrapper suggestion (basically the same as CSipHasher now, except for the extra tmp and count fields: both constructors cache the constant parts now.

    I’m not sure why the suggested name was Uint256ExtraSipHasher and not SipHasherUint256Extra (to be more similar to SipHashUint256), but I don’t really mind either way.

    I pushed a separate rebase (without conflicts), to simplify review, and the requested changes (and a few more related cleanups) in https://github.com/bitcoin/bitcoin/compare/2885e7785417b57a3f3cad420196837965572258..d848da97f2e4fd0997507b2d1c2a1f4a2325193d

    I’d like to clean up SipHash after this change (get rid of templates, reduce duplication) in a separate PR - if this gets merged.

  45. l0rinc renamed this:
    optimization: precalculate SipHash constant XOR with k0 and k1 in SaltedOutpointHasher
    [IBD] Precalculate some SipHash constant calculations
    on Mar 12, 2025
  46. l0rinc renamed this:
    [IBD] Precalculate some SipHash constant calculations
    [IBD] precalculate some SipHash constant calculations
    on Mar 12, 2025
  47. l0rinc renamed this:
    [IBD] precalculate some SipHash constant calculations
    [IBD] precalculate SipHash constant salt calculations
    on Mar 12, 2025
  48. l0rinc force-pushed on Mar 12, 2025
  49. bench: Add COutPoint and SaltedOutpointHasher benchmarks 
    This commit introduces new benchmarks to measure the performance of various operations using
SaltedOutpointHasher, including hash computation, set operations, and set creation.

These benchmarks are intended to provide insights about coin caching performance (e.g. during IBD).

> cmake -B build -DBUILD_BENCH=ON -DCMAKE_BUILD_TYPE=Release && cmake --build build -j$(nproc) && build/src/bench/bench_bitcoin -filter='SaltedOutpointHasherBench.*' -min-time=10000

> C++ compiler .......................... AppleClang 16.0.0.16000026

|               ns/op |                op/s |    err% |     total | benchmark
|--------------------:|--------------------:|--------:|----------:|:----------
|               58.60 |       17,065,922.04 |    0.3% |     11.02 | `SaltedOutpointHasherBench_create_set`
|               11.97 |       83,576,684.83 |    0.1% |     11.01 | `SaltedOutpointHasherBench_hash`
|               14.50 |       68,985,850.12 |    0.3% |     10.96 | `SaltedOutpointHasherBench_match`
|               13.90 |       71,942,033.47 |    0.4% |     11.03 | `SaltedOutpointHasherBench_mismatch`

> C++ compiler .......................... GNU 13.3.0

|               ns/op |                op/s |    err% |          ins/op |          cyc/op |    IPC |         bra/op |   miss% |     total | benchmark
|--------------------:|--------------------:|--------:|----------------:|----------------:|-------:|---------------:|--------:|----------:|:----------
|              136.76 |        7,312,133.16 |    0.0% |        1,086.67 |          491.12 |  2.213 |         119.54 |    1.1% |     11.01 | `SaltedOutpointHasherBench_create_set`
|               23.82 |       41,978,882.62 |    0.0% |          252.01 |           85.57 |  2.945 |           4.00 |    0.0% |     11.00 | `SaltedOutpointHasherBench_hash`
|               60.42 |       16,549,695.42 |    0.1% |          460.51 |          217.04 |  2.122 |          21.00 |    1.4% |     10.99 | `SaltedOutpointHasherBench_match`
|               78.66 |       12,713,595.35 |    0.1% |          555.59 |          282.52 |  1.967 |          20.19 |    2.2% |     10.74 | `SaltedOutpointHasherBench_mismatch`
    46f178470b
  50. test: Rename k1/k2 to k0/k1 for consistency 869e0bcb47
  51. refactor: Extract C0-C3 Siphash constants 37d5a30317
  52. optimization: refactor: Introduce Uint256ExtraSipHasher to cache SipHash constant state 
    Previously, only k0 and k1 were stored, causing the constant xor operations to be recomputed in every call to `SipHashUint256Extra`.
This commit adds a dedicated `Uint256ExtraSipHasher` class that caches the initial state (v0-v3) and to perform the `SipHash` computation on a `uint256` (with an extra parameter), hiding the constant computation details from higher-level code and improving efficiency.
This basically brings the precalculations in the `CSipHasher` constructor to the `uint256` specialized SipHash implementation.

> cmake -B build -DBUILD_BENCH=ON -DCMAKE_BUILD_TYPE=Release && cmake --build build -j$(nproc) && build/src/bench/bench_bitcoin -filter='SaltedOutpointHasherBench.*' -min-time=10000

> C++ compiler .......................... AppleClang 16.0.0.16000026

|               ns/op |                op/s |    err% |     total | benchmark
|--------------------:|--------------------:|--------:|----------:|:----------
|               57.27 |       17,462,299.19 |    0.1% |     11.02 | `SaltedOutpointHasherBench_create_set`
|               11.24 |       88,997,888.48 |    0.3% |     11.04 | `SaltedOutpointHasherBench_hash`
|               13.91 |       71,902,014.20 |    0.2% |     11.01 | `SaltedOutpointHasherBench_match`
|               13.29 |       75,230,390.31 |    0.1% |     11.00 | `SaltedOutpointHasherBench_mismatch`

compared to master:
create_set - 17,462,299.19/17,065,922.04 - 2.3% faster
hash       - 88,997,888.48/83,576,684.83 - 6.4% faster
match      - 71,902,014.20/68,985,850.12 - 4.2% faster
mismatch   - 75,230,390.31/71,942,033.47 - 4.5% faster

> C++ compiler .......................... GNU 13.3.0

|               ns/op |                op/s |    err% |          ins/op |          cyc/op |    IPC |         bra/op |   miss% |     total | benchmark
|--------------------:|--------------------:|--------:|----------------:|----------------:|-------:|---------------:|--------:|----------:|:----------
|              135.38 |        7,386,349.49 |    0.0% |        1,078.19 |          486.16 |  2.218 |         119.56 |    1.1% |     11.00 | `SaltedOutpointHasherBench_create_set`
|               23.67 |       42,254,558.08 |    0.0% |          247.01 |           85.01 |  2.906 |           4.00 |    0.0% |     11.00 | `SaltedOutpointHasherBench_hash`
|               58.95 |       16,962,220.14 |    0.1% |          446.55 |          211.74 |  2.109 |          20.86 |    1.4% |     11.01 | `SaltedOutpointHasherBench_match`
|               76.98 |       12,991,047.69 |    0.1% |          548.93 |          276.50 |  1.985 |          20.25 |    2.3% |     10.72 | `SaltedOutpointHasherBench_mismatch`

compared to master:
create_set -  7,386,349.49/7,312,133.16  - 1% faster
hash       - 42,254,558.08/41,978,882.62 - 0.6% faster
match      - 16,962,220.14/16,549,695.42 - 2.4% faster
mismatch   - 12,991,047.69/12,713,595.35 - 2% faster

Co-authored-by: sipa <pieter@wuille.net>
    987be1b529
  53. l0rinc force-pushed on Apr 17, 2025


l0rinc DrahtBot andrewtoth laanwj ismaelsadeeq sipa


laanwj josibake ismaelsadeeq

Labels
Utils/log/libs

github-metadata-mirror

This is a metadata mirror of the GitHub repository bitcoin/bitcoin. This site is not affiliated with GitHub. Content is generated from a GitHub metadata backup.
generated: 2025-04-26 03:12 UTC
This site is hosted by @0xB10C
More mirrored repositories can be found on mirror.b10c.me