6
\$\begingroup\$

I'm trying to beat the native Double.TryParse for performance in parsing large multi-million row (simple) CSV files as much as possible. I do not have to support exponential notation, thousand separators, Inf, -Inf, NaN, or anything exotic. Just millions of "0.##" format doubles.

Here's my best attempt, which is ~350% faster by my tests (64 bit release mode)

My Implementation

This is the setup of the function (mostly for context).

private static readonly char CharNegative = CurrentCulture.NumberFormat.NegativeSign[0];
private static readonly char CharDecimalSeparator =
    CurrentCulture.NumberFormat.NumberDecimalSeparator[0];

/// <summary>High performance double parser with rudimentary flexibility.
/// <returns>Returns true only if we can be certain we parsed the string correctly.
/// <remarks>Does not support exponential notation, thousand separators or whitespace.
/// Does not support Infinity, Negative Infinity, NaN, or detect over/underflows.
/// Supports only leading negative signs, no positive signs or trailing signs.</remarks>
public static bool FastTryParseDouble(string input, out double result)
{
    result = 0d;
    int length = input.Length;
    if (length == 0) return false;
    double sign = 1d;
    int currentIndex = 0;
    char nextChar = input[0];

    // Handle a possible negative sign at the beginning of the string.
    if (nextChar == CharNegative)
    {
        sign = -1d;
        ++currentIndex;
    }

As you can see, I try to remain culture aware and support negative numbers. This is the remainder of the method, which I think needs to be optimized for performance:

    unchecked
    {
        while (true)
        {
            // Return now if we have reached the end of the string
            if (currentIndex >= length)
            {
                result *= sign;
                return true;
            }
            nextChar = input[currentIndex++];
            // Break if the result wasn't a digit between 0 and 9
            if (nextChar < '0' || nextChar > '9') break;
            // Multiply by 10 and add the next digit.
            result = result * 10 + (nextChar - '0');
        }
        // The next character should be a decimal character, or else it's invalid.
        if (nextChar != CharDecimalSeparator) return false;
        double fractionalPart = 0d;
        int fractionLengh = length - currentIndex;
        while (currentIndex < length)
        {
            nextChar = input[currentIndex++];
            // If we encounter a non-digit now, it's an error
            if (nextChar < '0' || nextChar > '9') return false;
            fractionalPart = fractionalPart * 10 + (nextChar - '0');
        }
        // Add the fractional part to the result, apply sign, and return
        if (fractionLengh < NegPow10.Length)
            result = (result + fractionalPart * NegPow10[fractionLengh]) * sign;
        else
            result = (result + fractionalPart * Math.Pow(10, -fractionLengh)) * sign;
    }
    return true;
}

NegPow10 at the end there is just the following array, which has a quick lookup value to cover the first 20 or so values of 10^-n for quick reference. Anything bigger just falls back to Math.Pow()

/// <summary>A cache of negative powers of 10 for quick magnitude adjustment of parsed
/// decimals up to the maximum number of possible decimal places that might be consumed
/// from a string representation of a double.</summary>
private static readonly double[] NegPow10 = new double[]
{
    1d,
    0.1,
    0.01,
    ///... you get the idea
    0.0000000000000001
};

Test Cases

The following test cases are all passing:

TestSuccess("0", 0d);
TestSuccess("1", 1d);
TestSuccess("-1", -1d);
TestSuccess("123.45", 123.45);
TestSuccess("-123.45", -123.45);
TestSuccess("12345678901234", 12345678901234d);
TestSuccess("-12345678901234", -12345678901234d);
TestSuccess("0.12", 0.12);
TestSuccess("-0.12", -0.12);
TestSuccess("0.00", 0.00);
TestSuccess("-0.00", -0.00);
TestSuccess("1234567890123.01", 1234567890123.01);
TestSuccess("-1234567890123.01", -1234567890123.01);
TestSuccess("123456789000000000000000", 123456789000000000000000d);
TestSuccess("-123456789000000000000000", -123456789000000000000000d);

I also have the unsupported (failure) cases laid out if anyone's interested, but it's basically the limitations mentioned in the remarks above.


Benchmarks

I benchmarked my implementation against native Double.TryParse to guage the performance difference.

I tested parsing an array of 10 million different strings using:

Double.TryParse(value, NumberStyles.Float, cachedCulture, out _)

Note that I cache the culture instance and pass in explicit NumberStyles to get the native method as fast as possible before comparing it to my own. My method was of course running 10 million strings through:

Parsers.FastTryParseDouble(value, out _)

Results

Native Double.TryParse took ~4500 ms.

Custom Parsers.FastTryParseDouble took ~950 ms.

