[WIP] "Lockfree" Checkqueue Implementation #8464

JeremyRubin · 2016-08-05T17:16:23Z

This commit introduces a new Checkqueue that should have much better performance than the previous one. Lockfree in scare quotes because the whole checkqueue doesn't meet the strict academic definition of lockfree, but it does have lockfree operations.

The PR includes 1 new consensus rule, some refactoring of the checkqueue interface, reimplementation of the checkqueue, and tests, and one optional optimization (could be PR'd separately).

Please see https://gist.github.com/JeremyRubin/6eec0427edec6e68755ae274b27baae5 for more information.

edit: forgot WIP label, needs more testing and review. Opening PR for that purpose.
edit edit: removed WIP label, terminology confusion, it is indeed ready for testing.

Todo

Stronger Testing Suite
Figure out better wakeup mechanism
Add Benchmarking to the old checkqueue compatible with the new one.
cross platform testing (ARM, 32 bit,...)
remove static asserts for lock-free ness

sipa · 2016-08-05T17:29:32Z

src/checkqueue.h

@@ -26,7 +26,7 @@ class CCheckQueueControl;
  * the master is done adding work, it temporarily joins the worker pool
  * as an N'th worker, until all jobs are done.
  */
-template <typename T>
+template <typename T, size_t J size_t W>


Can you add comments explaining what J and W are?

You're viewing an outdated diff, I just did this for a clean interface change then implementation change set of commits. They are unused here.

sipa · 2016-08-05T17:44:04Z

src/checkqueue.h

+#include <sstream>
+#include <iostream>
+// This should be ignored eventually, but needs testing to ensure this works on more platforms
+static_assert(ATOMIC_BOOL_LOCK_FREE, "shared_status not lock free");


These error messages can indicate the failed type (bool/long/llong)?

I added a commit which changes them from static_asserts to warnings. I'm unsure if the warning is properly x-platform; seems to not be a consistent thing. In any case, not being lockfree only effects performance, not correctness.

JeremyRubin · 2016-08-07T18:17:03Z

Pull tester failure seems to be semi-related to #8425.

sipa · 2016-08-07T19:44:33Z

@JeremyRubin I don't think so. bitcoind segfaults in Travis with this PR (and all rpc tests fail). In #8425 there is just a failure in one test.

JeremyRubin · 2016-08-07T20:55:54Z

@sipa So when I run tests one by one they seem to not fail; when I run them using rpc_tests.py they do fail. Let me know if you have any ideas why this might be the case.

maflcko · 2016-08-07T21:10:38Z

@JeremyRubin You can try qa/pull-tester/rpc-tests.py -parallel=1 to mimic running them by one by one.

JeremyRand · 2016-08-07T21:48:38Z

@sipa I'm flattered that you tagged me (always an honor to be tagged by
you or any other big name in Bitcoin dev), but this isn't my pull
request. :)

JeremyRubin · 2016-08-08T01:15:33Z

Thanks @MarcoFalke.

Running with -parallel=1 all tests pass, except for rawtransactions which failed with

rawtransactions.py:
Initializing test directory /tmp/testricvjc8u/29
Stopping nodes
Cleaning up
Tests successful

stderr:
 Error: Unable to start HTTP server. See debug log for details.

Pass: False, Duration: 21 s

There's nothing in the tmpdir.

Rerunning rawtransactions alone (many times) it didn't fail so I think it's random failure as seen in #8425.

… the minimum of various consensus parameters

…ated and breaks the build

…ich can cause tests to hang otherwise. (Maybe the one time setup is something that should make it into the SetupCCheckQueue code itself)

…to cause segfaults

…ous round This fixes a bug where a deallocated check could be called.

…ement, switching to chrono over sys/time

…uts. Someone with more knowledge here should fix this

…acing it with it's definition

jtimon · 2016-09-01T22:50:19Z

src/main.cpp

