Optimize Strings.toString(uint) implementation

[3sGgpQ8H]

🧐 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

[frangio]

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?

[3sGgpQ8H]

Sure.

1. 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
2. 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.

[frangio]

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?

[3sGgpQ8H]

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:

1. 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)
2. Append a token ID to a ERC-721 NFT URI

[frangio]

I hadn't realized the StackOverflow answer was Solidity. 🙂

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.

[frangio]

Fixed by #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.