optimization: Speed up Base58 encoding/decoding by 400%/200% via preliminary byte packing

l0rinc commented at 12:52 pm on February 24, 2024: contributor

To mitigate the quadratic complexity inherent in the sequential byte division of the Base58 encoding process, this update aggregates characters into groups of 7 and 9, fitting them into 64-bit long integers. This refinement utilizes the inherent efficiency of native division and modulo operations on 64-bit architectures, significantly optimizing computational overhead. The benchmarks indicate a ~4.4x speedup for Base58Encode:

make && ./src/bench/bench_bitcoin –filter=Base58Encode –min-time=1000

before:

ns/byte	byte/s	err%	total	benchmark
61.00	16,393,083.32	0.2%	1.07	`Base58Encode`

after:

ns/byte	byte/s	err%	total	benchmark
13.79	72,502,616.20	0.1%	1.10	`Base58Encode`

The same was applied to decoding, resulting in a ~2x speedup:

make && ./src/bench/bench_bitcoin –filter=Base58Decode –min-time=1000

before:

ns/byte	byte/s	err%	total	benchmark
17.41	57,429,723.99	0.1%	1.10	`Base58Decode`

after:

ns/byte	byte/s	err%	total	benchmark
8.80	113,590,754.53	0.1%	1.11	`Base58Decode`

This also speed up listunspent by >50%.

See #29473 (comment) for additional benchmarks and #30035 for additional tests. I’ve also tested with with the following temp test (comparing the exact previous impl with the new one for random inputs: https://gist.github.com/paplorinc/96d8e355f6fef10ac79f62d89a6d9f19#file-base58_tests-cpp-L211-L249)

DrahtBot commented at 12:52 pm on February 24, 2024: contributor

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Code Coverage & Benchmarks

For details see: https://corecheck.dev/bitcoin/bitcoin/pulls/29473.

Reviews

See the guideline for information on the review process. A summary of reviews will appear here.

Conflicts

No conflicts as of last run.

l0rinc renamed this:
~~WIP optimization: Unify size estimations in Base58 encoding/decoding~~
WIP optimization: Enhance Base58 conversion through preliminary Base56 conversion
on Feb 24, 2024

l0rinc renamed this:
~~WIP optimization: Enhance Base58 conversion through preliminary Base56 conversion~~
WIP optimization: Enhance Base58 conversion through intermediary Base56 conversion
on Feb 24, 2024

in src/base58.cpp:93 in afbc980c36 outdated