Performance gain was ~370%


Next Steps

See any other ways I can squeeze out more performance?

Any awful flaws that might cause incorrect results to be returned? Note that I'm always happy to return "false" for unsupported cases if that's what's fastest, but I'm not okay to return true and a bad result.

\$\endgroup\$
  • \$\begingroup\$ You missed 3 cases, , -∞ and NaN. These should parse out as Double.PositiveInfinity, Double.NegativeInfinity and Double.NaN. Actually there is one more, your tests should be able to parse the positive symbol, ie: +1234.5678 \$\endgroup\$ – Ron Beyer Jul 31 '18 at 1:34
  • 2
    \$\begingroup\$ You should use a Stopwatch instead of just two time differences when doing benchmarks. \$\endgroup\$ – Ron Beyer Jul 31 '18 at 1:55
  • \$\begingroup\$ @RonBeyer I just discovered that Stopwatch uses DateTime.UTCNow behind the scenes unless you use it in high resolution mode.if (!Stopwatch.IsHighResolution) return DateTime.UtcNow.Ticks; Looks like it's only necessary if you're timing things at sub-20ms resolution. We're at seconds resolution here, so it should be okay. \$\endgroup\$ – Alain Jul 31 '18 at 2:47
  • 1
    \$\begingroup\$ Added comments and test cases to better indicate what formats are and aren't meant to be supported. \$\endgroup\$ – Alain Jul 31 '18 at 4:22
  • \$\begingroup\$ I found a bug in my 1st while loop that caused an invalid chacater to erronously return a double from all characters up to it. The fix was to use while(true) and have a separate check for if (currentIndex >= length). It brought performance gain down by almost 80%, so I'm looking for ways to merge the two again while still handling the failure scenario correctly. \$\endgroup\$ – Alain Aug 1 '18 at 0:08
3
\$\begingroup\$

Alternatives for OP to try

As OP is looking for performance improvements, consider only 1 loop for both whole and fractional part calculation. Simply iterate through all the digits in one loop and note if and where the decimal point occurred.

// Pseudo code
DP = '.'
significant = 0.0
fractionLengh = 0
for (i=0; i < input.len; i++) 
  ch = input[i]
  if (some_isdigit_test(ch)) {
    significant = significant * 10 + ch - '0'
  } else if (ch == DP) {
    DP = '0'  // Never match again
    fractionLengh = input.len - i - 1
  } else {
    return fail;
  }
}

// continue as before
if (fractionLengh < NegPow10.Length) ....

Perhaps integers?

Instead of accumulating result as some floating point type, accumulate the digits as a 64-bit integer. This, depending on platform, is often significantly faster than double.

Code could simply count leading zeros (important if there is a '.' there) and then loop onto the minimum of of the remaining text length or 18 (number of 999... digts in a 64-bit integer) and then do a final integer to double for subsequent calculation.


Not alwasy the best

There are concerns with OP's code about generating the best answer.

Challenging (lengthly) text input eventual causes significant * 10 to round its answer and even perhaps overflow (even with an in range possible result).

With OP's fractionalPart being rounded and NegPow10[fractionLengh]) also rounded, the product and than addition to result may be off by 1 or 2 ULP.

To get the best result, additional (slower) code is needed.

-0.0

It appears OP's code will generate the correct result. I suspect unposted test code is insufficient to fully test this case. Perhaps OP is not concerned about this case as "anything exotic".

Range

I'd expect test cases should include the maximum +/-Double as text and the minimum non-zero value +/-0.01

Positive numbers?

Code test for a leading '-'. How about a leading '+'? Research CurrentCulture.NumberFormat.PositiveSign.

\$\endgroup\$
  • \$\begingroup\$ On Integers: I actually have a second (much simpler) FastTryParseInt - it's ~2x slower (on my 64 bit machine) than than an identical routine using doubles. The answer I found on the webs was that CPUs are optimized to do integer addition quickly, but integer multiplication is slow. Doubles are the opposite - addition takes more ticks than multiplication. The multiplication by 10 in the inner loop appears to really slow down integers. Haven't tested with longs, which should in theory be the same speed on a machine with 64 bit registers, but less risk of overflowing for large doubles. \$\endgroup\$ – Alain Aug 2 '18 at 17:06
  • \$\begingroup\$ I like the idea of not tracking a separate "fraction part" double, and just continuing to add to result. I'm sure I can work with that. I still think it might be required to maintain two while loops (even though the code is not as nice) so that the branch predictor doesn't have to re-acclimate after the separator is encountered. \$\endgroup\$ – Alain Aug 2 '18 at 17:14
  • \$\begingroup\$ I applied your pseudo code to my new version below and it did improve performance, thanks! I think I'll make a separate version without support for exponential notation again and see if the single loop approach makes it any faster. I also changed the in-progress result and constants to long (until the final result) to see how that went, but it did cut performance almost by double. Quite strange. \$\endgroup\$ – Alain Aug 3 '18 at 13:52
