Striding loop performance

[jackmott]

System.numerics.vectors exposes a SIMD enhanced Vector classes. Using VS2015 Update 1, latest versions of .NET framework and F# and System.numerics.vectors the performance of System.Numerics is worse than not using it at all, for instance:

     let sumVectorLoop =
            let mutable total = Vector<int>.Zero
            for i in 0  .. COUNT/8-1 do
                total <- total + vecArray.[i]
            total

Is slower than the same operation on an array of integers:

     let sumsLoop =
            let mutable total = 0;
            for i in 0 .. COUNT - 1 do
                total <- total + numsArray.[i]
            total

I have confirmed that Vector.isHardwareAccelerated reports as true. I have confirmed that equivalent code in C# runs ~2x faster for the Vector approach. Interestingly, using Array.reduce on the vector array is faster than the imperative loop, which is the opposite of working with an array of ints, suggesting something may be amiss:

let sumVectorReduce =
        Array.reduce (fun a e -> a + e)  vecArray

[dsyme]

Could you please give the exact code in C#? There must be a difference in F# and C# code generation which is tripping up the optimizations applied by the RyuJIT.

[dsyme]

BTW does anyone know the right people to contact on the RyuJIT team? They may well want to fix this there rather than fiddling with F# codegen, as whatever needs fixing may lead to more general and more robust loop optimizations.

[jackmott]

Here you go

 const int COUNT = 10000000;
            int[] ints = new int[COUNT];
            for (int i = 0; i < COUNT-1;i++)
            {
                ints[i] = i;
            }

            Vector<int>[] vectors = new Vector<int>[COUNT / 8];
            for (int i = 0; i < COUNT / 8 - 1; i = i + 8)
            {
                vectors[i] = new Vector<int>(ints, i);
            }

            Stopwatch sw = new Stopwatch();
            sw.Start();
            Vector<int> sum = Vector<int>.Zero;

            for (int i = 0; i < COUNT/8-1;i++)
            {
                sum = sum + vectors[i];
            }

            sw.Stop();
            Console.WriteLine("Sum vector:" + sum + " time:" + sw.ElapsedMilliseconds);


            sw.Restart();
            int sumi = 0;
            for (int i = 0; i < COUNT-1; i++)
            {
                sumi = sumi + ints[i];
            }
            Console.WriteLine("Sum integers:" + sum + " time:" + sw.ElapsedMilliseconds);
            Console.ReadLine();

[jackmott]

Here is the IL of each vector summing loop as reported by ILSpy:

C#:

IL_004e: call valuetype [System.Numerics.Vectors]System.Numerics.Vector`1<!0> valuetype [System.Numerics.Vectors]System.Numerics.Vector`1<int32>::get_Zero()
        IL_0053: stloc.2
        IL_0054: ldc.i4.0
        IL_0055: stloc.s i
        IL_0057: br.s IL_006e
        // loop start (head: IL_006e)
            IL_0059: ldloc.2
            IL_005a: ldloc.1
            IL_005b: ldloc.s i
            IL_005d: ldelem.any valuetype [System.Numerics.Vectors]System.Numerics.Vector`1<int32>
            IL_0062: call valuetype [System.Numerics.Vectors]System.Numerics.Vector`1<!0> valuetype [System.Numerics.Vectors]System.Numerics.Vector`1<int32>::op_Addition(valuetype [System.Numerics.Vectors]System.Numerics.Vector`1<!0>, valuetype [System.Numerics.Vectors]System.Numerics.Vector`1<!0>)
            IL_0067: stloc.2
            IL_0068: ldloc.s i
            IL_006a: ldc.i4.1
            IL_006b: add
            IL_006c: stloc.s i

            IL_006e: ldloc.s i
            IL_0070: ldc.i4 1250000
            IL_0075: blt.s IL_0059
        // end loop

F#

IL_006a: ldloc.3
        IL_006b: stloc.1
        IL_006c: nop
        IL_006d: call valuetype [System.Numerics.Vectors]System.Numerics.Vector`1<!0> valuetype [System.Numerics.Vectors]System.Numerics.Vector`1<int32>::get_Zero()
        IL_0072: stloc.s total
        IL_0074: ldc.i4.0
        IL_0075: stloc.s i
        IL_0077: ldc.i4 10000000
        IL_007c: ldc.i4.8
        IL_007d: div
        IL_007e: stloc.2
        IL_007f: ldloc.2
        IL_0080: ldloc.s i
        IL_0082: blt.s IL_00a2
        // loop start (head: IL_0084)
            IL_0084: ldloc.s total
            IL_0086: ldloc.1
            IL_0087: ldloc.s i
            IL_0089: ldelem.any valuetype [System.Numerics.Vectors]System.Numerics.Vector`1<int32>
            IL_008e: call valuetype [System.Numerics.Vectors]System.Numerics.Vector`1<!0> valuetype [System.Numerics.Vectors]System.Numerics.Vector`1<int32>::op_Addition(valuetype [System.Numerics.Vectors]System.Numerics.Vector`1<!0>, valuetype [System.Numerics.Vectors]System.Numerics.Vector`1<!0>)
            IL_0093: stloc.s total
            IL_0095: ldloc.s i
            IL_0097: ldc.i4.1
            IL_0098: add
            IL_0099: stloc.s i
            IL_009b: ldloc.s i
            IL_009d: ldloc.2
            IL_009e: ldc.i4.1
            IL_009f: add
            IL_00a0: bne.un.s IL_0084
        // end loop

[mellinoe]

@CarolEidt works on the SIMD feature on RyuJIT. Carol, do you recognize any differences in the C#/F# IL that would lead to significantly worse performance?

On the usage side, I did want to point out that we don't usually recommend folks actually store their data in an array of Vector<int>'s. The idiomatic way to use the library would be to keep everything stored in your original int[] array, and construct Vector items directly from that. So your vectorized loop would be something like:

for (int i = 0; i < COUNT / Vector<int>.Count; i += Vector<int>.Count)
{
    sum = sum + new Vector<int>(ints, i);
}

Another thing to note is that your scalar and vector passes aren't necessarily computing the same thing. To get the sum of a single array's values efficiently, we'd need to something like a HorizontalAdd method (which would compute the sum of an individual Vector<T>'s elements. Right now you are left with a Vector<int> at the end of your vector computation, which you'd need to manually add together to get the same result as the scalar version.

[jackmott]

The idiomatic approach seems to make use of an enumerator for the loop which kills performance:

  let sumVectorLoop =
        let mutable total = Vector<int>.Zero
        for i in 0  .. 8 .. COUNT-1 do
            total <- total + new Vector<int>(numsArray,i)
        total    

if I get rid of the .. 8 .. in the for loop and do that by hand, or use a for loop that counts by one and then multiply the index, a do while loop is generated instead and performance is in line with C#:

 let sumVectorLoop =
        let mutable total = Vector<int>.Zero
        for i in 0  .. COUNT/8-1 do
            total <- total + new Vector<int>(numsArray,i*8)
        total    

If there are good reasons why that style of for loop becomes an enumerator and this is just reflecting my lack of practice with the language feel free to close. Thanks for the help everyone.

[dsyme]

@jackmott There is no fundamentally good reason why loops like that use an enumerator, except that the necessary optimizations just aren't done in the F# compiler for striding loops. It would be awesome to have this fixed.

[manofstick]

@dsyme,

Ha, beat me to it by a few minutes :-)

In DetectAndOptimizeForExpression there is a check that is only optimizing for step of 1 or -1.

And then an appropriate change to mkFastForLoop would be required.