10 ms·

Span<T>.SequenceEquals is faster than memcmp

148 points by xnorswap 2y ago

xnorswap 2y ago
A more meaningful adventure into microbenchmarking than my last. I look at why we no longer need to P/Invoke memcmp to efficiently compare arrays in C# / .NET. Old stackoverflow answers are a dangerous form of bit-rot. They get picked up by well-meaning developers and LLMs alike and recreated years after they are out of date.
- neonsunset 2y ago
  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.
  - xnorswap 2y ago
    No problem, I've raised the issue as https://github.com/dotnet/runtime/issues/114047 https://github.com/dotnet/runtime/issues/114047 .
    - neonsunset 2y ago
      Thanks!
      - jve 2y ago
        19 Hours in and that PR has already hands on from multiple people at MS. Incredible.
  - neonsunset 2y ago
    UPD: For those interested, it was an interaction between microbenchmark algorithm and tiered compilation and not a regression. https://github.com/dotnet/runtime/issues/114047#issuecomment-2764768173 https://github.com/dotnet/runtime/issues/114047#issuecomment...
    - Dylan16807 2y ago
      This is a ten line function that takes half a second to run. Why do you have to call it more than 50 times before it gets fully optimized?? Is the decision-maker completely unaware of the execution time?
      - lozenge 2y ago
        The optimiser doesn't know how long optimisation will take or how much time it will save before starting the work, therefore it has to hold off on optimising not frequently called functions. There are also often multiple concrete types that can be passed in, optimising for one will not help if it is also getting called with other concrete types.
        Dylan16807 2y ago
        > The optimiser doesn't know how long optimisation will take or how much time it will save before starting the work, therefore it has to hold off on optimising not frequently called functions. I don't buy that logic. It can use the length of the function to estimate how long it will take. It can estimate the time savings by the total amount of time the function uses. Time used is a far better metric than call count. And the math to track it is not significantly more complicated than a counter.
        gavinray 2y ago
        > It can use the length of the function to estimate how long it will take. Ah, yes, because a function that defines and then prints a 10,000 line string will take x1,000 longer to run than a 10 line function which does matrix multiplication over several billion elements.
        high_na_euv 2y ago
        I think he meant how long it will take to optimize it It is naive eitherway
- timewizard 2y ago
  The number of times I've caught developers wholesale copying stack overflow posts, errors and all, is far too high.
  - guerrilla 2y ago
    Indeed, the problems of LLMs are not new. We just automated what people who have no idea what they are doing were doing anyway. We... optimized incompetence.
    - eddythompson80 2y ago
      This is a bit elitist isn’t it. It highly depends on the type of code copied and it’s huge part of software engineer bullishness approach to LLMs compared to most other professions. Regardless of how competent as a programmer you are, you don’t necessarily possess the knowledge/answer to “How to find open ports on Linux” or “How to enumerate child pids of a parent pid” or “what is most efficient way to compare 2 byte arrays in {insert language}” etc. A search engine or an LLM is a fine solution for those problems. You know that the answer to that question if what you’re after. I’d generally consider you knowing the right question to ask is all that matters. The answer is not interesting. It’s most likely a deeply nested knowledge about how Linux networking stack works, or how process management works on a particular OS. If that was the central point of the software we’re build (like for example we’re a Linux Networking Stack company) then by all means. It’s silly to find a lead engineer in our company who is confused about how open ports work in Linux.
      - timewizard 2y ago
        In this case it was code to generate an "oauth2 code_challenge" and the correctly URLEncode it. Instead of using replaceAll the example used replace. So only the first character in the string was getting converted. When pressed the developer said they thought their code was "too fast for the oauth server" and that's why it failed about 25% of the time. The level of disappointment I had when I found the problem was enough to be memorable, but to find the post he flat out copied on stack overflow, along with a comment below it highlighting the bug AND the fix, nearly brought be to apoplexy.
