wallet: use vector instead of list for transactions #25236

This fixes #25229

I tested on Fedora with below steps and could list transactions several times on PR branch while Master branch bitcoind crashed in running listtransactions:

1. Add thousands of transactions in a wallet on regtest with bitcoin-cli generatetoaddress 100000 ADDRESS
2. Run listtransactions command multiple times in Master and PR branch: bitcoin-cli listtransactions "*" 100000 1000
3. Keep an eye on CPU and memory usage with top

Can you explain why this fixes the bug? This may change the memory usage, but I fail to see a memory leak or how this fixes it.

Can you explain why this fixes the bug? This may change the memory usage, but I fail to see a memory leak or how this fixes it.

I was testing based on the things shared in #25229 and trying to improve performance. I am assuming the issue is accidentally fixed with this pull request but need confirmation from reviewers. I did not find memory leak but bitcoind crashes when using listtransactions multiple times.

First thing that I wanted to change in the code was std::list with something that has less performance issues in C++. After reading a few articles found that std::vector can be an easy replacement to improve performance in this case.

In C++ there is only one God, and its name is vector.

https://blog.quasar.ai/using-c-containers-efficiently

std::vector is insanely faster than std::list to find an element std::vector always performs faster than std::list with very small data std::vector is always faster to push elements at the back than std::list std::list handles large elements very well, especially for sorting or inserting in the front

https://dzone.com/articles/c-benchmark-%E2%80%93-stdvector-vs

Cleared vector elements in ListTransactions() because I think its not going out of scope to free memory and is required before running listtransactions again. It was also done in CachedTxGetAmounts() in src/wallet/receive.cpp

It improved performance but did not fix the issue. In the video bitcoind still crashes after running listtransactions 4 times in a wallet with 100k transactions trying to list them all every minute. Closing this pull request as it does not fix the real issue.

https://user-images.githubusercontent.com/94559964/170909843-cf056e9e-f3a1-419c-83be-a241b4fc9ba6.mp4

It's not clear to me that this should be closed. Even if it doesn't fix the referenced issue, is it still a noticeable performance improvement?

It's not clear to me that this should be closed. Even if it doesn't fix the referenced issue, is it still a noticeable performance improvement?

I will reopen after doing a few more tests and see if there is any significant improvement in performance.

Out of curiosity I ran listtransactions with 54,000 transactions and the total time seems to be faster on this PR than master. Might be worth to merge 056547ae5a2ae731ed652d684e16630d5f71e26f, not sure about 6232ca74cbd838531ab623ca1015d6031db1da06 though.

PR

time ./src/bitcoin-cli -regtest -rpcwallet=test -named listtransactions count=100000 &>/dev/null
1.16s user 0.31s system 33% cpu 4.440 total
time ./src/bitcoin-cli -regtest -rpcwallet=test -named listtransactions count=100000 &>/dev/null
1.24s user 0.27s system 33% cpu 4.519 total
time ./src/bitcoin-cli -regtest -rpcwallet=test -named listtransactions count=100000 &>/dev/null
1.41s user 0.28s system 38% cpu 4.414 total

Master

time ./src/bitcoin-cli -regtest -rpcwallet=test -named listtransactions count=100000 &>/dev/null
1.21s user 0.28s system 32% cpu 4.559 total
time ./src/bitcoin-cli -regtest -rpcwallet=test -named listtransactions count=100000 &>/dev/null
1.25s user 0.29s system 33% cpu 4.605 total
time ./src/bitcoin-cli -regtest -rpcwallet=test -named listtransactions count=100000 &>/dev/null
1.28s user 0.28s system 33% cpu 4.625 total