Optimize custom double.parse()

Question

In my company's code, they use double.tryParse() which is quite good but sets too much security for our needs. As we sometimes have to parse a few billion strings, I came up with this code which is a little bit faster (10%) but I have the feeling that it's not at its best... Unfortunately, this kind of stuff require more knowledge than I have.

private static double GetDoubleValue(string input)
{
    double n = 0;
    int decimalPosition = input.Length;
    bool separatorFound = false;
    bool negative = input[0] == '-';
    for (int k = (negative ? 1 : 0); k < input.Length; k++)
    {
        char c = input[k];

        if (c == '.' || c == ',')
        {
            if (separatorFound)
                return Double.NaN;
            decimalPosition = k + 1;
            separatorFound = true;
        }
        else
        {
            if (!char.IsDigit(c))
                return Double.NaN;
            n = (n * 10) + (c - '0');
        }
    }
    return ((negative ? -1 : 1) * n) / CustomPow(10, input.Length - decimalPosition);
}

private static double CustomPow(int num, int exp)
{
    double result = 1.0;
    while (exp > 0)
    {
        if (exp%2 == 1)
            result *= num;
        exp >>= 1;
        num *= num;
    }
    return result;
}

Answer 1

Naming

Avoid single-letter or shortened form variable names. Extra characters on a variable's name are free, and work wonders for a maintenance programmer down the line.

e.g.

double n = 0;

would better be:

double output = 0;

Additionally, I'm not sold on the name GetDoubleValue. At no point does this method retrieve the value from anywhere. What this method does is conversion, so it should be appropriately named as such.

Var

Use the var keyword when defining local variables where the right hand side of the definition makes the type obvious. This looks cleaner and saves time when it comes to changing types during refactoring.

e.g.

bool separatorFound = false;

should be

var separatorFound = false;

You should also use var when declaring foreach and for loop iterators.

e.g.

for (int k = (negative ? 1 : 0); k < input.Length; k++)

should be:

for (var k = (negative ? 1 : 0); k < input.Length; k++)

Braces

Always use braces for if statement bodies. It's cleaner, more explicit in intent, and it's quicker should you later decide to add extra lines to the body.

e.g.

if (!char.IsDigit(c))
    return Double.NaN;

should be:

if (!char.IsDigit(c))
{
    return Double.NaN;
}

Design

Why have you created the function CustomPow when all you're really doing is repeatedly multiplying by 10? It seems this is a case of over-abstraction, unless you plan to use the method elsewhere too.

Why make GetDoubleValue private? It sounds like a useful function you may want to use elsewhere or in other projects. I suspect it's private because it is in a class it does not belong in, and you don't want somebody calling StringLoader.GetDoubleValue or something like that.

Put it in a utility class or an extension method somewhere, it doesn't make sense as a method of your string loader class or whatever.

Answer 2

Nick's answer is great for style points, I just wanted to make you aware of a bug in your implementation:

char.IsDigit(c) will return true for numerical digits not in the Western Arabic numerals (0 1 2 3 4 5 6 7 8 9). It's obscure but it will cause your program to fail. E.g.

var answer = GetDoubleValue("12345०7.56"); // DEVANAGARI DIGIT ZERO
// answer = 1258087.56 

You are assuming 0-9 only (c - '0') so you should only allow them. I.e. change

if (!char.IsDigit(c))
    return Double.NaN;

to

if (c < '0' || c > '9')
{
    return Double.NaN;
}

I've also added braces as I prefer that.

Edit:

Modifying to not use char.IsDigit shaves about 1% off execution time (mileage may vary).

Further edit:

Accidentally ran the test for speed comparison on Debug. Running on Release with no debugger 10 million iterations averaged over 5 runs:

With char.IsDigit - 311ms
With c < '0' || c > '9' - 287ms

Answer 3

You could try and optimize your CustomPow(int num, int exp) by pre-computing some/all possible values only once:

double[] pow10 = new double[309];

double p = 1.0;
for ( int i = 0; i < 309; i++ ) {
  pow10[i] = p;
  p = p * 10;
}

Then CustomPow10( int exp ) would just return pow10[exp].

Edit:

By the way, I see that you are basically building an integer representation first (in n). - Why not declare n as long integer then? This would operate on an integer most of the time, which should be faster than floating point, and only at the end, when finally dividing by the power of 10, a floating point number is needed.

Edit2: This only works if all your input numbers have less than 18 digits since that's the maximum number of digits a long can represent.

Edit3: Please see @Fredou's answer for the result of combined efforts. I think his code will perform really well by now.

Answer 4

This example includes the style suggestions of @nick and @RobH together with performance enhancements, namely using bitwise AND operation instead of the modulus operation.

