aboutsummaryrefslogtreecommitdiff
path: root/src/bench/coin_selection.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Remove WalletLocation classRussell Yanofsky2020-09-031-2/+2
| | | | | | | | | | | This removes a source of complexity and indirection that makes it harder to understand path checking code. Path checks will be simplified in upcoming commits. There is no change in behavior in this commit other than a slightly more descriptive error message in `loadwallet` if the default "" wallet can't be found. (The error message is improved more in upcoming commit "wallet: Remove path checking code from loadwallet RPC".)
* Merge #18011: Replace current benchmarking framework with nanobenchWladimir J. van der Laan2020-07-301-8/+8
|\ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 78c312c983255e15fc274de2368a2ec13ce81cbf Replace current benchmarking framework with nanobench (Martin Ankerl) Pull request description: Replace current benchmarking framework with nanobench This replaces the current benchmarking framework with nanobench [1], an MIT licensed single-header benchmarking library, of which I am the autor. This has in my opinion several advantages, especially on Linux: * fast: Running all benchmarks takes ~6 seconds instead of 4m13s on an Intel i7-8700 CPU @ 3.20GHz. * accurate: I ran e.g. the benchmark for SipHash_32b 10 times and calculate standard deviation / mean = coefficient of variation: * 0.57% CV for old benchmarking framework * 0.20% CV for nanobench So the benchmark results with nanobench seem to vary less than with the old framework. * It automatically determines runtime based on clock precision, no need to specify number of evaluations. * measure instructions, cycles, branches, instructions per cycle, branch misses (only Linux, when performance counters are available) * output in markdown table format. * Warn about unstable environment (frequency scaling, turbo, ...) * For better profiling, it is possible to set the environment variable NANOBENCH_ENDLESS to force endless running of a particular benchmark without the need to recompile. This makes it to e.g. run "perf top" and look at hotspots. Here is an example copy & pasted from the terminal output: | ns/byte | byte/s | err% | ins/byte | cyc/byte | IPC | bra/byte | miss% | total | benchmark |--------------------:|--------------------:|--------:|----------------:|----------------:|-------:|---------------:|--------:|----------:|:---------- | 2.52 | 396,529,415.94 | 0.6% | 25.42 | 8.02 | 3.169 | 0.06 | 0.0% | 0.03 | `bench/crypto_hash.cpp RIPEMD160` | 1.87 | 535,161,444.83 | 0.3% | 21.36 | 5.95 | 3.589 | 0.06 | 0.0% | 0.02 | `bench/crypto_hash.cpp SHA1` | 3.22 | 310,344,174.79 | 1.1% | 36.80 | 10.22 | 3.601 | 0.09 | 0.0% | 0.04 | `bench/crypto_hash.cpp SHA256` | 2.01 | 496,375,796.23 | 0.0% | 18.72 | 6.43 | 2.911 | 0.01 | 1.0% | 0.00 | `bench/crypto_hash.cpp SHA256D64_1024` | 7.23 | 138,263,519.35 | 0.1% | 82.66 | 23.11 | 3.577 | 1.63 | 0.1% | 0.00 | `bench/crypto_hash.cpp SHA256_32b` | 3.04 | 328,780,166.40 | 0.3% | 35.82 | 9.69 | 3.696 | 0.03 | 0.0% | 0.03 | `bench/crypto_hash.cpp SHA512` [1] https://github.com/martinus/nanobench ACKs for top commit: laanwj: ACK 78c312c983255e15fc274de2368a2ec13ce81cbf Tree-SHA512: 9e18770b18b6f95a7d0105a4a5497d31cf4eb5efe6574f4482f6f1b4c88d7e0946b9a4a1e9e8e6ecbf41a3f2d7571240677dcb45af29a6f0584e89b25f32e49e
| * Replace current benchmarking framework with nanobenchMartin Ankerl2020-06-131-8/+8
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This replaces the current benchmarking framework with nanobench [1], an MIT licensed single-header benchmarking library, of which I am the autor. This has in my opinion several advantages, especially on Linux: * fast: Running all benchmarks takes ~6 seconds instead of 4m13s on an Intel i7-8700 CPU @ 3.20GHz. * accurate: I ran e.g. the benchmark for SipHash_32b 10 times and calculate standard deviation / mean = coefficient of variation: * 0.57% CV for old benchmarking framework * 0.20% CV for nanobench So the benchmark results with nanobench seem to vary less than with the old framework. * It automatically determines runtime based on clock precision, no need to specify number of evaluations. * measure instructions, cycles, branches, instructions per cycle, branch misses (only Linux, when performance counters are available) * output in markdown table format. * Warn about unstable environment (frequency scaling, turbo, ...) * For better profiling, it is possible to set the environment variable NANOBENCH_ENDLESS to force endless running of a particular benchmark without the need to recompile. This makes it to e.g. run "perf top" and look at hotspots. Here is an example copy & pasted from the terminal output: | ns/byte | byte/s | err% | ins/byte | cyc/byte | IPC | bra/byte | miss% | total | benchmark |--------------------:|--------------------:|--------:|----------------:|----------------:|-------:|---------------:|--------:|----------:|:---------- | 2.52 | 396,529,415.94 | 0.6% | 25.42 | 8.02 | 3.169 | 0.06 | 0.0% | 0.03 | `bench/crypto_hash.cpp RIPEMD160` | 1.87 | 535,161,444.83 | 0.3% | 21.36 | 5.95 | 3.589 | 0.06 | 0.0% | 0.02 | `bench/crypto_hash.cpp SHA1` | 3.22 | 310,344,174.79 | 1.1% | 36.80 | 10.22 | 3.601 | 0.09 | 0.0% | 0.04 | `bench/crypto_hash.cpp SHA256` | 2.01 | 496,375,796.23 | 0.0% | 18.72 | 6.43 | 2.911 | 0.01 | 1.0% | 0.00 | `bench/crypto_hash.cpp SHA256D64_1024` | 7.23 | 138,263,519.35 | 0.1% | 82.66 | 23.11 | 3.577 | 1.63 | 0.1% | 0.00 | `bench/crypto_hash.cpp SHA256_32b` | 3.04 | 328,780,166.40 | 0.3% | 35.82 | 9.69 | 3.696 | 0.03 | 0.0% | 0.03 | `bench/crypto_hash.cpp SHA512` [1] https://github.com/martinus/nanobench * Adds support for asymptotes This adds support to calculate asymptotic complexity of a benchmark. This is similar to #17375, but currently only one asymptote is supported, and I have added support in the benchmark `ComplexMemPool` as an example. Usage is e.g. like this: ``` ./bench_bitcoin -filter=ComplexMemPool -asymptote=25,50,100,200,400,600,800 ``` This runs the benchmark `ComplexMemPool` several times but with different complexityN settings. The benchmark can extract that number and use it accordingly. Here, it's used for `childTxs`. The output is this: | complexityN | ns/op | op/s | err% | ins/op | cyc/op | IPC | total | benchmark |------------:|--------------------:|--------------------:|--------:|----------------:|----------------:|-------:|----------:|:---------- | 25 | 1,064,241.00 | 939.64 | 1.4% | 3,960,279.00 | 2,829,708.00 | 1.400 | 0.01 | `ComplexMemPool` | 50 | 1,579,530.00 | 633.10 | 1.0% | 6,231,810.00 | 4,412,674.00 | 1.412 | 0.02 | `ComplexMemPool` | 100 | 4,022,774.00 | 248.58 | 0.6% | 16,544,406.00 | 11,889,535.00 | 1.392 | 0.04 | `ComplexMemPool` | 200 | 15,390,986.00 | 64.97 | 0.2% | 63,904,254.00 | 47,731,705.00 | 1.339 | 0.17 | `ComplexMemPool` | 400 | 69,394,711.00 | 14.41 | 0.1% | 272,602,461.00 | 219,014,691.00 | 1.245 | 0.76 | `ComplexMemPool` | 600 | 168,977,165.00 | 5.92 | 0.1% | 639,108,082.00 | 535,316,887.00 | 1.194 | 1.86 | `ComplexMemPool` | 800 | 310,109,077.00 | 3.22 | 0.1% |1,149,134,246.00 | 984,620,812.00 | 1.167 | 3.41 | `ComplexMemPool` | coefficient | err% | complexity |--------------:|-------:|------------ | 4.78486e-07 | 4.5% | O(n^2) | 6.38557e-10 | 21.7% | O(n^3) | 3.42338e-05 | 38.0% | O(n log n) | 0.000313914 | 46.9% | O(n) | 0.0129823 | 114.4% | O(log n) | 0.0815055 | 133.8% | O(1) The best fitting curve is O(n^2), so the algorithm seems to scale quadratic with `childTxs` in the range 25 to 800.
* | scripted-diff: Replace WalletDatabase::Create* with CreateWalletDatabaseAndrew Chow2020-06-171-2/+2
|/ | | | | | | | -BEGIN VERIFY SCRIPT- sed -i -e 's/WalletDatabase::Create(/CreateWalletDatabase(/g' `git grep -l "WalletDatabase::Create("` sed -i -e 's/WalletDatabase::CreateDummy(/CreateDummyWalletDatabase(/g' `git grep -l "WalletDatabase::CreateDummy("` sed -i -e 's/WalletDatabase::CreateMock(/CreateMockWalletDatabase(/g' `git grep -l "WalletDatabase::CreateMock("` -END VERIFY SCRIPT-
* Refactor: Allow LegacyScriptPubKeyMan to be nullAndrew Chow2020-01-231-2/+4
| | | | | | In CWallet::LoadWallet, use this to detect and empty wallet with no keys This commit does not change behavior.
* scripted-diff: Bump copyright of files changed in 2019MarcoFalke2019-12-301-1/+1
| | | | | | -BEGIN VERIFY SCRIPT- ./contrib/devtools/copyright_header.py update ./ -END VERIFY SCRIPT-
* Pass NodeContext, ConnMan, BanMan references more placesRussell Yanofsky2019-10-281-2/+5
| | | | So g_connman and g_banman globals can be removed next commit.
* bitcoin-wallet tool: Drop MakeChain callsRussell Yanofsky2019-04-101-2/+2
| | | | | Pass null Chain interface pointer to CWallet. This is needed to drop libbitcoin_server dependency and avoid linking node code.
* bench: Destroy wallet txs instead of leaking their memoryMarcoFalke2018-11-271-14/+15
|
* Pass chain and client variables where neededRussell Yanofsky2018-11-061-2/+5
| | | | | | | | | This commit does not change behavior. All it does is pass new function parameters. It is easiest to review this change with: git log -p -n1 -U0 --word-diff-regex=.
* wallet: Refactor to use WalletLocationJoão Barbosa2018-10-251-2/+2
|
* tests: Use MakeUnique to construct objects owned by unique_ptrspracticalswift2018-09-211-1/+1
|
* Merge #13780: 0.17: Pre-branch maintenanceWladimir J. van der Laan2018-08-081-1/+1
|\ | | | | | | | | | | | | | | | | | | | | | | | | | | 3fc20632a3ad30809356a58d2cf0ea4a4ad4cec3 qt: Set BLOCK_CHAIN_SIZE = 220 (DrahtBot) 2b6a2f4a28792f2fe9dc1be843b1ff1ecae35e8a Regenerate manpages (DrahtBot) eb7daf4d600eeb631427c018a984a77a34aca66e Update copyright headers to 2018 (DrahtBot) Pull request description: Some trivial maintenance to avoid having to do it again after the 0.17 branch off. (The scripts to do this are in `./contrib/`) Tree-SHA512: 16b2af45e0351b1c691c5311d48025dc6828079e98c2aa2e600dc5910ee8aa01858ca6c356538150dc46fe14c8819ed8ec8e4ec9a0f682b9950dd41bc50518fa
| * Update copyright headers to 2018DrahtBot2018-07-271-1/+1
| |
* | bench: Make CoinSelection output groups pass eligibility filterAndrew Chow2018-07-311-1/+1
|/ | | | | Set the depth of the output groups used in the CoinSelection benchmark to be 6 in order to pass the eligibility filter for the benchmark.
* wallet: Switch to using output groups instead of coins in coin selectionKarl-Johan Alm2018-07-241-10/+14
|
* bench: Simplify CoinSelectionJoão Barbosa2018-06-281-16/+10
|
* scripted-diff: Rename wallet database classesRussell Yanofsky2018-04-071-1/+1
| | | | | | | | | | | | | | | | | | | | | -BEGIN VERIFY SCRIPT- sed -i 's/\<CWalletDBWrapper\>/BerkeleyDatabase/g' src/wallet/db.h src/wallet/db.cpp sed -i '/statuses/i/** Backend-agnostic database type. */\nusing WalletDatabase = BerkeleyDatabase\;\n' src/wallet/walletdb.h ren() { git grep -l "\<$1\>" 'src/*.cpp' 'src/*.h' ':(exclude)*dbwrapper*' test | xargs sed -i "s:\<$1\>:$2:g"; } ren CDBEnv BerkeleyEnvironment ren CDB BerkeleyBatch ren CWalletDBWrapper WalletDatabase ren CWalletDB WalletBatch ren dbw database ren m_dbw m_database ren walletdb batch ren pwalletdb batch ren pwalletdbIn batch_in ren wallet/batch.h wallet/walletdb.h ren pwalletdbEncryption encrypted_batch -END VERIFY SCRIPT-
* Benchmark BnB in the worst case where it exhaustsAndrew Chow2018-03-131-0/+44
|
* Have SelectCoinsMinConf and SelectCoins use BnB or Knapsack and use itAndrew Chow2018-03-131-1/+4
| | | | | | | | | | | | Allows SelectCoinsMinConf and SelectCoins be able to switch between using BnB or Knapsack for choosing coins. Has SelectCoinsMinConf do the preprocessing necessary to support either BnB or Knapsack. This includes calculating the filtering the effective values for each input. Uses BnB in CreateTransaction to find an exact match for the output. If BnB fails, it will fallback to the Knapsack solver.
* Use a struct for output eligibilityAndrew Chow2018-03-131-1/+2
| | | | | Instead of specifying 3 parameters, use a struct for those parameters in order to reduce the number of arguments to SelectCoinsMinConf.
* Allow wallet files in multiple directoriesRussell Yanofsky2018-03-031-1/+1
| | | | | | | | | Remove requirement that two wallet files can only be opened at the same time if they are contained in the same directory. This change mostly consists of updates to function signatures (updating functions to take fs::path arguments, instead of combinations of strings, fs::path, and CDBEnv / CWalletDBWrapper arguments).
* test: Plug memory leaks and stack-use-after-scopeMarcoFalke2018-02-221-5/+6
|
* Increment MIT Licence copyright header year on files modified in 2017Akira Takizawa2018-01-031-1/+1
|
* Improved microbenchmarking with multiple features.Martin Ankerl2017-12-231-1/+1
| | | | | | | | | | | | | | | * inline performance critical code * Average runtime is specified and used to calculate iterations. * Console: show median of multiple runs * plot: show box plot * filter benchmarks * specify scaling factor * ignore src/test and src/bench in command line check script * number of iterations instead of time * Replaced runtime in BENCHMARK makro number of iterations. * Added -? to bench_bitcoin * Benchmark plotly.js URL, width, height can be customized * Fixed incorrect precision warning
* scripted-diff: Replace #include "" with #include <> (ryanofsky)MeshCollider2017-11-161-2/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | -BEGIN VERIFY SCRIPT- for f in \ src/*.cpp \ src/*.h \ src/bench/*.cpp \ src/bench/*.h \ src/compat/*.cpp \ src/compat/*.h \ src/consensus/*.cpp \ src/consensus/*.h \ src/crypto/*.cpp \ src/crypto/*.h \ src/crypto/ctaes/*.h \ src/policy/*.cpp \ src/policy/*.h \ src/primitives/*.cpp \ src/primitives/*.h \ src/qt/*.cpp \ src/qt/*.h \ src/qt/test/*.cpp \ src/qt/test/*.h \ src/rpc/*.cpp \ src/rpc/*.h \ src/script/*.cpp \ src/script/*.h \ src/support/*.cpp \ src/support/*.h \ src/support/allocators/*.h \ src/test/*.cpp \ src/test/*.h \ src/wallet/*.cpp \ src/wallet/*.h \ src/wallet/test/*.cpp \ src/wallet/test/*.h \ src/zmq/*.cpp \ src/zmq/*.h do base=${f%/*}/ relbase=${base#src/} sed -i "s:#include \"\(.*\)\"\(.*\):if test -e \$base'\\1'; then echo \"#include <\"\$relbase\"\\1>\\2\"; else echo \"#include <\\1>\\2\"; fi:e" $f done -END VERIFY SCRIPT-
* scripted-diff: Remove #include <boost/foreach.hpp>Jorge Timón2017-06-221-1/+0
| | | | | | -BEGIN VERIFY SCRIPT- sed -i ':a;N;$!ba;s/#include <boost\/foreach.hpp>\n//' ./src/*.h ./src/*.cpp ./src/*/*.h ./src/*/*.cpp ./src/*/*/*.h ./src/*/*/*.cpp -END VERIFY SCRIPT-
* scripted-diff: Fully remove BOOST_FOREACHJorge Timón2017-06-051-1/+1
| | | | | | -BEGIN VERIFY SCRIPT- sed -i 's/BOOST_FOREACH *(\(.*\),/for (\1 :/' ./src/*.h ./src/*.cpp ./src/*/*.h ./src/*/*.cpp ./src/*/*/*.h ./src/*/*/*.cpp ; -END VERIFY SCRIPT-
* [Wallet] Rename std::pair<const CWalletTx*, unsigned int> to CInputCoinNicolasDorier2017-04-081-1/+1
|
* Add COutput::fSafe member for safe handling of unconfirmed outputsRussell Yanofsky2017-03-101-1/+1
| | | | | This exposes a value computed in CWallet::AvailableCoins so it can used for other things, like inclusion in listunspent output.
* Merge #9281: Refactor: Remove using namespace <xxx> from bench/ & test/ sourcesMarcoFalke2017-01-051-5/+3
|\ | | | | | | 73f4119 Refactoring: Removed using namespace <xxx> from bench/ and test/ source files. (Karl-Johan Alm)
| * Refactoring: Removed using namespace <xxx> from bench/ and test/ source files.Karl-Johan Alm2017-01-021-5/+3
| |
* | Increment MIT Licence copyright header year on files modified in 2016isle29832016-12-311-1/+1
|/ | | | | | Edited via: $ contrib/devtools/copyright_header.py update .
* Merge #9262: Prefer coins that have fewer ancestors, sanity check txn before ↵Wladimir J. van der Laan2016-12-201-1/+1
|\ | | | | | | | | | | | | | | | | ATMP cee1612 reduce number of lookups in TransactionWithinChainLimit (Gregory Sanders) af9bedb Test for fix of txn chaining in wallet (Gregory Sanders) 5882c09 CreateTransaction: Don't return success with too-many-ancestor txn (Gregory Sanders) 0b2294a SelectCoinsMinConf: Prefer coins with fewer ancestors (Gregory Sanders)
| * SelectCoinsMinConf: Prefer coins with fewer ancestorsGregory Sanders2016-12-131-1/+1
| |
* | Make CWalletTx store a CTransactionRef instead of inheritingPieter Wuille2016-12-021-1/+1
|/
* Add microbenchmarks to profile more code paths.Russell Yanofsky2016-10-181-0/+62
The new benchmarks exercise script validation, CCoinsDBView caching, mempool eviction, and wallet coin selection code. All of the benchmarks added here are extremely simple and don't necessarily mirror common real world conditions or interesting performance edge cases. Details about how specific benchmarks can be improved are noted in comments. Github-Issue: #7883
generated by cgit v1.2.3 (git 2.25.1) at 2026-03-12 17:39:38 +0000