junto 2y ago
It’s astounding just how fast modern .NET has become. I’d be curious as to how the .NET (Framework excluded) benchmarks run in a Linux container.
- api 2y ago
  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.
  - kfuse 2y ago
    All modern popular languages are fast, except the most popular one.
    - paulddraper 2y ago
      And Python+Ruby
    - api 2y ago
      JavaScript is hella fast for a dynamically typed language, but that's because we've put insane amounts of effort into making fast JITing VMs for it.
      - zamalek 2y ago
        Sure, but "for a dynamically typed language" still means that it's slow amongst all languages.
  - jeffbee 2y ago
    Java and .NET (and JS or anything that runs under v8 or HotSpot) usually compare favorably to others because they come out of the box with PGO. The outcomes for peak-optimized C++ are very good, but few organizations are capable of actually getting from their C++ build what every .NET user gets for free.
deleted 2y ago
[deleted]
merb 2y ago
> That's not a super helpful description, but the summary is that it's stack-allocated rather than heap allocated. I’m pretty sure that this is not 100% correct, since one can also use other allocation methods and use a span to represent it. Only with stackalloc will the memory it points to be stackallocated. What it basically means is that the type is stack allocated, always, but not the memory it points to.
- john-h-k 2y ago
  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
  - neonsunset 2y ago
    The design of spans does not make assumptions about this however. `ref T` pointer inside the span can point to any memory location. It is not uncommon to wrap unmanaged memory in spans. Another popular case, even if it's something most developers not realize, is readonly spans wrapping constant data embedded in the application binary. For example, if you pass '[1, 2, 3, 4]' to an argument accepting 'ReadOnlySpan<int>' - this will just pass a reference to constant data. It also works for new T[] { } as long as T is a primitive and the target of the expression is a read-only span. It's quite prevalent nowadays but the language tries to get out of your way when doing so.
- MarkSweep 2y ago
  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/runtime-libraries/system-span%7Bt%7D 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.
npalli 2y ago
Any idea on how it compares to std::span in C++. .NET is indeed quite fast nevertheless, (at least since 6).
- loeg 2y ago
  I think it is substantially equivalent to C++ std::span (essentially a typed pointer + length pair).
  - Dwedit 2y ago
    Span<T> is a "ref struct" type, and thus has a lot of restrictions on its use. For instance, you can't have one as a field or property in a class, so you can't assign it to outside of the scope that it was declared in.
    - neonsunset 2y ago
      You can assign the span to an out of scope variable as long as it does not violate the scoping of the memory referenced by that said span. The closer primitive to C#'s Span<T> is Rust's &mut [T] since both are subject to lifetime analysis (of course the one in C#[0] is quite rudimentary in comparison to Rust). [0]: https://em-tg.github.io/csborrow/ https://em-tg.github.io/csborrow/
- jeffbee 2y ago
  C++ std::span doesn't have comparison operators at all. If you were to write an equality operator you might use memcmp, in which case it will be exactly the same as memcmp, which LLVM will helpfully reinterpret as bcmp for best performance. See for example the difference between std::string::operator== and just calling memcmp yourself: https://godbolt.org/z/qn1crox8c https://godbolt.org/z/qn1crox8c
  - f33d5173 2y ago
    bcmp() is identical to memcmp(3); use it instead.
loeg 2y ago
This has gotta be some sort of modest overhead from calling into C memcmp that is avoided by using the native C# construct, right? There's no reason the two implementations shouldn't be doing essentially the same thing internally.
- lstodd 2y ago
  might as well mean that msvcrt's memcmp is terrible
- xnorswap 2y ago
  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.
DeathArrow 2y ago
.NET got pretty fast.
Dwedit 2y ago
The call to "memcmp" has overhead. It's an imported function which cannot be inlined, and the marshaller will automatically create pinned GC handles to the memory inside of the arrays as they are passed to the native code. I wonder how it would compare if you passed actual pointers to "memcmp" instead of marshalled arrays. You'd use "fixed (byte *p = bytes) {" on each array first so that the pinning happens outside of the function call.
- deleted 2y ago
  [deleted]
