Collect Optimization Candidates for Using Intel Hardware Intrinsics in mscorlib

[fiigii]

Status of Intel hardware intrinsic work

At this time (12/13/2017), we have enabled all the infrastructures for Intel hardware intrinsic and certain scalar/SIMD intrinsics. The next step is to implement specific Intel hardware intrinsics.

Optimizing mscorlib using Intel hardware intrinsic

The base class library (mscorlib) is used by every .NET Core program, so its performance is critical, and we can use hardware intrinsics to improve performance of mscorlib by leveraging modern Intel Architecture instructions. For instance, we experimented rewriting the nonrandomized hash function of String with Sse42.Crc32 intrinsic in a micro-benchmark. The result showed that Crc32 version provided 2~5.5x(32-bit)/8.5x(64-bit) performance gain on short strings and 6.5x(32-bit)/12.3x(64-bit) gain hashing for longer strings.

Capturing optimization candidates

This issue attempts to capture a list of optimization candidates in mscorlib for taking advantage of Intel hardware intrinsics. We are looking for popular use cases from the community and mscorlib authors, and their input on how such methods could be optimized. For example, "we use method XYZ intensively, and if XYZ were to be optimized using intrinsic A and B, we may get X% performance gain". That kind of information could help steer subsequent intrinsic work, with highly demanded hardware intrinsics and many uses cases to have higher implementation priority. In addition, listed below are some general guidelines we plan to use when considering optimization candidates.

1. We would prioritize 256-bit SIMD intrinsics (that operate over Vector256<T>) higher because they have distinctive performance advantage over 128-bit SIMD intrinsics, and AVX/AVX2 machines (Sandy Bridge, Haswell, and above) are widely available and used.
2. We would prefer to fully implement an ISA class, then move to another one. When hardware intrinsics ship with the next release (.NET Core 2.1), "IsSupported" will be true only for fully implemented classes. For example, if we want Sse42.Crc32 available in .NET Core 2.1, other SSE4.2 intrinsics should also be implemented in CoreCLR.

[fiigii]

cc @jkotas @CarolEidt @AndyAyersMS @stephentoub @eerhardt @tannergooding @benaadams @4creators

[tannergooding]

I don't think they are highly used, but System.Buffer.Memmove would likely benefit (adding non-temporal support for large buffers might also be useful).

System.Numerics.Vectors may benefit (although outside mscorlib)

Other general areas:

• System.String
• Regex
• Cryptography

[stephentoub]

This isn't a specific answer, but I expect we'd see good wins if the methods on string (e.g. IndexOf, Equals, Compare, etc.) and on array (e.g. IndexOf, Sort if possible, etc.) were optimized with these intrinsics Those are used all over the place, including by other core types in corelib, e.g. List<T>.IndexOf uses Array.IndexOf.

[benaadams]

Not mscorlib but BitCount(long value) in Kestrel and CountBits in System.Reflection.Internal.BitArithmetic would work with popcnt (second could maybe be type forwarded?)

[fiigii]

@benaadams Popcnt is already implemented dotnet/coreclr#14456. Would you like to give a try?

[4creators]

There are several implementations of performance critical functions for web based on SIMD both SSE2 - SSE42 and AVX2:

1. Base64 encoding and decoding.
2. General String search - String.Contains, String.IndexOf.
3. Hash algorithms - there are specialized intrinsics like SHA but besides there are SSE/AVX2 optimized, reference implementations of major hashing algorithms including SHA3/Keccak.
4. Pop count and leading/trailing zero count done faster even than intrinsics for longer streams (I do not recall threshold level though) realized in SSE/AVX2.
5. Collections - Dictionaries/HashTables/Trees using latest algorithms - large group of new implementations on JVM mainly done in Scala world - not patented and open sourced under permissive licenses.
6. Several new SSE/AVX imaging algorithms implementations ranging from image resizing (some are faster than Intel implementations in Intel Performance Primitives library) to color space conversions may suplement or replace some System.Drawing implementations - all open sourced with permissive licences.
7. BigInteger arithmetic.
8. Many more which I could not recall at the moment - will need to do some search in my collected articles.

