[.NET] Should I roll my own version of ParseInt32?

Question

I am writing a high performance parser, and it seems to me that Int32.Parse can be too slow. I wrote a simple version that assumes correct input, and it's performing much better. So should I create my own version instead? Or is there another faster method already available?

My method is like this:

// parse simple int, assuming relatively correct input (i.e. all digits)
public static int ParseInt32Simply(string str) {
    if (str == null) throw new ArgumentNullException("str");
    if (str.Length == 0) throw new ArgumentException("str is empty");

    int sign = 1, index = 0;
    if (str[0] == '-') { sign = -1; index = 1; }
    else if (str[0] == '+') { index = 1; }

    int result = 0;
    for (; index < str.Length; ++index) {
        result = 10 * result + (str[index] - '0');
    }

    if (result < 0) throw new OverflowException(str + " is too large for Int32");

    return result * sign;
}

My results are very different from the builtin equivalent:

Int32.Parse      took 8.2775453 seconds
ParseInt32Simply took 0.6511523 seconds
Int32.Parse      took 6.7625807 seconds
ParseInt32Simply took 0.4677390 seconds

(Running 25 million iterations on my machine; a P4 3 GHz, running VS 2008 SP1)

So, should I use my version? Or is there another method available that I can use?

Answer 1

Have you profiled your code yet to determine that ParseInt32 is actually the bottleneck? I wouldn't replace something that's part of the "standard library" of the environment you're coding in unless you know for certain that you're going to see a benefit.

Answer 2

I think the main problem here is your sentence assumes correct input. From reading your code, it doesn't appear to handle "12x" properly.

There's lots of things that Int32.Parse does to validate the input, and might even take note of your culture to handle some culture-differences, although I can't think of any specifically for Int32.

You're sure that the bottleneck is Int32 in your code?

Answer 3

The validation for null and empty string is not enough, you should check if parameter is valid integer.

Answer 4

My view would be that if the time savings you are getting are significant and of benefit for your application, then go for it.

We had a vaguely similar issue with XML parsing and opted to do it manually for performance reasons, but it was based on a known environment - we were feeding the XML, so we could fairly safely take shortcuts in the parsing.

Obviously the risk is that it is not likely to be complete as the standard library version and so new developers to the team will need to be made aware of this, lest they do something to break it.

Answer 5

how does your test look like? It seems your test is not ok.

I only have a small difference when I loop 50000 times and then I have a difference of about 30K ticks in favour of your custom method, but that is neglectable for the advantages of the normal method

Answer 6

In .net Int32.Parse is very very quick, when it's successful.

When it fails it throws an exception - then it's very slow because exceptions are slow.

You need to expand your test - you need to check times for a pattern of good and bad strings that's similar to what you need it to do.

If you are pretty sure that all your strings are valid ints then Int32.Parse is the way to go. If you suspect that any more than a negligible few are going to be valid then it is much quicker to use Int32.TryParse, rather than a try-catch in your loop.

Typically if your try-catch is outside the loop use Int32.Parse - you'll get an exception and stop the first time you get an invalid value.

If your try-catch is inside the loop use Int32.TryParse instead.

Both Int32.Parse and Int32.TryParse are pretty highly optimised and are relatively mature - I'd expect them to be very tough to improve on unless you have specialist circumstances.

Answer 7

How do you measure the speed? I tried this:

Stopwatch sw = new Stopwatch();
Random rand = new Random();

for (int n = 0; n < 10; n++)
{
    sw.Start();
    for (int i = 0; i < 1000000; i++)
    {
        ParseInt32Simply(rand.Next().ToString());
    }
    sw.Stop();
    Console.WriteLine(sw.Elapsed.Ticks + " - ParseInt32Simply");
    sw.Reset();

    sw.Start();
    for (int i = 0; i < 1000000; i++)
    {
        int.Parse(rand.Next().ToString());
    }
    sw.Stop();
    Console.WriteLine(sw.Elapsed.Ticks + " - int.Parse");
    sw.Reset();
    Console.WriteLine();
}

and the results are quite different:

2932852 - ParseInt32Simply
4684522 - int.Parse

3003988 - ParseInt32Simply
4666928 - int.Parse

2892545 - ParseInt32Simply
4660209 - int.Parse

2888998 - ParseInt32Simply
4636007 - int.Parse

2955727 - ParseInt32Simply
4668501 - int.Parse

2929210 - ParseInt32Simply
4653799 - int.Parse

2893706 - ParseInt32Simply
4671503 - int.Parse

2899547 - ParseInt32Simply
4633957 - int.Parse

Your simple method is still faster, but less than 2x (that is very good performance actually!).

Answer 8

Yes - you can use your own version of parsing int as long that you are 100% certain that the source data is something you have control over (and thus always conforms to your format of Int32). Also, you should use your own code isolated from the rest of the world because if you've got this in some library you're publishing, people might want to have the standard behaviour of Int32.Parse. If you can't provide it, it's no good for them. However, as many people here suggests, you should really be certain that this is what really needs doing if you're trying to squeeze out the most of your performance. However, you probably know your own code better than anyone here.

Personally I would try and avoid changing parsing. IF there are other bottlenecks then those might be worth investigating first.

Answer 9

If your tests are verifiable and you truly need the performance gains (e.g. you call the function like tens of thousands of times a second) than go for it.

I would just change the name... because ParseInt32Simply does not tell the maintenance programmer anything. I think a name like TrustedSourceInt32Parse or GuaranteedInt32Parse or something along those lines is a better name.

Answer 10

If your parsing a format of which you know to be valid numbers, you can indeed write a faster custom parser. I've written a Double.Parse function for the same purpose once. And it faster to begin with the least significant digit. That way you can just increment the power of the digit your parsing.

I've created a quick implementation of this,

public static Int32 ParseValidNumberAsInt32(string str)
{
    if (str == null) 
     throw new ArgumentNullException("str");
    if (str.Length == 0) 
     throw new ArgumentException("str is empty");
    Int32 result = 0;
    Int32 currentPower = 1;
    Boolean isNegative = str[0] == '-';

    for (int currentCharIndex = str.Length - 1; currentCharIndex > 0; currentCharIndex--)
    {
     result += (str[currentCharIndex] - '0') * currentPower;
     currentPower *= 10;
    }
    return isNegative ? -1 * result : result + ((str[0] - '0') * currentPower);
}

If you really want speed, you can write a unsafe implementation..

If your parsing a big file, you could read the files as raw bytes and work with those. That will make it a lot faster (no converting to unicode string, no splitting the strings in lines, no splitting the lines in substrings, no parsing the substrings), but you're going to lose maintainability.

Answer 11

Take a look at this blog entry: Fast string to integer conversion by Karl Seguin.