Improve Performance

[jackmott]

Thanks to @cloudRoutine we have a solid benchmarking framework in place. There are some cases where SIMD versions of the operations don't win, or only win with very large arrays. We should investigate ways to improve that.

Loop Unrolling

Unrolling the main SIMD loop could be viable, as the JIT tends not to do that, while C++ compilers tend to put two SIMD operations per loop. EDIT - I've not managed to get any meaningful performance gains by trying this, but maybe there is a more clever way.

[cloudRoutine]

Maybe playing fast and loose on the stack could kick it up a notch? (was based on this)

We could see if it can combine well with NativePtr.stackalloc<'a>

[jackmott]

Doing some experiments with loop unrolling on map seems to have no change in runtime at all, doing it like so:

 let mutable i, ri = 0, 0    
    while i <= len - (inCount <<< 2) do                
        let mutable v = Vector< ^T>(array,i )
        (f v).CopyTo(result,ri)
        i <- i + inCount
        ri <- ri + outCount
        v <- Vector< ^T>(array,i)
        (f v).CopyTo(result,ri)
        i <- i + inCount
        ri <- ri + outCount
        v <- Vector< ^T>(array,i)
        (f v).CopyTo(result,ri)
        i <- i + inCount
        ri <- ri + outCount
        v <- Vector< ^T>(array,i)
        (f v).CopyTo(result,ri)
        i <- i + inCount
        ri <- ri + outCount

Two at a time, or 4 at a time, no difference. Interestingly it also did not seem to matter if you constrain map to return the same type it started with, which lets you omit the separate ri counter. So maybe memory throughput is the limiter then the mapping function is a single add instruction.

[cloudRoutine]

Have you been inspecting the differences in the generated IL?

[jackmott]

Not yet. But I will have to go down that path soon.

[jackmott]

Another note: filling an array with random values nets very different benchmark results than filling them with a constant value.

[cloudRoutine]

can you post the results? there should be a gh-flavor .md file in the /bin

[jackmott]

How do I run the benchmarks to produce the .md output file? I'm just running it from the command line and only get output to the terminal.

[jackmott]

Ok I seem to have convinced myself that the random values vs constant values different wasn't really happening anyway.

[jackmott]

@cloudRoutine am I interpreting that BlitParser stuff correctly? They are outputting IL by hand there? That is rad.

[cloudRoutine]

Yea it was originally in C#, but I took a look at it and knew I could rewrite it in F# 😀

[jackmott]

So it looks like removing the inline call to getLeftovers and just, actually making it inline is a big win. I will experiment with that more to be sure though.

[jackmott]

So the primary loop for map is :

 while i <= lenLessCount do
        (f (Vector< ^T>(array,i ))).CopyTo(result,i)        
        i <- i + count

and the IL for that loop is:

IL_0038: stloc.s i
    // loop start (head: IL_003a)
        IL_003a: ldloc.s i
        IL_003c: call instance !0 class [FSharp.Core]Microsoft.FSharp.Core.FSharpRef`1<int32>::get_contents()
        IL_0041: ldloc.3
        IL_0042: bgt.s IL_007b

        IL_0044: ldarg.0
        IL_0045: ldarg.1
        IL_0046: ldloc.s i
        IL_0048: call instance !0 class [FSharp.Core]Microsoft.FSharp.Core.FSharpRef`1<int32>::get_contents()
        IL_004d: newobj instance void valuetype [System.Numerics.Vectors]System.Numerics.Vector`1<!!T>::.ctor(!0[], int32)
        IL_0052: callvirt instance !1 class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<valuetype [System.Numerics.Vectors]System.Numerics.Vector`1<!!T>, valuetype [System.Numerics.Vectors]System.Numerics.Vector`1<!!T>>::Invoke(!0)
        IL_0057: stloc.s v
        IL_0059: ldloca.s v
        IL_005b: ldloc.1
        IL_005c: ldloc.s i
        IL_005e: call instance !0 class [FSharp.Core]Microsoft.FSharp.Core.FSharpRef`1<int32>::get_contents()
        IL_0063: call instance void valuetype [System.Numerics.Vectors]System.Numerics.Vector`1<!!T>::CopyTo(!0[], int32)
        IL_0068: ldloc.s i
        IL_006a: ldloc.s i
        IL_006c: call instance !0 class [FSharp.Core]Microsoft.FSharp.Core.FSharpRef`1<int32>::get_contents()
        IL_0071: ldloc.2
        IL_0072: add
        IL_0073: call instance void class [FSharp.Core]Microsoft.FSharp.Core.FSharpRef`1<int32>::set_contents(!0)
        IL_0078: nop
        IL_0079: br.s IL_003a
    // end loop

My IL knowledge is near zero, not sure if there is any low hanging fruit there. I do know that the SIMD stuff creates unnecessary bounds checks but I don't know that those can be elided at the IL level.

[jackmott]

Possible to roll our own copyto without the checks?
https://github.com/dotnet/corefx/blob/future/src/System.Numerics.Vectors/src/System/Numerics/Vector.cs#L777

Doesn't seem like JitIntrinsic is an attribute we get to use :(
It is possible the JitIntrinsic magic elides all of that somehow anyway, as well.

[jackmott]

Oh wow, using a tail recursive main loop instead of a while loop is consistently faster. This test was done with an array of doubles (half as wide as int32s)

Host Process Environment Information:
BenchmarkDotNet=v0.9.8.0
OS=Microsoft Windows NT 6.2.9200.0
Processor=Intel(R) Core(TM) i7-4712HQ CPU 2.30GHz, ProcessorCount=8
Frequency=2240907 ticks, Resolution=446.2479 ns, Timer=TSC
CLR=MS.NET 4.0.30319.42000, Arch=64-bit RELEASE [RyuJIT]
GC=Concurrent Workstation
JitModules=clrjit-v4.6.1080.0

Type=SIMDBenchmark  Mode=Throughput  Platform=X64  
Jit=RyuJit  GarbageCollection=Concurrent Workstation  

Method	Length	Median	StdDev	Gen 0	Gen 1	Gen 2	Bytes Allocated/Op
SIMDMap	10000	13.9526 us	0.2316 us	7,357.00	-	-	35,302.57
SIMDMapRec	10000	9.5063 us	0.1882 us	7,207.81	-	-	34,532.16
Map	10000	11.9088 us	0.1615 us	7,934.99	-	-	34,738.85

[jackmott]

So this trick doesn't work with sum, map2, or map3 unfortunately. Works great with mapInPlace though!

Host Process Environment Information:
BenchmarkDotNet=v0.9.8.0
OS=Microsoft Windows NT 6.2.9200.0
Processor=Intel(R) Core(TM) i7-4712HQ CPU 2.30GHz, ProcessorCount=8
Frequency=2240907 ticks, Resolution=446.2479 ns, Timer=TSC
CLR=MS.NET 4.0.30319.42000, Arch=64-bit RELEASE [RyuJIT]
GC=Concurrent Workstation
JitModules=clrjit-v4.6.1080.0

Type=SIMDBenchmark  Mode=Throughput  Platform=X64  
Jit=RyuJit  GarbageCollection=Concurrent Workstation  

Method	Length	Median	StdDev	Gen 0	Gen 1	Gen 2	Bytes Allocated/Op
SIMDMapInPlace	100000	31.8363 us	0.5257 us	-	-	-	63.30
SIMDMapInPlaceRec	100000	19.5686 us	0.4455 us	-	-	-	36.54
Map	100000	166.5645 us	4.6652 us	-	-	4,582.00	156,742.26