22
\$\begingroup\$

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;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ I note that you do not parse doubles in exponential format, you do not parse infinities, and so on. Is this intentional? \$\endgroup\$ – Eric Lippert Jan 6 '15 at 14:41
  • \$\begingroup\$ @EricLippert yes it is, my input data is or a real number (no concept like infinity) or an error (like a bunch of letter or mis-formated number) \$\endgroup\$ – Thomas Ayoub Jan 6 '15 at 14:58
  • \$\begingroup\$ If you really want to get more performance you could try to experiment with branching/branch prediction. The custom return-statements can probably slow you down, so you could try to set an error-variable to true inside the loop, but keep parsing and return error afterwards... Branch prediction, instruction pipelining and caching can do wonders on simple for-loops with huge iteration-count so you could try a little around there... \$\endgroup\$ – Falco Jan 7 '15 at 9:21
  • \$\begingroup\$ You should look at my answer, I have now removed output as double to make sure there is no possible floating error introduced. I now use 2 long variables. \$\endgroup\$ – Fredou Jan 8 '15 at 15:03
  • \$\begingroup\$ This question could have gone to code golf too :) \$\endgroup\$ – JimmyB Jan 8 '15 at 15:40
12
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Well that's a nice answer in many points! Any idea about performance...? \$\endgroup\$ – Thomas Ayoub Jan 6 '15 at 12:09
  • \$\begingroup\$ For performance I recommend chucking into visual studio's profiler first, it'll be able to help you see where you're spending most of your processing time. If you put the results up here we'll be able to better help you. \$\endgroup\$ – Nick Udell Jan 6 '15 at 12:13
  • \$\begingroup\$ about the name of local variable, I found out that it does matter how long the name is also that is why you can see better speed after code obfuscation, all variable name are changed into a,b,c,d,etc. long parameter name DO NOT matter speed wise. \$\endgroup\$ – Fredou Jan 6 '15 at 15:26
  • 1
    \$\begingroup\$ No, it doesn't: stackoverflow.com/questions/2443164/… The compiler is stripping your variables down anyway, so you should use as many characters as you need to get the information across. \$\endgroup\$ – Nick Udell Jan 6 '15 at 15:28
  • \$\begingroup\$ I agree with the OP's decision to use a private static function, rather than a public member of a utility class. This kind of optimization tends to be pretty tightly focused, so it probably doesn't need to be used in more than one place. Since the optimizations involved are not always safe (fails to handle various cases that double.Parse and double.TryParse can handle properly), it should only be used in the special case where the OP found it to be absolutely necessary. \$\endgroup\$ – Brian Jan 7 '15 at 14:07
10
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ That's cool :) but still no perf optimization \$\endgroup\$ – Thomas Ayoub Jan 6 '15 at 12:49
  • \$\begingroup\$ You can do things like optimize the calculation of the exp arg to CustomPow which makes a difference on Debug but in Release gets optimized out anyway by the looks of it. \$\endgroup\$ – RobH Jan 6 '15 at 13:14
  • \$\begingroup\$ (c ^ '0') > 9 should be about 20% faster than c < '0' || c > '9' because of branch misprediction (the less comparisons the better and char.IsDigit does about 3 comparisons per non-unicode digit) \$\endgroup\$ – Slai Jan 13 '17 at 15:18
  • \$\begingroup\$ @Slai Have you tested that? For well formed numbers, the branch is always false which is ideal for prediction. \$\endgroup\$ – RobH Jan 13 '17 at 16:46
  • 1
    \$\begingroup\$ @RobH I was just testing it for this answer stackoverflow.com/a/41639665/1383168 with decimal digits only. \$\endgroup\$ – Slai Jan 13 '17 at 16:58
8
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Well as exp is never (in my case) higher than 7 I used a switch statment with multiplication in the place of the for loop \$\endgroup\$ – Thomas Ayoub Jan 7 '15 at 9:18
  • 1
    \$\begingroup\$ You'd actually want to store the reciprocal (pow10[i] = 1/p;) so that you're multiplying (fast) instead of dividing (slow). \$\endgroup\$ – Gabe Jan 8 '15 at 7:07
