b0c774b Add new mempool benchmarks for a complex pool (Jeremy Rubin)

Pull request description:

  This PR is related to #17268.

  It adds a mempool stress test which makes a really big complicated tx graph, and then, similar to mempool_eviction test, trims the size.

  The test setup is to make 100 original transactions with Rand(10)+2 outputs each.

  Then, 800 times:

  we create a new transaction with Rand(10) + 1 parents that are randomly sampled from all existing transactions (with unspent outputs). From each such parent, we then select Rand(remaining outputs) +1 50% of the time, or 1 outputs 50% of the time.

  Then, we trim the size to 3/4. Then we trim it to just a single transaction.

  This creates, hopefully, a big bundle of transactions with lots of complex structure, that should really put a strain on the mempool graph algorithms.

  This ends up testing both the descendant and ancestor tracking.

  I don't love that the test is "unstable". That is, in order to compare this test to another, you really can't modify any of the internal state because it will have a different order of invocations of the deterministic randomness. However, it certainly suffices for comparing branches.

Top commit has no ACKs.

Tree-SHA512: cabe96b849b9885878e20eec558915e921d49e6ed1e4b011b22ca191b4c99aa28930a8b963784c9adf78cc8b034a655513f7a0da865e280a1214ae15ebb1d574

b0c774b Add new mempool benchmarks for a complex pool (Jeremy Rubin)

Pull request description:

  This PR is related to bitcoin#17268.

  It adds a mempool stress test which makes a really big complicated tx graph, and then, similar to mempool_eviction test, trims the size.

  The test setup is to make 100 original transactions with Rand(10)+2 outputs each.

  Then, 800 times:

  we create a new transaction with Rand(10) + 1 parents that are randomly sampled from all existing transactions (with unspent outputs). From each such parent, we then select Rand(remaining outputs) +1 50% of the time, or 1 outputs 50% of the time.

  Then, we trim the size to 3/4. Then we trim it to just a single transaction.

  This creates, hopefully, a big bundle of transactions with lots of complex structure, that should really put a strain on the mempool graph algorithms.

  This ends up testing both the descendant and ancestor tracking.

  I don't love that the test is "unstable". That is, in order to compare this test to another, you really can't modify any of the internal state because it will have a different order of invocations of the deterministic randomness. However, it certainly suffices for comparing branches.

Top commit has no ACKs.

Tree-SHA512: cabe96b849b9885878e20eec558915e921d49e6ed1e4b011b22ca191b4c99aa28930a8b963784c9adf78cc8b034a655513f7a0da865e280a1214ae15ebb1d574

b0c774b Add new mempool benchmarks for a complex pool (Jeremy Rubin)

Pull request description:

  This PR is related to bitcoin#17268.

  It adds a mempool stress test which makes a really big complicated tx graph, and then, similar to mempool_eviction test, trims the size.

  The test setup is to make 100 original transactions with Rand(10)+2 outputs each.

  Then, 800 times:

  we create a new transaction with Rand(10) + 1 parents that are randomly sampled from all existing transactions (with unspent outputs). From each such parent, we then select Rand(remaining outputs) +1 50% of the time, or 1 outputs 50% of the time.

  Then, we trim the size to 3/4. Then we trim it to just a single transaction.

  This creates, hopefully, a big bundle of transactions with lots of complex structure, that should really put a strain on the mempool graph algorithms.

  This ends up testing both the descendant and ancestor tracking.

  I don't love that the test is "unstable". That is, in order to compare this test to another, you really can't modify any of the internal state because it will have a different order of invocations of the deterministic randomness. However, it certainly suffices for comparing branches.

Top commit has no ACKs.

Tree-SHA512: cabe96b849b9885878e20eec558915e921d49e6ed1e4b011b22ca191b4c99aa28930a8b963784c9adf78cc8b034a655513f7a0da865e280a1214ae15ebb1d574

Summary:
Add new mempool benchmarks for a complex pool (Jeremy Rubin)

Pull request description:

  This PR is related to #17268.

  It adds a mempool stress test which makes a really big complicated tx graph, and then, similar to mempool_eviction test, trims the size.

  The test setup is to make 100 original transactions with Rand(10)+2 outputs each.

  Then, 800 times:

  we create a new transaction with Rand(10) + 1 parents that are randomly sampled from all existing transactions (with unspent outputs). From each such parent, we then select Rand(remaining outputs) +1 50% of the time, or 1 outputs 50% of the time.

  Then, we trim the size to 3/4. Then we trim it to just a single transaction.

  This creates, hopefully, a big bundle of transactions with lots of complex structure, that should really put a strain on the mempool graph algorithms.

  This ends up testing both the descendant and ancestor tracking.

  I don't love that the test is "unstable". That is, in order to compare this test to another, you really can't modify any of the internal state because it will have a different order of invocations of the deterministic randomness. However, it certainly suffices for comparing branches.

Top commit has no ACKs.

---

Backport of Core [[bitcoin/bitcoin#17292 | PR17292]] and [[bitcoin/bitcoin#17349 | PR17349]] (to unbreak [[bitcoin/bitcoin#17292 | PR17292]])

Rationale: On PR17292, struct 'Available' does not follow the rule-of-three with raises a compiler warning that our CI treats with -Werror (it has a user-defined copy-assignment operator without respective copy-constructor and destructor), so I removed it since no deep-copy behavior was required. Noticing that PR17349 did that plus removed a spurious copy-constructor from src/psbt.h, I decided that was reason enough to squash the two PR's together instead of submitting a modified version of each.

Test Plan:
  ninja check check-functional
  bitcoin-bench -filter=ComplexMemPool

Reviewers: #bitcoin_abc, jasonbcox

Reviewed By: #bitcoin_abc, jasonbcox

Differential Revision: https://reviews.bitcoinabc.org/D7414

b0c774b Add new mempool benchmarks for a complex pool (Jeremy Rubin)

Pull request description:

  This PR is related to bitcoin#17268.

  It adds a mempool stress test which makes a really big complicated tx graph, and then, similar to mempool_eviction test, trims the size.

  The test setup is to make 100 original transactions with Rand(10)+2 outputs each.

  Then, 800 times:

  we create a new transaction with Rand(10) + 1 parents that are randomly sampled from all existing transactions (with unspent outputs). From each such parent, we then select Rand(remaining outputs) +1 50% of the time, or 1 outputs 50% of the time.

  Then, we trim the size to 3/4. Then we trim it to just a single transaction.

  This creates, hopefully, a big bundle of transactions with lots of complex structure, that should really put a strain on the mempool graph algorithms.

  This ends up testing both the descendant and ancestor tracking.

  I don't love that the test is "unstable". That is, in order to compare this test to another, you really can't modify any of the internal state because it will have a different order of invocations of the deterministic randomness. However, it certainly suffices for comparing branches.

Top commit has no ACKs.

Tree-SHA512: cabe96b849b9885878e20eec558915e921d49e6ed1e4b011b22ca191b4c99aa28930a8b963784c9adf78cc8b034a655513f7a0da865e280a1214ae15ebb1d574

…ol benchmark

29e9833 Fixes Bug in Transaction generation in ComplexMempool benchmark (Shorya)

Pull request description:

  This fixes issues with `ComplexMempool` benchmark introduced in [#17292](#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

…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

…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

…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

…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