Faster txid hash tables with SipHash-1-3-UJ

Excellent writeup!

I would also like to point out that SipHash-1-3-UJ was also used to speed up fetch block input prevouts in parallel during ConnectBlock. Since the parallel fetching change was merged first, the PR introducing SipHash-1-3-UJ also modified the earlier_txids set in CoinsViewOverlay::StartFetching to use the new hash function. We need to store all txids for each block we connect in a set, which is used to filter out prevouts that are created by an earlier transaction in the same block. These prevouts will be created in the CoinsViewOverlay cache directly, so they must not be fetched from the main cache or disk.

This set must hash the txid for every transaction in each block for insertion, and then hash the prevout hash of every input of each transaction to check existence. This is all serial overhead on the main thread before any of the parallel fetching speedup can be made, so this lighter hash function is a clear win here as well. This set is only inserting txids that are the result of SHA256ing the transaction data by our node directly, so they fit the use case for this new hash function exactly.

4 Likes