- xnorswap 2y ago
  I tried that but cut it from the code because it had the same performance.
  - Rohansi 2y ago
    Have you tried the newer [LibraryImport] attribute?
    - xnorswap 2y ago
      I haven't, I wasn't aware of that attribute. I would gratefully accept a PR with such a benchmark case. Edit: I've now tried it, and it reduced overhead a small amount. (e.g. Average 7.5 ns vs 8 ns for the 10-byte array )
- MarkSweep 2y ago
  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/21d518fee314ad484eeec981aeed78f1 https://gist.github.com/AustinWise/21d518fee314ad484eeec981a...
neonsunset 2y ago
FWIW LINQ's SequenceEqual and many other CoreLib methods performing sequence comparison forward to the same underlying comparison routine used here whenever possible. All of this builds on top of very powerful portable SIMD primitives and platform intrinsics that ship with the standard library.
bob1029 2y ago
Span<T> is easily my favorite new abstraction. I've been using the hell out of it for building universal Turing machine interpreters. It's really great at passing arbitrary views of physical data around. I default to using it over arrays in most places now.
- deleted 2y ago
  [deleted]
OptionOfT 2y ago
I did some digging, and found that SequenceEquals is heavily optimized for when T = Byte: https://github.com/dotnet/runtime/blob/454673e1d6da4067750646523ee67e066a388cd7/src/libraries/System.Private.CoreLib/src/System/SpanHelpers.Byte.cs#L760 https://github.com/dotnet/runtime/blob/454673e1d6da406775064... Does memcmp do all of these things? Is msvcrt.dll checking at runtime which extensions the CPU support? Because I don't think msvcrt.dll is recompiled per machine. I think a better test would be to create a DLL in C, expose a custom version of memcmp, and compile that with all the vectorization enabled.
- neonsunset 2y ago
  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/System.Private.CoreLib/src/System/MemoryExtensions.cs#L3416-L3433 https://github.com/dotnet/runtime/blob/main/src/libraries/Sy... and here https://github.com/dotnet/runtime/blob/main/src/coreclr/tools/Common/TypeSystem/IL/Stubs/RuntimeHelpersIntrinsics.cs#L33-L90 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.
- xnorswap 2y ago
  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.
- asveikau 2y ago
  > 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.
userbinator 2y ago
Interestingly, Intel made REP CMPS much faster in the latest CPUs: https://stackoverflow.com/questions/75309389/which-processors-support-fast-short-rep-cmpsb-and-scasb https://stackoverflow.com/questions/75309389/which-processor...
CyanLite2 2y ago
The article missed the biggest thing: SequenceEquals is SIMD accelerated. memcmp is not.
- qingcharles 2y ago
  This is almost certainly the answer. There are a bunch of Intel folks on the dotnet core github regularly pushing new SIMD updates for CPUs that aren't even released yet. They are trying to make sure your .NET code runs nice on your new datacenter servers.
ac130kz 2y ago
memcmp must be missing AVX instructions.
29athrowaway 2y ago
It's not memcmp that's slow, it's the .NET marshalling that has an extra cost.
runevault 2y ago
The amount of optimizations, specifically around using stack allocated objects, .net has seen in recent years is amazing. Another one beyond all the span stuff (though related) that got added in dotnet 9 was AlternateLookup for stuff like dictionary and HashSet where you create a stack allocated object that lets you use stack related objects to compare. Simple example, if you have a dictionary you are building and you're parsing a json file, you can use spans and compare those directly into the dictionary without having to allocate new strings until you know it is a distinct value. (Yes I know you can just use the inbuilt json library, this was just he simplest example of the idea I could think of to get the point across).
groos 2y ago
This is a little bit of bait and click. Of course, SequenceEquals is not as fast as memcmp in absolute terms. In a C or C++ program memcmp usually translates into a compiler intrinsic under optimization. It's only slower than SequenceEquals because of P/Invoke and function call overhead while SequenceEquals is probably JIT-compiled into efficient instructions.
- iforgotpassword 2y ago
  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...