private static double GetDoubleValue(string input)
{
    double output = 0;
    int inputLength = input.Length;
    int decimalPosition = inputLength;
    var hasSeperator = false;
    var isNegative = input[0] == '-';

    for (int k = (isNegative ? 1 : 0); k < inputLength; k++)
    {
        char currentCharacter = input[k];

        if (currentCharacter == '.' || currentCharacter == ',')
        {
            if (hasSeperator)
            {
                return Double.NaN;
            }
            else
            {
                hasSeperator = true;
            }

            decimalPosition = k + 1;
        }
        else
        {
            var digitValue = currentCharacter - '0';

            if (digitValue < 0 || digitValue > 9)
            {
                return Double.NaN;
            }

            output = (output * 10) + digitValue;
        }
    }

    var powDividend = CustomPow(10, inputLength - decimalPosition);
    var integer = ((isNegative ? -1 : 1) * output);

    return integer / powDividend;
}

private static double CustomPow(int num, int exp)
{
    double result = 1.0;

    while (exp > 0)
    {
        if ((exp & 1) == 1)
        {
            result *= num;
        }

        exp >>= 1;
        num *= num;
    }

    return result;
}

Answer 5

Two comments regarding your algorithm:

Note that your algorithm can introduce errors in borderline cases like "1.00000000000000000000000000000000" which is parsed to Infinity, or "1.0000000000000000" which is parsed to 5333562.5371386623 (!).

Especially the second behavior is caused by a bug in your CustomPow function which keeps num as int, which can overflow easily for exponents above 16 (CustomPow(10, 16) returns 1874919424).

But even if this is fixed, extremely borderline cases like GetDoubleValue("1." + new string('0', 310)) return Infinity. (Note that Fredou’s solution is worse here, it dies with IndexOutOfRangeException.)

(The problem is that you are composing the whole number without regard to decimal separator, which might overflow prior to the final division.)

Improved algorithm, which also has better performance (by my experiments, ~30 % better than your original, ~20 % better than Fredou’s):

private static double QuickDoubleParse(string input)
{
    double result = 0;
    var pos = 0;
    var len = input.Length;
    if (len == 0) return Double.NaN;
    char c = input[0];
    double sign = 1;
    if (c == '-')
    {
        sign = -1;
        ++pos;
        if (pos >= len) return Double.NaN;
    }

    while (true) // breaks inside on pos >= len or non-digit character
    {
        if (pos >= len) return sign * result;
        c = input[pos++];
        if (c < '0' || c > '9') break;
        result = (result * 10.0) + (c - '0');
    }

    if (c != '.' && c != ',') return Double.NaN;
    double exp = 0.1;
    while (pos < len)
    {
        c = input[pos++];
        if (c < '0' || c > '9') return Double.NaN;
        result += (c - '0') * exp;
        exp *= 0.1;
    }
    return sign * result;
}

The algorithm parses the integral and fractional parts separately. I have also tried to implement it using unsafe features, but the improvement is inconclusive, but you may try:

private unsafe static double UnsafeQuickDoubleParse(string input)
{
    double result = 0;
    var len = input.Length;
    if (len == 0) return Double.NaN;
    double sign = 1;
    fixed (char* pstr = input)
    {
        var end = (pstr + len);
        var pc = pstr;
        char c = *pc;
        if (c == '-')
        {
            sign = -1;
            ++pc;
            if (pc >= end) return Double.NaN;
        }

        while (true) // breaks inside on pos >= len or non-digit character
        {
            if (pc >= end) return sign * result;
            c = *pc++;
            if (c < '0' || c > '9') break;
            result = (result * 10.0) + (c - '0');
        }

        if (c != '.' && c != ',') return Double.NaN;
        double exp = 0.1;
        while (pc < end)
        {
            c = *pc++;
            if (c < '0' || c > '9') return Double.NaN;
            result += (c - '0') * exp;
            exp *= 0.1;
        }
    }
    return sign * result;
}

Answer 6

I changed the if logic to remove some branching I think, can you test on your side?

Also using the cache suggestion of Hanno Binder

Not using any double during string processing, only when returning the final result.

I'm gaining about 50% speed and it seem to still return proper value

Compile as Release under 64bits

using System;

namespace ConsoleApplication1
{
    class Program
    {
        private readonly static double[] pow10Cache;
        static Program()
        {
            pow10Cache = new double[309];

            double p = 1.0;
            for (int i = 0; i < 309; i++)
            {
                pow10Cache[i] = p;
                p /=  10;
            }
        }

