Improve speed of Base58 Encoding #21176
Conversation
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 bitcoin#7656
fc38405 to
0d96470
Compare
|
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? |
|
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 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! |
Thanks, that makes sense.
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. |
|
Personally I find the existing version in 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? |
|
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. |
|
Closing, as it's not performance relevant but critical code so more complexity is bad. Thanks for having a look! |
This modifies
DecodeBase58andEncodeBase58by processing multiple input bytes at once. ForDecodeBase58we can take 9 bytes at once, and forEncodeBase587. This reduces the number of calls of the inner conversion loop.Benchmark results:
Base58Decode, ~2.8 times faster.EncodeBase58, ~4.1 times faster.Note that I tried to improve
blockToJSONwith this change, but the difference there is not really significant. This optimization might still be relevant though for e.g.listunspents, see #7656