- neonsunset 2y ago
  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.
theshrike79 2y ago
That domain is kinda unfortunate, it has expert-sexchange vibes with Rich Hard ... Wonder how many over-eager corporate filters block it outright?
jiggawatts 2y ago
Is anyone else annoyed with the terrible data visualisations? Too many data points for a bar chart, the colours are far too close together, the colours are easily confused by red-green colourblind users, the colours rotate all the way back to the same yellow/orange/red causing duplicates, and neither the bars nor the colours are in any meaningful kind of order! Then the table shows nanoseconds to 3-digits of fractional precision, which is insane because no modern CPU has clock speeds above 6 Ghz, which is 1/6th of a nanosecond. There is no point showing 1/1000th of a nanosecond! This is just begging to be a pivot-table, but that's a rare sight outside of the finance department. Better yet, show clocks-per-byte at different sizes, which is the meaningful number developers are interested in. Even better yet, take measurements at many more sizes and compute a fit to estimate the fixed overhead (y-intercept) and the clocks-per-byte (slope) and show only those.
- deleted 2y ago
  [deleted]
airybreath 2y ago
The post links to one answer to a StackOverflow question, but the top answer to that same question when sorting by "Trending (recent votes count more)", << https://stackoverflow.com/a/48599119/1083771 https://stackoverflow.com/a/48599119/1083771 >>, suggests exactly* the same thing: use ReadOnlySpan<T>.SequenceEqual *the post suggests that IEnumerable<T>.SequenceEqual is more-or-less the same, but the underlying reason is because ReadOnlySpan<T>.SequenceEqual is so fast that the implementation of IEnumerable<T>.SequenceEqual spends a bit of overhead in order to let it use that exact same call when feasible: https://github.com/dotnet/runtime/blob/v9.0.3/src/libraries/System.Linq/src/System/Linq/SequenceEqual.cs#L27-L30 https://github.com/dotnet/runtime/blob/v9.0.3/src/libraries/...

148 points by xnorswap 2y ago

A more meaningful adventure into microbenchmarking than my last. I look at why we no longer need to P/Invoke memcmp to efficiently compare arrays in C# / .NET. Old stackoverflow answers are a dangerous form of bit-rot. They get picked up by well-meaning developers and LLMs alike and recreated years after they are out of date.

neonsunset 2y ago
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.
- xnorswap 2y ago
  No problem, I've raised the issue as https://github.com/dotnet/runtime/issues/114047 https://github.com/dotnet/runtime/issues/114047 .
  - neonsunset 2y ago
    Thanks!
    - jve 2y ago
      19 Hours in and that PR has already hands on from multiple people at MS. Incredible.
- neonsunset 2y ago
  UPD: For those interested, it was an interaction between microbenchmark algorithm and tiered compilation and not a regression. https://github.com/dotnet/runtime/issues/114047#issuecomment-2764768173 https://github.com/dotnet/runtime/issues/114047#issuecomment...
  - Dylan16807 2y ago
    This is a ten line function that takes half a second to run. Why do you have to call it more than 50 times before it gets fully optimized?? Is the decision-maker completely unaware of the execution time?
    - lozenge 2y ago
      The optimiser doesn't know how long optimisation will take or how much time it will save before starting the work, therefore it has to hold off on optimising not frequently called functions. There are also often multiple concrete types that can be passed in, optimising for one will not help if it is also getting called with other concrete types.
      - Dylan16807 2y ago
        > The optimiser doesn't know how long optimisation will take or how much time it will save before starting the work, therefore it has to hold off on optimising not frequently called functions. I don't buy that logic. It can use the length of the function to estimate how long it will take. It can estimate the time savings by the total amount of time the function uses. Time used is a far better metric than call count. And the math to track it is not significantly more complicated than a counter.
        gavinray 2y ago
        > It can use the length of the function to estimate how long it will take. Ah, yes, because a function that defines and then prints a 10,000 line string will take x1,000 longer to run than a 10 line function which does matrix multiplication over several billion elements.
        high_na_euv 2y ago
        I think he meant how long it will take to optimize it It is naive eitherway
