Parallel script verification #2060

sipa commented at 1:13 AM on December 2, 2012: member

During block verification (when parallelism is requested), script check actions are stored instead of being executed immediately.
After every processed transactions, its signature actions are pushed to a CScriptCheckQueue, which maintains a queue and some synchronization mechanism.
Two or more threads (if enabled) process elements from this queue, and, and signal the waiting block verification code when they are done.

As cs_main is held the entire time, and all verification must be finished before the block continues processing, this does not reach the best possible performance. It is a less drastic change than some more advanced mechanisms (like doing verification out-of-band entirely, and rolling back blocks when a failure is detected).

This feature is enabled though the -par=N flag.

Depends on #2058 and #2059.

sipa commented at 5:09 PM on December 2, 2012: member

Benchmark result: on my system (an i7-2670QM), a reindex of the first 210000 blocks, with script verification enabled everywhere, and -dbcache=900:

HEAD: 3h22m
-par=4: 1h14m

With -par=4, CPU usage is around 350% (though the first ~100000 blocks cause lower CPU usage)

in src/init.cpp:None in ee3bcb4bac outdated

 587 | @@ -579,6 +588,11 @@ bool AppInit2()
 588 |      if (fDaemon)
 589 |          fprintf(stdout, "Bitcoin server starting\n");
 590 |  
 591 | +    if (nScriptCheckThreads) {

Diapolo commented at 2:59 PM on December 3, 2012:

When -par=1 this would cause no thread to get spawned for verification and matches current behaviour?

sipa commented at 10:23 PM on December 3, 2012:

If nScriptCheckThreads == 0, there is some special code that just runs the script validation inline, instead of pushing it to queues.

nScriptCheckThreads == 1 shouldn't ever happen - there's some code that turns it into 0 if set to 1.

If nScriptCheckThreads is higher, nScriptCheckThreads-1 actual separate threads are started. When the main block processing thread is done with its normal tasks, it joins the worker thread pool temporarily, becoming the N'th worker, so there are always N threads working.

sipa commented at 12:40 AM on December 4, 2012: member

cleaned up the code
moved the job queue implementation to checkqueue.h
added comments
enabled by default (-par=0 autodetects)

in src/checkqueue.h:None in 07b690e793 outdated

  62 | +        vChecks.reserve(nBatchSize);
  63 | +        nTotal++;
  64 | +        unsigned int nNow = 0;
  65 | +        bool fOk = true;
  66 | +        do {
  67 | +            {

Diapolo commented at 8:35 AM on December 4, 2012:

Nit: Small indentation glitch.

sipa commented at 1:37 PM on December 4, 2012:

How so? Indentation is 4 spaces...

Diapolo commented at 1:40 PM on December 4, 2012:

You are right, it's fine ... just looked weird because of the do { above.

in src/init.cpp:None in 07b690e793 outdated

 492 | +    nScriptCheckThreads = GetArg("-par", 0);
 493 | +    if (nScriptCheckThreads == 0)
 494 | +        nScriptCheckThreads = boost::thread::hardware_concurrency();
 495 | +    if (nScriptCheckThreads <= 1)
 496 | +        nScriptCheckThreads = 0;
 497 | +    if (nScriptCheckThreads > 64)

Diapolo commented at 8:39 AM on December 4, 2012:

This could be an else if.

sipa commented at 1:37 PM on December 4, 2012:

Indeed.

in src/checkqueue.h:None in 07b690e793 outdated

   0 | @@ -0,0 +1,155 @@

Diapolo commented at 8:41 AM on December 4, 2012:

Can you include checkqueue.h in bitcoin-qt.pro, to be visible in the Qt IDE.

sipa commented at 1:37 PM on December 4, 2012:

Ok.

Diapolo commented at 8:42 AM on December 4, 2012: none

I love your comments, great work here. I still need to try out the code though :).

in src/init.cpp:None in 4112400b77 outdated

 492 | +    nScriptCheckThreads = GetArg("-par", 0);
 493 | +    if (nScriptCheckThreads == 0)
 494 | +        nScriptCheckThreads = boost::thread::hardware_concurrency();
 495 | +    if (nScriptCheckThreads <= 1) 
 496 | +        nScriptCheckThreads = 0;
 497 | +    else if (nScriptCheckThreads > 64)

laanwj commented at 12:39 PM on December 6, 2012:

Please make this (arbitary?) limit of 64 a constant instead of a magic number.

laanwj commented at 12:39 PM on December 6, 2012: member

Nice!

sipa commented at 12:52 PM on December 6, 2012: member

I've been doing some benchmark, and it seems the contention on the (single) lock protecting the queue makes the throughput and contention overhead go rather high when using too many threads. At least extrapolating from what I see on my system. more than 8 or 16 threads will probably cause significantly degraded performance. Switching to a per-thread queue is probably better, with jobs assigned in a round-robin way to them, or something more intelligent

That said, rebuilding the coindb from scratch (-dbcache=1000, -par=12, with #2061 and #2062, script checks only after block 193k) takes 13m51s on a hexacore E5-1650 @ 3.2Ghz)...

BitcoinPullTester commented at 3:24 AM on December 7, 2012: none

Automatic sanity-testing: PASSED, see http://jenkins.bluematt.me/pull-tester/8f706026e6dee8e38cca0d17acbfc75107d2dcba for binaries and test log.

sipa commented at 10:55 PM on December 8, 2012: member

Changes:

Access to the script check queue is now piped through a RAII CScriptCheckQueueControl, which guarantees the queue is fully processed before continuing
Print the number of threads used in debug.log
Don't store block validation results in signature cache (only mempool transactions are stored), but still use them. This allows multiple threads reading the cache simultaneously.

BitcoinPullTester commented at 11:12 PM on December 8, 2012: none

Automatic sanity-testing: PASSED, see http://jenkins.bluematt.me/pull-tester/5c713c9daa1128d407d9c483d1abae9bde6d48ad for binaries and test log.

BitcoinPullTester commented at 3:29 AM on December 16, 2012: none

Automatic sanity-testing: PASSED, see http://jenkins.bluematt.me/pull-tester/2f3ae3eebd979c1c4c7f43d9cfbe95f61db93ec6 for binaries and test log.

gmaxwell commented at 5:08 PM on December 19, 2012: contributor

Just a comment on negative testing results:

I've been running loops of par inside valgrind on fuzzed blockchains with an instrumented copy of Bitcoin that disables most of the block validity tests (so that the fuzzing doesn't cause the chain to be rejected). In 1000 runs, no errors so far— but I did trigger invalid memory accesses after about 100 runs on this code prior to the RAII CScriptCheckQueueControl added in the last patch.

sipa commented at 5:32 PM on December 19, 2012: member

Given that any non-trivial code has at least one bug (see http://www.murphys-laws.com/murphy/murphy-computer.html), this is indeed bad news :(

Move VerifySignature to main f1136200a6

Add CScriptCheck: a closure representing a script check 2800ce7367

Remove CheckSig_mode and move logic out of CheckInputs() 1d70f4bde8

Parallelize script verification

* During block verification (when parallelism is requested), script
  check actions are stored instead of being executed immediately.
* After every processed transactions, its signature actions are
  pushed to a CScriptCheckQueue, which maintains a queue and some
  synchronization mechanism.
* Two or more threads (if enabled) start processing elements from
  this queue,
* When the block connection code is finished processing transactions,
  it joins the worker pool until the queue is empty.

As cs_main is held the entire time, and all verification must be
finished before the block continues processing, this does not reach
the best possible performance. It is a less drastic change than
some more advanced mechanisms (like doing verification out-of-band
entirely, and rolling back blocks when a failure is detected).

The -par=N flag controls the number of threads (1-16). 0 means auto,
and is the default.

f9cae832e6

Remove contention on signature cache during block validation

Since block validation happens in parallel, multiple threads may be
accessing the signature cache simultaneously. To prevent contention:
* Turn the signature cache lock into a shared mutex
* Make reading from the cache only acquire a shared lock
* Let block validations not store their results in the cache

ef0f422519

BitcoinPullTester commented at 1:23 AM on January 8, 2013: none

Automatic sanity-testing: PASSED, see http://jenkins.bluematt.me/pull-tester/ef0f422519de4a3ce47d923e5f8f90cd12349f3e for binaries and test log.

gavinandresen commented at 10:00 PM on January 17, 2013: contributor

ACK.

Benchmark results on my mac, testing by doing a fresh sync of the -testnet blockchain pulled over the LAN:

Without this pull: 32-bit compile: 270 seconds 64-bit compile: 180 seconds

With this pull: 64-bit, 4-CPU : 125 seconds

gavinandresen referenced this in commit 0e31ae9818 on Jan 18, 2013

gavinandresen merged this on Jan 18, 2013

gavinandresen closed this on Jan 18, 2013

sipa deleted the branch on May 3, 2013

laudney referenced this in commit 969c7c9ef9 on Mar 19, 2014

practicalswift commented at 10:05 AM on August 3, 2017: contributor

@gmaxwell Is your instrumented copy that disables most of the block validity tests available on GitHub? I've thought about writing something similar myself to facilitate deeper fuzzing (my current fuzzing is quite shallow) so I'd be very interested in your version :-)

DrahtBot locked this on Sep 8, 2021