-                } else if (!check()) {
+                if (emplacer) {
+                    emplacer(CScriptCheck(*coins, tx, i, flags, cacheStore));
+                    continue;


I tend to prefer else over continue, but it is understandable is just to avoid the re-indent and minimize disruption.
I would the continue be gone "for free" when/if CheckInputs needs a reindent (btw, unrelated, we've been owing one to Consensus::CheckTxInputs for a while...)

Yeah it was a little bit crowded there.

jtimon · 2016-09-01T22:54:28Z

Randomly noting this won't interfere with #8498 at all (well, probably in obvious-to-resolve ways).
utACK main.o is all I can give for now.

I heard %10 to 20% benchmark improvement...happy to benchmark if someone provides dumbed down instructions or they exist already and I missed them. ping @TheBlueMatt

JeremyRubin · 2016-09-01T23:15:50Z

@jtimon in an hour or less i should have a refactored version which has benchmarks added as commit one so you can test benching on all versions.

JeremyRubin · 2016-09-02T00:57:09Z

@laanwj I'd like to get #8632 and some variant of #8633 merged if possible before I PR the new version, otherwise when I push the cleaned up version I won't pass tests due to timeouts.

You can see the restructured version here if anyone wants to review right away: master...JeremyRubin:lockfree-checkqueue-restructured

JeremyRubin · 2016-09-02T01:09:26Z

Some benchmarks from the new version BTW:

Before

#Benchmark,count,min,max,average
CCheckQueueSpeed,6144,0.000019055791199,0.000413492321968,0.000275931825551
CCheckQueueSpeedPrevectorJob,416,0.001668065786362,0.004345431923866,0.002541266954862

After:

#Benchmark,count,min,max,average
CCheckQueueSpeed,6144,0.000050746137276,0.000491065904498,0.000192628746542
CCheckQueueSpeedPrevectorJob,768,0.000427763909101,0.003052964806557,0.001347809719543

CCheckQueueSpeed is a trivial fake job (benchmark slightly unfair, as the emplacement vs resize call probably costs the time). New code takes 70% of the time.

CCheckQueueSpeedPrevectorJob is a job that contains a prevector that (deterministically randomly) is either direct or indirect. My code takes 50% of the time.

edit: just noting, there was a small performance bug (using wrong form of emplace_back) and with that the vector test is at 20% :)

luke-jr · 2016-09-10T09:00:54Z

src/consensus/consensus.h

@@ -19,6 +19,7 @@ static const int64_t MAX_BLOCK_SIGOPS_COST = 80000;
 /** Coinbase transaction outputs can only be spent after this number of new blocks (network rule) */
 static const int COINBASE_MATURITY = 100;

+static const unsigned long long MAX_SCRIPTCHECKS = static_cast<unsigned long long>(MAX_BLOCK_SERIALIZED_SIZE)/41;


Why is 41 safe? Does this consider that invalid signatures/keys could be smaller?

41 bytes is the minimum size of a serialized CTxIn, even when the scriptSig is empty.

jtimon · 2016-10-20T02:15:15Z

Needs rebase

fanquake · 2017-01-12T13:23:50Z

@JeremyRubin What's the status of this?

JeremyRubin · 2017-01-12T14:14:33Z

@fanquake I think I have a rebased version of this laying around somewhere. Have been doing experimentation to see if there's something simpler (read: more reviewable) that accomplishes much of the same. I'll try to see if there's a reasonable version around. If I recall correctly, most of the benefit of the faster CheckQueue was not observable without the cuckoocache, so I focused on that first (lock free queue doesn't matter much if all jobs lock).

JeremyRubin changed the title ~~"Lockfree" Checkqueue Implementation~~ [WIP] "Lockfree" Checkqueue Implementation Aug 5, 2016

sipa reviewed Aug 5, 2016
View reviewed changes

JeremyRubin changed the title ~~[WIP] "Lockfree" Checkqueue Implementation~~ "Lockfree" Checkqueue Implementation Aug 5, 2016

sipa reviewed Aug 5, 2016
View reviewed changes

JeremyRubin mentioned this pull request Aug 7, 2016

Rare walletbackup.py failure: cannot reproduce #8425

Closed

jonasschnelli added the Refactoring label Aug 8, 2016

JeremyRubin closed this Aug 8, 2016

JeremyRubin reopened this Aug 8, 2016

laanwj changed the title ~~"Lockfree" Checkqueue Implementation~~ [WIP] "Lockfree" Checkqueue Implementation Aug 13, 2016

sipa mentioned this pull request Aug 16, 2016

Cache hashes #8422

Closed

JeremyRubin force-pushed the lockfree-checkqueue-squashed branch 2 times, most recently from 58d0a45 to 139f8c1 Compare August 18, 2016 22:13

JeremyRubin force-pushed the lockfree-checkqueue-squashed branch 2 times, most recently from 8a2af6e to cfe0e22 Compare August 29, 2016 02:17

JeremyRubin added 10 commits August 30, 2016 21:18

Add the MAX_SCRIPTCHECKS const to consensus. Can be safely reduced to…

f9f86d7

… the minimum of various consensus parameters

refactor templating and initialization

61540f7

Re-Implement the CheckQueue to only use lockfree atomics

62e05da

add tests for lockfree checkqueue

9d10b67

directly emplace jobs rather than create & swap

9c6b136

Remove BOOST_MESSAGE in test/checkqueue_tests.cpp because it's deprec…

f93524e

…ated and breaks the build

turn compiler static_assert to pragma message

849f5ca

Make the testing setup of CCheckQueue threads only occur one time, wh…

ec12a43

…ich can cause tests to hang otherwise. (Maybe the one time setup is something that should make it into the SetupCCheckQueue code itself)

Explicit shutdown of checkqueue as implicit thread collection seemed …

211d4bb

…to cause segfaults

Decrease number of threads for testing depending on platform

fec0fdc

JeremyRubin added 16 commits August 30, 2016 21:18

make travis search root for corefile

1381483

Use unique_ptr in miner_tests

677f915

Made CBlockIndex and uint256 hashes allocated in RAII containers

d2c886d

add test-suite.log printing to travis

1ca2941

Fixed a bug where a worker could observe nAvail and fAllOk from previ…

6a0582d

…ous round This fixes a bug where a deallocated check could be called.

remove boost::thread from test/test_bitcoin

cc85c7e

Ensure that at least 2 cores are used for benchmarking

50c0ac8

add benchmarking to travis

af2bd76

Got rid of manual placement new in favor of using vector emplace_back.

2acb1ec

Restore RAII style for emplacement

05b1451

Fixed OSX build

969c524

Make benchmarking cross platform friendlier by: removing boost requir…

d0fb3b8

…ement, switching to chrono over sys/time

Ugly hack to print out tests as they are run to mitigate travis timeo…

1a57ba3

…uts. Someone with more knowledge here should fix this

remove uneccesary travis stuff and disable benching till it works

3bedc5d

speed up prevector tests by parallelization

5210b40

BOOST_CHECK_MESSAGE doesn't exist in older versions of boost, so repl…

72e4296

…acing it with it's definition

JeremyRubin force-pushed the lockfree-checkqueue-squashed branch from 464701e to 72e4296 Compare August 31, 2016 01:21

JeremyRubin mentioned this pull request Aug 31, 2016

Nuke boost::thread and boost::thread_group #8631

Closed

jtimon reviewed Sep 1, 2016
View reviewed changes

luke-jr reviewed Sep 10, 2016
View reviewed changes

JeremyRubin closed this Mar 7, 2017

JeremyRubin mentioned this pull request Mar 7, 2017

Lock-Free CheckQueue #9938

Closed

bitcoin locked as resolved and limited conversation to collaborators Sep 8, 2021

[WIP] "Lockfree" Checkqueue Implementation #8464

[WIP] "Lockfree" Checkqueue Implementation #8464

Uh oh!

Conversation

JeremyRubin commented Aug 5, 2016 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Todo

Uh oh!

sipa Aug 5, 2016

Choose a reason for hiding this comment

Uh oh!

JeremyRubin Aug 5, 2016

Choose a reason for hiding this comment

Uh oh!

sipa Aug 5, 2016

Choose a reason for hiding this comment

Uh oh!

JeremyRubin Aug 6, 2016

Choose a reason for hiding this comment

Uh oh!

JeremyRubin commented Aug 7, 2016

Uh oh!

sipa commented Aug 7, 2016 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

JeremyRubin commented Aug 7, 2016

Uh oh!

maflcko commented Aug 7, 2016

Uh oh!

JeremyRand commented Aug 7, 2016

Uh oh!

JeremyRubin commented Aug 8, 2016

Uh oh!

jtimon Sep 1, 2016

Choose a reason for hiding this comment

Uh oh!

JeremyRubin Sep 2, 2016

Choose a reason for hiding this comment

Uh oh!

jtimon commented Sep 1, 2016 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

JeremyRubin commented Sep 1, 2016

Uh oh!

JeremyRubin commented Sep 2, 2016

Uh oh!

JeremyRubin commented Sep 2, 2016 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

luke-jr Sep 10, 2016

Choose a reason for hiding this comment

Uh oh!

sipa Sep 10, 2016 via email

Choose a reason for hiding this comment

Uh oh!

jtimon commented Oct 20, 2016

Uh oh!

fanquake commented Jan 12, 2017

Uh oh!

JeremyRubin commented Jan 12, 2017

Uh oh!

Uh oh!

JeremyRubin commented Aug 5, 2016 •

edited

Loading

sipa commented Aug 7, 2016 •

edited

Loading

jtimon commented Sep 1, 2016 •

edited

Loading

JeremyRubin commented Sep 2, 2016 •

edited

Loading