refactor: Reduce memory copying operations in bech32 encoding

paplorinc commented at 1:12 pm on March 9, 2024: contributor

Started optimizing the base conversions in TryParseHex, Base58 and IsSpace - this is the next step.

Part of this change was already merged in #30047, which made decoding ~26% faster.

Here I’ve reduced the memory reallocations and copying operations in bech32 encode, making it ~15% faster.

make && ./src/bench/bench_bitcoin –filter=‘Bech32Encode’ –min-time=1000

Before:

0|             ns/byte |              byte/s |    err% |     total | benchmark
1|--------------------:|--------------------:|--------:|----------:|:----------
2|               19.97 |       50,074,562.72 |    0.1% |      1.06 | `Bech32Encode`

After:

0|             ns/byte |              byte/s |    err% |     total | benchmark
1|--------------------:|--------------------:|--------:|----------:|:----------
2|               17.33 |       57,687,668.20 |    0.1% |      1.10 | `Bech32Encode`

DrahtBot commented at 1:12 pm on March 9, 2024: contributor

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

Code Coverage

For detailed information about the code coverage, see the test coverage report.

Reviews

See the guideline for information on the review process.

Type	Reviewers
ACK	josibake, sipa, achow101

If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.

Conflicts

No conflicts as of last run.

DrahtBot added the label Refactoring on Mar 9, 2024

paplorinc force-pushed on Mar 9, 2024

paplorinc marked this as ready for review on Mar 9, 2024

DrahtBot added the label CI failed on Apr 19, 2024

paplorinc force-pushed on Apr 21, 2024

paplorinc marked this as a draft on Apr 21, 2024

paplorinc force-pushed on Apr 21, 2024

paplorinc force-pushed on Apr 22, 2024

DrahtBot removed the label CI failed on Apr 22, 2024

paplorinc marked this as ready for review on Apr 22, 2024

josibake commented at 9:42 am on May 11, 2024: member

Concept ACK

I cherry-picked your last commit into #30047 to get rid of the hardcoded values inside ExpandHRP. Looking at the rest of your commits here, the rest of the changes look great and the benchmark numbers are a nice improvement. Will review more thoroughly this week!

paplorinc force-pushed on May 11, 2024

paplorinc force-pushed on May 12, 2024

paplorinc force-pushed on May 13, 2024

paplorinc force-pushed on May 20, 2024

paplorinc force-pushed on May 29, 2024

DrahtBot added the label Needs rebase on Jun 5, 2024

paplorinc force-pushed on Jun 5, 2024

paplorinc renamed this:
~~refactor: Reduce memory copying operations in bech32 encoding/decoding~~
refactor: Reduce memory copying operations in bech32 encoding
on Jun 5, 2024

paplorinc force-pushed on Jun 5, 2024

DrahtBot added the label CI failed on Jun 5, 2024

DrahtBot commented at 10:46 am on June 5, 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/25832897694

Reserve hrp memory in Decode and LocateErrors d5ece3c4b5

paplorinc force-pushed on Jun 5, 2024

DrahtBot removed the label Needs rebase on Jun 5, 2024

paplorinc force-pushed on Jun 5, 2024

paplorinc commented at 11:02 am on June 5, 2024: contributor

@josibake, now that the cherry-pick was merged, I’ve rebased and re-measured - the important part of this change was already included in the other PR, the remaining optimizations here are smaller, but also a lot simpler.

in src/bech32.cpp:372 in e7c55d4f4d outdated

375+    std::string ret;
376+    ret.reserve(hrp.size() + 1 + values.size() + CHECKSUM_SIZE);
377+    ret += hrp;
378+    ret += '1';
379+    for (const auto& c : values) ret += CHARSET[c];
380+    for (const auto& c : CreateChecksum(encoding, hrp, values)) ret += CHARSET[c];

josibake commented at 11:09 am on June 5, 2024:

in https://github.com/bitcoin/bitcoin/pull/29607/commits/e7c55d4f4dea4c42b40ff326a17e6884de181ed6:

Is there a reason to prefer auto over explicitly mentioning the types? I find it to be more readable as

0    for (const char& c : hrp) assert(c < 'A' || c > 'Z');
1
2    std::string ret;
3    ret.reserve(hrp.size() + 1 + values.size() + CHECKSUM_SIZE);
4    ret += hrp;
5    ret += '1';
6    for (const uint8_t& i : values) ret += CHARSET[i];
7    for (const uint8_t& i : CreateChecksum(encoding, hrp, values)) ret += CHARSET[i];

since in the second and third loop its not actually a character, but an index for the character in the CHARSETarray. Using auto c leaves the impression that its all characters, which is incorrect.

paplorinc commented at 11:19 am on June 5, 2024:

Done, thanks

Reduce memory copying operations in bech32 encode

Here I've reduced the memory reallocations and copying operations in bech32 encode, making it ~15% faster.

make && ./src/bench/bench_bitcoin --filter='Bech32Encode' --min-time=1000

Before:

|             ns/byte |              byte/s |    err% |     total | benchmark
|--------------------:|--------------------:|--------:|----------:|:----------
|               19.97 |       50,074,562.72 |    0.1% |      1.06 | `Bech32Encode`
After:

|             ns/byte |              byte/s |    err% |     total | benchmark
|--------------------:|--------------------:|--------:|----------:|:----------
|               17.33 |       57,687,668.20 |    0.1% |      1.10 | `Bech32Encode`

Co-authored-by: josibake <josibake@protonmail.com>

07f64177a4

paplorinc force-pushed on Jun 5, 2024

josibake commented at 11:30 am on June 5, 2024: member

ACK https://github.com/bitcoin/bitcoin/pull/29607/commits/07f64177a49f1b6b4d486d10cf67fddfa3c995eb

Verified the benchmark locally. Aside from the speed improvements, this also improves the readability of the code.

DrahtBot removed the label CI failed on Jun 5, 2024

sipa commented at 1:26 pm on June 5, 2024: member

utACK 07f64177a49f1b6b4d486d10cf67fddfa3c995eb

Making the code more readable is a good reason to make this change, but this code was specifically written to prioritize simplicity over performance. If we’d care about performance, it’s probably better to use an approach similar to that of the C reference implementation (as it works entirely on the stack, while the current code does several allocations: 1 in ExpandHRP, between 1 and 3 in CreateChecksum, and 1 inevitable one in Encode).

achow101 commented at 4:10 pm on June 13, 2024: member

ACK 07f64177a49f1b6b4d486d10cf67fddfa3c995eb

achow101 merged this on Jun 13, 2024

achow101 closed this on Jun 13, 2024

paplorinc deleted the branch on Jun 13, 2024

paplorinc commented at 4:54 pm on June 13, 2024: contributor

Thanks for the reviews @josibake, @sipa, @achow101. There’s a similar small optimization for transaction input/output allocations as well, I’d appreciate a review.

refactor: Reduce memory copying operations in bech32 encoding #29607

Code Coverage

Reviews

Conflicts