base58: Improve DecodeBase58 performance. #8736

pull wjx wants to merge 2 commits into bitcoin:master from wjx:speedup-decodebase58 changing 1 files +7 −3

wjx commented at 10:10 AM on September 15, 2016: contributor

Improve DecodeBase58 performance the same way as commit 3252208 did for EncodeBase58.

bench_bitcoin result for Base58Decode before and after the patch, each tested three times: Before the patch:

Benchmark,count,min,max,average

Base58Decode,524288,0.000000976440788,0.000002053217031,0.000001960330792 Base58Decode,524288,0.000000979518518,0.000001978729415,0.000001956941560 Base58Decode,524288,0.000000986496161,0.000001988708391,0.000001964757757

After the patch:

Benchmark,count,min,max,average

Base58Decode,786432,0.000000660018486,0.000001336600690,0.000001329504509 Base58Decode,786432,0.000000668867870,0.000001348496880,0.000001338565805 Base58Decode,786432,0.000000656273187,0.000001334869012,0.000001324702074

That's about 32% decrease for the average time.

base58: Improve DecodeBase58 performance.

Improve DecodeBase58 performance the same way as commit 3252208 did
for EncodeBase58.

159ed95f74

MarcoFalke added the label Resource usage on Sep 15, 2016
MarcoFalke added the label Refactoring on Sep 15, 2016
fanquake commented at 3:22 AM on September 16, 2016: member

@wjx Can you provide any numbers as to the performance improvement? Is it inline with what was seen in #7656?
Use prefix operator in for loop of DecodeBase58. e892dc1268

in src/base58.cpp:None in 159ed95f74 outdated

  40 | @@ -39,12 +41,14 @@ bool DecodeBase58(const char* psz, std::vector<unsigned char>& vch)
  41 |              return false;
  42 |          // Apply "b256 = b256 * 58 + ch".
  43 |          int carry = ch - pszBase58;
  44 | -        for (std::vector<unsigned char>::reverse_iterator it = b256.rbegin(); it != b256.rend(); it++) {
  45 | +        int i = 0;
  46 | +        for (std::vector<unsigned char>::reverse_iterator it = b256.rbegin(); (carry != 0 || i < length) && (it != b256.rend()); it++, i++) {

fanquake commented at 3:24 AM on September 16, 2016:

Comments from the original PR suggest you should use ++i here.

wjx commented at 11:44 AM on September 16, 2016:

Updated, and benchmark number attached.

laanwj commented at 4:49 AM on September 22, 2016: member

code review ACK https://github.com/bitcoin/bitcoin/pull/8736/commits/e892dc1268d33bfba01f35b70359b286bb9d6376
jonasschnelli commented at 11:23 AM on October 24, 2016: contributor

Code Review utACK e892dc1268d33bfba01f35b70359b286bb9d6376
sipa commented at 6:17 PM on October 24, 2016: member

utACK e892dc1268d33bfba01f35b70359b286bb9d6376
fanquake commented at 7:45 AM on November 7, 2016: member

Benchmarks

Before

Base58Decode,786432,0.000000720581738,0.000001479576895,0.000001459018677 Base58Decode,786432,0.000000731757609,0.000001487409463,0.000001467602791 Base58Decode,786432,0.000000714662747,0.000001470549250,0.000001451156398 Base58Decode,786432,0.000000723695848,0.000001477301339,0.000001463891143

After

Base58Decode,1048576,0.000000478641596,0.000001010337655,0.000000991023853 Base58Decode,1048576,0.000000484878910,0.000000999572876,0.000000988008424 Base58Decode,1048576,0.000000494663254,0.000001009095286,0.000000993179128 Base58Decode,1048576,0.000000960510079,0.000000998141331,0.000000973840770

in src/base58.cpp:None in e892dc1268

  30 |          zeroes++;
  31 |          psz++;
  32 |      }
  33 |      // Allocate enough space in big-endian base256 representation.
  34 | -    std::vector<unsigned char> b256(strlen(psz) * 733 / 1000 + 1); // log(58) / log(256), rounded up.
  35 | +    int size = strlen(psz) * 733 /1000 + 1; // log(58) / log(256), rounded up.

paveljanik commented at 8:36 AM on November 7, 2016:

SPC before 1000

paveljanik commented at 8:51 AM on November 7, 2016: contributor

Confirming the numbers:

$ pwd; while :; do ./bench_bitcoin | grep -m1 Base58Decode; done
/tmp/bitcoin-master/src/bench
Base58Decode,786432,0.000000705200364,0.000001495651304,0.000001435880222
Base58Decode,786432,0.000000754334906,0.000001533042450,0.000001507242814
Base58Decode,786432,0.000000738342351,0.000001584410711,0.000001496629011
...
$ pwd; while :; do ./bench_bitcoin | grep -m1 Base58Decode; done
/tmp/bitcoin-8736/src/bench
Base58Decode,1310720,0.000000458023351,0.000000963798811,0.000000941479630
Base58Decode,1048576,0.000000513755367,0.000001057205736,0.000000997559710
Base58Decode,1048576,0.000000455460395,0.000001009773769,0.000000967173719
...

paveljanik commented at 8:52 AM on November 7, 2016: contributor

ACK https://github.com/bitcoin/bitcoin/pull/8736/commits/e892dc1268d33bfba01f35b70359b286bb9d6376
laanwj merged this on Nov 7, 2016
laanwj closed this on Nov 7, 2016
laanwj referenced this in commit 5fa7b07565 on Nov 7, 2016
random-zebra referenced this in commit 961e2d2a70 on Jun 27, 2020
MarcoFalke locked this on Sep 8, 2021

Contributors

wjx

Labels

Refactoring Resource usage

base58: Improve DecodeBase58 performance. #8736

Benchmark,count,min,max,average

Benchmark,count,min,max,average

Before

After