timewizard 2y ago
The number of times I've caught developers wholesale copying stack overflow posts, errors and all, is far too high.
- guerrilla 2y ago
  Indeed, the problems of LLMs are not new. We just automated what people who have no idea what they are doing were doing anyway. We... optimized incompetence.
  - eddythompson80 2y ago
    This is a bit elitist isn’t it. It highly depends on the type of code copied and it’s huge part of software engineer bullishness approach to LLMs compared to most other professions. Regardless of how competent as a programmer you are, you don’t necessarily possess the knowledge/answer to “How to find open ports on Linux” or “How to enumerate child pids of a parent pid” or “what is most efficient way to compare 2 byte arrays in {insert language}” etc. A search engine or an LLM is a fine solution for those problems. You know that the answer to that question if what you’re after. I’d generally consider you knowing the right question to ask is all that matters. The answer is not interesting. It’s most likely a deeply nested knowledge about how Linux networking stack works, or how process management works on a particular OS. If that was the central point of the software we’re build (like for example we’re a Linux Networking Stack company) then by all means. It’s silly to find a lead engineer in our company who is confused about how open ports work in Linux.
    - timewizard 2y ago
      In this case it was code to generate an "oauth2 code_challenge" and the correctly URLEncode it. Instead of using replaceAll the example used replace. So only the first character in the string was getting converted. When pressed the developer said they thought their code was "too fast for the oauth server" and that's why it failed about 25% of the time. The level of disappointment I had when I found the problem was enough to be memorable, but to find the post he flat out copied on stack overflow, along with a comment below it highlighting the bug AND the fix, nearly brought be to apoplexy.

junto 2y ago

It’s astounding just how fast modern .NET has become. I’d be curious as to how the .NET (Framework excluded) benchmarks run in a Linux container.

api 2y ago
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.
- kfuse 2y ago
  All modern popular languages are fast, except the most popular one.
  - paulddraper 2y ago
    And Python+Ruby
  - api 2y ago
    JavaScript is hella fast for a dynamically typed language, but that's because we've put insane amounts of effort into making fast JITing VMs for it.
    - zamalek 2y ago
      Sure, but "for a dynamically typed language" still means that it's slow amongst all languages.
- jeffbee 2y ago
  Java and .NET (and JS or anything that runs under v8 or HotSpot) usually compare favorably to others because they come out of the box with PGO. The outcomes for peak-optimized C++ are very good, but few organizations are capable of actually getting from their C++ build what every .NET user gets for free.

deleted 2y ago

[deleted]

merb 2y ago

> That's not a super helpful description, but the summary is that it's stack-allocated rather than heap allocated. I’m pretty sure that this is not 100% correct, since one can also use other allocation methods and use a span to represent it. Only with stackalloc will the memory it points to be stackallocated. What it basically means is that the type is stack allocated, always, but not the memory it points to.

john-h-k 2y ago
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
- neonsunset 2y ago
  The design of spans does not make assumptions about this however. `ref T` pointer inside the span can point to any memory location. It is not uncommon to wrap unmanaged memory in spans. Another popular case, even if it's something most developers not realize, is readonly spans wrapping constant data embedded in the application binary. For example, if you pass '[1, 2, 3, 4]' to an argument accepting 'ReadOnlySpan<int>' - this will just pass a reference to constant data. It also works for new T[] { } as long as T is a primitive and the target of the expression is a read-only span. It's quite prevalent nowadays but the language tries to get out of your way when doing so.
MarkSweep 2y ago
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/runtime-libraries/system-span%7Bt%7D 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.

npalli 2y ago

Any idea on how it compares to std::span in C++. .NET is indeed quite fast nevertheless, (at least since 6).