0
\$\begingroup\$

Here is a much longer implementation that handles scientific notation, NaN, Infinity, Negative Infinity, and leading positive signs. I also added a lot of comments to help visually break it into chunks.

It manages to be almost as fast as the previous method - most of the logic takes place in the body of previous if checks that simply returned false before.

I found a few places where I could avoid repeated checks for non-digit characters, and use the first digit character to initialize the result directly to avoid unnecessary additions/multiplcations with zero on the first iteration of the loop.

/// <summary>High performance double parser with rudimentary flexibility.</summary>
/// <returns>Returns true only if we can be certain we parsed the string correctly.</returns>
/// <remarks>Does not support thousand separators or whitespace.</remarks>
/// <remarks>Supports all culture-specific symbols specified by the NumberFormatInfo of the
/// <see cref="CultureInfo.CurrentCulture"/> at the time this static class is instantiated.
/// So long as all culture symbols are a single character in length.
/// TODO: In theory, this class could be made instantiable, take the culture as an argument,
///       and support changing the culture at runtime in case the file the user is uploading
///       was generated on a machine with different culture settings.</remarks>
/// <remarks>Supports leading negative signs and positive signs, scientific notation,
/// as well as Infinity, Negative Infinity, and NaN, string representations.</remarks>
/// <remarks>A string containing only a negative sign (usually "-") intentionally returns a
/// value of zero. This is because it's a common representation of 0 in accounting.</remarks>
public static bool FastTryParseDouble(string input, out double result)
{
    int length = input.Length;
    if (length <= 0)
    {
        result = Double.NaN;
        return false;
    }
    double sign = 1d;
    int currentIndex = 0;
    char nextChar = input[0];

    /**************** Sign (+/-) and Special Case String Representations *****************/
    // Handle all cases where the string does not start with a numeric character
    if (nextChar < '0' || nextChar > '9')
    {
        // Non-numeric 1-character strings must match one of the supported special cases.
        if (length == 1)
            return CheckForSpecialCaseDoubleStrings(input, out result);
        // For anything more than one character, this should be a sign character.
        if (nextChar == CharNegative)
            sign = -1d;
        // The very next character may also be the decimal separator.
        else if (nextChar == CharDecimalSeparator)
        {
            // In this case, we treat the integer part as 0 and skip to the fractional part.
            result = 0d;
            goto SkipIntegerPart;
        }
        // Finally, unless it was a '+' sign, input must match one of a set of special cases.
        else if (nextChar != CharPositive)
            return CheckForSpecialCaseDoubleStrings(input, out result);

        // Once the sign is consumed, advance to the next character for further parsing
        nextChar = input[unchecked(++currentIndex)];
        // We must once more check whether the character is numeric before proceeding.
        if (nextChar < '0' || nextChar > '9')
        {
            // If not numeric, at this point, the character can only be a decimal separator
            // (as in "-.123" or "+.123"), or else it must be part of a special case string
            // (as in "-∞"). So check for those.
            if (nextChar != CharDecimalSeparator)
                return CheckForSpecialCaseDoubleStrings(input, out result);
            result = 0d;
            goto SkipIntegerPart;
        }
    }

    /********************************** "Integer Part" ***********************************/
    // Treat all subsequent numeric characters as the "integer part" of the result.
    // Since we've already checked that the next character is numeric,
    // We can save 2 ops by initializing the result directly.
    unchecked
    {
        result = nextChar - '0';
        while (++currentIndex < length)
        {
            nextChar = input[currentIndex];
            if (nextChar < '0' || nextChar > '9') break;
            result = result * 10d + (nextChar - '0');
        }
    }

    // This label and corresponding goto statements is a performance optimization to
    // allow us to efficiently skip "integer part" parsing in cases like ".123456"
    // Please don't be mad.
    SkipIntegerPart:

    // The expected case is that the next character is a decimal separator, however
    // this section might be skipped in normal use cases (e.g. as in "1e18")
    // TODO: If we broke out of the while loop above due to reaching the end of the
    //       string, this operation is superfluous. Is there a way to skip it?
    if (nextChar == CharDecimalSeparator)
    {
        /******************************* "Fractional Part" *******************************/
        // Track the index at the start of the fraction part.
        unchecked
        {
            int fractionPos = ++currentIndex;
            // Continue shifting and adding to the result as before
            do
            {
                nextChar = input[currentIndex];
                // Note that we flip the OR here, because it's now more likely that
                // nextChar > '9' ('e' or 'E'), leading to an early exit condition.
                if (nextChar > '9' || nextChar < '0') break;
                result = result * 10d + (nextChar - '0');
            } while (++currentIndex < length);

            // Update this to store the number of digits in the "fraction part".
            // We will use this to adjust down the magnitude of the double.
            fractionPos = currentIndex - fractionPos;
            // Use our tiny array of negative powers of 10 if possible, but fallback to
            // our larger array (still fast), whose higher indices store negative powers.
            // Finally, while practically unlikely, ridiculous strings (>300 characters)
            // can still be supported with a final fallback to native Math.Pow
            // TODO: Is it possible to combine this magnitude adjustment with any
            //       applicable adjustment due to scientific notation?
            result *= fractionPos < NegPow10Length ?
                NegPow10[fractionPos] : fractionPos < MaxDoubleExponent ?
                Pow10[MaxDoubleExponent + fractionPos] : Math.Pow(10, -fractionPos);
        }
    }

    // Apply the sign now that we've added all digits that belong to the significand
    result *= sign;
    // If we have consumed every character in the string, return now.
    if (currentIndex >= length) return true;

    // The next character encountered must be an exponent character
    if (nextChar != 'e' && nextChar != 'E')
        return false;

    /**************************** "Scientific Notation Part" *****************************/
    unchecked
    {
        // If we're at the end of the string (last character was 'e' or 'E'), that's an error
        if (++currentIndex >= length) return false;
        // Otherwise, advance the current character and begin parsing the exponent
        nextChar = input[currentIndex];
        bool exponentIsNegative = false;
        // The next character can only be a +/- sign, or a numeric character
        if (nextChar < '0' || nextChar > '9')
        {
            if (nextChar == CharNegative)
                exponentIsNegative = true;
            else if (nextChar != CharPositive)
                return false;
            // Again, require there to be at least one more character in the string after the sign
            if (++currentIndex >= length) return false;
            nextChar = input[currentIndex];
            // And verify that this next character is numeric
            if (nextChar < '0' || nextChar > '9') return false;
        }

        // Since we know the next character is a digit, we can initialize the exponent int
        // directly and avoid 2 wasted ops (multiplying by and adding to zero).
        int exponent = nextChar - '0';
        // Shift and add any additional digit characters
        while (++currentIndex < length)
        {
            nextChar = input[currentIndex];
            // If we encounter any non-numeric characters now, it's definitely an error
            if (nextChar < '0' || nextChar > '9') return false;
            exponent = exponent * 10 + nextChar - '0';
        }
        // Apply the exponent. If negative, our index jump is a little different.
        if (exponentIsNegative)
            result *= exponent < Pow10Length - MaxDoubleExponent ?
                // Fallback to Math.Pow if the lookup array doesn't cover it.
                Pow10[exponent + MaxDoubleExponent] : Math.Pow(10, -exponent);
        // If positive, our array covers all possible positive exponents - ensure its valid.
        else if (exponent > MaxDoubleExponent)
            return false;
        else
            result *= Pow10[exponent];
    }
    // Doubles that underwent scientific notation parsing should be checked for overflow
    // (Otherwise, this isn't really a risk we don't expect strings of >308 characters)
    return !Double.IsInfinity(result);
}

