Skip to content

Commit ec11b9f

Browse files
l0rincsipa
l0rinc
and
sipa
committed
optimization: introduce PresaltedSipHasher for repeated hashing
Replaces the `SipHashUint256Extra` function with the `PresaltedSipHasher` class that caches the constant-salted state (v[0-3] after XORing with keys). This avoids redundant XOR operations when hashing multiple values with the same keys, benefiting use cases like `SaltedOutpointHasher`. This essentially 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 <[email protected]>
1 parent 2033054 commit ec11b9f

File tree

6 files changed

+31
-22
lines changed

6 files changed

+31
-22
lines changed

‎src/crypto/siphash.cpp‎

Lines changed: 4 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -137,17 +137,12 @@ uint64_t SipHashUint256(uint64_t k0, uint64_t k1, const uint256& val)
137137
return v0 ^ v1 ^ v2 ^ v3;
138138
}
139139

140-
uint64_t SipHashUint256Extra(uint64_t k0, uint64_t k1, const uint256& val, uint32_t extra)
140+
/** Specialized implementation for efficiency */
141+
uint64_t PresaltedSipHasher::operator()(const uint256& val, uint32_t extra) const noexcept
141142
{
142-
/* Specialized implementation for efficiency */
143+
uint64_t v0 = v[0], v1 = v[1], v2 = v[2], v3 = v[3];
143144
uint64_t d = val.GetUint64(0);
144-
145-
// TODO moved in followup commit
146-
uint64_t v0 = CSipHasher::C0 ^ k0;
147-
uint64_t v1 = CSipHasher::C1 ^ k1;
148-
uint64_t v2 = CSipHasher::C2 ^ k0;
149-
uint64_t v3 = CSipHasher::C3 ^ k1 ^ d;
150-
145+
v3 ^= d;
151146
SIPROUND;
152147
SIPROUND;
153148
v0 ^= d;

‎src/crypto/siphash.h‎

Lines changed: 15 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -48,6 +48,20 @@ class CSipHasher
4848
* .Finalize()
4949
*/
5050
uint64_t SipHashUint256(uint64_t k0, uint64_t k1, const uint256& val);
51-
uint64_t SipHashUint256Extra(uint64_t k0, uint64_t k1, const uint256& val, uint32_t extra);
51+
52+
class PresaltedSipHasher
53+
{
54+
uint64_t v[4];
55+
56+
public:
57+
explicit PresaltedSipHasher(uint64_t k0, uint64_t k1) noexcept {
58+
v[0] = CSipHasher::C0 ^ k0;
59+
v[1] = CSipHasher::C1 ^ k1;
60+
v[2] = CSipHasher::C2 ^ k0;
61+
v[3] = CSipHasher::C3 ^ k1;
62+
}
63+
64+
uint64_t operator()(const uint256& val, uint32_t extra) const noexcept;
65+
};
5266

5367
#endif // BITCOIN_CRYPTO_SIPHASH_H

‎src/test/fuzz/integer.cpp‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -119,7 +119,7 @@ FUZZ_TARGET(integer, .init = initialize_integer)
119119
(void)MillisToTimeval(i64);
120120
(void)SighashToStr(uch);
121121
(void)SipHashUint256(u64, u64, u256);
122-
(void)SipHashUint256Extra(u64, u64, u256, u32);
122+
(void)PresaltedSipHasher(u64, u64)(u256, u32);
123123
(void)ToLower(ch);
124124
(void)ToUpper(ch);
125125
{

‎src/test/hash_tests.cpp‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -130,7 +130,7 @@ BOOST_AUTO_TEST_CASE(siphash)
130130
ss << TX_WITH_WITNESS(tx);
131131
BOOST_CHECK_EQUAL(SipHashUint256(1, 2, ss.GetHash()), 0x79751e980c2a0a35ULL);
132132

133-
// Check consistency between CSipHasher and SipHashUint256[Extra].
133+
// Check consistency between CSipHasher and SipHashUint256 and PresaltedSipHasher.
134134
FastRandomContext ctx;
135135
for (int i = 0; i < 16; ++i) {
136136
uint64_t k0 = ctx.rand64();
@@ -146,7 +146,7 @@ BOOST_AUTO_TEST_CASE(siphash)
146146
uint8_t nb[4];
147147
WriteLE32(nb, n);
148148
sip288.Write(nb);
149-
BOOST_CHECK_EQUAL(SipHashUint256Extra(k0, k1, x, n), sip288.Finalize()); // TODO modified in follow-up commit
149+
BOOST_CHECK_EQUAL(PresaltedSipHasher(k0, k1)(x, n), sip288.Finalize());
150150
}
151151
}
152152

‎src/util/hasher.cpp‎

Lines changed: 5 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -19,14 +19,15 @@ SaltedWtxidHasher::SaltedWtxidHasher() :
1919
k0{FastRandomContext().rand64()},
2020
k1{FastRandomContext().rand64()} {}
2121

22-
SaltedOutpointHasher::SaltedOutpointHasher(bool deterministic) :
23-
k0{deterministic ? 0x8e819f2607a18de6 : FastRandomContext().rand64()},
24-
k1{deterministic ? 0xf4020d2e3983b0eb : FastRandomContext().rand64()}
22+
SaltedOutpointHasher::SaltedOutpointHasher(bool deterministic) : m_hasher{
23+
deterministic ? 0x8e819f2607a18de6 : FastRandomContext().rand64(),
24+
deterministic ? 0xf4020d2e3983b0eb : FastRandomContext().rand64()}
2525
{}
2626

2727
SaltedSipHasher::SaltedSipHasher() :
2828
m_k0{FastRandomContext().rand64()},
29-
m_k1{FastRandomContext().rand64()} {}
29+
m_k1{FastRandomContext().rand64()}
30+
{}
3031

3132
size_t SaltedSipHasher::operator()(const std::span<const unsigned char>& script) const
3233
{

‎src/util/hasher.h‎

Lines changed: 4 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -60,9 +60,7 @@ class SaltedWtxidHasher
6060

6161
class SaltedOutpointHasher
6262
{
63-
private:
64-
/** Salt */
65-
const uint64_t k0, k1;
63+
const PresaltedSipHasher m_hasher;
6664

6765
public:
6866
SaltedOutpointHasher(bool deterministic = false);
@@ -76,8 +74,9 @@ class SaltedOutpointHasher
7674
*
7775
* @see https://gcc.gnu.org/onlinedocs/gcc-13.2.0/libstdc++/manual/manual/unordered_associative.html
7876
*/
79-
size_t operator()(const COutPoint& id) const noexcept {
80-
return SipHashUint256Extra(k0, k1, id.hash.ToUint256(), id.n);
77+
size_t operator()(const COutPoint& id) const noexcept
78+
{
79+
return m_hasher(id.hash.ToUint256(), id.n);
8180
}
8281
};
8382

0 commit comments

Comments
 (0)