[HFadeel]

1. General String search - String.Contains, String.IndexOf
2. String encoding and decoding UTF8, UTF16, Base64
3. GetHashCode() in string and other types
4. Regex is a broad area to investigate and improve (.NET Core is 2 to 3 times slower than JVM)

[benaadams]

Encoding Utf8 <-> string, Ascii <-> string (vector widen/narrow)

[danmoseley]

.NET Core is 2 to 3 times slower than JVM

Is that still the case if you use a build from master with RegexOptions.Compiled? In 2.0 that flag did not do anything. If so, do you have a benchmark you could share?

@ViktorHofer is considering options for regex perf.

[danmoseley]

Should have tagged @HFadeel for question above

[danmoseley]

fyi. @bartonjs @JeremyKuhne

[Tornhoof]

@danmosemsft
I tried that out using @ViktorHofer's version of regex-redux https://github.com/ViktorHofer/CompiledRedux-Desktop-Vs-Core. I added the appropriate 2.2 preview SDK and the output is on par with the full framework.
Still it's roughly 2s slower than the original regex-redux java version from https://benchmarksgame.alioth.debian.org/u64q/program.php?test=regexredux&lang=java&id=3

BenchmarkDotNet=v0.10.11, OS=Windows 10 Redstone 3 [1709, Fall Creators Update] (10.0.16299.64)
Processor=Intel Core i7-4790K CPU 4.00GHz (Haswell), ProcessorCount=8
Frequency=3906248 Hz, Resolution=256.0001 ns, Timer=TSC
.NET Core SDK=2.2.0-preview1-007813
  [Host]     : .NET Core 2.1.0-preview1-26013-05 (Framework 4.6.26013.03), 64bit RyuJIT
  Job-YJWDPO : .NET Framework 4.7 (CLR 4.0.30319.42000), 64bit RyuJIT-v4.7.2600.0
  Job-IGBXGQ : .NET Core 2.0.3 (Framework 4.6.25815.02), 64bit RyuJIT
  Job-XFRTQH : .NET Core 2.1.0-preview1-26013-05 (Framework 4.6.26013.03), 64bit RyuJIT

Jit=RyuJit  Platform=X64  InvocationCount=1  
LaunchCount=1  TargetCount=3  UnrollFactor=1  
WarmupCount=1  

Method	Runtime	Toolchain	Mean	Error	StdDev	Gen 0	Gen 1	Gen 2	Allocated
Do	Clr	Default	6.916 s	0.6470 s	0.0366 s	385333.3333	64666.6667	11666.6667	2972.52 MB
Do	Core	.NET Core 2.0	10.523 s	0.5107 s	0.0289 s	387000.0000	64000.0000	13000.0000	356.5 MB
Do	Core	.NET Core 2.1	6.439 s	0.0590 s	0.0033 s	386000.0000	64333.3333	12333.3333	356.5 MB

Java 9.0.1: 4,878875 s

[danmoseley]

Thanks for measuring that. That's 30% slower than Java. Still plenty of room to improve, including perhaps intrinsics.

[redknightlois]

At the moment I am trying a few POCs on our codebase. I would really appreciate if I can make this algorithm to work for showcase purposes on a real workload :D

// This stops the JIT from accesing originalBuffer directly, as we know
// it is not mutable, this lowers the number of generated instructions
byte* originalPtr = (byte*)originalBuffer;
byte* modifiedPtr = (byte*)modifiedBuffer;

var zero = Avx.SetZero<byte>();
for (long i = 0; i < len; i += 32, originalPtr += 32, modifiedPtr += 32)
{
    var o0 = Avx.Load(originalPtr);
    var m0 = Avx.Load(modifiedPtr);

    if (allZeros)
        allZeros &= Avx.TestZ(m0, zero);

    if (Avx.TestZ(o0, m0))
        continue;

   /// ... 
   /// Lots of stuff that I still don't know if it makes sense to try to go SIMD too. 
   /// Not interesting for the purposes of making this work :D
}

[fiigii]

@redknightlois Thank you so much to report this demand. I will implement SetZero and TestZ after the new year.