/// <summary>Checks if the string matches one of a few supported special case
/// double strings. If so, assigns the result and returns true.</summary>
public static bool CheckForSpecialCaseDoubleStrings(string input, out double result)
{
    if (input == NumberFormat.PositiveInfinitySymbol)
        result = Double.PositiveInfinity;
    else if (input == NumberFormat.NegativeInfinitySymbol)
        result = Double.NegativeInfinity;
    else if (input == NumberFormat.NaNSymbol)
        result = Double.NaN;
    // Special Case: Excel has been known to format zero as "-".
    // We intentionally support it by returning zero now (most parsers would not)
    else if (input == NumberFormat.NegativeSign)
        result = 0d;
    // Special Case: Our organization treats the term "Unlimited" as referring
    // to Double.MaxValue (most parsers would not)
    else if (input.Equals("unlimited", StringComparison.OrdinalIgnoreCase))
        result = Double.MaxValue;
    // Anything else is not a valid input
    else
    {
        result = Double.NaN;
        return false;
    }
    return true;
}

/// <summary>The largest exponent (or smallest when negative) that can be given to a Double.</summary>
private const int MaxDoubleExponent = 308;

/// <summary>The number of elements that will be generated in the Pow10 array.</summary>
private const int Pow10Length = MaxDoubleExponent * 2 + 1;

