Details

Reviewers

deadalnix
Fabien
jasonbcox

Group Reviewers

Restricted Owners Package	(Owns No Changed Paths)
Restricted Project

Commits

rSTAGING08f879687543: Use best-fit strategy in Arena, now O(log(n)) instead O(n)
rABC08f879687543: Use best-fit strategy in Arena, now O(log(n)) instead O(n)

Summary

PR12048:
5fbf7c4 fix nits: variable naming, typos (Martin Ankerl)
1e0ee90 Use best-fit strategy in Arena, now O(log(n)) instead O(n) (Martin Ankerl)

Pull request description:

This replaces the first-fit algorithm used in the Arena with a best-fit. According to "Dynamic Storage Allocation: A Survey and Critical Review", Wilson et. al. 1995, http://www.scs.stanford.edu/14wi-cs140/sched/readings/wilson.pdf, both startegies work well in practice.

The advantage of using best-fit is that we can switch the O(n) allocation to O(log(n)). Additionally, some previously O(log(n)) operations are now O(1) operations by using hash maps. The end effect is that the benchmark runs about 2.5 times faster on my machine:

    # Benchmark, evals, iterations, total, min, max, median
    old: BenchLockedPool, 5, 530, 5.25749, 0.00196938, 0.00199755, 0.00198172
    new: BenchLockedPool, 5, 1300, 5.11313, 0.000781493, 0.000793314, 0.00078606

I've run all unit tests and benchmarks, and increased the number of iterations so that BenchLockedPool takes about 5 seconds again.

Tree-SHA512: 6551e384671f93f10c60df530a29a1954bd265cc305411f665a8756525e5afe2873a8032c797d00b6e8c07e16d9827465d0b662875433147381474a44119ccce

Also included PR16161 which fixes a bug introduced by PR12048:

Changes in #12048 cause a compilation error in Arena::walk() when
ARENA_DEBUG is defined. Specifically, Arena's chunks_free map was
changed to have a different value type.

Additionally, missing includes cause other compilation errors when
ARENA_DEBUG is defined.

Second commit fixes segfault in allocator_tests/arena_tests
The test uses reinterpret_cast<void*> on unallocated memory. Using this
memory in printchunk as char* causes a segfault, so have printchunk take
void* instead.

Reproduced with:

make CPPFLAGS=-DARENA_DEBUG

Backport of Core PR12048 and PR16161
https://github.com/bitcoin/bitcoin/pull/12048/
https://github.com/bitcoin/bitcoin/pull/16161/

Reviewer note: the last commit in PR16161 is TRAVIS related and was therefore modified to our code base. The new flag was excluded from our TSAN build after discussing with Fabien.

Test Plan

make check
test_runner.py
./bitcoin-qt -> settings -> Encrypt Wallet -> set password and/or change password if already encrypted
./bench_bitcoin

old: BenchLockedPool, 5, 530, 5.15069, 0.00192059, 0.00199956, 0.00193796
new: BenchLockedPool, 5, 1300, 4.44411, 0.00067821, 0.000698535, 0.000678916

../configure CPPFLAGS=-DARENA_DEBUG
make check
test_runner.py
ABC_BUILD_NAME=build-asan build-configurations.sh

Diff Detail

Repository

rABC Bitcoin ABC

Lint

Lint Not Applicable

Unit

Tests Not Applicable

Event Timeline

nakihito created this revision.Aug 16 2019, 23:53

Owners added a reviewer: Restricted Owners Package.Aug 16 2019, 23:53

Herald added a reviewer: Restricted Project. · View Herald TranscriptAug 16 2019, 23:53

Build Bitcoin-ABC / Diffs / Diff Testing started.

Build Bitcoin-ABC / Diffs / Diff Testing passed.

Harbormaster completed remote builds in B7179: Diff 10848.Aug 17 2019, 00:13

Please test password usage with the wallet and bitcoin-qt for sanity, as this is where this allocation thing is used and the unit test coverage seems pretty limited.

