openzeppelin-contracts

openzeppelin-contracts copied to clipboard

Fixes #????

This PR reduces gas usage of Strings.toString for decimal numbers. Here are some results:

Input                                                                          | Current | New  | Gas saved
-------------------------------------------------------------------------------|---------|------|-----------------
0                                                                              | 131     | 458  | -327  (-249,62%)
1                                                                              | 833     | 458  | 375   (45,02%)
12                                                                             | 1383    | 534  | 849   (61,39%)
123                                                                            | 1933    | 611  | 1322  (68,39%)
1234                                                                           | 2483    | 687  | 1796  (72,33%)
12345                                                                          | 3033    | 735  | 2298  (75,77%)
1234567                                                                        | 4133    | 888  | 3245  (78,51%)
1234567890                                                                     | 5783    | 1059 | 4724  (81,69%)
123456789012345                                                                | 8533    | 1413 | 7120  (83,44%)
12345678901234567890                                                           | 11283   | 1708 | 9575  (84,86%)
123456789012345678901234567890                                                 | 16783   | 2357 | 14426 (85,96%)
1234567890123456789012345678901234567890                                       | 22289   | 2983 | 19306 (86,62%)
12345678901234567890123456789012345678901234567890                             | 27789   | 3574 | 24215 (87,14%)
123456789012345678901234567890123456789012345678901234567890                   | 33289   | 4252 | 29037 (87,23%)
1234567890123456789012345678901234567890123456789012345678901234567890         | 38795   | 4820 | 33975 (87,58%)
115792089237316195423570985008687907853269984665640564039457584007913129639935 | 43195   | 5345 | 37850 (87,63%)

(Edit: results updated for the newest commits) Each measurement was done in a separate dapptools test to remove memory usage bias. Solc was in version 0.8.13 with optimizer set to 1 million runs.

A little more gas can be pinched, e.g. manual string allocation with Yul saves ~119 gas, but that both complicates the codebase and makes the optimizer behavior harder to predict.

Tests are cleaned up and extended.

PR Checklist

• [x] Tests
• [x] Documentation
• [x] Changelog entry

Thanks @CodeSandwich for this PR

Note: We could use the same length-search pattern for the hex version.

Yes, if this PR goes through, we can add these optimizations there too. One thing at a time :smiley:

I've pushed an optimization of the memory writing loop. I don't exactly understand why, streamlining the loop and putting the iszero command as the last thing of the loop just clicks with the optimizer. The new gas usage results:

0: 458
1: 458
12: 534
123: 611
1234: 687
12345: 735
1234567: 888
1234567890: 1059
123456789012345: 1413
12345678901234567890: 1708
123456789012345678901234567890: 2357
1234567890123456789012345678901234567890: 2983
12345678901234567890123456789012345678901234567890: 3574
123456789012345678901234567890123456789012345678901234567890: 4252
1234567890123456789012345678901234567890123456789012345678901234567890: 4820
115792089237316195423570985008687907853269984665640564039457584007913129639935: 5345 (8 fold decrease from master 😆)

The usage of the symbols table has zero impact on gas, but IMO it's much clearer than the addition of a magic number.

Sorry I'm late to this PR.

My thoughts are:

• For loops in Yul have very unfamiliar syntax, at the moment we don't have any in the entire codebase, and I would prefer if that remained the case. The main gains in this PR are due to an optimized log10 implementation, and probably some more from removing bounds checks on array accesses. Some assembly is necessary for the second part but I would strongly prefer if the for loop was outside of that.
• I would really appreciate if the log10 implementation was added as Math.log10 so it could be used on its own. That also implies some more testing though, so I would be ok with doing that in a later PR.
• As I commented above, >= 1 << 128 vs >> 127 > 0 seems to not make a difference at all so I'd like us to revert the unrelated changes in Math.sol.

I would really appreciate if the log10 implementation was added as Math.log10 so it could be used on its own. That also implies some more testing though, so I would be ok with doing that in a later PR.

Making a PR that includes Math.log10 and Math.log2 would be great.

• Math.log2 could be used in Math.sqrt(uint256) and Strings.toHexString(uint256)
• Math.log10 would be used in Strings.toString(uint256)

@CodeSandwich, would you be able to do that ?