Skip to content

fuzz: Speed up PickValue in txorphan #30474

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Merged
merged 1 commit into from
Jul 23, 2024
Merged

fuzz: Speed up PickValue in txorphan #30474

merged 1 commit into from
Jul 23, 2024

Conversation

maflcko
Copy link
Member

@maflcko maflcko commented Jul 17, 2024

PickValue will advance a begin iterator on the outpoints set, which is expensive, because it only has a ++ operator. As it is called in a loop of num_in (~outpoints.size()), the runtime is O(outpoints.size() ^ 2).

Fix it by making the runtime linear.

@DrahtBot
Copy link
Contributor

DrahtBot commented Jul 17, 2024 •
edited
Loading

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Code Coverage

For detailed information about the code coverage, see the test coverage report.

Reviews

See the guideline for information on the review process.

Type Reviewers
ACK glozow, dergoegge
Stale ACK paplorinc

If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.

@DrahtBot DrahtBot added the Tests label Jul 17, 2024
@maflcko maflcko mentioned this pull request Jul 17, 2024
Merged
dergoegge
dergoegge reviewed Jul 18, 2024
View reviewed changes
@maflcko
Copy link
Member Author

maflcko commented Jul 18, 2024

I forgot to mention the fuzz input for testing. It is c6efad2b3a41cf2a2a682dabed1310bf5e3c101e. See https://cirrus-ci.com/task/6178647134961664?logs=ci#L4058

Run txorphan with args ['/ci_container_base/ci/scratch/build/bitcoin-x86_64-pc-linux-gnu/src/test/fuzz/fuzz', '-runs=1', PosixPath('/ci_container_base/ci/scratch/qa-assets/fuzz_seed_corpus/txorphan')]INFO: Running with entropic power schedule (0xFF, 100).
INFO: Seed: 3180047797
INFO: Loaded 1 modules   (623498 inline 8-bit counters): 623498 [0x55a9ae6a0518, 0x55a9ae7388a2), 
INFO: Loaded 1 PC tables (623498 PCs): 623498 [0x55a9ae7388a8,0x55a9af0bc148), 
INFO:      651 files found in /ci_container_base/ci/scratch/qa-assets/fuzz_seed_corpus/txorphan
INFO: -max_len is not provided; libFuzzer will not generate inputs larger than 1048576 bytes
INFO: seed corpus: files: 651 min: 1b max: 2173657b total: 41752504b rss: 114Mb
#512	pulse  cov: 2457 ft: 11189 corp: 262/885Kb exec/s: 170 rss: 280Mb
Slowest unit: 13 s:
artifact_prefix='./'; Test unit written to ./slow-unit-c6efad2b3a41cf2a2a682dabed1310bf5e3c101e
#652	INITED cov: 2514 ft: 12563 corp: 349/23Mb exec/s: 5 rss: 491Mb
#652	DONE   cov: 2514 ft: 12563 corp: 349/23Mb lim: 978076 exec/s: 5 rss: 491Mb
Done 652 runs in 117 second(s)

Screenshot from 2024-07-18 09-45-16

dergoegge
dergoegge approved these changes Jul 18, 2024
View reviewed changes
Copy link
Member

@dergoegge dergoegge left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

utACK fa4e796

@DrahtBot
Copy link
Contributor

🚧 At least one of the CI tasks failed.
Debug: https://github.com/bitcoin/bitcoin/runs/27602359666

Hints

Make sure to run all tests locally, according to the documentation.

The failure may happen due to a number of reasons, for example:

  • Possibly due to a silent merge conflict (the changes in this pull request being
    incompatible with the current code in the target branch). If so, make sure to rebase on the latest
    commit of the target branch.

  • A sanitizer issue, which can only be found by compiling with the sanitizer and running the
    affected test.

  • An intermittent issue.

Leave a comment here, if you need help tracking down a confusing failure.

@maflcko
Copy link
Member Author

maflcko commented Jul 18, 2024

Re-running known Wine CI failure.

l0rinc
l0rinc reviewed Jul 18, 2024
View reviewed changes
glozow
glozow reviewed Jul 19, 2024
View reviewed changes
Copy link
Member

@glozow glozow left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

concept ACK, thanks @maflcko!

@l0rinc
Copy link
Contributor

l0rinc commented Jul 23, 2024 •
edited
Loading

utACK fa030ad

(could you please add me as co-author, l0rinc <pap.lorinc@gmail.com>?)

@DrahtBot DrahtBot requested review from glozow and dergoegge July 23, 2024 07:31
@l0rinc
fuzz: Speed up PickValue in txorphan
fa33a63 
Co-Authored-By: l0rinc <pap.lorinc@gmail.com>
@maflcko
Copy link
Member Author

maflcko commented Jul 23, 2024

(could you please add me as co-author, l0rinc <pap.lorinc@gmail.com>?)

Sure, done

glozow
glozow reviewed Jul 23, 2024
View reviewed changes
Copy link
Member

@glozow glozow left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

ACK fa33a63, thanks for taking the suggestion

@DrahtBot DrahtBot requested a review from l0rinc July 23, 2024 09:15
dergoegge
dergoegge approved these changes Jul 23, 2024
View reviewed changes
Copy link
Member

@dergoegge dergoegge left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

utACK fa33a63

@fanquake fanquake merged commit 910d38b into bitcoin:master Jul 23, 2024
15 of 16 checks passed
@maflcko maflcko deleted the 2407-fuzz-txo branch July 23, 2024 10:04
@bitcoin bitcoin locked and limited conversation to collaborators Jul 23, 2025
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Reviewers

@glozow glozow glozow left review comments

@l0rinc l0rinc Awaiting requested review from l0rinc

+1 more reviewer

@dergoegge dergoegge dergoegge approved these changes

Reviewers whose approvals may not affect merge requirements
Assignees
No one assigned
Labels
Tests
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.
6 participants
@maflcko @DrahtBot @l0rinc @dergoegge @glozow @fanquake