Faster string to integer conversion

Faster string to integer conversion

[Faissal Bensefia]

Good day,
The way glibc does strlen got me thinking, and I believe I've devised a
way to do something similar for string to integer conversion. Using Sean
Anderson's hasless, Juha Järvi's hasmore (both of which can be found
here:
https://graphics.stanford.edu/~seander/bithacks.html#HasLessInWord) and
some things I came up with. I'll outline the algorithm here, I'll be
happy to explain more if necessary. In theory, this should be
significantly faster than what is being done in things such as strtol
etc in glibc:
1. We handle the first 2 characters normally to check the base.
2. If the base is 10 we don't handle it number by number as normal,
instead we continue on...
3. Instead we take a double word, we'll call this 'snippet' when we do
calculations with it
4. Increment the string pointer by double word size (so, 4).
5. Check hasless(snippet,0x30), if true, start checking for a 0
terminator and if a zero terminator is not found, nor whitespace (which
we skip) assume there was an invalid character.
6. Check hasmore(snippet,0x39), if true, assume there was an invalid
character.
7. If neither hasless nor hasmore have returned true then xor 0x30303030
from the value.
8. We then multiply the current total for the number by 10000
9. And add:
snippet&0xFF
((snippet>>8)&0xFF)*10
((snippet>>16)&0xFF)*100
((snippet>>24)&0xFF)*1000
10. Loop back to step 3

Thank you for your time,
~Faissal Bensefia

Re: Faster string to integer conversion

[Paul Eggert]

Thanks for thinking about this. Certainly strtol etc. could be sped up and the 
approach you mention might be a win; it's hard to say, given its setup overhead. 
In practice most integers are small, and you'd need to benchmark the approach on 
a set of integers that are of "typical" size. It may well be more work to come 
up with a convincing benchmark than to come up with the actual code.

If you're interested in strtol speedup ideas, how about this one? Jettison 
tables like __strtol_ul_max_tab and replace their uses with invocations of the 
INT_ADD_WRAPV macro defined by the following recently-proposed patch:

https://sourceware.org/ml/libc-alpha/2016-04/msg00174.html