Page MenuHomePhabricator
Differential D10379

[avalanche] Avoid O(n2) when voting on proofs
ClosedPublic
Actions

Authored by Fabien on Oct 21 2021, 16:57.

Details

Reviewers
deadalnix
Group Reviewers
Restricted Project
Maniphest Tasks
Restricted Maniphest Task
Commits
rABCb1e53bef68c6: [avalanche] Avoid O(n2) when voting on proofs
Summary

This fix the quadratic complexity that occurs when voting on proofs. There is no change in behavior.

Ref T1854.

Depends on D10378 and D10384.

Test Plan
ninja all check-all

Diff Detail

Repository
rABC Bitcoin ABC
Lint
Lint Not Applicable
Unit
Tests Not Applicable

Event Timeline

Fabien created this revision.Oct 21 2021, 16:57
Herald added a reviewer: Restricted Project. · View Herald TranscriptOct 21 2021, 16:57
Fabien requested review of this revision.Oct 21 2021, 16:57
Harbormaster completed remote builds in B17094: Diff 30634.Oct 21 2021, 17:07
deadalnix requested changes to this revision.Oct 21 2021, 20:23
deadalnix added a subscriber: deadalnix.
deadalnix added inline comments.
src/avalanche/processor.cpp
630 ↗(On Diff #30634)

Can you extract this refactoring in its own patch?

This revision now requires changes to proceed.Oct 21 2021, 20:23
Fabien updated this revision to Diff 30648.Oct 22 2021, 09:06

Rebase on top of D10384.

Fabien edited the summary of this revision. (Show Details)Oct 22 2021, 09:07
Fabien added a parent revision: D10384: [avalanche] Factorize the inflight request timeout handling.
Fabien removed a parent revision: D10378: [avalanche] Determine proof acceptance status from the peer manager.
Fabien edited the summary of this revision. (Show Details)
Fabien added a parent revision: D10378: [avalanche] Determine proof acceptance status from the peer manager.
Harbormaster completed remote builds in B17107: Diff 30648.Oct 22 2021, 09:20
deadalnix requested changes to this revision.Oct 26 2021, 21:14
deadalnix added inline comments.
src/avalanche/processor.cpp
653 ↗(On Diff #30648)

This should use the WITH_LOCk construct.

656 ↗(On Diff #30648)

This introduce the same unnecessary lock as D10384 .

This revision now requires changes to proceed.Oct 26 2021, 21:14
Fabien updated this revision to Diff 30668.Oct 27 2021, 08:07

Feedback

Harbormaster completed remote builds in B17118: Diff 30668.Oct 27 2021, 08:19
teamcity added a comment.Oct 27 2021, 08:19
Build Bitcoin ABC Diffs / Diff Testing (build-clang) failed.

Tail of the build log:

[396/455] bitcoin: testing finalization_tests
[397/455] Running utility command for check-bitcoin-finalization_tests
[398/455] bitcoin: testing merkleblock_tests
[399/455] bitcoin: testing cuckoocache_tests
[400/455] Running utility command for check-bitcoin-merkleblock_tests
[401/455] Running utility command for check-bitcoin-cuckoocache_tests
[402/455] bitcoin: testing bip32_tests
[403/455] bitcoin: testing txvalidationcache_tests
[404/455] Running utility command for check-bitcoin-bip32_tests
[405/455] Running utility command for check-bitcoin-txvalidationcache_tests
[406/455] bitcoin: testing scheduler_tests
[407/455] bitcoin: testing sync_tests
[408/455] Running utility command for check-bitcoin-scheduler_tests
[409/455] bitcoin: testing torcontrol_tests
[410/455] Running utility command for check-bitcoin-sync_tests
[411/455] Running utility command for check-bitcoin-torcontrol_tests
[412/455] bitcoin: testing settings_tests
[413/455] bitcoin: testing op_reversebytes_tests
[414/455] bitcoin: testing streams_tests
[415/455] Running utility command for check-bitcoin-settings_tests
[416/455] Running utility command for check-bitcoin-op_reversebytes_tests
[417/455] Running utility command for check-bitcoin-streams_tests
[418/455] bitcoin: testing validation_flush_tests
[419/455] bitcoin: testing timedata_tests
[420/455] Running utility command for check-bitcoin-validation_flush_tests
[421/455] Running utility command for check-bitcoin-timedata_tests
[422/455] bitcoin: testing compilerbug_tests
[423/455] bitcoin: testing blockcheck_tests
[424/455] Running utility command for check-bitcoin-compilerbug_tests
[425/455] Running utility command for check-bitcoin-blockcheck_tests
[426/455] bitcoin: testing checkpoints_tests
[427/455] bitcoin: testing transaction_tests
[428/455] bitcoin: testing serialize_tests
[429/455] bitcoin: testing schnorr_tests
[430/455] Running utility command for check-bitcoin-checkpoints_tests
[431/455] bitcoin: testing validationinterface_tests
[432/455] Running utility command for check-bitcoin-transaction_tests
[433/455] Running utility command for check-bitcoin-serialize_tests
[434/455] Running utility command for check-bitcoin-schnorr_tests
[435/455] Running utility command for check-bitcoin-validationinterface_tests
[436/455] bitcoin: testing blockstatus_tests
[437/455] Running utility command for check-bitcoin-blockstatus_tests
[438/455] bitcoin: testing cashaddr_tests
[439/455] Running utility command for check-bitcoin-cashaddr_tests
[440/455] bitcoin: testing wallet_tests
[441/455] Running utility command for check-bitcoin-wallet_tests
[442/455] bitcoin: testing versionbits_tests
[443/455] Running utility command for check-bitcoin-versionbits_tests
[444/455] bitcoin: testing script_tests
[445/455] bitcoin: testing crypto_tests
[446/455] Running utility command for check-bitcoin-script_tests
[447/455] Running utility command for check-bitcoin-crypto_tests
[448/455] bitcoin: testing monolith_opcodes_tests
[449/455] Running utility command for check-bitcoin-monolith_opcodes_tests
[450/455] bitcoin: testing intmath_tests
[451/455] Running utility command for check-bitcoin-intmath_tests
[452/455] bitcoin: testing coins_tests
[453/455] Running utility command for check-bitcoin-coins_tests
ninja: build stopped: cannot make progress due to previous errors.
Build build-clang failed with exit code 1
Fabien added a comment.Oct 27 2021, 08:22

Unrelated spurious failure, restarting the build

deadalnix requested changes to this revision.Oct 27 2021, 14:16
deadalnix added inline comments.
src/avalanche/processor.cpp
431 ↗(On Diff #30668)

This does not looks like it require the lock.

647 ↗(On Diff #30668)

likestamp

This revision now requires changes to proceed.Oct 27 2021, 14:16
Fabien updated this revision to Diff 30672.Oct 27 2021, 15:21

Reduce scope lock.
The same will be done for the block index in a follow up.

Fabien added a child revision: D10391: [avalanche] Slightly reduce cs_main scope in registerVotes.Oct 27 2021, 15:29
Harbormaster completed remote builds in B17120: Diff 30672.Oct 27 2021, 15:38
deadalnix accepted this revision.Nov 1 2021, 16:02
This revision is now accepted and ready to land.Nov 1 2021, 16:02
Closed by commit rABCb1e53bef68c6: [avalanche] Avoid O(n2) when voting on proofs (authored by Fabien). · Explain WhyNov 2 2021, 10:29
This revision was automatically updated to reflect the committed changes.
Fabien added a commit: rABCb1e53bef68c6: [avalanche] Avoid O(n2) when voting on proofs.

Revision Contents
Changeset List

PathSize
src/
avalanche/
26 lines

Diff 30724

View Options

src/avalanche/processor.cpp

Loading...