OpenZeppelin
Optimize `Strings.toString(uint)` implementation
🧐 Motivation
The current Strings.toString(uint) implementation is quite inefficient on large inputs.
📝 Details Consider optimizing it as suggested here: https://stackoverflow.com/a/71095692/2038768
Thank you @3sGgpQ8H. Can you elaborate on what exactly makes the current implementation inefficient and what is the reason we would see an improvement with the link you shared?
Sure.
- The current implementation uses linear search to find out the number of digits in the result, while binary search would be much more efficient: https://github.com/OpenZeppelin/openzeppelin-contracts/blob/master/contracts/utils/Strings.sol#L22-L27
- In the current implementation, the main loop evaluate loop condition after every digit, which is a significant overhead. Unrolling the loop could save much gas.
Got it. Agree with the first point. Perhaps we should have a general purpose Math.log10 and use that function here?
For the second point we need to consider that toString returns a string of arbitrary length so I'm not sure how that plays together with the loop unrolling.
As a side note, do you see this function being used on-chain as opposed to off-chain queries?
I'm not sure how that plays together with the loop unrolling.
Look at the StackOverflow answer referred in the original post.
As a side note, do you see this function being used on-chain as opposed to off-chain queries?
Surely, its its primary purpose is to be used on-chain. For off-chain use it would be more efficient to return a number and convert to a string off-chain (i.e. in UI). Two quite common on-chain usages are:
- Include a number into a signed message whose signature is verified by a smart contract (a message has to be human readable, thus numbers are included in decimal format)
- Append a token ID to a ERC-721 NFT URI
I hadn't realized the StackOverflow answer was Solidity. :slightly_smiling_face:
Signatures are a decent use case, though a standard like EIP712 doesn't convert them to decimal format. NFT URIs are not normally computed on chain as far as I know.
In any case I think it makes sense to optimize this.
Fixed by https://github.com/OpenZeppelin/openzeppelin-contracts/issues/3573 where toString was changed to binary search (see also the new log functions from #3670).
We haven't unrolled the loop. We can consider that if someone wants to open a PR and it shows significant savings.