Faster Checked Addition in C# (Part 2)

In the initial blog I developed a faster checked summation of ulong arrays. By using integer operations when no arithmetic overflow is detected, helped propel performance 15X higher to 682 MegaUlongAdditions/second, for a typical case. However, the worst case was still as slow as summation of Decimal arrays – 48 MegaUlongAdditions/second. In this blog I’ll develop a method to raise this worst case to the same level as the typical case and then even higher.

The Main Idea

Decimal data type in C# is a wonderful thing. Precision is extended to 96-bits, versus 64-bit ulong. Decimal is handles positive and negative integers, as well as fractions. However, Decimal is not supported natively by the processor, whereas integers and floating-point numbers are. Decimal addition is about 20X slower. BigInteger addition is even worse, and is about 100X slower.

The main idea behind improving performance of ulong array summation is to stop using Decimal addition in the inner loop.  Instead, I’ll extend integer precision beyond 64-bit ulong to 96-bits. By using an extra 32-bit unsigned integer to accumulate each overflow that is detected, all computations stay as integer computations – much faster.

Below is the extended integer only summation:

public static decimal SumToDecimalEvenFaster(this ulong[] arrayToSum)
{
    decimal overallSum = 0;
    ulong ulongSum = 0;
    uint uintUpperSum = 0;      // together uintUpperSum and ulongSum represent a 96-bit uint
    for (int i = 0; i < arrayToSum.Length; i++)
    {
        ulong newUlongSum = ulongSum + arrayToSum[i];
        if (newUlongSum < ulongSum)
            uintUpperSum++;            // carry-out of lower 64-bit into carry-in of upper 32-bits
        ulongSum = newUlongSum;
    }
    decimal multiplier = 0x8000_0000_0000_0000;
    overallSum = multiplier * (Decimal)2 * (Decimal)uintUpperSum;   // uintUpperSum << 64
    overallSum += ulongSum;
    
    return overallSum;
}

This algorithm is implemented more like it came from a chip designer, than a software developer. In the inner loop only integer operations are performed. Arithmetic overflow is detected and dealt with inside the inner loop. If arithmetic overflow is detected than the uintUpperSum is incremented.

Another way of looking at it is, when arithmetic overflow is detected a carry-out is generated from the 64-bit addition, which serves as carry-in to the 32-bit integer extension. Now, I’m talking like a hardware designer. Since C# arrays can only hold 2 GigaElements, 32-bit integer extension is more than sufficient to handle any size array. If C# ever extends its capabilities to larger arrays, then this 32-bit extension can easily be extended to 64-bits.

Performance

In the worst case of every array element being UInt32.MaxValue, the above implementation on a single core, runs at 1.2 GigaUlongAdditions/second instead of 48 MegaUlongAdditions/second of using a Decimal

Decimal sum = ulongArray.Sum(x => (decimal)x);

This is a 25X speed improvement!

Notice that performance of 1.2 Giga in the worst case is nearly 2X higher than the typical/best case of the previous algorithm’s 682 Mega. Every case benefited from this new integer-only algorithm.

This algorithm can also be translated to use SIMD/SSE instructions, which raises performance to 1.7 GigaUlongAdditions/second on a single core.

This is a 35X speed improvement!

On a quad-core laptop CPU with dual-memory channel system memory, performance goes up to 2.7 GigaUlongAdditions/second

This is a 26X speed improvement!

Decimal sum = ulongArray.AsParallel().Sum(x => (decimal)x);

When compared to the code above. Note .AsParallel() to run on all four cores – running at 102 MegaUlongAdditions/second.

It’s nice to run in Giga instead of Mega!

HPCsharp nuget package includes this new higher performance algorithm.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s