Make sigcache faster, more efficient, larger #6918

pull sipa wants to merge 3 commits into bitcoin:master from sipa:smallsigcache changing 4 files +65 −36

sipa commented at 10:20 PM on October 30, 2015: member
- Changes the -maxsigcachesize argument from entries to megabytes
- Change the default to 40 MiB (as opposed to ~10 MiB before), corresponding to over 500000 entries on 64-bit systems.
- Store salted SHA256 hashes in the cache, rather than full entries.
- Switch implementation from std::set to boost::unordered_set (smaller and faster)
- Remove cache entries after having been validated inside a block, to keep the cache fresh.
sipa force-pushed on Oct 30, 2015
morcos commented at 10:25 PM on October 30, 2015: member

Concept ACK

Sent from my iPhone

On Oct 30, 2015, at 6:20 PM, Pieter Wuille notifications@github.com wrote:

Changes the -maxsigcachesize argument from entries to megabytes Change the default to 40 MiB (as opposed to ~10 MiB before), corresponding to over 500000 entries on 64-bit systems. Store salted SHA256 hashes in the cache, rather than full entries. Switch implementation from std::set to boost::unordered_set (smaller and faster) You can view, comment on, or merge this pull request online at:

#6918

Commit Summary

Make sigcache faster and more efficient File Changes

M src/init.cpp (3) M src/script/sigcache.cpp (80) M src/script/sigcache.h (4) Patch Links:

#6918.patch #6918.diff — Reply to this email directly or view it on GitHub.
pstratem commented at 10:30 PM on October 30, 2015: contributor

concept ACK
laanwj added the label Validation on Oct 30, 2015

in src/script/sigcache.cpp:None in e15b9beb61 outdated

  91 | +        if (nMaxSize <= 0) return;
  92 |  
  93 |          boost::unique_lock<boost::shared_mutex> lock(cs_sigcache);
  94 | -
  95 | -        while (static_cast<int64_t>(setValid.size()) > nMaxCacheSize)
  96 | +        while (memusage::DynamicUsage(setValid) > nMaxSize)

dcousens commented at 11:40 PM on October 30, 2015:

OOI, what is the time complexity of memusage::DynamicUsage?

sipa commented at 11:44 PM on October 30, 2015:

O(1).

in src/script/sigcache.cpp:None in e15b9beb61 outdated
```
 113 | +            }
 114 |          }
 115 |  
 116 | -        sigdata_type k(hash, vchSig, pubKey);
 117 | -        setValid.insert(k);
 118 | +        setValid.insert(entry);
```
dcousens commented at 11:41 PM on October 30, 2015:

nit: technically, this would mean it could briefly be greater than the allowed memory limits.

sipa commented at 11:43 PM on October 30, 2015:

correct, but we're talking about ~80 bytes...
dcousens commented at 11:42 PM on October 30, 2015: contributor

concept ACK, utACK :+1:
in src/script/sigcache.cpp:None in e15b9beb61 outdated
```
  60 | +        CSHA256().Write(nonce.begin(), 32).Write(hash.begin(), 32).Write(&pubkey[0], pubkey.size()).Write(&vchSig[0], vchSig.size()).Finalize(entry.begin());
  61 | +    }
  62 | +
  63 |      bool
  64 | -    Get(const uint256 &hash, const std::vector<unsigned char>& vchSig, const CPubKey& pubKey)
  65 | +    Get(const uint256& entry)
```
dcousens commented at 11:42 PM on October 30, 2015:

Get is such a weird name, its really more like Contains?

instagibbs commented at 10:12 PM on November 2, 2015:

I think it's going for a getter/setter paradigm(see: Set function below), but I think the names could indeed be improved. It's confusing to have "Set" be both the type of data structure and the primary way of updating it, imo.

in src/script/sigcache.cpp:None in e15b9beb61 outdated

  63 |      bool
  64 | -    Get(const uint256 &hash, const std::vector<unsigned char>& vchSig, const CPubKey& pubKey)
  65 | +    Get(const uint256& entry)
  66 |      {
  67 |          boost::shared_lock<boost::shared_mutex> lock(cs_sigcache);
  68 | +        return setValid.count(entry);

dcousens commented at 11:43 PM on October 30, 2015:

std::static_cast<bool>(count) or count > 0?

sipa force-pushed on Oct 30, 2015
Make sigcache faster and more efficient 830e3f3d02
Evict sigcache entries that are seen in a block 0b9e9dca4e
sipa force-pushed on Oct 31, 2015
sipa commented at 12:16 AM on October 31, 2015: member

Added a commit that removes cache entries after they've been seen in a block, so the cache remains fresh.
dcousens commented at 12:18 AM on October 31, 2015: contributor

re-ACK
Don't wipe the sigcache in TestBlockValidity 69d373ff66
in src/script/sigcache.cpp:None in 0b9e9dca4e outdated
```
  22 | + * blinding in the set hash computation.
  23 | + */
  24 | +class CSignatureCacheHasher
  25 | +{
  26 | +public:
  27 | +    size_t operator()(const uint256& key) const {
```
Diapolo commented at 9:20 AM on October 31, 2015:

Just a qustion to understand the motivation, why is here the opening bracket in the same line and below (line 48) it's on a new line?
sipa commented at 1:02 AM on November 2, 2015: member

Added a commit to not wipe the cache from TBV.
sipa commented at 7:14 AM on November 2, 2015: member

Currently gathering statistics about the cache size - hitrate relation.
instagibbs commented at 10:37 PM on November 2, 2015: member

utACK
gmaxwell added this to the milestone 0.12.0 on Nov 5, 2015
sdaftuar commented at 1:31 PM on November 6, 2015: member

Concept ACK. However in my first attempt at benchmarking I'm not seeing any speedup with this code change (in fact block verification times seem to have gotten very, very slightly slower for some reason). Will continue to debug and try to see if my benchmarking is broken, or if there's some effect here we're missing.
sipa commented at 8:33 AM on November 11, 2015: member

@sdaftuar The results #6976 indicate that this improves things. Does that contradict your earlier findings?
sdaftuar commented at 10:08 AM on November 11, 2015: member

Sorry forgot to update with my results. I ran longer studies comparing the old and new behavior more carefully and yes I agree this does improve things. I saw roughly a 5% speed up in processing all the October historical data using the new default cache size compared with the old implementation (running with a sig cache of approximately the same size).

ACK
gmaxwell commented at 11:19 PM on November 11, 2015: contributor

ACK
laanwj merged this on Nov 12, 2015
laanwj closed this on Nov 12, 2015
laanwj referenced this in commit eb6172a8ca on Nov 12, 2015
zkbot referenced this in commit 9217c8e093 on May 14, 2018
zkbot referenced this in commit 8ce4bc1425 on May 14, 2018
zkbot referenced this in commit 03532b173c on May 31, 2018
zkbot referenced this in commit 9cd74866c7 on Nov 30, 2018
milesmanley referenced this in commit 67d2fb18d2 on Mar 5, 2019
furszy referenced this in commit 7e65a82e7d on Jun 18, 2020
DrahtBot locked this on Sep 8, 2021

Contributors

Labels

Milestone
0.12.0

Linked (view graph)

#6976 Summary of potential performance improvements