89@@ -84,44 +90,45 @@ static const int8_t mapBase58[256] = {
90     return true;
91 }
92 
93+auto ConvertToLongArray(const Span<const unsigned char>& input, size_t leadingZeros, size_t GROUP_SIZE) -> std::vector<int64_t> {

l0rinc commented at 6:00 pm on February 24, 2024:

convert to base56 quickly before converting to base58 to minimize the inner quadratic loop

Empact commented at 6:26 pm on February 24, 2024:

Looks like you are unintentionally aliasing GROUP_SIZE as both a constant and this argument.

l0rinc commented at 8:25 pm on February 24, 2024:

Hah, indeed, last minute refactoring, thanks!

l0rinc renamed this:
~~WIP optimization: Enhance Base58 conversion through intermediary Base56 conversion~~
optimization: Enhance Base58 conversion through intermediary Base56 conversion by 300%
on Feb 24, 2024

l0rinc renamed this:
~~optimization: Enhance Base58 conversion through intermediary Base56 conversion by 300%~~
optimization: Speed up Base58 conversion through intermediary Base56 conversion by 300%
on Feb 24, 2024

l0rinc marked this as ready for review on Feb 24, 2024

l0rinc force-pushed on Feb 24, 2024

DrahtBot added the label CI failed on Feb 24, 2024

DrahtBot commented at 6:12 pm on February 24, 2024: contributor

🚧 At least one of the CI tasks failed. Make sure to run all tests locally, according to the documentation.

Possibly this is due to a silent merge conflict (the changes in this pull request being incompatible with the current code in the target branch). If so, make sure to rebase on the latest commit of the target branch.

Leave a comment here, if you need help tracking down a confusing failure.

Debug: https://github.com/bitcoin/bitcoin/runs/21941361780

l0rinc force-pushed on Feb 24, 2024

in src/base58.cpp:141 in e168e6215d outdated

137+    std::string result;
138+    result.reserve(leadingZeros + size);
139+    result.assign(leadingZeros, '1');
140+
141+    auto inputAsLongs = ConvertToLongs(input, leadingZeros);
142+    for (auto i{0U}; i < inputAsLongs.size();) {

optout21 commented at 5:40 am on February 25, 2024:

This construct with the two nested loops is not evident. Maybe some comment would be useful. The inner loop does not depend on the value of i. Is it repeated for as long as all inputAsLongs elements are reduced to 0?

l0rinc commented at 6:52 am on February 25, 2024:

Fantastic comment, the internal loop should skip the leading zeros, indeed.

l0rinc marked this as a draft on Feb 25, 2024

l0rinc force-pushed on Feb 25, 2024

DrahtBot removed the label CI failed on Feb 25, 2024

l0rinc force-pushed on Feb 25, 2024

DrahtBot added the label CI failed on Feb 25, 2024

DrahtBot commented at 3:24 pm on February 25, 2024: contributor

🚧 At least one of the CI tasks failed. Make sure to run all tests locally, according to the documentation.

Possibly this is due to a silent merge conflict (the changes in this pull request being incompatible with the current code in the target branch). If so, make sure to rebase on the latest commit of the target branch.

Leave a comment here, if you need help tracking down a confusing failure.

Debug: https://github.com/bitcoin/bitcoin/runs/21955441135

DrahtBot removed the label CI failed on Feb 25, 2024

l0rinc requested review from optout21 on Feb 25, 2024

l0rinc requested review from Empact on Feb 25, 2024

l0rinc marked this as ready for review on Feb 25, 2024

l0rinc force-pushed on Feb 26, 2024

l0rinc renamed this:
~~optimization: Speed up Base58 conversion through intermediary Base56 conversion by 300%~~
optimization: Speed up Base58 conversion through intermediary Base56 conversion by 400%
on Feb 26, 2024

l0rinc force-pushed on Feb 26, 2024

Empact commented at 4:59 am on February 27, 2024: contributor

I have some questions about this change, but to start I would encourage you to make the change a minimal one. I.e. avoid strictly unnecessary changes, such as those in the last commit. Merge the variable name changes with the commit they are introduced, and don’t change other lines in the file for conventions.

The goal, again, is to ease review and avoid cause for controversy. Leaving the code unchanged is a good default if not significantly justified.

l0rinc renamed this:
~~optimization: Speed up Base58 conversion through intermediary Base56 conversion by 400%~~
optimization: Speed up Base58 encoding with 64-bit packing by 400%
on Feb 27, 2024

l0rinc force-pushed on Feb 27, 2024

fanquake commented at 10:45 am on February 27, 2024: member

Pleas stop leaving endless self review comments on PRs. It’s not only unecessary, but everytime you comment here, it sends 4000 people an email. Some commentary / responding to review comment is obviously fine, but what you are currently doing is just turning the thread into a spammy/confusing mess, and I’d assume, making things potentially harder for reviewers.

l0rinc renamed this:
~~optimization: Speed up Base58 encoding with 64-bit packing by 400%~~
optimization: Speed up Base58 encoding by 400% by 64-bit preliminary byte packing
on Feb 27, 2024

DrahtBot renamed this:
~~optimization: Speed up Base58 encoding by 400% by 64-bit preliminary byte packing~~
optimization: Speed up Base58 encoding by 400% by 64-bit preliminary byte packing
on Feb 27, 2024

Empact commented at 5:25 pm on February 27, 2024: contributor

@paplorinc agree with @fanquake, a better place to articulate your motivations and reasoning is in the commit messages, that way they’ll be retained for future reference via git blame, etc.

l0rinc renamed this:
~~optimization: Speed up Base58 encoding by 400% by 64-bit preliminary byte packing~~
optimization: Speed up Base58 encoding/decoding by 400%/200% via preliminary byte packing
on Mar 6, 2024

l0rinc force-pushed on Mar 6, 2024

DrahtBot added the label CI failed on Mar 6, 2024

DrahtBot commented at 5:52 pm on March 6, 2024: contributor

🚧 At least one of the CI tasks failed. Make sure to run all tests locally, according to the documentation.

Possibly this is due to a silent merge conflict (the changes in this pull request being incompatible with the current code in the target branch). If so, make sure to rebase on the latest commit of the target branch.

Leave a comment here, if you need help tracking down a confusing failure.

Debug: https://github.com/bitcoin/bitcoin/runs/22353467861

l0rinc force-pushed on Mar 6, 2024

l0rinc marked this as a draft on Mar 7, 2024

l0rinc force-pushed on Mar 7, 2024

l0rinc marked this as ready for review on Mar 7, 2024

DrahtBot removed the label CI failed on Mar 7, 2024

l0rinc force-pushed on Mar 7, 2024

l0rinc renamed this:
~~optimization: Speed up Base58 encoding/decoding by 400%/200% via preliminary byte packing~~
refactor: Speed up Base58 encoding/decoding by 400%/200% via preliminary byte packing
on Mar 8, 2024

DrahtBot added the label Refactoring on Mar 8, 2024

l0rinc force-pushed on Mar 8, 2024

l0rinc force-pushed on Mar 9, 2024

in src/test/data/base58_encode_decode.json:16 in ffb81c978a outdated

10@@ -11,6 +11,13 @@
11 ["ecac89cad93923c02321", "EJDM8drfXA6uyA"],
12 ["10c8511e", "Rt5zm"],
13 ["00000000000000000000", "1111111111"],
14+["00000000000000000000000000000000000000000000000000000000000000000000000000000000", "1111111111111111111111111111111111111111"],
15+["00000000000000000000000000000000000000000000000000000000000000000000000000000001", "1111111111111111111111111111111111111112"],
16+["0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000ec39d04c37e71e5d591881f6", "111111111111111111111111111111111111111111111111111111111111111111111111111111111111115TYzLYH1udmLdzCLM"],

maflcko commented at 12:11 pm on March 15, 2024:

Seems fine to add tests, but I don’t think this is used in a critical path, to warrant a speedup?

l0rinc commented at 12:16 pm on March 15, 2024:

I’ve added the random test cases that failed during development to make sure they’re covered deterministically. Also added ones which are testing the boundaries of powers of 58, since those cases happen less frequently in the randomized tests.

maflcko commented at 12:20 pm on March 15, 2024:

Yes, I meant you can open a new pull request with the added tests, if you want.

l0rinc force-pushed on May 7, 2024

l0rinc force-pushed on May 8, 2024

l0rinc marked this as a draft on May 8, 2024

l0rinc marked this as ready for review on May 8, 2024

l0rinc force-pushed on May 11, 2024

l0rinc force-pushed on May 29, 2024

DrahtBot added the label Needs rebase on Jun 12, 2024

l0rinc force-pushed on Jun 13, 2024

DrahtBot removed the label Needs rebase on Jun 13, 2024

achow101 referenced this in commit fcc3b653dc on Jun 13, 2024

l0rinc renamed this:
~~refactor: Speed up Base58 encoding/decoding by 400%/200% via preliminary byte packing~~
optimization: Speed up Base58 encoding/decoding by 400%/200% via preliminary byte packing
on Jun 23, 2024

l0rinc commented at 10:45 am on July 1, 2024: contributor

@Sjors, this is the optimization I’ve mentioned to you in person, I’d appreciate a review if you think it’s worthwhile:

maflcko commented at 12:48 pm on July 1, 2024: member

I don’t think this is used in a critical path, to warrant a speedup?

l0rinc commented at 12:58 pm on July 1, 2024: contributor

I don’t think this is used in a critical path, to warrant a speedup?

It’s literally the example from the benchmarking docs:

which was specifically optimized in various other commits before: https://github.com/bitcoin/bitcoin/commit/bcab47bc1b2bfdd29f8b89f8a211755299938aea, https://github.com/bitcoin/bitcoin/commit/3252208cb10be645bae415c90fb2ed8217838490, https://github.com/bitcoin/bitcoin/commit/159ed95f7452ab5454e9d660f6f095b8476b1eed

maflcko commented at 1:05 pm on July 1, 2024: member

What you link to is supporting my point, is it not? #12704 (comment)

Stop wasting time on discussing the performance. This does not matter. Decoding an address could take 50 us and I don’t think anyone would notice.

If the resulting code looks better, go for it. Otherwise, don’t.

-0

l0rinc commented at 1:09 pm on July 1, 2024: contributor

What’s the point of the benchmarks in that case exactly? Anyway, I can make the code slightly simpler and similarly performant, would that be welcome?

maflcko commented at 1:09 pm on July 1, 2024: member

Ok, the reason for #7656#issue-139438690 was an improvement in listunspent. Seems fine, if this is still the case. But this will need to be checked first.

sipa commented at 1:40 pm on July 1, 2024: member

@paplorinc The reason you’re getting some pushback on your PRs is because review is the biggest bottleneck for our project, which makes contributors and maintainers weary about proposed changes that demand review (which could be spent elsewhere) but don’t result in observable benefits (even if they improve microbenchmarks). I hope you don’t conclude from this that we don’t care about performance, but it may take some experience with the codebase and the project to figure out what people consider important. In that sense, reviewing things like #28280 are far more impactful, so thank you for that.

As long as it doesn’t introduce a lot of complexity, I don’t think a pure performance improvement is an inherently bad change that we should reject, but it is a reason why you may not get much attention from reviewers. So (speaking just for myself), this isn’t “don’t make such changes!”, but a “be warned that people may not care about this enough for it go anywhere”.

l0rinc commented at 1:47 pm on July 1, 2024: contributor

Thanks @sipa, appreciate your comment! How do I find small changes that are needed, welcome, not so controversial, and don’t need 3 years of up-front studying? That’s why I like optimizations, since the desired behavior is already in the code and test and benchmarks and history, and I can have visible progress while learning about the project.

maflcko commented at 1:59 pm on July 1, 2024: member

How do I find small changes that are needed, welcome, not so controversial, and don’t need 3 years of up-front studying?

You can spend time on in-depth review of open pull requests and compare your review with the review done by others. This may be time-consuming (Yes, some pull requests may need up-front studying, but there are many that do not). Ideally the process will teach you relevant skills for this project and for yourself to apply elsewhere. Moreover, on some pull requests there remain small follow-ups that were found during review, so you’ll naturally find stuff to work on if you start out by reviewing pull requests done by others.

andrewtoth commented at 2:00 pm on July 1, 2024: contributor

How do I find small changes that are needed, welcome, not so controversial, and don’t need 3 years of up-front studying? @paplorinc I know you are past your first PR and issue, but most of the issues with this label would fit that criteria https://github.com/bitcoin/bitcoin/labels/good%20first%20issue. Also, browsing open issues I’m sure you could find others that fulfill most of the criteria as well.

l0rinc commented at 2:24 pm on July 1, 2024: contributor

@andrewtoth, that was the first thing I checked, couldn’t find any reasonable “good first issue” - or other issue that piqued my interest. The problem has to be personal, otherwise the solution won’t be honest. @maflcko, you already suggested that multiple times, but my question wasn’t how to review PRs.

I’ll check if this PR improved listunspent, as suggested, if not, I’ll just close this.

andrewtoth commented at 2:28 pm on July 1, 2024: contributor

@paplorinc #28945 was abandoned and I don’t think @fjahr has taken it over. Perhaps that would be interesting to you. Maybe check in that PR if anyone is working on it if you are.

fjahr commented at 2:46 pm on July 1, 2024: contributor

I have reopened #28945 now

andrewtoth commented at 2:48 pm on July 1, 2024: contributor

Ahh sorry thanks.

l0rinc force-pushed on Jul 1, 2024

l0rinc commented at 8:37 pm on July 1, 2024: contributor

Ok, the reason for #7656#issue-139438690 was an improvement in listunspent. Seems fine, if this is still the case. But this will need to be checked first.

I’ve created 10k blocks in regtest and measured the performance of listunspent before and after:

 0killall bitcoind 2>/dev/null || true
 1./src/bitcoind -regtest -daemon
 2./src/bitcoin-cli -regtest createwallet "test_wallet"
 3./src/bitcoin-cli -regtest generatetoaddress 10000 $(./src/bitcoin-cli -regtest getnewaddress) >/dev/null
 4
 5hyperfine \
 6  --warmup 3 --runs 10 \
 7  --parameter-list BRANCH master,l0rinc/optimize-base58-conversion \
 8  --prepare '
 9    killall bitcoind 2>/dev/null || true
10    git checkout "{BRANCH}" && git reset --hard
11    make -j10 >/dev/null
12    ./src/bitcoind -regtest -daemon
13    sleep 1
14    ./src/bitcoin-cli -regtest loadwallet "test_wallet"
15  ' \
16  './src/bitcoin-cli -regtest listunspent'

which resulted in:

 0Benchmark 1: ./src/bitcoin-cli -regtest listunspent (BRANCH = master)
 1  Time (mean ± σ):     378.7 ms ±   2.8 ms    [User: 71.7 ms, System: 13.9 ms]
 2  Range (min … max):   376.4 ms … 386.0 ms    10 runs
 3 
 4Benchmark 2: ./src/bitcoin-cli -regtest listunspent (BRANCH = l0rinc/optimize-base58-conversion)
 5  Time (mean ± σ):     244.0 ms ±   1.3 ms    [User: 71.4 ms, System: 13.7 ms]
 6  Range (min … max):   242.2 ms … 246.1 ms    10 runs
 7 
 8Summary
 9  ./src/bitcoin-cli -regtest listunspent (BRANCH = l0rinc/optimize-base58-conversion) ran
10    1.55 ± 0.01 times faster than ./src/bitcoin-cli -regtest listunspent (BRANCH = master)

i.e. 55% faster listunspent for the given usecase.

l0rinc force-pushed on Jul 1, 2024

l0rinc force-pushed on Jul 2, 2024

maflcko commented at 7:37 am on July 2, 2024: member

I presume, if you wanted to speed up listunspent in this case of a bip-32 base58 encoded descriptor string, a higher speed-up could be achieved by caching the descriptor string results, because the expectation is that there are generally only a few (or one) per wallet. But I am not sure how easy that is, or whether it is worth it.

l0rinc commented at 7:42 am on July 2, 2024: contributor

I was following the benchmarks to decide what to work on, but since you’ve mentioned this is an important usecase, I measured it as well. Is there anything else you’d like me to measure or change in this pull request?

maflcko commented at 8:04 am on July 2, 2024: member

I don’t think I said that “this is an important usecase”. I simply said that the reason for the improvement in #7656#issue-139438690 was listunspent. That pull request was created before bech32(m) addresses and descriptor wallets existed. Considering that bech32 is the default address type and that descriptor wallets are the default as well, the only expected remaining use of base58 should be in the bip-32 descriptor string. My guess is that, if it was important to optimize that for speed, a higher speedup could be achieved by caching the generated descriptor string.

However, this is just background information and a guess. I don’t know if it is true, how easy it is to implement, whether it is worth it to review, or worth it at all.

l0rinc commented at 11:48 am on July 12, 2024: contributor

@luke-jr, would this optimization be more welcome in https://github.com/bitcoin/libbase58 instead?

l0rinc force-pushed on Jul 12, 2024

luke-jr commented at 2:35 pm on July 12, 2024: member

would this optimization be more welcome in https://github.com/bitcoin/libbase58 instead?

The algorithm used in libbase58 is different, so not sure this even applies. Kinda doubt it would be worth the time to port/review either, unless a library consumer cares about performance or the other criteria explained already here.

If you’re just looking for things to do, extending libbase58 to Bech32 might be worth doing. See https://github.com/bitcoin/libbase58/issues/6

DrahtBot added the label CI failed on Jul 13, 2024

l0rinc force-pushed on Jul 14, 2024

Unify size estimations in Base58 encoding/decoding

Note that the constants for size allocations have slightly changed after recalculating them

b42dd6c530

Remove redundant zero-skipping logic in Base58 encode/decode 0c4bc5e54f

Encode by iterating forward and dividing in-place

Instead of collecting the values to and empty b58, we're cloning the input without leading zeros and dividing it in-place, while doing the quadratic division from the most significant, non-zero digit, forward.

make && ./src/bench/bench_bitcoin --filter=Base58Encode --min-time=1000
Before:
```
|             ns/byte |              byte/s |    err% |     total | benchmark
|--------------------:|--------------------:|--------:|----------:|:----------
|               59.34 |       16,851,250.88 |    0.2% |      1.10 | `Base58Encode`
|               59.20 |       16,892,479.61 |    0.2% |      1.10 | `Base58Encode`
|               58.97 |       16,958,226.76 |    0.2% |      1.10 | `Base58Encode`
```
After:
```
|             ns/byte |              byte/s |    err% |     total | benchmark
|--------------------:|--------------------:|--------:|----------:|:----------
|               40.80 |       24,508,402.06 |    0.1% |      1.10 | `Base58Encode`
|               40.83 |       24,489,762.49 |    0.2% |      1.10 | `Base58Encode`
|               39.71 |       25,182,310.62 |    0.2% |      1.10 | `Base58Encode`
```

and

make && ./src/bench/bench_bitcoin --filter=Base58CheckEncode --min-time=1000
Before:
```
|             ns/byte |              byte/s |    err% |     total | benchmark
|--------------------:|--------------------:|--------:|----------:|:----------
|               79.93 |       12,511,576.75 |    0.4% |      1.10 | `Base58CheckEncode`
|               79.49 |       12,580,136.21 |    0.1% |      1.10 | `Base58CheckEncode`
|               79.65 |       12,554,785.16 |    0.1% |      1.10 | `Base58CheckEncode`
```
After:
```
|             ns/byte |              byte/s |    err% |     total | benchmark
|--------------------:|--------------------:|--------:|----------:|:----------
|               55.27 |       18,094,561.35 |    0.1% |      1.10 | `Base58CheckEncode`
|               55.41 |       18,046,778.32 |    0.1% |      1.10 | `Base58CheckEncode`
|               55.32 |       18,075,763.16 |    0.1% |      1.10 | `Base58CheckEncode`
```

Co-authored-by: optout21 <13562139+optout21@users.noreply.github.com>

a24ad3e008

Speed up Base58 encoding with 64-bit packing

To mitigate the quadratic complexity inherent in the sequential byte division of the Base58 encoding process, this update aggregates characters into groups of 7, fitting them into 64-bit long integers.
This refinement utilizes the inherent efficiency of native division and modulo operations on 64-bit architectures, significantly optimizing computational overhead.
The benchmarks indicate a 4x speedup for `Base58CheckEncode` and `Base58Encode`:

make && ./src/bench/bench_bitcoin --filter=Base58Encode --min-time=1000
After:
```
|             ns/byte |              byte/s |    err% |     total | benchmark
|--------------------:|--------------------:|--------:|----------:|:----------
|               14.32 |       69,831,031.44 |    0.1% |      1.10 | `Base58Encode`
|               14.32 |       69,811,995.18 |    0.1% |      1.10 | `Base58Encode`
|               14.35 |       69,662,527.88 |    0.5% |      1.10 | `Base58Encode`
```

make && ./src/bench/bench_bitcoin --filter=Base58CheckEncode --min-time=1000
After:
```
|             ns/byte |              byte/s |    err% |     total | benchmark
|--------------------:|--------------------:|--------:|----------:|:----------
|               19.15 |       52,231,968.11 |    0.1% |      1.06 | `Base58CheckEncode`
|               19.13 |       52,269,345.54 |    0.4% |      1.05 | `Base58CheckEncode`
|               19.14 |       52,244,117.61 |    0.3% |      1.06 | `Base58CheckEncode`
```

e6a147d468

Decode by iterating forward and dividing in-place

> make && ./src/bench/bench_bitcoin --filter=Base58Decode --min-time=1000
Before:
```
|             ns/byte |              byte/s |    err% |     total | benchmark
|--------------------:|--------------------:|--------:|----------:|:----------
|               17.50 |       57,141,622.65 |    0.1% |      1.10 | `Base58Decode`
|               17.42 |       57,392,223.96 |    0.0% |      1.10 | `Base58Decode`
|               17.43 |       57,358,655.44 |    0.2% |      1.10 | `Base58Decode`
```
After:
```
|             ns/byte |              byte/s |    err% |     total | benchmark
|--------------------:|--------------------:|--------:|----------:|:----------
|               16.37 |       61,093,842.90 |    0.2% |      1.10 | `Base58Decode`
|               16.37 |       61,100,514.64 |    0.1% |      1.10 | `Base58Decode`
|               16.38 |       61,046,275.93 |    0.1% |      1.10 | `Base58Decode`
```

227cd497a1

Speed up Base58 decoding with 64-bit packing

> make && ./src/bench/bench_bitcoin --filter=Base58Decode --min-time=1000

After:
```
|             ns/byte |              byte/s |    err% |     total | benchmark
|--------------------:|--------------------:|--------:|----------:|:----------
|                8.79 |      113,767,685.06 |    0.1% |      1.10 | `Base58Decode`
|                8.78 |      113,831,528.33 |    0.0% |      1.10 | `Base58Decode`
|                8.80 |      113,607,470.35 |    0.2% |      1.10 | `Base58Decode`
```

c1291fdae7

l0rinc force-pushed on Jul 18, 2024

DrahtBot removed the label CI failed on Jul 18, 2024

achow101 removed review request from optout21 on Oct 15, 2024

achow101 requested review from achow101 on Oct 15, 2024

achow101 commented at 11:05 pm on November 4, 2024: member

As this is basically a complete rewrite of the base58 encoding and decoding code, I don’t think the review effort required to review this is worth it relative to the unimportance of these functions.

l0rinc commented at 10:16 am on November 5, 2024: contributor

Thanks for checking it out @achow101. I could make the diff minimal, but given that it’s not that important, I will leave it as is - until someone starts complaining that listunspent is slow :)

l0rinc commented at 7:33 pm on November 25, 2024: contributor

I just found this was already attempted in a very similar way by @martinus a few years ago in #21176 - so now we have two versions, if this will turn out to be important again. Closing, thanks for the reviews!

l0rinc closed this on Nov 25, 2024

optimization: Speed up Base58 encoding/decoding by 400%/200% via preliminary byte packing #29473

Code Coverage & Benchmarks

Reviews

Conflicts