Span<T>.SequenceEquals is faster than memcmp

For loop regression in .NET 9, please submit an issue at dotnet/runtime. It’s yet another loop tearing miscompilation caused by suboptimal loop lowering changes if my guess is correct.

The number of times I've caught developers wholesale copying stack overflow posts, errors and all, is far too high.

I'm pretty sure the marshaling code for the pinvoke is not creating GC handles. It is just using a pinned local, like a fixed statement in csharp does. This is what the LibraryImport at least and I don't see why the built in marshaller would be different. The author says in the peer comment that they confirmed the performance is the same.

I think the blog post is quite good at showing that seemingly similar things can have different performance tradeoffs. A follow up topic might digging deeper into the why. For example, if you look at the disassembly of the p/invoke method, you can see the source of the overhead: setting up a p/invoke frame so the stack is walkable while in native code, doing a GC poll after returning from the native function, and removing the frame.

https://gist.github.com/AustinWise/21d518fee314ad484eeec981a...

I tried that but cut it from the code because it had the same performance.

memcmp and friends can be a funny one when looking at disasm

Depending on context and optimization settings we might see:

  - Gone entirely
  - A memcmp call has been inlined and turned into a single instruction
  - It's turned into a short loop
  - A loop has been turned into a memcmp call.

Subtly I think it also encourages a "that'll do" mindset up the stack. You're working in an environment where you're not really incentivised to care so some patterns just don't feel like they'd have happened in a more native language.

Yeah, as written this is quite confusing and does not describe why a Span is useful. It seems to be a garbled quoting of the first sentence of the supplement documentation about this API:

https://learn.microsoft.com/en-us/dotnet/fundamentals/runtim...

I think a better description of what a Span does is later in the article:

> A Span<T> represents a contiguous region of arbitrary memory. A Span<T> instance is often used to hold the elements of an array or a portion of an array. Unlike an array, however, a Span<T> instance can point to managed memory, native memory, or memory managed on the stack.

The fact that you have to put the Span<T> on the stack only is a limitation worth knowing (and enforced by the compiler). But it is not the most interesting thing about them.

Yes, this is correct. The span itself - the (ptr, len) pair - is on stack (by default) but the data is almost always on the heap, with stackalloc being the most notable exception

I agree, .NET Core has improved by gigantic leaps and bounds. Which makes it all the more frustrating to me that .NET and Java both had "lost decades" of little to no improvement. Java mostly only on the language side, where 3rd-party JVMs still saw decent changes, but .NET both on the language and runtime side. I think this freeze made (and continues to make) people think the ceiling of both performance and developer ergonomics of these languages is much lower than it actually is.

I wonder how it compares to (1) Go, (2) the JVM, and (3) native stuff like Rust and C++.

Obviously as with all such benchmarks the skill of the programmer doing the implementing matters a lot. You can write inefficient clunky code in any language.

I just did some benchmarks of this!

Linux in general provides the same speed for pure CPU workloads like generating JSON or HTML responses.

Some I/O operations run about 20% better, especially for small files.

One killer for us was that the Microsoft.Data.SqlClient is 7x slower on Linux and 10x slower on Linux with Docker compared to a plain Windows VM!

That has a net 2x slowdown effect for our applications which completely wipes out the licensing cost benefit when hosted in Azure.

Other database clients have different performance characteristics. Many users have reported that PostgreSQL is consistent across Windows and Linux.

The comparison isn't to prove that .NET is always faster than C in all circumstances, it was to demonstrate that the advice to call out to C from .NET is outdated and now worse than the naive approach.

Can C wizards write faster code? I'm sure they can, but I bet it takes longer than writing a.SequenceEquals(b) and moving on to the next feature, safe in the knowledge that the standard library is taking care of business.

"Your standard library is more heavily optimised" isn't exactly a gotcha. Yes, the JIT nature of .NET means that it can leverage processor features at runtime, but that is a benefit to being compiled JIT.

> Does memcmp do all of these things? Is msvcrt.dll checking at runtime which extensions the CPU support

It's possible for a C implemention to check the CPU at dynamic link time (when the DLL is loaded) and select which memcmp gets linked.

The most heavily used libc string functions also have a tendency to use SIMD when the data sizes and offsets align, and fall back to the slow path for any odd/unaligned bytes.

I don't know to what extent MSVCRT is using these techniques. Probably some.

Also, it's common for a compiler to recognize references to common string functions and not even emit a call to a shared library, but provide an inline implementation.

It's not limited to bytes. It works with any bitwise comparable primitive i.e. int, long, char, etc.

The logic which decides which path to use is here https://github.com/dotnet/runtime/blob/main/src/libraries/Sy... and here https://github.com/dotnet/runtime/blob/main/src/coreclr/tool... (this one is used by ILC for NativeAOT but the C++ impl. for the JIT is going to be similar)

The [Intrinsic] annotation is present because such comparisons on strings/arrays/spans are specially recognized in the compiler to be unrolled and inlined whenever one of the arguments has constant length or is a constant string or a span which points to constant data.

memcmp is also supposed to be heavily optimized for comparing arrays of bytes since, well, that is literally all that it does.

msvcrt.dll is the C runtime from VC++6 days; a modern (as in, compiled against VC++ released in the last 10 years) C app would use the universal runtime, ucrt.dll. That said, stuff like memcpy or memcmp is normally a compiler intrinsic, and the library version is there only so that you can take an pointer to it and do other such things that require an actual function.

Outside of the 10 elements case, I don't think it's an overhead issue, the overhead is surely minuscule compared to the 1GB of data in the final tests, which also show a large difference in performance.

I suspect it's that the memcmp in the Visual C++ redistributable isn't as optimised for modern processor instructions as the .NET runtime is.

I'd be interested to see a comparison against a better more optimised runtime library.

Ultimately you're right that neither .NET nor C can magic out performance from a processor that isn't fundamentally there, but it's nice that doing the out-of-the-box approach performs well and doesn't require tricks.

might as well mean that msvcrt's memcmp is terrible

I don't think it's clickbait. Even though the title doesn't mention C# or .net explicitly it seems clear from that Span<> stuff that this is talking about some higher level language...

You can look at SquenceEqual implementation and see for yourself. It is as fast in absolute terms and likely faster because it can pick the widest supported vectors. Maybe not as unrolled bot mostly because it’s already fast enough.