Note that this introduces a regression (https://github.com/bitcoin/bitcoin/pull/16161), but I don't think it's a big deal and it can probably wait for core to merge a fix.

Otherwise LGTM.

src/support/lockedpool.cpp
137 ↗	(On Diff #10848)	Braces

This revision now requires changes to proceed.Aug 19 2019, 19:21

It looks like Core is almost done with the patch for the regression this will add. I will update later once it is finished so they can be landed (hopefully) around the same time.

nakihito edited the test plan for this revision. (Show Details)Aug 21 2019, 19:22

Fixed braces.

Build Bitcoin-ABC / Diffs / Diff Testing started.

Build Bitcoin-ABC / Diffs / Diff Testing passed.

Harbormaster completed remote builds in B7575: Diff 13122.Sep 24 2019, 17:49

The regression fix is still open: https://github.com/bitcoin/bitcoin/pull/16161

This revision now requires changes to proceed.Sep 25 2019, 17:35

Still waiting for PR16161.

nakihito added a child revision: D4548: Fix compilation errors in support/lockedpool.cpp.Nov 26 2019, 02:42

nakihito requested review of this revision.Nov 26 2019, 02:49

Fabien accepted this revision.Nov 26 2019, 10:10

Back on the queue.

This revision now requires changes to proceed.Nov 28 2019, 13:43

Rebase.

Build Bitcoin-ABC / Diffs / Diff Testing started.

Build Bitcoin-ABC / Diffs / Diff Testing passed.

Harbormaster completed remote builds in B8388: Diff 14594.Dec 3 2019, 19:29

PR16161 was merged.

This revision now requires changes to proceed.Dec 9 2019, 00:45

nakihito requested review of this revision.Dec 10 2019, 02:06

It overall looks, good, expect the fact that many nits should have been done prior to the back port, and not have a handful of them in.

I would also like to know the reason why this is included as this, even though this is known to have bug.

src/support/lockedpool.cpp
137 ↗	(On Diff #14594)	Doing a pass over the file to fix these on their own would have been a good first step.

This revision now requires changes to proceed.Dec 11 2019, 02:41

nakihito planned changes to this revision.Dec 12 2019, 00:00

nakihito edited the summary of this revision. (Show Details)Dec 12 2019, 21:38

nakihito edited the test plan for this revision. (Show Details)

Combined with D4548 (PR16161).

Build Bitcoin-ABC / Diffs / Diff Testing started.

Originally I had to two separated because it would be easier for review and I had already previously discussed it with Fabien. I have now combined this and D4548 together after updating the summary, test plan, and title and rebasing.

src/support/lockedpool.cpp
137 ↗	(On Diff #14594)	Moved these changes to D4704.

nakihito retitled this revision from Merge #12048: Use best-fit strategy in Arena, now O(log(n)) instead O(n) to Use best-fit strategy in Arena, now O(log(n)) instead O(n).Dec 12 2019, 22:28

nakihito edited the summary of this revision. (Show Details)

nakihito mentioned this in D4548: Fix compilation errors in support/lockedpool.cpp.

Build Bitcoin-ABC / Diffs / Diff Testing passed.

Harbormaster completed remote builds in B8534: Diff 14816.Dec 12 2019, 22:41

deadalnix accepted this revision.Dec 18 2019, 00:57

Needs rebase.

Rebased.

nakihito planned changes to this revision.Jan 6 2020, 17:26

Build Bitcoin-ABC / Diffs / Diff Testing started.

Build Bitcoin-ABC / Diffs / Diff Testing passed.

Harbormaster completed remote builds in B8754: Diff 15178.Jan 6 2020, 17:33

Build Bitcoin-ABC / Diffs / Diff Testing started.

Build Bitcoin-ABC / Diffs / Diff Testing failed.

Snippet of first build failure:

[18:35:55] :	 [Step 1/1] *** Output of /tmp/sanitizer_logs/lsan.log.5542 ***
[18:35:55] :	 [Step 1/1] =================================================================
[18:35:55] :	 [Step 1/1] ==5542==ERROR: AddressSanitizer: SEGV on unknown address 0x00006a09e5e7 (pc 0x557701832be1 bp 0x7ffe9c418d60 sp 0x7ffe9c418bf0 T0)
[18:35:55] :	 [Step 1/1] ==5542==The signal is caused by a WRITE memory access.
[18:35:55] :	 [Step 1/1]     #0 0x557701832be0 in sha256_sse4::Transform(unsigned int*, unsigned char const*, unsigned long) ../src/crypto/sha256_sse4.cpp:953
[18:35:55] :	 [Step 1/1]     #1 0x5577018303f3 in SelfTest ../src/crypto/sha256.cpp:690
[18:35:55] :	 [Step 1/1]     #2 0x557701830d05 in SHA256AutoDetect[abi:cxx11]() ../src/crypto/sha256.cpp:812
[18:35:55] :	 [Step 1/1]     #3 0x5576ffde713a in BasicTestingSetup::BasicTestingSetup(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&) ../src/test/test_bitcoin.cpp:54
[18:35:55] :	 [Step 1/1]     #4 0x557700a279fd in uint256_tests::basics::basics() ../src/test/uint256_tests.cpp:67
[18:35:55] :	 [Step 1/1]     #5 0x5577009f7927 in basics_invoker ../src/test/uint256_tests.cpp:67
[18:35:55] :	 [Step 1/1]     #6 0x5576ffe3c485 in boost::detail::function::void_function_invoker0<void (*)(), void>::invoke(boost::detail::function::function_buffer&) /usr/include/boost/function/function_template.hpp:118
[18:35:55] :	 [Step 1/1]     #7 0x7f51763fef5d in boost::detail::function::function_obj_invoker0<boost::detail::forward, int>::invoke(boost::detail::function::function_buffer&) (/lib/x86_64-linux-gnu/libboost_unit_test_framework.so.1.67.0+0x54f5d)
[18:35:55] :	 [Step 1/1]     #8 0x7f51763feb64 in boost::execution_monitor::catch_signals(boost::function<int ()> const&) (/lib/x86_64-linux-gnu/libboost_unit_test_framework.so.1.67.0+0x54b64)
[18:35:55] :	 [Step 1/1]     #9 0x7f51763fec30 in boost::execution_monitor::execute(boost::function<int ()> const&) (/lib/x86_64-linux-gnu/libboost_unit_test_framework.so.1.67.0+0x54c30)
[18:35:55] :	 [Step 1/1]     #10 0x7f51763fecfc in boost::execution_monitor::vexecute(boost::function<void ()> const&) (/lib/x86_64-linux-gnu/libboost_unit_test_framework.so.1.67.0+0x54cfc)
[18:35:55] :	 [Step 1/1]     #11 0x7f51764268a8 in boost::unit_test::unit_test_monitor_t::execute_and_translate(boost::function<void ()> const&, unsigned int) (/lib/x86_64-linux-gnu/libboost_unit_test_framework.so.1.67.0+0x7c8a8)
[18:35:55] :	 [Step 1/1]     #12 0x7f517640146a  (/lib/x86_64-linux-gnu/libboost_unit_test_framework.so.1.67.0+0x5746a)
[18:35:55] :	 [Step 1/1]     #13 0x7f517640172e  (/lib/x86_64-linux-gnu/libboost_unit_test_framework.so.1.67.0+0x5772e)
[18:35:55] :	 [Step 1/1]     #14 0x7f517640172e  (/lib/x86_64-linux-gnu/libboost_unit_test_framework.so.1.67.0+0x5772e)
[18:35:55] :	 [Step 1/1]     #15 0x7f5176403fd4 in boost::unit_test::framework::run(unsigned long, bool) (/lib/x86_64-linux-gnu/libboost_unit_test_framework.so.1.67.0+0x59fd4)
[18:35:55] :	 [Step 1/1]     #16 0x7f5176424317 in boost::unit_test::unit_test_main(bool (*)(), int, char**) (/lib/x86_64-linux-gnu/libboost_unit_test_framework.so.1.67.0+0x7a317)
[18:35:55] :	 [Step 1/1]     #17 0x5576ffe2ba9f in main ../src/test/test_bitcoin_main.cpp:48
[18:35:55] :	 [Step 1/1]     #18 0x7f51752c409a in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x2409a)
[18:35:55] :	 [Step 1/1]     #19 0x5576ffdbd749 in _start (/home/teamcity/buildAgent/work/c4a5708f2bae7929/build/src/test/test_bitcoin+0x3b5749)
[18:35:55] :	 [Step 1/1] 
[18:35:55] :	 [Step 1/1] AddressSanitizer can not provide additional info.
[18:35:55] :	 [Step 1/1] SUMMARY: AddressSanitizer: SEGV ../src/crypto/sha256_sse4.cpp:953 in sha256_sse4::Transform(unsigned int*, unsigned char const*, unsigned long)
[18:35:55] :	 [Step 1/1] ==5542==ABORTING
[18:35:55] :	 [Step 1/1] *** Output of /tmp/sanitizer_logs/lsan.log.5547 ***
[18:35:55] :	 [Step 1/1] =================================================================
[18:35:55] :	 [Step 1/1] ==5547==ERROR: AddressSanitizer: SEGV on unknown address 0x00006a09e5e7 (pc 0x55cec7e20be1 bp 0x7fff8db1bf80 sp 0x7fff8db1be10 T0)
[18:35:55] :	 [Step 1/1] ==5547==The signal is caused by a WRITE memory access.
[18:35:55] :	 [Step 1/1]     #0 0x55cec7e20be0 in sha256_sse4::Transform(unsigned int*, unsigned char const*, unsigned long) ../src/crypto/sha256_sse4.cpp:953
[18:35:55] :	 [Step 1/1]     #1 0x55cec7e1e3f3 in SelfTest ../src/crypto/sha256.cpp:690
[18:35:55] :	 [Step 1/1]     #2 0x55cec7e1ed05 in SHA256AutoDetect[abi:cxx11]() ../src/crypto/sha256.cpp:812
[18:35:55] :	 [Step 1/1]     #3 0x55cec63d513a in BasicTestingSetup::BasicTestingSetup(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&) ../src/test/test_bitcoin.cpp:54
[18:35:55] :	 [Step 1/1]     #4 0x55cec63d5a37 in TestingSetup::TestingSetup(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&) ../src/test/test_bitcoin.cpp:79
[18:35:55] :	 [Step 1/1]     #5 0x55cec63d6c73 in TestChain100Setup::TestChain100Setup() ../src/test/test_bitcoin.cpp:146
[18:35:55] :	 [Step 1/1]     #6 0x55cec6fe36ec in txvalidationcache_tests::tx_mempool_block_doublespend::tx_mempool_block_doublespend() ../src/test/txvalidationcache_tests.cpp:39
[18:35:55] :	 [Step 1/1]     #7 0x55cec6fcf779 in tx_mempool_block_doublespend_invoker ../src/test/txvalidationcache_tests.cpp:39
[18:35:55] :	 [Step 1/1]     #8 0x55cec642a485 in boost::detail::function::void_function_invoker0<void (*)(), void>::invoke(boost::detail::function::function_buffer&) /usr/include/boost/function/function_template.hpp:118
[18:35:55] :	 [Step 1/1]     #9 0x7f1e9c7a0f5d in boost::detail::function::function_obj_invoker0<boost::detail::forward, int>::invoke(boost::detail::function::function_buffer&) (/lib/x86_64-linux-gnu/libboost_unit_test_framework.so.1.67.0+0x54f5d)
[18:35:55] :	 [Step 1/1]     #10 0x7f1e9c7a0b64 in boost::execution_monitor::catch_signals(boost::function<int ()> const&) (/lib/x86_64-linux-gnu/libboost_unit_test_framework.so.1.67.0+0x54b64)
[18:35:55] :	 [Step 1/1]     #11 0x7f1e9c7a0c30 in boost::execution_monitor::execute(boost::function<int ()> const&) (/lib/x86_64-linux-gnu/libboost_unit_test_framework.so.1.67.0+0x54c30)
[18:35:55] :	 [Step 1/1]     #12 0x7f1e9c7a0cfc in boost::execution_monitor::vexecute(boost::function<void ()> const&) (/lib/x86_64-linux-gnu/libboost_unit_test_framework.so.1.67.0+0x54cfc)
[18:35:55] :	 [Step 1/1]     #13 0x7f1e9c7c88a8 in boost::unit_test::unit_test_monitor_t::execute_and_translate(boost::function<void ()> const&, unsigned int) (/lib/x86_64-linux-gnu/libboost_unit_test_framework.so.1.67.0+0x7c8a8)
[18:35:55] :	 [Step 1/1]     #14 0x7f1e9c7a346a  (/lib/x86_64-linux-gnu/libboost_unit_test_framework.so.1.67.0+0x5746a)
[18:35:55] :	 [Step 1/1]     #15 0x7f1e9c7a372e  (/lib/x86_64-linux-gnu/libboost_unit_test_framework.so.1.67.0+0x5772e)
[18:35:55] :	 [Step 1/1]     #16 0x7f1e9c7a372e  (/lib/x86_64-linux-gnu/libboost_unit_test_framework.so.1.67.0+0x5772e)
[18:35:55] :	 [Step 1/1]     #17 0x7f1e9c7a5fd4 in boost::unit_test::framework::run(unsigned long, bool) (/lib/x86_64-linux-gnu/libboost_unit_test_framework.so.1.67.0+0x59fd4)
[18:35:55] :	 [Step 1/1]     #18 0x7f1e9c7c6317 in boost::unit_test::unit_test_main(bool (*)(), int, char**) (/lib/x86_64-linux-gnu/libboost_unit_test_framework.so.1.67.0+0x7a317)
[18:35:55] :	 [Step 1/1]     #19 0x55cec6419a9f in main ../src/test/test_bitcoin_main.cpp:48
[18:35:55] :	 [Step 1/1]     #20 0x7f1e9b66609a in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x2409a)
[18:35:55] :	 [Step 1/1]     #21 0x55cec63ab749 in _start (/home/teamcity/buildAgent/work/c4a5708f2bae7929/build/src/test/test_bitcoin+0x3b5749)
[18:35:55] :	 [Step 1/1] 
[18:35:55] :	 [Step 1/1] AddressSanitizer can not provide additional info.
[18:35:55] :	 [Step 1/1] SUMMARY: AddressSanitizer: SEGV ../src/crypto/sha256_sse4.cpp:953 in sha256_sse4::Transform(unsigned int*, unsigned char const*, unsigned long)
[18:35:55] :	 [Step 1/1] ==5547==ABORTING
[18:35:55]W:	 [Step 1/1] Process exited with code 1
[18:35:55]E:	 [Step 1/1] Process exited with code 1 (Step: Command Line)

Rebased.

Build Bitcoin-ABC / Diffs / Diff Testing started.

Build Bitcoin-ABC / Diffs / Diff Testing passed.

Harbormaster completed remote builds in B8774: Diff 15211.Jan 7 2020, 19:33

Build Bitcoin-ABC / Diffs (Resource Intensive) / Resource Intensive Diff Testing started.

Build Bitcoin-ABC / Diffs (Resource Intensive) / Resource Intensive Diff Testing passed.

jasonbcox accepted this revision.Jan 8 2020, 22:05

This revision is now accepted and ready to land.Jan 8 2020, 22:05

Build Bitcoin-ABC / Diffs / Diff Testing started.

Build Bitcoin-ABC / Diffs / Diff Testing passed.

Closed by commit rABC08f879687543: Use best-fit strategy in Arena, now O(log(n)) instead O(n) (authored by Wladimir J. van der Laan <laanwj@gmail.com>, committed by nakihito). · Explain WhyJan 9 2020, 18:04

This revision was automatically updated to reflect the committed changes.

nakihito added a commit: rABC08f879687543: Use best-fit strategy in Arena, now O(log(n)) instead O(n).

nakihito edited the summary of this revision. (Show Details)Jan 9 2020, 18:05

markblundeberg added a subscriber: markblundeberg.Feb 15 2020, 11:35

markblundeberg added inline comments.

contrib/teamcity/build-configurations.sh

Note that in combination with D5042, it means we now see the following kind of thing (harmless) in asan CI build log.

https://build.bitcoinabc.org/viewLog.html?buildId=29441&buildTypeId=BitcoinABC_Master_BitcoinAbcMasterAsan&tab=buildLog&_focus=1053&state=59#_state=59

[10:39:54]
[Step 1/1] Running 455 test cases...
[10:39:54]
[Step 1/1] 0x00000000x80ffc10 0x00000000000003f0 0x1
[10:39:54]
[Step 1/1] 
[10:39:54]
[Step 1/1] 0x00000000x8000000 0x00000000000ffc10 0x0
[10:39:54]
[Step 1/1] 
[10:39:54]
[Step 1/1] 
[10:39:54]
[Step 1/1] 0x00000000x8000000 0x0000000000100000 0x0
[10:39:54]
[Step 1/1] 
[10:39:54]
[Step 1/1] 0x00000000x80ffc80 0x0000000000000200 0x1
[10:39:54]
[Step 1/1] 0x00000000x80fff80 0x0000000000000080 0x1
[10:39:54]
[Step 1/1] 0x00000000x80ffe80 0x0000000000000100 0x1
[10:39:54]
[Step 1/1] 
[10:39:54]
[Step 1/1] 0x00000000x8000000 0x00000000000ffc80 0x0
[10:39:54]
[Step 1/1] 
[10:39:54]
[Step 1/1] 0x00000000x80ffc80 0x0000000000000200 0x1
[10:39:54]
[Step 1/1] 0x00000000x80ffe80 0x0000000000000100 0x1
[10:39:54]
[Step 1/1] 
[10:39:54]
[Step 1/1] 0x00000000x80fff80 0x0000000000000080 0x0
[10:39:54]
[Step 1/1] 0x00000000x8000000 0x00000000000ffc80 0x0
[10:39:54]
[Step 1/1] 
[10:39:54]
[Step 1/1] 0x00000000x80fff80 0x0000000000000080 0x1
[10:39:54]
[Step 1/1] 0x00000000x80ffc80 0x0000000000000200 0x1
[10:39:54]
[Step 1/1] 
[10:39:54]
[Step 1/1] 0x00000000x80ffe80 0x0000000000000100 0x0
[10:39:54]
[Step 1/1] 0x00000000x8000000 0x00000000000ffc80 0x0
[10:39:54]
[Step 1/1] 
[10:39:54]
[Step 1/1] 
[10:39:54]
[Step 1/1] 0x00000000x8000000 0x0000000000100000 0x0
[10:39:54]
[Step 1/1]

nakihito added a commit: rSTAGING08f879687543: Use best-fit strategy in Arena, now O(log(n)) instead O(n).Apr 7 2020, 22:20

Use best-fit strategy in Arena, now O(log(n)) instead O(n)
ClosedPublic
Actions

Details

Diff Detail

Event Timeline

Revision Contents
Changeset List

Diff 15282

contrib/teamcity/build-configurations.sh

src/bench/lockedpool.cpp

src/support/lockedpool.h

src/support/lockedpool.cpp

Use best-fit strategy in Arena, now O(log(n)) instead O(n)ClosedPublicActions

Details

Diff Detail

Event Timeline

Revision ContentsChangeset List

Diff 15282

contrib/teamcity/build-configurations.sh

src/bench/lockedpool.cpp

src/support/lockedpool.h

src/support/lockedpool.cpp

Use best-fit strategy in Arena, now O(log(n)) instead O(n)
ClosedPublic
Actions

Revision Contents
Changeset List