I want an integer parser so fast it risks discovering time travel.
I'm stuck in C# for a language, but that doesn't mean I can't try to use c++. So I wrote the following:
The best I could do
public static unsafe bool FastTryParseInt(string input, out int result)
{
fixed (char* cString = input) {
unchecked {
char* nextChar = cString;
bool isNegative = false;
if (*nextChar == CharNegative) {
isNegative = true;
nextChar++;
}
result = 0;
while (*nextChar >= '0' && *nextChar <= '9')
result = result * 10 + (*nextChar++ - '0');
if (*nextChar != Char.MinValue) return false;
long ptrLen = nextChar - cString;
if (isNegative) {
result = -result;
return ptrLen < 11L || ptrLen <= 11L && result <= 0;
}
return ptrLen < 10L || ptrLen <= 10L && result >= 0;
}
}
}
Shoutout to @chux who gave me many good suggestions while reviewing our custom Double parser at Custom double parser optimized for performance .
With comments
Here it is with comments, because I'm not a monster (at least not that kind of monster):
// High performance integer parser with rudimentary flexibility.
// Supports leading negatives, but no white-space or other non-numeric characters.
public static unsafe bool FastTryParseInt(string input, out int result)
{
fixed (char* cString = input) { // Allows pointer math
unchecked { // Allows faster integer math by not testing for overflows
char* nextChar = cString;
bool isNegative = false;
// Handle a possible negative sign at the beginning of the string.
if (*nextChar == CharNegative)
{
isNegative = true;
nextChar++;
}
// Now process each character of the string
result = 0;
while (*nextChar >= '0' && *nextChar <= '9')
result = result * 10 + (*nextChar++ - '0');
// If the non-numeric character encountered to end the while loop
// wasn't the null terminator, the string is invalid.
if (*nextChar != Char.MinValue) return false;
// We need to check for an integer overflow based on the length of the string
long ptrLen = nextChar - cString;
// Result and overflow logic is different if there was a minus sign.
if (isNegative)
{
result = -result;
// Less than 11 characters (including negative) is no risk of overflow
// Longest possible negative int is 11 chars (-2147483648)
// If exactly 11 characters, we know our negative integer overflowed
// if the final result is greater than zero, otherwise it's fine.
return ptrLen < 11L || ptrLen <= 11L && result <= 0;
}
// Otherwise, overflow logic is the same, but opposite, and one fewer
// characters is allowed (because there was no minus sign)
return ptrLen < 10L || ptrLen <= 10L && result >= 0;
}
}
}
This is ~6x faster than a billion calls to Int.TryParse.
Native parser took 13808 ms. Custom parser took 2191 ms. Performance gain was 530%
Unsafe? Gross!
I tried getting as close as I could to the above algorithm without using unsafe, and to my surprise, it's about as good. It made me sad, because I was proud of my pointer math:
public static bool FastTryParseIntOld(string input, out int result)
{
result = 0;
int length = input.Length;
if (length == 0) return false;
bool isNegative = false;
int currentIndex = 0;
char nextChar = input[0];
unchecked
{
if (nextChar == CharNegative)
{
isNegative = true;
++currentIndex;
}
while (currentIndex < length)
{
nextChar = input[currentIndex++];
if (nextChar < '0' || nextChar > '9') return false;
result = result * 10 + (nextChar - '0');
}
if (isNegative)
{
result = -result;
return length < 11 || length <= 11 && result <= 0;
}
return length < 10 || length <= 10 && result >= 0;
}
}
Native parser took 13727 ms. Custom parser took 2377 ms. Performance gain was 477%
Frequently Asked Questions
Is Double.Parse really your performance bottleneck?
Yes! We benchmarked it in release mode and everything. We're ripping through billions of strings loaded into memory from a super-fast CSV reader, and calling native Double.TryParse was around ~70% of our execution time. More than I/O even.
Then why are you using C#?
It's much nicer for the 100 other things our app has to do that aren't performance critical.
What's your benchmark code?
Here it is. I'm pretty sure it's a good measure:
const int iterations = 100000000;
string[] randomIntegers = Enumerable.Repeat(0, iterations )
.Select(i => generateRandomInput()).ToArray();
CultureInfo cachedCulture = CultureInfo.CurrentCulture;
Stopwatch timer = Stopwatch.StartNew();
foreach (string value in randomIntegers)
Int32.TryParse(value, nativeNumberStyles, cachedCulture, out T _);
Console.WriteLine($"Native parser took {timer.ElapsedMilliseconds} ms.");
timer.Restart();
foreach (string value in randomIntegers)
FastTryParseInt(value, out T _);
Console.WriteLine($"Custom parser took {timer.ElapsedMilliseconds} ms.");
Compiled and run as "Release|Any CPU" on a 64 bit machine.
My Question
Can we do better? Did I miss something in unsafe mode that can make it way better than boring, safe C#?
