Could you please review my Quick Int Parser implementation?

Question

I wrote some utility methods that can parse a 32-bit signed integer much faster than Int32.Parse. I hope you could give me some of your experience by reviewing my code and suggesting enhancements or pointing out bugs. If you are interested (and have the time of course), I would be very grateful.

I have posted my code on the "Refactor My Code" website. Here is the link: http://refactormycode.com/codes/699-int32-quick-parser

Thank you.

---

Edit: Thanks everybody for your helpful suggestions. I have followed your ideas, and here is the updated version: http://refactormycode.com/codes/699-int32-quick-parser#refactor_142758

(Please use a diff utility to see the changed code lines.)

Thank you!

Answer 1

One though; consider renaming the class; calling it Int32 is just asking for trouble, although you get a bit of scope here because it is nested (Numbers.Int32). I wouldn't get too excited about this, though (the nesting does save a lot of pain for the consumer).

Don't call arguments thing like str - that isn't meaningful. That said, int.Parse calls it s, so I can't be too critical.

But I've got to grant you, a 10x performance figure isn't bad ;-p (although it only supports one format, of course).

One other thing; a start and length is a more common pattern than a start and end.

Finally - is there an off-by-one in the ParseSimple checks?

if (end > str.Length) throw new ArgumentOutOfRangeException("end");

Shouldn't that be >=? If length is 1, end can only be 0?

Answer 2

So if you have parse trusted, then maybe you should consider implementing ParsePositive ParseNegative

And you should be watching the IL while editing your code

Answer 3

One somewhat bizarre thought: rather than subtracting '0' on every iteration, you could have a precalculated amount to subtract at the very end, depending on the number of digits. (length=1, subtract '0'; length=2, subtract ('0'*10 + '0')). You may well only be able to get away with this for relatively short strings though, due to overflow. (Or use a long, but that may slow it down too much.)

Also, I haven't tried it, but you might check whether

result = (result << 3) + result + result + [...]

or

result = (result << 3) + (result << 1) + [...]

is faster than

result = result*10 + [...]

I suspect that it won't be, but it may be worth at least trying. (Certainly bitshifting is faster than multiplying, but I suspect the extra additions involved counterbalance this.)

Have you profiled the code to see where any bottlenecks are?

Do you have any benchmark results of how much faster this is than Int32.Parse, btw?

Answer 4

I think your implementation is pretty decent. I've made an unsafe version using pointer math, which is indeed faster, but is dirtier in my opinion.

Results (running 30 samples of 10M random int strings):

Int32.Parse                      1766.17 ms (stddev: 1.83 ms)
Numbers.Int32.ParseTrusted       262.07 ms (stddev: 0.44 ms)
ParseTrustedUnsafe               146.13 ms (stddev: 0.43 ms)

here is my unsafe implementation:

public static unsafe int ParseTrustedUnsafe(string str, int start, int end)
{
    unsafe
    {
     Int32 result = 0;
     Int32 length = end - start;
     Boolean isNegative = false;
     fixed (Char* startChar = str)
     {
      Byte* currentChar = ((Byte*)startChar) + (start * 2);
      if (*currentChar == 0x2D)
      {
       isNegative = true;
       currentChar += 2;
       length--;
      }
      else if (*currentChar == 0x2B)
      {
       currentChar += 2;
       length--;
      }
      while (length >= 4)
      {
       result = (result * 10) + (*currentChar - 0x30);
       result = (result * 10) + (*(currentChar + 2) - 0x30);
       result = (result * 10) + (*(currentChar + 4) - 0x30);
       result = (result * 10) + (*(currentChar + 6) - 0x30);

       currentChar += 8;
       length -= 4;
      }
      while (length > 0)
      {
       result = (result * 10) + (*currentChar - 0x30);

       currentChar += 2;
       length -= 1;
      }
     }
     return isNegative ? -result : result;
    }
}

Below is my validation and benchmark program:

static void Main(string[] args)
{
    String[] testValues = new String[10 * 100 * 100 * 100];
    Random rand = new Random();
    for (int i = 0; i < testValues.Length; i++)
    {
     testValues[i] = rand.Next().ToString();
    }
    // validate
    for (int i = 0; i < testValues.Length; i++)
    {
     Debug.Assert(String.CompareOrdinal(testValues[i], ParseTrustedUnsafe(testValues[i], 0, testValues[i].Length).ToString()) == 0, "ParseTrustedUnsafe failed on " + testValues[i]);
     Debug.Assert(String.CompareOrdinal(testValues[i], Numbers.Int32.ParseTrusted(testValues[i], 0, testValues[i].Length).ToString()) == 0, "Numbers.Int32.ParseTrusted failed on " + testValues[i]);
    }
#if DEBUG
    return;
#endif    
    List<List<Double>> results = new List<List<double>>();
    for (int i = 0; i < 3; i++)
    {
     results.Add(new List<double>());
    }

    Thread.CurrentThread.Priority = ThreadPriority.Highest;
    Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.RealTime;
    if (Environment.ProcessorCount > 1)
    {
     Process.GetCurrentProcess().ProcessorAffinity = new IntPtr(1 << (Environment.ProcessorCount - 1)); // use last core only
    }
    Stopwatch sw = new Stopwatch();
    for (int testrun = 0; testrun < 30; testrun++)
    {
     sw.Reset();
     sw.Start();
     for (int i = 0; i < testValues.Length; i++)
     {
      Int32.Parse(testValues[i]);
     }
     sw.Stop();
     results[0].Add(sw.ElapsedMilliseconds);

     sw.Reset();
     sw.Start();
     for (int i = 0; i < testValues.Length; i++)
     {
      Numbers.Int32.ParseTrusted(testValues[i]);
     }
     sw.Stop();
     results[1].Add(sw.ElapsedMilliseconds);

     sw.Reset();
     sw.Start();
     for (int i = 0; i < testValues.Length; i++)
     {
      ParseTrustedUnsafe(testValues[i], 0, testValues[0].Length);
     }
     sw.Stop();
     results[2].Add(sw.ElapsedMilliseconds);

    }
    Console.WriteLine("Int32.Parse \t\t\t {0:0.00}ms (stddev: {1:0.00}ms)", results[0].Average(), StandardDeviation(results[0]));
    Console.WriteLine("Numbers.Int32.ParseTrusted \t {0:0.00}ms (stddev: {1:0.00}ms)", results[1].Average(), StandardDeviation(results[1]));
    Console.WriteLine("ParseTrustedUnsafe \t\t {0:0.00}ms (stddev: {1:0.00}ms)", results[2].Average(), StandardDeviation(results[2]));
}

private static double StandardDeviation(IEnumerable<double> doubleList)
{
    double average = doubleList.Average();
    double sumOfDerivation = 0;
    foreach (double value in doubleList)
    {
     sumOfDerivation += (value) * (value);
    }
    double sumOfDerivationAverage = sumOfDerivation / doubleList.Count();
    return Math.Sqrt(sumOfDerivationAverage - (average * average));
}