In addition to my suggestion, you don't actually need to calculate sum(log10(i)). The idea is simple: the concatenation of numbers 0..9 is 10*1 chars in length, for 0..100 is 10*1 + 90*2 chars in length, for 0..1000 it is 10*1 + 90*2 + 900*3, and so on. So you can tell what your resulting string length almost in O(log10(n)) calculations, which is super fast.
You're wellcome. One last thing - as far as I know Rust doesn't have a C-equivalent of itoa, in other words there is no function in Rust stdlib to convert number to string in preallocated buffer. But there is an itoa crate which does exactly that, you can read about it here: docs.rs/itoa/0.4.5/itoa/
I feel strangely excited about messing with these benchmarks, so I may share my results in a few days when I'll try these things.
After reading all your comments, i am very excited. I am new to rust but your feedback is very motivating. I'll work on implementing your feedbacks. Thank you very much. Looking forward to your benchmarks too.
Sure, I will try that out. Thank you for the suggestions.
In addition to my suggestion, you don't actually need to calculate sum(log10(i)). The idea is simple: the concatenation of numbers 0..9 is 10*1 chars in length, for 0..100 is 10*1 + 90*2 chars in length, for 0..1000 it is 10*1 + 90*2 + 900*3, and so on. So you can tell what your resulting string length almost in O(log10(n)) calculations, which is super fast.
Awesome thanks a lot Dmitry.
You're wellcome. One last thing - as far as I know Rust doesn't have a C-equivalent of itoa, in other words there is no function in Rust stdlib to convert number to string in preallocated buffer. But there is an itoa crate which does exactly that, you can read about it here: docs.rs/itoa/0.4.5/itoa/
I feel strangely excited about messing with these benchmarks, so I may share my results in a few days when I'll try these things.
After reading all your comments, i am very excited. I am new to rust but your feedback is very motivating. I'll work on implementing your feedbacks. Thank you very much. Looking forward to your benchmarks too.
So I implemented a single allocation version in Rust with itoa crate. The results exceeded my expectations:
Mutable implementation can be found in this gist
Nice Dmitry, this looks awesome.