test: Fix bug in transaction generation in ComplexMempool benchmark #22856

shoryak · 2021-09-01T17:53:34Z

This fixes issues with ComplexMempool benchmark introduced in #17292 , this stress test benchmarks performance of ancestor and descendant tracking of mempool graph algorithms on a complex Mempool.

This Benchmark first creates 100 base transactions and stores them in available_coins vector. available_coins is used for selecting ancestor transactions while creating 800 new transactions. For this a random transaction is picked from available_coins and some of its outputs are mapped to the inputs of the new transaction being created.

Now in case we exhaust all the outputs of an entry in available_coins then we need to remove it from available_coins before the next iteration of choosing a potential ancestor , it is now implemented with this patch.

As the index of the entry is randomly chosen from available_coins , In order to remove it from the vector , if index of the selected entry is not at the end of available_coins vector , it is swapped with the entry at the back of the vector , then the entry at the end of available_coins is popped out.

Earlier the code responsible for constructing outputs of the newly created transaction was inside the loop used for assigning ancestors to the transaction , which does some unnecessary work as it creates outputs of the transaction again and again , now it is moved out of the loop so outputs of the transaction are created just once before adding it to the final list of the transactions created. This one is a minor change to save some computation.

These changes have changed the ComplexMempool benchmark results on bitcoin:master as follows :

Before

ns/op	op/s	err%	total	benchmark
232,881,625.00	4.29	0.7%	2.55	`ComplexMemPool`

After

ns/op	op/s	err%	total	benchmark
497,275,135.00	2.01	0.5%	5.49	`ComplexMemPool`

fanquake · 2021-09-02T02:20:47Z

Please modify the commit message to actually explain the changes.

JeremyRubin · 2021-09-02T17:16:25Z

src/bench/mempool_stress.cpp

can use available_coins.back() here too.

src/bench/mempool_stress.cpp

Available in line 59 is made a reference , so contents of the coin can be modified While generating transactions we select ancestors from available_coins ,in case we exhaust all the outputs of an entry in available_coins then we need to remove it from available_coins before the next iteration of choosing a potential ancestor , it is now implemented with this patch by ,As the index of the entry is randomly chosen from available_coins , In order to remove it from the vector if index of the selected entry is not at the end of available_coins vector, it is swapped with the entry at the back of the vector , then the entry at the end of available_coins is popped out. Code generating outputs for the transaction is moved out of the loop, as it needs to be done only once before adding the transaction to ordered_coins

theStack

Concept ACK

If I understand correctly, this PR actually contains two bug fixes (remove correct element from available_coins, make modification to available_coins[idx] effective by declaring coin as reference) and one performance improvement?

Would maybe be worth splitting up into two commits. Also the commit body looks a bit messy currently (too long lines, confusing interpunction, grammar). In the course of doing that, a rebase on master couldn't hurt -- I am actually surprised that there is no merge conflict, since #23157 generalized the CreateOrderedCoins helper function.

JeremyRubin · 2021-11-10T22:13:24Z

i'm not sure if @shoryak is still watching bitcoin core stuff since the semester is quite busy and this was a SoB project...

i think it'd be fine to merge as is?

laanwj · 2021-11-26T16:26:12Z

That's a valid reason to no longer work on it, but "author doesn't have time" is not a valid reason for something to be merged while ignoring reviewer comments. Normally we'd close and label "up for grabs".

But in this particular case, yes, it's probably fine like this. @theStack do you agree?

theStack · 2021-11-26T19:09:16Z

@laanwj: My concerns were mainly considering aesthetics (commit message formatting etc.), but the code change itself looks correct to me, so yes, I agree 👍

shoryak · 2021-12-02T08:37:51Z

@theStack I would be happy to make any changes in the formatting of the commit message, though I prefer it to be just a single commit rather than two.

maflcko · 2021-12-07T12:19:10Z

/usr/bin/time --format='%M' ./src/bench/bench_bitcoin --filter=ComplexMemPool
Before: 57016
After: 56532
/usr/bin/time --format='%M' valgrind ./src/bench/bench_bitcoin --filter=ComplexMemPool
Before: 340496
After: 340420

maflcko · 2021-12-07T14:01:27Z

src/bench/mempool_stress.cpp

+            Available& coin = available_coins[idx];
            uint256 hash = coin.ref->GetHash();
            // biased towards taking just one ancestor, but maybe more
            size_t n_to_take = det_rand.randrange(2) == 0 ? 1 : 1+det_rand.randrange(coin.ref->vout.size() - coin.vin_left);


bench/mempool_stress.cpp:59:89: runtime error: unsigned integer overflow: 9 - 11 cannot be represented in type 'unsigned long'