        private static double GetDoubleValue(string input)
        {
            long inputLength = input.Length;
            long digitValue = long.MaxValue;
            long output1 = 0;
            long output2 = 0;
            long sign = 1;
            double multiBy = 0.0;
            int k;

            //integer part
            for (k = 0; k < inputLength; ++k)
            {
                digitValue = input[k] - 48; // '0'

                if (digitValue >= 0 && digitValue <= 9 )
                {
                    output1 = digitValue + (output1 * 10);
                }
                else if (k == 0 && digitValue == -3 /* '-' */)
                {
                    sign = -1;
                }
                else if (digitValue == -2 /* '.' */ || digitValue == -4 /* ',' */)
                {
                    break;
                }
                else
                {
                    return Double.NaN;
                }
            }

            //decimal part
            if (digitValue == -2 /* '.' */ || digitValue == -4 /* ',' */)
            {
                multiBy = pow10Cache[inputLength - (++k)];

                for (; k < inputLength; ++k)
                {
                    digitValue = input[k] - 48; // '0'

                    if (digitValue >= 0 && digitValue <= 9)
                    {
                        output2 = digitValue + (output2 * 10);
                    }
                    else
                    {
                        return Double.NaN;
                    }
                }

                multiBy *= output2;
            }

            return sign * (output1 + multiBy);
        }

        static void Main(string[] args)
        {
            Console.Write("Preparing values to test ");
            var rnd = new Random(42);
            var test = new string[10000000];
            double value;
            for (int i = 0; i < 10000000; ++i)
            {
                value = rnd.NextDouble() * 10000;
                value *= value;
                value += rnd.NextDouble();
                value *= (i % 2) == 0 ? 1 : -1;

                test[i] = value.ToString();

                if ((i % 1000000) == 0)
                {
                    Console.Write(".");
                }
            }

            Console.WriteLine(" benchmarking them");
            for (int a = 1; a < 5; ++a)
            {
                var sw = System.Diagnostics.Stopwatch.StartNew();
                for (int i = 0; i < 10000000; ++i)
                {
                    GetDoubleValue(test[i]);
                }
                sw.Stop();
                Console.WriteLine("Run {0} took {1}ms",a,sw.ElapsedMilliseconds);
            }

            bool anyError = false;
            int errorCount = 0;
            Console.Write("Any error? ");
            for (int i = 0; i < 10000000; ++i)
            {
                if (!string.Equals(GetDoubleValue(test[i]).ToString(), test[i]))
                {
                    if (!anyError)
                    {
                        Console.WriteLine(" Yes");
                        anyError = true;
                    }

                    errorCount++;
                    Console.WriteLine("{0} = {1} = {2}", GetDoubleValue(test[i]), test[i], string.Equals(GetDoubleValue(test[i]).ToString(), test[i]));
                    if (errorCount >= 10)
                    {
                        break;
                    }
                }
                if ((i % 1000000) == 0)
                {
                    Console.Write(".");
                }
            }

            Console.WriteLine(" {0}", anyError ? "" : "No");

            Console.ReadKey();
        }
    }
}

Answer 7

I'm sorry I don't have enough time to write and benchmark everything, so here are just some ideas:

Some approaches to get more performance:

1. Use C# parallel execution mechanics if you are converting millions of Strings to doubles. The executions are all independent, so on a quad core you should roughly save 70% of your execution time on one core.

2. Operator optimizations: Since the parsing essentially comes down to a very basic loop which is executed very often you can try to micro-optimize thinking of the processor architecture. Multiplications are usually faster than divisions. Additions are even faster and shifts are fastest.

3. Pipelining/Branch prediction: You processor usually tries to overlap as many instructions as possible, if they are not dependent on each other. If you have branches the branch predictor tries to predict the outcome and if it is wrong you usually get a big performance penalty. In a loop you have a bottleneck if variables are written in one iteration and read in the next. But modern processors can even do fancy stuff like passing results from one calculation directly into the next.

So what could probably speed up the whole process would be to eliminate complex branching on dependent variables. Code will follow if I have the time...

Answer 8

It doesn't seem that anybody has mentioned this.

if (c == '.' || c == ',')

You seem to be making the assumption that any string containing a period or comma is able to be parsed into a double. How will your code react to me sending this string into it?

It seems this is a case of over-abstraction, unless you plan to use the method elsewhere too.

---

I was wrong about that, but that's because it wasn't clear what was going on. Why wasn't it clear? Lack of brackets.

if (c == '.' || c == ',')
{
    if (separatorFound)
        return Double.NaN;
    decimalPosition = k + 1;
    separatorFound = true;
}

Brackets would have made it instantly clear that you were returning and not just letting the code blithely stumble on. Heck, even a new line after the return statement would have cleared that up.

---

I'm not sure, but it doesn't seem to me that you considered that someone could/would pass some strange string into your method that would potentially break it.

You definitely didn't consider that many cultures use spaces as separators instead of commas. I don't know the right way to do what you're attempting, but I'm convinced that this isn't it.

---

I take it back that "I'm not sure you're considering strings that could break your method". You're definitely not. It turns out that you're not considering group separators at all. You probably should be. These are strings after all. These are numbers in a format that could be expected to be as people would write them. All of the following numbers in string format will break your code.

4 294 967 295,000 (Canadian)
4,294,967,295.000 (US - English)
4 294 967.295,000 (German)
4.294.967.295,000 (Norwegian)