Branch: refs/heads/master
Home: https://github.com/btcsuite/btcd
Commit: 3b39edcaa1e867efc4223d95ca1496aaadf8eca3
https://github.com/btcsuite/btcd/commit/3b39edcaa1e867efc4223d95ca1496aaadf8eca3
Author: Olaoluwa Osuntokun <[email protected]>
Date: 2016-04-13 (Wed, 13 Apr 2016)
Changed paths:
M btcec/pubkey.go
M btcec/pubkey_test.go
M btcec/signature.go
M btcec/signature_test.go
M config.go
M txscript/reference_test.go
M txscript/sigcache.go
Log Message:
-----------
txscript: optimize sigcache lookup (#598)
Profiles discovered that lookups into the signature cache included an
expensive comparison to the stored `sigInfo` struct. This lookup had the
potential to be more expensive than directly verifying the signature
itself!
In addition, evictions were rather expensive because they involved
reading from /dev/urandom, or equivalent, for each eviction once the
signature cache was full as well as potentially iterating over every
item in the cache in the worst-case.
To remedy this poor performance several changes have been made:
* Change the lookup key to the fixed sized 32-byte signature hash
* Perform a full equality check only if there is a cache hit which
results in a significant speed up for both insertions and existence
checks
* Override entries in the case of a colliding hash on insert Add an
* .IsEqual() method to the Signature and PublicKey types in the
btcec package to facilitate easy equivalence testing
* Allocate the signature cache map with the max number of entries in
order to avoid unnecessary map re-sizes/allocations
* Optimize evictions from the signature cache Delete the first entry
* seen which is safe from manipulation due to
the pre image resistance of the hash function
* Double the default maximum number of entries within the signature
cache due to the reduction in the size of a cache entry
* With this eviction scheme, removals are effectively O(1)
Fixes #575.
