Improve speed of Base58 Encoding #21176

1. 
   martinus commented at 10:05 pm on February 14, 2021: contributor

   This modifies DecodeBase58 and EncodeBase58 by processing multiple input bytes at once. For DecodeBase58 we can take 9 bytes at once, and for EncodeBase58 7. This reduces the number of calls of the inner conversion loop.

   Benchmark results:

   • 37.78 -> 13.73 ns/byte for Base58Decode, ~2.8 times faster.
   • 28.81 -> 7.02 ns/byte for EncodeBase58, ~4.1 times faster.

   Note that I tried to improve blockToJSON with this change, but the difference there is not really significant. This optimization might still be relevant though for e.g. listunspents, see #7656

2. martinus renamed this:
   process multiple input bytes at once
   Improve speed of Base58Encode & Base58Decode
   on Feb 14, 2021
3. martinus renamed this:
   Improve speed of Base58Encode & Base58Decode
   Improve speed of Base58 Encoding
   on Feb 14, 2021
4. Improve speed of Base58 Encoding

   This modifies `DecodeBase58` and `EncodeBase58` by processing multiple input bytes at once. For `DecodeBase58` we can take 9 bytes at once,
   and for `EncodeBase58` 7. This reduces the number of calls of the inner conversion loop.
   
   Benchmark results:
   
   * 37.78 -> 13.73 ns/byte for `Base58Decode`, ~2.8 times faster.
   * 28.81 -> 7.02 ns/byte for `EncodeBase58`, ~4.1 times faster.
   
   Note that I tried to improve `blockToJSON` with this change, but the difference there is not really significant. This optimization might still be
   relevant though for e.g. `listunspents`, see #7656

   0d96470bca
5. martinus force-pushed on Feb 14, 2021
6. laanwj added the label Utils/log/libs on Feb 15, 2021
7. 
   laanwj commented at 7:41 am on February 15, 2021: member

   The gains are quite impressive!

   That said, this does make the code longer and quite a bit more complicated.

   What motivated you to optimize this specifically? Are you experiencing any behavior where decoding / encoding Base58 is in the critical path?

8. 
   martinus commented at 7:55 am on February 15, 2021: contributor

   In my tool BitcoinUtxoVisualizer I am basically limited by the speed of how fast bitcoind can send me JSON block data. While profiling I saw EncodeBase58 quite a few times so I had a look at it. It’s about 2% faster or so with that change.

   So for my use case honestly this change is probably not worth it. There are other much more important changes, e.g. #21006. But I saw @promag’s PR #7656 so having a faster Base58 encoding might be worthwhile for others? If not, feel free to decline the PR, I’m perfectly fine with that!

9. 
   laanwj commented at 8:13 am on February 15, 2021: member

   In my tool BitcoinUtxoVisualizer I am basically limited by the speed of how fast bitcoind can send me JSON block data

   Thanks, that makes sense.

   might be worthwhile for others? If not, feel free to decline the PR, I’m perfectly fine with that!

   I’ll leave that to others. If this can get enough review I’m fully okay with it! I’m not really declining this, my point was only that “reviewable straightforward code” is important from a security perspective and this sometimes trumps pure performance (depending on the part of the code). Especially in a memory-unsafe language like C++ where it’s so easy to reach outside a buffer. We’ve had some discussions about this in the past when Base58 seemed to attract a lot of pretty arbitrary “make it faster” changes. At least you’re doing proper benchmarking.

10. 
    practicalswift commented at 11:01 am on February 15, 2021: contributor

    Personally I find the existing version in master easier to reason about.

    I tend to prefer “dumb and easy to reason about” over “cleverly optimised but harder to reason about” in code that is not performance critical (as seen from a macro level).

    I don’t mean to be boring: this is a clever optimization. I’m just afraid it might remove the “trivially correct” property of the code it optimizes :) @martinus, out of curiosity: have you looked anything at profiling IBD in search of optimization opportunities?

11. 
    martinus commented at 12:03 pm on February 15, 2021: contributor

    I agree the existing version is easier to read. I did not look at IBD at all, are there still improvements to be done there? It seemed to me that it’s already well optimized.

    I mostly profiled fetching JSON block data. The biggest optimization opportunity for this is reducing the global lock, and making univalue faster.

12. 
    martinus commented at 10:02 am on February 17, 2021: contributor

    Closing, as it’s not performance relevant but critical code so more complexity is bad. Thanks for having a look!
13. martinus closed this on Feb 17, 2021

    ---

14. bitcoin locked this on Aug 16, 2022
15. bitcoin unlocked this on Nov 26, 2024
16. bitcoin locked this on Nov 26, 2024

Contributors
martinus laanwj practicalswift

Labels
Utils/log/libs