loeg 2y ago
I think it is substantially equivalent to C++ std::span (essentially a typed pointer + length pair).
- Dwedit 2y ago
  Span<T> is a "ref struct" type, and thus has a lot of restrictions on its use. For instance, you can't have one as a field or property in a class, so you can't assign it to outside of the scope that it was declared in.
  - neonsunset 2y ago
    You can assign the span to an out of scope variable as long as it does not violate the scoping of the memory referenced by that said span. The closer primitive to C#'s Span<T> is Rust's &mut [T] since both are subject to lifetime analysis (of course the one in C#[0] is quite rudimentary in comparison to Rust). [0]: https://em-tg.github.io/csborrow/ https://em-tg.github.io/csborrow/
jeffbee 2y ago
C++ std::span doesn't have comparison operators at all. If you were to write an equality operator you might use memcmp, in which case it will be exactly the same as memcmp, which LLVM will helpfully reinterpret as bcmp for best performance. See for example the difference between std::string::operator== and just calling memcmp yourself: https://godbolt.org/z/qn1crox8c https://godbolt.org/z/qn1crox8c
- f33d5173 2y ago
  bcmp() is identical to memcmp(3); use it instead.

loeg 2y ago

This has gotta be some sort of modest overhead from calling into C memcmp that is avoided by using the native C# construct, right? There's no reason the two implementations shouldn't be doing essentially the same thing internally.

lstodd 2y ago
might as well mean that msvcrt's memcmp is terrible
xnorswap 2y ago
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.

DeathArrow 2y ago

.NET got pretty fast.

Dwedit 2y ago

The call to "memcmp" has overhead. It's an imported function which cannot be inlined, and the marshaller will automatically create pinned GC handles to the memory inside of the arrays as they are passed to the native code. I wonder how it would compare if you passed actual pointers to "memcmp" instead of marshalled arrays. You'd use "fixed (byte *p = bytes) {" on each array first so that the pinning happens outside of the function call.

deleted 2y ago
[deleted]
xnorswap 2y ago
I tried that but cut it from the code because it had the same performance.
- Rohansi 2y ago
  Have you tried the newer [LibraryImport] attribute?
  - xnorswap 2y ago
    I haven't, I wasn't aware of that attribute. I would gratefully accept a PR with such a benchmark case. Edit: I've now tried it, and it reduced overhead a small amount. (e.g. Average 7.5 ns vs 8 ns for the 10-byte array )
MarkSweep 2y ago
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/21d518fee314ad484eeec981aeed78f1 https://gist.github.com/AustinWise/21d518fee314ad484eeec981a...

neonsunset 2y ago

FWIW LINQ's SequenceEqual and many other CoreLib methods performing sequence comparison forward to the same underlying comparison routine used here whenever possible. All of this builds on top of very powerful portable SIMD primitives and platform intrinsics that ship with the standard library.

bob1029 2y ago

Span<T> is easily my favorite new abstraction. I've been using the hell out of it for building universal Turing machine interpreters. It's really great at passing arbitrary views of physical data around. I default to using it over arrays in most places now.

deleted 2y ago
[deleted]

OptionOfT 2y ago

I did some digging, and found that SequenceEquals is heavily optimized for when T = Byte: https://github.com/dotnet/runtime/blob/454673e1d6da4067750646523ee67e066a388cd7/src/libraries/System.Private.CoreLib/src/System/SpanHelpers.Byte.cs#L760 https://github.com/dotnet/runtime/blob/454673e1d6da406775064... Does memcmp do all of these things? Is msvcrt.dll checking at runtime which extensions the CPU support? Because I don't think msvcrt.dll is recompiled per machine. I think a better test would be to create a DLL in C, expose a custom version of memcmp, and compile that with all the vectorization enabled.

