tcoinchooser: improve performance significantly - electrum - Electrum Bitcoin wallet
HTML git clone https://git.parazyd.org/electrum
DIR Log
DIR Files
DIR Refs
DIR Submodules
---
DIR commit d56917f4b15541164047ecb61e411fc902b81515
DIR parent 15dda65c5282c133558584cff3bc397ad3763905
HTML Author: SomberNight <somber.night@protonmail.com>
Date: Thu, 2 May 2019 03:07:34 +0200
coinchooser: improve performance significantly
existing code was n^2 in number of UTXOs
tthis is now mostly linear
(linear if shortcut is hit; otherwise in rare cases still quadratic)
ttested using wallet with 800 UTXOs, most of which were needed to make payment
coinchooser.make_tx() went from 18 sec to 0.8 sec
Diffstat:
M electrum/coinchooser.py | 41 ++++++++++++++++++++++---------
1 file changed, 29 insertions(+), 12 deletions(-)
---
DIR diff --git a/electrum/coinchooser.py b/electrum/coinchooser.py
t@@ -80,12 +80,17 @@ class Bucket(NamedTuple):
def strip_unneeded(bkts, sufficient_funds):
'''Remove buckets that are unnecessary in achieving the spend amount'''
- bkts = sorted(bkts, key = lambda bkt: bkt.value)
+ if sufficient_funds([], bucket_value_sum=0):
+ # none of the buckets are needed
+ return []
+ bkts = sorted(bkts, key=lambda bkt: bkt.value, reverse=True)
+ bucket_value_sum = 0
for i in range(len(bkts)):
- if not sufficient_funds(bkts[i + 1:]):
- return bkts[i:]
- # none of the buckets are needed
- return []
+ bucket_value_sum += (bkts[i]).value
+ if sufficient_funds(bkts[:i+1], bucket_value_sum=bucket_value_sum):
+ return bkts[:i+1]
+ raise Exception("keeping all buckets is still not enough")
+
class CoinChooserBase(PrintError):
t@@ -230,10 +235,15 @@ class CoinChooserBase(PrintError):
return total_weight
- def sufficient_funds(buckets):
+ def sufficient_funds(buckets, *, bucket_value_sum):
'''Given a list of buckets, return True if it has enough
value to pay for the transaction'''
- total_input = input_value + sum(bucket.value for bucket in buckets)
+ # assert bucket_value_sum == sum(bucket.value for bucket in buckets) # expensive!
+ total_input = input_value + bucket_value_sum
+ if total_input < spent_amount: # shortcut for performance
+ return False
+ # note re performance: so far this was constant time
+ # what follows is linear in len(buckets)
total_weight = get_tx_weight(buckets)
return total_input >= spent_amount + fee_estimator_w(total_weight)
t@@ -278,7 +288,7 @@ class CoinChooserRandom(CoinChooserBase):
# Add all singletons
for n, bucket in enumerate(buckets):
- if sufficient_funds([bucket]):
+ if sufficient_funds([bucket], bucket_value_sum=bucket.value):
candidates.add((n, ))
# And now some random ones
t@@ -289,9 +299,12 @@ class CoinChooserRandom(CoinChooserBase):
# incrementally combine buckets until sufficient
self.p.shuffle(permutation)
bkts = []
+ bucket_value_sum = 0
for count, index in enumerate(permutation):
- bkts.append(buckets[index])
- if sufficient_funds(bkts):
+ bucket = buckets[index]
+ bkts.append(bucket)
+ bucket_value_sum += bucket.value
+ if sufficient_funds(bkts, bucket_value_sum=bucket_value_sum):
candidates.add(tuple(sorted(permutation[:count + 1])))
break
else:
t@@ -320,16 +333,20 @@ class CoinChooserRandom(CoinChooserBase):
bucket_sets = [conf_buckets, unconf_buckets, other_buckets]
already_selected_buckets = []
+ already_selected_buckets_value_sum = 0
for bkts_choose_from in bucket_sets:
try:
- def sfunds(bkts):
- return sufficient_funds(already_selected_buckets + bkts)
+ def sfunds(bkts, *, bucket_value_sum):
+ bucket_value_sum += already_selected_buckets_value_sum
+ return sufficient_funds(already_selected_buckets + bkts,
+ bucket_value_sum=bucket_value_sum)
candidates = self.bucket_candidates_any(bkts_choose_from, sfunds)
break
except NotEnoughFunds:
already_selected_buckets += bkts_choose_from
+ already_selected_buckets_value_sum += sum(bucket.value for bucket in bkts_choose_from)
else:
raise NotEnoughFunds()