Use SipHash-2-4 for:
Computing a hash for a txid using this takes around 52 CPU cycles in benchmarks (the Lookup3/XOR based mechanism used for CCoinsViewCache took 31 cycles). I think that’s negligible still, while using a much more standard construct designed for such purposes.
4721 {
4722 if (pnode->nVersion < CADDR_TIME_VERSION)
4723 continue;
4724- unsigned int nPointer;
4725+ uint64_t nPointer = 0;
4726 memcpy(&nPointer, &pnode, sizeof(nPointer));
Here is a comment about using SipHash-1-3 instead of SipHash-2-4: https://github.com/rust-lang/rust/issues/29754#issuecomment-156073946
It would be approximately twice as fast for hashing txids, and the distinguisher mentioned in that comment is not relevant for data that is a multiple of 8 bytes (which is the case for us), as 8 bytes of padding are added in that case. Opinions?
Siphash 2-4 seems to be the defacto ‘safe’ choice. Siphash 1-3 happens to be secure for our use case right now, but that sounds a tad brittle: as if a small change in our use case, or a small advancement in cryptoanalysis of the function, could mean that the known weakness does suddenly affect us?
Not sure how much hashing the txids is a bottleneck in the whole scheme of things around CCoinsCache, it’s only 32 bytes after all. Conservatively I’d say only consider ‘downgrading’ if performance is seriously affected by going from 29 cycles to 49 cycles.
On the other hand it’s pretty nice if using a hash with better security properties could be faster than the Lookup3/XOR scheme, so I see the attraction in that.
Did some better benchmarks:
137+}
138+
139+uint64_t SipHashUint256(uint64_t k0, uint64_t k1, const uint256& val)
140+{
141+ /* Specialized implementation for efficiency */
142+ const uint64_t* data = (const uint64_t*)(val.begin());
Going to stick to SipHash-2-4 for now. We can always switch to something else later.
Ready for merge, I think.
This is ~1.7x slower than the Lookup3-of-Xor-with-salt construct we were
using before, but it is a primitive designed for exactly this.
82@@ -83,6 +83,12 @@ class base_blob
83 return sizeof(data);
84 }
85
86+ uint64_t GetUint64(int pos) const
87+ {
88+ const uint8_t* ptr = data + pos * 8;
89+ return ((uint64_t)ptr[0]) | ((uint64_t)ptr[1]) << 8 | ((uint64_t)ptr[2]) << 16 | ((uint64_t)ptr[3]) << 24 | ((uint64_t)ptr[4]) << 32 | ((uint64_t)ptr[5]) << 40 | ((uint64_t)ptr[6]) << 48 | ((uint64_t)ptr[7]) << 56;
Can you make this more readable?
Something like
0 (uint64_t(ptr[0]) << 0) |
1 (uint64_t(ptr[1]) << 8) |
2 (uint64_t(ptr[2]) << 16) |
3 (uint64_t(ptr[3]) << 24) |
4 (uint64_t(ptr[4]) << 32) |
5 (uint64_t(ptr[5]) << 40) |
6 (uint64_t(ptr[6]) << 48) |
7 (uint64_t(ptr[7]) << 56))
137+}
138+
139+uint64_t SipHashUint256(uint64_t k0, uint64_t k1, const uint256& val)
140+{
141+ /* Specialized implementation for efficiency */
142+ uint64_t d = le64toh(val.GetUint64(0));
296@@ -295,7 +297,7 @@ struct CCoinsCacheEntry
297 CCoinsCacheEntry() : coins(), flags(0) {}
298 };
299
300-typedef boost::unordered_map<uint256, CCoinsCacheEntry, CCoinsKeyHasher> CCoinsMap;
301+typedef boost::unordered_map<uint256, CCoinsCacheEntry, SaltedTxidHasher> CCoinsMap;
It’s fast and cryptographically solid - which reduces DoS risk by attackers remotely predicting the behavior of the hash function.
As I quoted above already, pretty much same rationale as for Python: https://www.python.org/dev/peps/pep-0456/
Here is a comment about using SipHash-1-3 instead of SipHash-2-4: rust-lang/rust#29754 (comment)
It would be approximately twice as fast for hashing txids, and the distinguisher mentioned in that comment is not relevant for data that is a multiple of 8 bytes (which is the case for us), as 8 bytes of padding are added in that case. Opinions?
For future reference.
Because of all the interesting results @jamesob got from the hashmap modifications, I decided to try benchmarking siphash2-4 vs 1-3 by replacing SaltedOutpointHasher and SaltedTxidHasher with SipHash1-3 and this is the result:
Command: /home/profiler/bitcoin/src/bitcoind -datadir="/home/profiler/.bitcoin" -dbcache=12288 -debug=0 -nodebuglogfile -printtoconsole=0 -reindex-chainstate -stopatheight=600000
Before:
0real 119m16.133s
1user 137m38.092s
2sys 2m30.990s
After:
0real 115m6.045s
1user 133m53.661s
2sys 2m30.177s
Spec: i7-8700 CPU @ 3.20GHz, 32GB RAM, NVMe SSD.