I've reverted the merge in commit 95fe477 again due to this

interesting -- why was it passing here but not on master?

we changed from clang-12 to clang-13, maybe?

…exMempool benchmark 29e9833 Fixes Bug in Transaction generation in ComplexMempool benchmark (Shorya) Pull request description: This fixes issues with `ComplexMempool` benchmark introduced in [bitcoin#17292](bitcoin#17292) , this stress test benchmarks performance of ancestor and descendant tracking of mempool graph algorithms on a complex Mempool. This Benchmark first creates 100 base transactions and stores them in `available_coins` vector. `available_coins` is used for selecting ancestor transactions while creating 800 new transactions. For this a random transaction is picked from `available_coins` and some of its outputs are mapped to the inputs of the new transaction being created. Now in case we exhaust all the outputs of an entry in `available_coins` then we need to remove it from `available_coins` before the next iteration of choosing a potential ancestor , it is now implemented with this patch. As the index of the entry is randomly chosen from `available_coins` , In order to remove it from the vector , if index of the selected entry is not at the end of `available_coins` vector , it is swapped with the entry at the back of the vector , then the entry at the end of `available_coins` is popped out. Earlier the code responsible for constructing outputs of the newly created transaction was inside the loop used for assigning ancestors to the transaction , which does some unnecessary work as it creates outputs of the transaction again and again , now it is moved out of the loop so outputs of the transaction are created just once before adding it to the final list of the transactions created. This one is a minor change to save some computation. These changes have changed the `ComplexMempool` benchmark results on `bitcoin:master` as follows : **Before** > | ns/op | op/s | err% | total | benchmark |--------------------:|--------------------:|--------:|----------:|:---------- | 232,881,625.00 | 4.29 | 0.7% | 2.55 | `ComplexMemPool` **After** > | ns/op | op/s | err% | total | benchmark |--------------------:|--------------------:|--------:|----------:|:---------- | 497,275,135.00 | 2.01 | 0.5% | 5.49 | `ComplexMemPool` Top commit has no ACKs. Tree-SHA512: d6946d7e65c55f54c84cc49d7abee52e59ffc8b7668b3c80b4ce15a57690ab00a600c6241cc71a2a075def9c30792a311256fed325ef162f37aeacd2cce93624

…in ComplexMempool benchmark 2b02e09 Fixes Bug in Transaction generation in ComplexMempool benchmark (Shorya) Pull request description: This fixes issues with `ComplexMempool` benchmark introduced in [#17292](bitcoin/bitcoin#17292) , this stress test benchmarks performance of ancestor and descendant tracking of mempool graph algorithms on a complex Mempool. This Benchmark first creates 100 base transactions and stores them in `available_coins` vector. `available_coins` is used for selecting ancestor transactions while creating 800 new transactions. For this a random transaction is picked from `available_coins` and some of its outputs are mapped to the inputs of the new transaction being created. Now in case we exhaust all the outputs of an entry in `available_coins` then we need to remove it from `available_coins` before the next iteration of choosing a potential ancestor , it is now implemented with this patch. As the index of the entry is randomly chosen from `available_coins` , In order to remove it from the vector , if index of the selected entry is not at the end of `available_coins` vector , it is swapped with the entry at the back of the vector , then the entry at the end of `available_coins` is popped out. Earlier the code responsible for constructing outputs of the newly created transaction was inside the loop used for assigning ancestors to the transaction , which does some unnecessary work as it creates outputs of the transaction again and again , now it is moved out of the loop so outputs of the transaction are created just once before adding it to the final list of the transactions created. This one is a minor change to save some computation. These changes have changed the `ComplexMempool` benchmark results on `bitcoin:master` as follows : **Before** > | ns/op | op/s | err% | total | benchmark |--------------------:|--------------------:|--------:|----------:|:---------- | 232,881,625.00 | 4.29 | 0.7% | 2.55 | `ComplexMemPool` **After** > | ns/op | op/s | err% | total | benchmark |--------------------:|--------------------:|--------:|----------:|:---------- | 497,275,135.00 | 2.01 | 0.5% | 5.49 | `ComplexMemPool` Top commit has no ACKs. Tree-SHA512: d6946d7e65c55f54c84cc49d7abee52e59ffc8b7668b3c80b4ce15a57690ab00a600c6241cc71a2a075def9c30792a311256fed325ef162f37aeacd2cce93624

…exMempool benchmark 29e9833 Fixes Bug in Transaction generation in ComplexMempool benchmark (Shorya) Pull request description: This fixes issues with `ComplexMempool` benchmark introduced in [bitcoin#17292](bitcoin#17292) , this stress test benchmarks performance of ancestor and descendant tracking of mempool graph algorithms on a complex Mempool. This Benchmark first creates 100 base transactions and stores them in `available_coins` vector. `available_coins` is used for selecting ancestor transactions while creating 800 new transactions. For this a random transaction is picked from `available_coins` and some of its outputs are mapped to the inputs of the new transaction being created. Now in case we exhaust all the outputs of an entry in `available_coins` then we need to remove it from `available_coins` before the next iteration of choosing a potential ancestor , it is now implemented with this patch. As the index of the entry is randomly chosen from `available_coins` , In order to remove it from the vector , if index of the selected entry is not at the end of `available_coins` vector , it is swapped with the entry at the back of the vector , then the entry at the end of `available_coins` is popped out. Earlier the code responsible for constructing outputs of the newly created transaction was inside the loop used for assigning ancestors to the transaction , which does some unnecessary work as it creates outputs of the transaction again and again , now it is moved out of the loop so outputs of the transaction are created just once before adding it to the final list of the transactions created. This one is a minor change to save some computation. These changes have changed the `ComplexMempool` benchmark results on `bitcoin:master` as follows : **Before** > | ns/op | op/s | err% | total | benchmark |--------------------:|--------------------:|--------:|----------:|:---------- | 232,881,625.00 | 4.29 | 0.7% | 2.55 | `ComplexMemPool` **After** > | ns/op | op/s | err% | total | benchmark |--------------------:|--------------------:|--------:|----------:|:---------- | 497,275,135.00 | 2.01 | 0.5% | 5.49 | `ComplexMemPool` Top commit has no ACKs. Tree-SHA512: d6946d7e65c55f54c84cc49d7abee52e59ffc8b7668b3c80b4ce15a57690ab00a600c6241cc71a2a075def9c30792a311256fed325ef162f37aeacd2cce93624

shoryak force-pushed the complexmempool branch from f65b92f to 8ae1334 Compare September 1, 2021 18:17

DrahtBot added the Tests label Sep 1, 2021

fanquake requested a review from JeremyRubin September 2, 2021 02:20

JeremyRubin reviewed Sep 2, 2021

View reviewed changes

src/bench/mempool_stress.cpp Outdated

Copy link

Contributor

JeremyRubin Sep 2, 2021

Choose a reason for hiding this comment

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

can use available_coins.back() here too.

shoryak reacted with thumbs up emoji

JeremyRubin reviewed Sep 2, 2021

View reviewed changes

src/bench/mempool_stress.cpp Outdated Show resolved Hide resolved

shoryak force-pushed the complexmempool branch 4 times, most recently from fe3d95f to b3f89cc Compare September 4, 2021 12:44

shoryak force-pushed the complexmempool branch from b3f89cc to 29e9833 Compare September 4, 2021 12:48

laanwj changed the title ~~Modifications in ComplexMempool benchmark~~ test: Fix bug in transaction generation in ComplexMempool benchmark Sep 16, 2021

theStack reviewed Nov 10, 2021

View reviewed changes

maflcko merged commit abc26fa into bitcoin:master Dec 7, 2021

maflcko mentioned this pull request Dec 7, 2021

bench: Avoid OOM for now #23691

Closed

maflcko reviewed Dec 7, 2021

View reviewed changes

bitcoin locked and limited conversation to collaborators Dec 7, 2022

test: Fix bug in transaction generation in ComplexMempool benchmark #22856

test: Fix bug in transaction generation in ComplexMempool benchmark #22856

Uh oh!

Conversation

shoryak commented Sep 1, 2021 • edited by maflcko Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

fanquake commented Sep 2, 2021

Uh oh!

JeremyRubin Sep 2, 2021

Choose a reason for hiding this comment

Uh oh!

Uh oh!

theStack left a comment

Choose a reason for hiding this comment

Uh oh!

JeremyRubin commented Nov 10, 2021

Uh oh!

laanwj commented Nov 26, 2021

Uh oh!

theStack commented Nov 26, 2021

Uh oh!

shoryak commented Dec 2, 2021

Uh oh!

maflcko commented Dec 7, 2021

Uh oh!

maflcko Dec 7, 2021

Choose a reason for hiding this comment

Uh oh!

maflcko Dec 7, 2021

Choose a reason for hiding this comment

Uh oh!

JeremyRubin Dec 7, 2021

Choose a reason for hiding this comment

Uh oh!

maflcko Dec 7, 2021

Choose a reason for hiding this comment

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

7 participants

shoryak commented Sep 1, 2021 •

edited by maflcko

Loading