C++ most efficient way to convert string to int (faster than atoi)

Question

As mentioned in the title, I'm looking for something that can give me more performance than atoi. Presently, the fastest way I know is

atoi(mystring.c_str()) 

Finally, I would prefer a solution that doesn't rely on Boost. Does anybody have good performance tricks for doing this?

Additional Information: int will not exceed 2 billion, it is always positive, the string has no decimal places in it.

Answer 1

I experimented with solutions using lookup tables, but found them fraught with issues, and actually not very fast. The fastest solution turned out to be the least imaginitive:

int fast_atoi( const char * str ) {     int val = 0;     while( *str ) {         val = val*10 + (*str++ - '0');     }     return val; } 

Running a benchmark with a million randomly generated strings:

fast_atoi : 0.0097 seconds atoi      : 0.0414 seconds 

To be fair, I also tested this function by forcing the compiler not to inline it. The results were still good:

fast_atoi : 0.0104 seconds atoi      : 0.0426 seconds 

Provided your data conforms to the requirements of the fast_atoi function, that is pretty reasonable performance. The requirements are:

1. Input string contains only numeric characters, or is empty
2. Input string represents a number from 0 up to INT_MAX

Answer 2

atoi can be improved upon significantly, given certain assumptions. This was demonstrated powerfully in a presentation by Andrei Alexandrescu at the C++ and Beyond 2012 conference. Hi s replacement used loop unrolling and ALU parallelism to achieve orders of magnitude in perf improvement. I don't have his materials, but this link uses a similar technique: http://tombarta.wordpress.com/2008/04/23/specializing-atoi/