/// <summary>A cache of all possible positive powers of 10 that might be required to
/// apply an exponent to a double (Indices 0-308), as well as the first 308 negative
/// exponents. (Indices 309-616)</summary>
private static readonly double[] Pow10 =
    Enumerable.Range(0, MaxDoubleExponent + 1).Select(i => Math.Pow(10, i))
        .Concat(Enumerable.Range(1, MaxDoubleExponent).Select(i => Math.Pow(10, -i)))
        .ToArray();

/// <summary>The number of negative powers to pre-compute and store in a small array.</summary>
private const int NegPow10Length = 16;

/// <summary>A cache of the first 15 negative powers of 10 for quick
/// magnitude adjustment of common parsed fractional parts of doubles.</summary>
/// <remarks>Even though this overlaps with the Pow10 array, it is kept separate so that
/// users that don't use scientific notation or extremely long fractional parts
/// might get a speedup by being able to reference the smaller array, which has a better
/// chance of being served out of L1/L2 cache.</remarks>
private static readonly double[] NegPow10 =
    Enumerable.Range(0, NegPow10Length).Select(i => Math.Pow(10, -i)).ToArray();

This new method matches all of the following test cases:

// Numbers without a fractional part
TestSuccess("0", 0d);
TestSuccess("1", 1d);
TestSuccess("-1", -1d);
TestSuccess("12345678901234", 12345678901234d);
TestSuccess("-12345678901234", -12345678901234d);
// Numbers with a fractional part
TestSuccess("123.45678", 123.45678);
TestSuccess("-123.45678", -123.45678);
// Numbers without an integer part
TestSuccess(".12345678901234", 0.12345678901234);
TestSuccess("-.12345678901234", -0.12345678901234);
// Various high-precision numbers
TestSuccess("0.12345678901234", 0.12345678901234);
TestSuccess("-0.12345678901234", -0.12345678901234);
TestSuccess("0.00000987654321", 0.00000987654321);
TestSuccess("-0.00000987654321", -0.00000987654321);
TestSuccess("1234567890123.0123456789", 1234567890123.0123456789);
TestSuccess("-1234567890123.0123456789", -1234567890123.0123456789);
// Numbers with very long fractional parts (more than 16 characters)
TestSuccess("0.00826499999979784", 0.00826499999979784);
TestSuccess("-0.00826499999979784", -0.00826499999979784);
TestSuccess("1.0123456789012345678901234567890", 1.0123456789012345678901234567890);
TestSuccess("-1.0123456789012345678901234567890", -1.0123456789012345678901234567890);
// Numbers with a leading positive sign
TestSuccess("+1", 1d);
TestSuccess("+12345678901234", 12345678901234d);
TestSuccess("+.12345678901234", 0.12345678901234);
TestSuccess("+0.00826499999979784", 0.00826499999979784);
// Very large numbers without scientific notation
TestSuccess("123456789000000000000000", 123456789000000000000000d);
TestSuccess("-123456789000000000000000", -123456789000000000000000d);
// Very small numbers without scientific notation
TestSuccess("0.00000000000000000123456789", 0.00000000000000000123456789);
TestSuccess("-0.00000000000000000123456789", -0.00000000000000000123456789);
// Scientific notation without a sign
TestSuccess("1.2345678e5", 1.2345678e5);
TestSuccess("1.2345678e5", 1.2345678e5);
TestSuccess("-1.2345678e5", -1.2345678e5);
// Scientific notation with a sign
TestSuccess("1.2345678e+25", 1.2345678e25);
TestSuccess("-1.2345678e+25", -1.2345678e25);
TestSuccess("1.2345678e-255", 1.2345678e-255);
TestSuccess("-1.2345678e-255", -1.2345678e-255);
// Epsilon, and other tiny doubles
// TODO: Known "failure" scenarios. Our parsing logic results in a return value of 0
// for these, but the native parser returns Double.Epsilon (smallest number greater
// than zero). I think we can live with this shortcoming.
//TestSuccess("4.94065645841247e-324", 4.94065645841247e-324);
//TestSuccess("-4.94065645841247e-324", -4.94065645841247e-324);
TestSuccess("3.33E-333", 3.33E-333);
TestSuccess("-3.33E-333", -3.33E-333);
TestSuccess("1E-1022", 1E-1022);
TestSuccess("-1E-1022", -1E-1022);
// Boundary cases
TestSuccess("1e0", 1);
TestSuccess("1e1", 10);
TestSuccess("1e-1", 0.1);
TestSuccess("1e-308", 1e-308);
TestSuccess("1e308", 1e308);
// Min and Max Double
TestSuccess("1.7976931348623157E+308", 1.7976931348623157E+308);
TestSuccess("-1.7976931348623157E+308", -1.7976931348623157E+308);
// Large Negative Exponents (Near-epsilon) doubles.
TestSuccess("1.23E-999", 1.23E-999);
TestSuccess("-1.23E-999", -1.23E-999);
// Special keywords
TestSuccess("∞", Double.PositiveInfinity);
TestSuccess("-∞", Double.NegativeInfinity);
TestSuccess("NaN", Double.NaN);
// Special case: "Unlimited" is used in our organization to refer to Double.MaxValue
TestSuccess("Unlimited", Double.MaxValue);
// Special case: "-" character only means zero in accounting formats.
TestSuccess("-", 0d);