neonsunset 2y ago
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/System.Private.CoreLib/src/System/MemoryExtensions.cs#L3416-L3433 https://github.com/dotnet/runtime/blob/main/src/libraries/Sy... and here https://github.com/dotnet/runtime/blob/main/src/coreclr/tools/Common/TypeSystem/IL/Stubs/RuntimeHelpersIntrinsics.cs#L33-L90 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.
xnorswap 2y ago
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.
asveikau 2y ago
> 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.

userbinator 2y ago

Interestingly, Intel made REP CMPS much faster in the latest CPUs: https://stackoverflow.com/questions/75309389/which-processors-support-fast-short-rep-cmpsb-and-scasb https://stackoverflow.com/questions/75309389/which-processor...

CyanLite2 2y ago

The article missed the biggest thing: SequenceEquals is SIMD accelerated. memcmp is not.

qingcharles 2y ago
This is almost certainly the answer. There are a bunch of Intel folks on the dotnet core github regularly pushing new SIMD updates for CPUs that aren't even released yet. They are trying to make sure your .NET code runs nice on your new datacenter servers.

ac130kz 2y ago

memcmp must be missing AVX instructions.

29athrowaway 2y ago

It's not memcmp that's slow, it's the .NET marshalling that has an extra cost.

runevault 2y ago

The amount of optimizations, specifically around using stack allocated objects, .net has seen in recent years is amazing. Another one beyond all the span stuff (though related) that got added in dotnet 9 was AlternateLookup for stuff like dictionary and HashSet where you create a stack allocated object that lets you use stack related objects to compare. Simple example, if you have a dictionary you are building and you're parsing a json file, you can use spans and compare those directly into the dictionary without having to allocate new strings until you know it is a distinct value. (Yes I know you can just use the inbuilt json library, this was just he simplest example of the idea I could think of to get the point across).

groos 2y ago

This is a little bit of bait and click. Of course, SequenceEquals is not as fast as memcmp in absolute terms. In a C or C++ program memcmp usually translates into a compiler intrinsic under optimization. It's only slower than SequenceEquals because of P/Invoke and function call overhead while SequenceEquals is probably JIT-compiled into efficient instructions.

iforgotpassword 2y ago
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...
neonsunset 2y ago
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.

theshrike79 2y ago

That domain is kinda unfortunate, it has expert-sexchange vibes with Rich Hard ... Wonder how many over-eager corporate filters block it outright?

jiggawatts 2y ago

Is anyone else annoyed with the terrible data visualisations? Too many data points for a bar chart, the colours are far too close together, the colours are easily confused by red-green colourblind users, the colours rotate all the way back to the same yellow/orange/red causing duplicates, and neither the bars nor the colours are in any meaningful kind of order! Then the table shows nanoseconds to 3-digits of fractional precision, which is insane because no modern CPU has clock speeds above 6 Ghz, which is 1/6th of a nanosecond. There is no point showing 1/1000th of a nanosecond! This is just begging to be a pivot-table, but that's a rare sight outside of the finance department. Better yet, show clocks-per-byte at different sizes, which is the meaningful number developers are interested in. Even better yet, take measurements at many more sizes and compute a fit to estimate the fixed overhead (y-intercept) and the clocks-per-byte (slope) and show only those.

deleted 2y ago
[deleted]

airybreath 2y ago

The post links to one answer to a StackOverflow question, but the top answer to that same question when sorting by "Trending (recent votes count more)", << https://stackoverflow.com/a/48599119/1083771 https://stackoverflow.com/a/48599119/1083771 >>, suggests exactly* the same thing: use ReadOnlySpan<T>.SequenceEqual *the post suggests that IEnumerable<T>.SequenceEqual is more-or-less the same, but the underlying reason is because ReadOnlySpan<T>.SequenceEqual is so fast that the implementation of IEnumerable<T>.SequenceEqual spends a bit of overhead in order to let it use that exact same call when feasible: https://github.com/dotnet/runtime/blob/v9.0.3/src/libraries/System.Linq/src/System/Linq/SequenceEqual.cs#L27-L30 https://github.com/dotnet/runtime/blob/v9.0.3/src/libraries/...