Number parsing optimization

[MarkPflug]

In dealing with a dataset (CSV) that contains a lot of single-digit numbers, I've found that by special-casing the handling of the single digit case and circumventing int.parse, it was measurably faster. I was curious if this special case handling was worth putting into the number parsing routines in the BCL. Single-character string will always parse to the same integer value regardless of number style or culture, so it is possible to avoid those altogether (I'd love to know if I'm wrong about that assumption).

The optimization is trivial, if the string is a single character assume it is a digit in the range 0-9, otherwise fallback to the standard implementation:

static int ParseIntEx(string str)
{
    if (str.Length == 1)
    {
        var v = (str[0] - '0');
        if ((uint)v < 10)
            return v;
    }
    return int.Parse(str);
}

I created a benchmark to compare this to the BCL implementation. These results for single-character strings show significant performance improvement: (the "s" column is the string being parsed)

Method	s	Mean	Error	StdDev
IntBCL	5	11.3591 ns	0.1501 ns	0.1331 ns
IntOpt	5	0.4828 ns	0.0031 ns	0.0027 ns
DoubleBCL	5	43.6512 ns	0.1307 ns	0.1091 ns
DoubleOpt	5	0.6161 ns	0.0055 ns	0.0043 ns
DecimalBCL	5	44.2901 ns	0.0523 ns	0.0437 ns
DecimalOpt	5	4.4839 ns	0.0070 ns	0.0062 ns

The improvement for decimal isn't as significant because new Decimal has to do a bit of work. I found that creating a lookup table of the 10 values and indexing into it instead, cut this approx in half to 2ns.

Of course, this comes at the cost of slightly slower parsing for longer strings that encounter this new branch in the logic:

Method	s	Mean	Error	StdDev
IntBCL	55	13.4448 ns	0.0277 ns	0.0246 ns
IntOpt	55	11.8391 ns	0.1230 ns	0.1091 ns
DoubleBCL	55	45.9182 ns	0.1125 ns	0.0997 ns
DoubleOpt	55	47.1309 ns	0.3478 ns	0.2715 ns
DecimalBCL	55	48.2871 ns	0.2075 ns	0.1941 ns
DecimalOpt	55	48.7201 ns	0.0834 ns	0.0739 ns
IntBCL	555	12.2237 ns	0.0563 ns	0.0500 ns
IntOpt	555	13.4234 ns	0.0543 ns	0.0424 ns
DoubleBCL	555	48.4734 ns	0.1847 ns	0.1442 ns
DoubleOpt	555	48.9273 ns	0.1566 ns	0.1388 ns
DecimalBCL	555	54.2170 ns	0.1937 ns	0.1618 ns
DecimalOpt	555	51.9970 ns	0.1032 ns	0.0965 ns
IntBCL	5555	13.0938 ns	0.0578 ns	0.0540 ns
IntOpt	5555	15.3348 ns	0.0462 ns	0.0432 ns
DoubleBCL	5555	51.1805 ns	0.2844 ns	0.2375 ns
DoubleOpt	5555	50.8550 ns	0.1115 ns	0.1043 ns
DecimalBCL	5555	54.1844 ns	0.9361 ns	0.8757 ns
DecimalOpt	5555	54.4468 ns	0.4588 ns	0.4067 ns
IntBCL	55555	13.7659 ns	0.0462 ns	0.0432 ns
IntOpt	55555	13.9920 ns	0.0689 ns	0.0644 ns
DoubleBCL	55555	52.7799 ns	0.0988 ns	0.0772 ns
DoubleOpt	55555	53.4449 ns	0.1178 ns	0.1044 ns
DecimalBCL	55555	56.0303 ns	0.2475 ns	0.2315 ns
DecimalOpt	55555	58.1518 ns	0.0969 ns	0.0859 ns

The results are a little inconsistent here. The difference between 2-char integers (which I think should be the worst-case regression) shows >10% improvement (surprising), and the 3-char integer show ~10% regression. On average though, there appears to be a very slight regression, maybe only a couple percent. I'm not sure if it is possible to get more stable/consistent results with BenchmarkDotNet (I'm a bit new to it) and this is using the default configurations.

So, is that very slight regression worth the significant improvement in single character parsing? Obviously, it depends on the dataset/use-case whether this would be a net win. The breakeven point is mostly dictated by the regression, so a 1% regression means the breakeven is when ~1% of the values are single digit. Do enough real-world data sets meet this criteria? "0" certainly comes up a lot. For integers in an ordered list, the first 9 elements would be single digit, and only after 900 elements would the breakeven point be reached. How often does that happens in reality, I have no idea. For double and decimal values, it is probably less likely provide a gain.

In the benchmark dataset for the csFastFloat the mesh.txt contains 5% single-character values. Actually, 10% of the values would be single-digit if formatted differentl; there are a lot of "0.0" and "1.0" values. The canada.txt, on the other hand, has no single-digit values.

Of course, the real benefit would be in data sets that contain a significant number of single-digit values; I just don't know if this is common enough to merit baking this into the BCL. For my specific scenario where I had a majority of '0' values, it was a win.

One specific use-case where single digits are very common is in System.Version parsing, which currently uses int.Parse to convert the version components into integer values. Perhaps, at the very least, it would be worth considering applying this optimization there?

[MarkPflug]

Looking closer at optimizing Version.Parse, I slapped together this implementation that avoids int.parse:

static Version Parse(string str)
{
    return TryParse(str, out var v) ? v : throw new FormatException();
}

static bool TryParse(string str, out Version ver)
{
    ver = default;
    Span<int> components = stackalloc int[4];
    int count = 0;
    uint v = 0;
    var l = -1;
    var i = 0;
    for (; i < str.Length; i++)
    {
        var c = str[i];
        var d = (uint)(c - '0');
        if (d <= 9)
        {
            v = v * 10 + d;
            continue;
        }
        if (c == '.')
        {
            if (i - l == 1 || v > short.MaxValue)
                return false;
            components[count] = (int)v;
            v = 0;
            count++;
            l = i;
            if(count >= 4)
                return false;
            continue;
        }
        return false;
    }
    if(l == i)
        return false;
    components[count] = (int)v;
    count++;
    switch (count)
    {
        default:
            return false;
        case 2:
            ver = new Version(components[0], components[1]);
            break;
        case 3:
            ver = new Version(components[0], components[1], components[2]);
            break;
        case 4:
            ver = new Version(components[0], components[1], components[2], components[3]);
            break;
    }
    return true;
}

Which benchmarks between 4-5x faster than the BCL implementation.

Method	s	Mean	Error	StdDev
VersionBCL	1.2	42.70 ns	0.306 ns	0.286 ns
VersionOpt	1.2	10.81 ns	0.269 ns	0.276 ns
VersionBCL	1.2.3	60.22 ns	0.201 ns	0.179 ns
VersionOpt	1.2.3	13.24 ns	0.258 ns	0.241 ns
VersionBCL	1.2.3.4	77.33 ns	0.528 ns	0.468 ns
VersionOpt	1.2.3.4	15.15 ns	0.227 ns	0.190 ns

There are probably edge cases I didn't consider that might slow it down though.