Benchmark Results

Using a Stopwatch this time, and ran with 1,000,000,000 (a billion) strings just to quell any debate about timing sensitivity:

Native parser took 26220 ms.

Custom parser took 6471 ms.

Performance gain was 305.19%

\$\endgroup\$
  • \$\begingroup\$ @chux I applied your suggestion in this updated version and it took the performance up another ~15% - while still supporting all valid double cases. The results still differ from Native Double.Parse by 1 or 2 ULPs for certain very large or very small numbers, but I don't consider that a meaningful drawback. It just means results aren't always being parsed to precisely the closest possible double representation of the string processed. \$\endgroup\$ – Alain Aug 3 '18 at 12:36
  • \$\begingroup\$ Code like do { nextChar = input[currentIndex]; if (nextChar > '9' || nextChar < '0') break; result = result * 10d + (nextChar - '0'); } while (++currentIndex < length); is doing 2 checks (is digit, is at end) per loop to see if it should stop. If able, append a non-digit to index[] and then code only need to to check for digit. After to loop code can test if loop quit due to end of string or not. ` \$\endgroup\$ – chux Aug 3 '18 at 14:20
  • \$\begingroup\$ That's a good idea. If only strings in c# returned the null character as the last element in their character array like c++. Can you think of any way without building a new array? \$\endgroup\$ – Alain Aug 3 '18 at 14:30
  • \$\begingroup\$ "think of any way without building a new array?" --> No, yet appending to the existing array may not cost much. \$\endgroup\$ – chux Aug 3 '18 at 14:39
  • \$\begingroup\$ Other idea: consider profiling a table lookup isdigit[nextChar] instead of if (nextChar > '9' || nextChar < '0'). \$\endgroup\$ – chux Aug 3 '18 at 14:40
0
\$\begingroup\$

Here's the most performant version I've got so far based on suggestions by @chux, @PieterWitvoet and @202_accepted. (From both this and the Custom integer parser optimized for performance question.)

/// <summary>High performance double parser with rudimentary flexibility.</summary>
/// <returns>Returns true only if we can be certain we parsed the string correctly.</returns>
/// <remarks>Does not support thousand separators or whitespace.</remarks>
/// <remarks>Supports all culture-specific symbols specified by the NumberFormatInfo of the
/// <see cref="CultureInfo.CurrentCulture"/> at the time this static class is instantiated.
/// So long as all culture symbols are a single character in length.
/// TODO: In theory, this class could be made instantiable, take the culture as an argument,
///       and support changing the culture at runtime in case the file the user is uploading
///       was generated on a machine with different culture settings.</remarks>
/// <remarks>Supports leading negative signs and positive signs, scientific notation,
/// as well as Infinity, Negative Infinity, and NaN, string representations.</remarks>
/// <remarks>A string containing only a negative sign (usually "-") intentionally returns a
/// value of zero. This is because it's a common representation of 0 in accounting.</remarks>
public static unsafe bool FastTryParseDouble(string input, out double result)
{
    // We never expect null, but enforcing this may enable some JIT optimizations.
    if (input == null)
    {
        result = default(double);
        return false;
    }
    fixed (char* cInput = input)
    {
        double localValue;
        double sign = 1d;
        char* nextChar = cInput;

        /************** Sign (+/-) and Special Case String Representations ***************/
        // Handle all cases where the string does not start with a numeric character
        if (*nextChar < '0' || *nextChar > '9')
        {
            // The first character may be a sign character (-/+). Take note of a negative.
            if (*nextChar == CharNegative)
                sign = -1d;
            // The very first character may also be the decimal separator.
            else if (*nextChar == CharDecimalSeparator)
            {
                // In this case, we treat the integer part as 0 and skip to the fractional part.
                localValue = 0;
                goto SkipIntegerPart;
            }
            // Finally, unless it was a '+' sign, we cannot parse this double.
            // Return true only if the input matches one of a set of special cases.
            else if (*nextChar != CharPositive)
                return CheckForSpecialCaseDoubleStrings(input, out result);

            // Once the sign is consumed, advance to the next character for further parsing
            // We must once more check whether the character is numeric before proceeding.
            if (*++nextChar < '0' || *nextChar > '9')
            {
                // If not numeric, at this point, the character can only be a decimal separator
                // (as in "-.123" or "+.123"), or else it must be part of a special case string
                // (as in "-∞"). So check for those.
                if (*nextChar != CharDecimalSeparator)
                    return CheckForSpecialCaseDoubleStrings(input, out result);
                localValue = 0;
                goto SkipIntegerPart;
            }
        }

        /******************************** "Integer Part" *********************************/
        // Treat all subsequent numeric characters as the "integer part" of the result.
        // Since we've already checked that the next character is numeric,
        // We can save 2 ops by initializing the localValue directly.
        localValue = *nextChar++ - '0';
        while (*nextChar >= '0' && *nextChar <= '9')
            localValue = localValue * 10L + (*nextChar++ - '0');

        // This label and corresponding goto statements is a performance optimization to
        // allow us to efficiently skip "integer part" parsing in cases like ".123456"
        // Please don't be mad.
        SkipIntegerPart:

        // The expected case is that the next character is a decimal separator, however
        // this section might be skipped in normal use cases (e.g. as in "1e18")
        // TODO: If we broke out of the while loop above due to reaching the end of the
        //       string, this operation is superfluous. Is there a way to skip it?
        //       Also, if we used goto `SkipIntegerPart`, this test for '.' is redundant.
        int fractionLen;
        if (*nextChar == CharDecimalSeparator)
        {
            /***************************** "Fractional Part" *****************************/
            // Track the index at the start of the fraction part.
            char* fractionStart = ++nextChar;
            // Continue shifting and adding to the localValue as before
            // Note that we flip the OR here, because it's now more likely that
            // nextChar > '9' ('e' or 'E'), leading to an early exit condition.
            while (*nextChar <= '9' && *nextChar >= '0')
                localValue = localValue * 10L + (*nextChar++ - '0');

            // Keep track of the digits in the fraction for the final magnitude adjustment.
            fractionLen = unchecked((int)(nextChar - fractionStart));
        }
        else
            fractionLen = 0;

        // If we have consumed every character in the string, return now (successfully)
        if (*nextChar == Char.MinValue)
        {
            // Produce the final result and return
            result = sign * localValue * Pow10[unchecked(MaxDoubleExponent - fractionLen)];
            return true;
        }

        /**************************** "Scientific Notation Part" *****************************/
        // The next character encountered must be an exponent character ('e' or 'E').
        // Any other character appears, or if there's nothing afterwards, that's an error
        if (*nextChar != 'e' && *nextChar != 'E' || *++nextChar == Char.MinValue)
        {
            result = default(double);
            return false;
        }
        // Otherwise, begin parsing the exponent
        bool exponentIsNegative = false;
        // The next character can only be a +/- sign, or a numeric character
        if (*nextChar < '0' || *nextChar > '9')
        {
            if (*nextChar == CharNegative)
                exponentIsNegative = true;
            // Fail if the non-digit character was not one of these two signs
            else if (*nextChar != CharPositive)
            {
                result = default(double);
                return false;
            }
            // Advance, and fail if the sign is not followed by a numeric character
            if (*++nextChar < '0' || *nextChar > '9')
            {
                result = default(double);
                return false;
            }
        }

        unchecked
        {
            // Since we know the next character is a digit, we can initialize the exponent
            // int directly and avoid 2 wasted ops (multiplying by and adding to zero).
            int exponent = *nextChar++ - '0';
            // Shift and add any additional digit characters
            while (*nextChar <= '9' && *nextChar >= '0')
                exponent = exponent * 10 + (*nextChar++ - '0');
            // If we broke for anything other than the end of string, it's an error
            if (*nextChar != Char.MinValue)
            {
                result = default(double);
                return false;
            }
            // Account for the negative sign and any parsed fractional digits
            int powerIndex;
            if (exponentIsNegative)
                powerIndex = MaxDoubleExponent - fractionLen - exponent;
            else
                powerIndex = MaxDoubleExponent - fractionLen + exponent;
            // Apply the exponent using our array, falling to Math.Pow it's out of range.
            if (powerIndex >= 0 && powerIndex < Pow10Length)
                result = sign * localValue * Pow10[powerIndex];
            else
                result = sign * localValue * Math.Pow(10, powerIndex - MaxDoubleExponent);
        }

        // Doubles that underwent scientific notation parsing should be checked for overflow
        // (This isn't really a risk before now as we don't expect strings of >308 characters).
        // This trick tests whether the value evaluates to negative or positive infinity:
        return !Double.IsInfinity(result);
    }
}

/// <summary>Checks if the string matches one of a few supported special case
/// double strings. If so, assigns the result and returns true.</summary>
public static bool CheckForSpecialCaseDoubleStrings(string input, out double result)
{
    if (input == NumberFormat.PositiveInfinitySymbol)
        result = Double.PositiveInfinity;
    else if (input == NumberFormat.NegativeInfinitySymbol)
        result = Double.NegativeInfinity;
    else if (input == NumberFormat.NaNSymbol)
        result = Double.NaN;
    // Special Case: Excel has been known to format zero as "-".
    // We intentionally support it by returning zero now (most parsers would not)
    else if (input == NumberFormat.NegativeSign)
        result = 0d;
    // Special Case: Our organization treats the term "Unlimited" as referring
    // to Double.MaxValue (most parsers would not)
    else if (input.Equals("unlimited", StringComparison.OrdinalIgnoreCase))
        result = Double.MaxValue;
    // Anything else is not a valid input
    else
    {
        result = Double.NaN;
        return false;
    }
    return true;
}

/// <summary>The largest exponent (or smallest when negative) that can be given to a Double.</summary>
private const int MaxDoubleExponent = 308;

/// <summary>The number of elements that will be generated in the Pow10 array.</summary>
private const int Pow10Length = MaxDoubleExponent * 2 + 1;

/// <summary>A cache of all possible positive powers of 10 that might be required to
/// apply an exponent to a double (Indices 308-616), as well as the first 308 negative
/// exponents. (Indices 0-301)</summary>
private static readonly double[] Pow10 =
    Enumerable.Range(1, MaxDoubleExponent).Select(i => Math.Pow(10, -i)).Reverse()
    .Concat(Enumerable.Range(0, MaxDoubleExponent + 1).Select(i => Math.Pow(10, i)))
        .ToArray();

Benchmarks

I was seeing a lot of variability in my benchmark runs when I looped over a billion strings at once, so to mange noise, I changed my test code to run several smaller test in succession. Here are the results for the above code:

Native parser took 1976 ms. Custom parser took 452 ms. Performance gain was 337.17% Native parser took 1967 ms. Custom parser took 457 ms. Performance gain was 330.42% Native parser took 1957 ms. Custom parser took 449 ms. Performance gain was 335.86% Native parser took 2009 ms. Custom parser took 452 ms. Performance gain was 344.47% Native parser took 1958 ms. Custom parser took 451 ms. Performance gain was 334.15% Native parser took 1981 ms. Custom parser took 485 ms. Performance gain was 308.45% Native parser took 2028 ms. Custom parser took 458 ms. Performance gain was 342.79% Native parser took 2018 ms. Custom parser took 462 ms. Performance gain was 336.80% Native parser took 1987 ms. Custom parser took 472 ms. Performance gain was 320.97% Native parser took 1958 ms. Custom parser took 455 ms. Performance gain was 330.33%

The average is about 330% faster than native parse.

Performance Improvements

  • Uses unsafe and fixed to treat the string as a null-terminated character array, avoiding the need to monitor or pre-compute the length of the string as we traverse it.

  • Uses a local double value for accumulation during parsing, and only assigns out result once - since manipulating out variables directly is more expensive.

  • Initializes the local value directly using the first numeric digit, avoiding a superfluous multiplication and addition with zero in the first loop.

  • A null check at the beginning may enable some JIT optimizations.

  • Merged the magnitude adjustment made after parsing the fraction with the one made after parsing the scientific notation.

  • Simplified the power lookup by using a single array, and always falling back to Math.Pow - allowing it to overflow if applicable and checking for overflow in the final return statement.

  • Tried to reduce the amount of condition checking / branching in the "expected case" (all numeric digits) by grouping special case handling beneath the initial check for a numeric digit.

Omissions

  • Still does not allow white-space or thousand separators. Note that in all above 'unhandled' cases, we're very careful to return false - we will never return true with an incorrect result. You could (in theory) replace any instances of return false with return Double.TryParse(input, out result) if you wanted to "fall-back" to the native parser in these rare cases and add back its flexibility. In our case, something similar is done further up the chain, so I haven't included it in this code.
\$\endgroup\$
  • \$\begingroup\$ I just discovered that I can go fixed (char* cString = input) in an unsafe method to get a null-terminated character array pointer directly from a string. I'm going to try again using that, which will remove the need for any memory copying. \$\endgroup\$ – Alain Aug 3 '18 at 21:02

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.