Branch: refs/heads/master
Home: https://github.com/btcsuite/btcd
Commit: 0e71867dfea2749357d3731381efd2c47b47a6a6
https://github.com/btcsuite/btcd/commit/0e71867dfea2749357d3731381efd2c47b47a6a6
Author: Dave Collins <da...@conformal.com>
Date: 2016-10-23 (Sun, 23 Oct 2016)
Changed paths:
M mempool/mempool.go
Log Message:
-----------
mempool: Optimize orphan map limiting.
This optimizes the way in which the mempool oprhan map is limited in the
same way the server block manager maps were previously optimized.
Previously the code would read a cryptographically random value large
enough to construct a hash, find the first entry larger than that value,
and evict it.
That approach is quite inefficient and could easily become a
bottleneck when processing transactions due to the need to read from a
source such as /dev/urandom and all of the subsequent hash comparisons.
Luckily, strong cryptographic randomness is not needed here. The primary
intent of limiting the maps is to control memory usage with a secondary
concern of making it difficult for adversaries to force eviction of
specific entries.
Consequently, this changes the code to make use of the pseudorandom
iteration order of Go's maps along with the preimage resistance of the
hashing function to provide the desired functionality. It has
previously been discussed that the specific pseudorandom iteration order
is not guaranteed by the Go spec even though in practice that is how it
is implemented. This is not a concern however because even if the
specific compiler doesn't implement that, the preimage resistance of the
hashing function alone is enough.
The following is a before and after comparison of the function for both
speed and memory allocations:
benchmark old ns/op new ns/op delta
----------------------------------------------------------------
BenchmarkLimitNumOrphans 3727 243 -93.48%
benchmark old allocs new allocs delta
-----------------------------------------------------------------
BenchmarkLimitNumOrphans 4 0 -100.00%
