diff options
author | Andrew Chow <achow101-github@achow101.com> | 2022-03-21 17:38:51 -0400 |
---|---|---|
committer | Andrew Chow <achow101-github@achow101.com> | 2022-03-21 17:44:54 -0400 |
commit | e66630cc87c017f40ec29f6c1edf2ed5a286e49d (patch) | |
tree | 965ee8670d4ae3a9498b8f2dcb1c71a09b8d014e /src/bitcoin-cli.cpp | |
parent | 91d12344b1e51809c1ef6b630b631a6da00267c3 (diff) | |
parent | 9d2005285c77f6c4148bccfa0b8b9135abfa021c (diff) | |
download | bitcoin-e66630cc87c017f40ec29f6c1edf2ed5a286e49d.tar.xz |
Merge bitcoin/bitcoin#13226: Optimize SelectCoinsBnB by tracking the selection by index rather than by position
9d2005285c77f6c4148bccfa0b8b9135abfa021c doc: Revise comments and whitespace to clarify (Ben Woosley)
def43a4d888b4a21c082404d1b25707c481d7625 refactor: Rename i to curr_try in SelectCoinsBnB (Ben Woosley)
1dd092367789749527777ac2b256e639f5706584 refactor: Track BnB selection by index (Ben Woosley)
Pull request description:
This is prompted by #13167 and presented as a friendly alternative to it.
IMO you can improve code readability and performance by about 20% by tracking the selected utxos by index, rather than by position. This reduces the storage access complexity from roughly O(utxo_size) to O(selection_size).
On my machine (median of 5 trials):
```
BnBExhaustion, 5, 650, 2.2564, 0.000672999, 0.000711565, 0.000693112 - master
BnBExhaustion, 5, 650, 1.76232, 0.000528563, 0.000568806, 0.000539147 - this PR
```
ACKs for top commit:
achow101:
reACK 9d2005285c77f6c4148bccfa0b8b9135abfa021c
glozow:
code review ACK 9d2005285c77f6c4148bccfa0b8b9135abfa021c
Xekyo:
reACK 9d2005285c77f6c4148bccfa0b8b9135abfa021c
Tree-SHA512: 453ea11ad58c48928dc76956e3e98916f6924e95510eb02fe89a899ff102fe9cc08a04d557f381ad0218a210275e5383101d971c1ffad38b06b1c57d81144315
Diffstat (limited to 'src/bitcoin-cli.cpp')
0 files changed, 0 insertions, 0 deletions