From 7d77eb1a5b980a7d56acbf0b3861434c5e195c54 Mon Sep 17 00:00:00 2001 From: Andrew Chow Date: Fri, 9 Mar 2018 23:11:20 -0500 Subject: Use a struct for output eligibility Instead of specifying 3 parameters, use a struct for those parameters in order to reduce the number of arguments to SelectCoinsMinConf. --- src/bench/coin_selection.cpp | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) (limited to 'src/bench/coin_selection.cpp') diff --git a/src/bench/coin_selection.cpp b/src/bench/coin_selection.cpp index 98965840c7..55ff7b61f1 100644 --- a/src/bench/coin_selection.cpp +++ b/src/bench/coin_selection.cpp @@ -44,7 +44,8 @@ static void CoinSelection(benchmark::State& state) std::set setCoinsRet; CAmount nValueRet; - bool success = wallet.SelectCoinsMinConf(1003 * COIN, 1, 6, 0, vCoins, setCoinsRet, nValueRet); + CoinEligibilityFilter filter_standard(1, 6, 0); + bool success = wallet.SelectCoinsMinConf(1003 * COIN, filter_standard, vCoins, setCoinsRet, nValueRet); assert(success); assert(nValueRet == 1003 * COIN); assert(setCoinsRet.size() == 2); -- cgit v1.2.3 From 6a34ff5335786615771ca423134a484b04831c4e Mon Sep 17 00:00:00 2001 From: Andrew Chow Date: Mon, 5 Mar 2018 16:42:49 -0500 Subject: Have SelectCoinsMinConf and SelectCoins use BnB or Knapsack and use it 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. --- src/bench/coin_selection.cpp | 5 ++++- 1 file changed, 4 insertions(+), 1 deletion(-) (limited to 'src/bench/coin_selection.cpp') diff --git a/src/bench/coin_selection.cpp b/src/bench/coin_selection.cpp index 55ff7b61f1..605d9e3e66 100644 --- a/src/bench/coin_selection.cpp +++ b/src/bench/coin_selection.cpp @@ -44,8 +44,11 @@ static void CoinSelection(benchmark::State& state) std::set setCoinsRet; CAmount nValueRet; + bool bnb_used; CoinEligibilityFilter filter_standard(1, 6, 0); - bool success = wallet.SelectCoinsMinConf(1003 * COIN, filter_standard, vCoins, setCoinsRet, nValueRet); + CoinSelectionParams coin_selection_params(false, 34, 148, CFeeRate(0), 0); + bool success = wallet.SelectCoinsMinConf(1003 * COIN, filter_standard, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used) + || wallet.SelectCoinsMinConf(1003 * COIN, filter_standard, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used); assert(success); assert(nValueRet == 1003 * COIN); assert(setCoinsRet.size() == 2); -- cgit v1.2.3 From 76d2f068a4cbd2bfe50c166fe0babfc5f17acaf4 Mon Sep 17 00:00:00 2001 From: Andrew Chow Date: Tue, 6 Mar 2018 14:24:15 -0500 Subject: Benchmark BnB in the worst case where it exhausts --- src/bench/coin_selection.cpp | 44 ++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 44 insertions(+) (limited to 'src/bench/coin_selection.cpp') diff --git a/src/bench/coin_selection.cpp b/src/bench/coin_selection.cpp index 605d9e3e66..4b2a0e72fe 100644 --- a/src/bench/coin_selection.cpp +++ b/src/bench/coin_selection.cpp @@ -4,6 +4,7 @@ #include #include +#include #include @@ -61,4 +62,47 @@ static void CoinSelection(benchmark::State& state) } } +typedef std::set CoinSet; + +// Copied from src/wallet/test/coinselector_tests.cpp +static void add_coin(const CAmount& nValue, int nInput, std::vector& set) +{ + CMutableTransaction tx; + tx.vout.resize(nInput + 1); + tx.vout[nInput].nValue = nValue; + set.emplace_back(MakeTransactionRef(tx), nInput); +} +// Copied from src/wallet/test/coinselector_tests.cpp +static CAmount make_hard_case(int utxos, std::vector& utxo_pool) +{ + utxo_pool.clear(); + CAmount target = 0; + for (int i = 0; i < utxos; ++i) { + target += (CAmount)1 << (utxos+i); + add_coin((CAmount)1 << (utxos+i), 2*i, utxo_pool); + add_coin(((CAmount)1 << (utxos+i)) + ((CAmount)1 << (utxos-1-i)), 2*i + 1, utxo_pool); + } + return target; +} + +static void BnBExhaustion(benchmark::State& state) +{ + // Setup + std::vector utxo_pool; + CoinSet selection; + CAmount value_ret = 0; + CAmount not_input_fees = 0; + + while (state.KeepRunning()) { + // Benchmark + CAmount target = make_hard_case(17, utxo_pool); + SelectCoinsBnB(utxo_pool, target, 0, selection, value_ret, not_input_fees); // Should exhaust + + // Cleanup + utxo_pool.clear(); + selection.clear(); + } +} + BENCHMARK(CoinSelection, 650); +BENCHMARK(BnBExhaustion, 650); -- cgit v1.2.3