5
\$\begingroup\$

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;
}
\$\endgroup\$
  • 2
    \$\begingroup\$ Well I suggest you a bit of reading about this, I was also surprised! \$\endgroup\$ – Thomas Ayoub Jan 6 '15 at 13:43
  • \$\begingroup\$ I cannot reproduce the article's performance results. In my test environment bitwise is always faster than a modulus operator, in Debug mode and also in the Release mode. \$\endgroup\$ – kerem Jan 6 '15 at 13:46
  • \$\begingroup\$ Then I'll test it :) \$\endgroup\$ – Thomas Ayoub Jan 6 '15 at 13:47
  • 1
    \$\begingroup\$ what about saving some time by calculating pow as 0.1, 0.01, ... and multiplying with the lookup? Multiply is faster than division on many systems.... \$\endgroup\$ – Falco Jan 7 '15 at 10:21
  • 4
    \$\begingroup\$ Looking into intel.com/content/www/us/en/architecture-and-technology/… I find that on current Intel CPUs FDIV is about 39 clock cycles while FMUL needs only 1. Potentially saving 38 CPU cycles per number, for 1 billion numbers @ 3.8 GHz multiplication could save a total 10 seconds of CPU time over division. \$\endgroup\$ – JimmyB Jan 7 '15 at 11:02
5
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ Nice one! In my data, the exp is never > 7, I don't deal with big number \$\endgroup\$ – Thomas Ayoub Jan 7 '15 at 13:21
  • \$\begingroup\$ Just note that the absolute magnitude of the number does not matter, only the length of the string; my examples are all equal to one, just written in a roundabout way with a lot of decimal places. \$\endgroup\$ – Mormegil Jan 7 '15 at 13:31
  • \$\begingroup\$ your algorithm have rounding issue i think, if you use my main code in my answer and replace my parse with your parse, there is error like this showing up: input: 78.1784928767842 output:78.1784928767841, input: 87.5688321364898 output:87.5688321364897, input: -68.6253328195891 -68.625332819589, etc... \$\endgroup\$ – Fredou Jan 7 '15 at 15:01
  • \$\begingroup\$ @Thomas, don't forget to do quality check with my answer or any others answers to be sure what get in get properly out. \$\endgroup\$ – Fredou Jan 7 '15 at 15:05
  • \$\begingroup\$ This algorithm does have rounding problems due to inexactness of floating point numbers. Each time you calculate result += (c - '0') * exp you introduce a bit more error. \$\endgroup\$ – RobH Jan 7 '15 at 16:28
5
\$\begingroup\$

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();
        }
    }
}
\$\endgroup\$
  • 3
    \$\begingroup\$ If you are using a lookup table - why are you still using division? Multiplication is usually faster - so you should save 0.1, 0.01, ... in you array and multiply! \$\endgroup\$ – Falco Jan 7 '15 at 9:28
  • 1
    \$\begingroup\$ @Falco, I made the change and it does help. \$\endgroup\$ – Fredou Jan 7 '15 at 14:51
  • \$\begingroup\$ @Fredou Could you try and check if changing double output = 0.0; to int output = 0; makes a difference? \$\endgroup\$ – JimmyB Jan 7 '15 at 17:19
  • 1
    \$\begingroup\$ @Falco I was doing all my testing under 32bits (anycpu) :-) doing it under 64bits change things :-) \$\endgroup\$ – Fredou Jan 8 '15 at 14:04
  • 1
    \$\begingroup\$ @Falco, I have updated my code which now I think is way better than before \$\endgroup\$ – Fredou Jan 8 '15 at 14:57
2
\$\begingroup\$

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...

\$\endgroup\$
2
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ Well I've got this piece of code if (!char.IsDigit(c)) return Double.NaN; which will kill your phrase down :p but +1 for space separator ! (which I'll not consider as it's not in my data) \$\endgroup\$ – Thomas Ayoub Jan 7 '15 at 8:16
  • \$\begingroup\$ Ahh you're right. I overlooked that. Probably due to a lack of brackets there... Will update my answer when I have a sec. \$\endgroup\$ – RubberDuck Jan 7 '15 at 11:05
  • \$\begingroup\$ He's accepting either a period or comma as decimal point, not a group separator - his code has no support at all for group separators. \$\endgroup\$ – Random832 Jan 7 '15 at 20:59
  • \$\begingroup\$ @Random832 doesn't that mean a string like "200,123.45" would break the code? \$\endgroup\$ – RubberDuck Jan 7 '15 at 22:48
  • 1
    \$\begingroup\$ @RubberDuck yes, it would. He apparently doesn't have any strings like that. This is apparently meant to be very specialized for a specific dataset, not a general parsing function. Honestly, I'm more surprised he's bothering to handle both possible decimal points at all. \$\endgroup\$ – Random832 Jan 8 '15 at 16:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.