Runtime: Adding memcmp intrisinc?

[ayende]

We are using memcmp a _lot_, to do comparisons of pieces of data inside mmap file.
Because of the cost of p/invoke, we wrote our own memory comparison function and only shell to memcmp if the size is large enough to be worth it.

I would rather be able to directly call memcmp without paying the pinvoke costs.
Calls to memset and memcpy are already exposed via Unsafe.InitBlock and Unsafe.CopyBlock, respectively.
See:
https://github.com/dotnet/corefx/blob/64c6d9fe5409be14bdc3609d73ffb3fea1f35797/src/System.Runtime.CompilerServices.Unsafe/src/System.Runtime.CompilerServices.Unsafe.il#L162

What would be the process of adding a similar functionality for exposing memcmp ?

[jkotas]

Unsafe. are thin wrappers over IL instructions. There is no memcmp IL instruction and that's why there is no Unsafe.MemCmp.

int SequenceCompareTo<byte>(ReadOnlySpan<byte> span, ReadOnlySpan<byte> other) is the public API equivalent of memcmp. Have you tried that?

[ayende]

I wasn't aware of SequenceCompareTo, thanks for that. I run the following benchmark ( https://gist.github.com/ayende/4333c4fc3b4eb1ab05680234dbc6b76e ) on three modes.
Very different values, identical values and values that differ only in the end.

The results are:

Different:

Method | N | Mean | Error | StdDev |
-------- |---- |---------:|----------:|----------:|
Native | 16 | 8.032 ns | 0.0084 ns | 0.0075 ns |
Managed | 16 | 5.579 ns | 0.0021 ns | 0.0019 ns |
Native | 32 | 7.616 ns | 0.0059 ns | 0.0055 ns |
Managed | 32 | 5.592 ns | 0.0032 ns | 0.0026 ns |
Native | 256 | 7.564 ns | 0.0049 ns | 0.0046 ns |
Managed | 256 | 4.852 ns | 0.0031 ns | 0.0029 ns |

Same:

Method | N | Mean | Error | StdDev |
-------- |---- |----------:|----------:|----------:|
Native | 16 | 8.845 ns | 0.0193 ns | 0.0181 ns |
Managed | 16 | 8.966 ns | 0.0059 ns | 0.0052 ns |
Native | 32 | 8.325 ns | 0.0075 ns | 0.0066 ns |
Managed | 32 | 10.906 ns | 0.0032 ns | 0.0030 ns |
Native | 256 | 16.161 ns | 0.0018 ns | 0.0016 ns |
Managed | 256 | 30.713 ns | 0.0109 ns | 0.0102 ns |

Almost same:

Method | N | Mean | Error | StdDev |
-------- |---- |----------:|----------:|----------:|
Native | 16 | 8.292 ns | 0.0060 ns | 0.0053 ns |
Managed | 16 | 9.420 ns | 0.0060 ns | 0.0056 ns |
Native | 32 | 8.654 ns | 0.0032 ns | 0.0028 ns |
Managed | 32 | 11.420 ns | 0.0052 ns | 0.0048 ns |
Native | 256 | 16.675 ns | 0.0053 ns | 0.0047 ns |
Managed | 256 | 33.305 ns | 0.0150 ns | 0.0125 ns |

As you can see, if we bail early, we see significant savings by avoiding the pinvoke costs. But for data that require to do a major amount of work, we see that the memcmp is faster _even with the cost of pinvoke_.
That tell me that there is performance to be had on the table if we could call the memcmp without the pinvoke overhead.

Would it make sense to expose this in another location, given how common this operation is?
Or is there another way to call to memcmp without pinvoke overhead somehow?

[ayende]

Okay, I run with some other numbers, not using power of 2 sizes, and I got:

Almost same

Method | N | Mean | Error | StdDev |
-------- |--- |----------:|----------:|----------:|
Native | 17 | 8.779 ns | 0.0078 ns | 0.0073 ns |
Managed | 17 | 6.518 ns | 0.0026 ns | 0.0024 ns |
Native | 25 | 9.355 ns | 0.0166 ns | 0.0155 ns |
Managed | 25 | 7.145 ns | 0.0017 ns | 0.0015 ns |
Native | 79 | 12.130 ns | 0.0020 ns | 0.0018 ns |
Managed | 79 | 13.930 ns | 0.0091 ns | 0.0071 ns |

Same:

Method | N | Mean | Error | StdDev |
-------- |--- |----------:|----------:|----------:|
Native | 17 | 8.526 ns | 0.0056 ns | 0.0053 ns |
Managed | 17 | 6.537 ns | 0.0036 ns | 0.0032 ns |
Native | 25 | 8.887 ns | 0.0217 ns | 0.0203 ns |
Managed | 25 | 7.148 ns | 0.0016 ns | 0.0015 ns |
Native | 79 | 12.668 ns | 0.0348 ns | 0.0325 ns |
Managed | 79 | 13.268 ns | 0.0144 ns | 0.0120 ns |

Different:

Method | N | Mean | Error | StdDev |
-------- |--- |---------:|----------:|----------:|
Native | 17 | 8.368 ns | 0.0010 ns | 0.0007 ns |
Managed | 17 | 5.605 ns | 0.0011 ns | 0.0010 ns |
Native | 25 | 8.025 ns | 0.0008 ns | 0.0007 ns |
Managed | 25 | 5.598 ns | 0.0030 ns | 0.0028 ns |
Native | 79 | 9.581 ns | 0.0065 ns | 0.0061 ns |
Managed | 79 | 4.893 ns | 0.0027 ns | 0.0022 ns |

[benaadams]

Probably better to improve
SpanHelpers.SequenceCompareTo(ref byte first, int firstLength, ref byte second, int secondLength) which has access to the intrinsics of the actual running CPU at Jit time; rather than to include a statically compiled memcmp which would be lowest common denominator CPU?

[ayende]

I wouldn't actually include a static copy of it. My intent was to basically shell to the same memcmp that is used everywhere. I assume that this gets to the normal C library, which is already as optimized as we can get.

[jkotas]

Probably better to improve SpanHelpers.SequenceCompareTo

Agree.

statically compiled memcmp which would be lowest common denominator CPU

memcmp and similar methods are usually statically compiled in multiple flavors, and the most efficient flavor is picked up at runtime based on the current hardware.

[GSPP]

@ayende

which is already as optimized as we can get.

I'm not so sure about that. I saw reports about major optimizations in memcpy/memcmp in standard libraries fairly recently (at most very few years ago). At that time I was amazed to learn that these methods had not been properly optimized before.

I have also seen major optimizations being made in the last year here in the CoreClr repository. Not sure for what memcpy/memcmp API it was. Maybe it was an internal runtime helper, maybe some exposed API.

It is not safe to rely on standard library memcpy/memcmp to be maximally fast.

[redknightlois]

@jkotas I have seen in the code some things that could be streamlined (no guarantees though), but those improvements would also be of benefit given our use case. The code is going to be a bit more complex though because we will be working with intrinsics and managing the emitted assembler type of techniques.

If it is of your interest I can give it a try. I wouldn't start though if there is no interest to pursue that direction.

[jkotas]

We are interested in performance improvements. As you know, we try to maintain a balance between the code complexity and performance of different cases (e.g. it is common for changes like these to help for some cases and regress other cases).

@benaadams tried improvements for SequenceEquals in https://github.com/dotnet/coreclr/pull/22019 that did not seem to work well.

[redknightlois]

Will give it a try then.

[benaadams]

@benaadams tried improvements for SequenceEquals in dotnet/coreclr#22019 that did not seem to work well.

OTOH it did help me notice that IndexOf can be likely significantly improved; which SequenceCompareTo can like benefit from; as they are similar in that they both need to find the location of the match/non-match in a vector and equals already gives it https://github.com/dotnet/coreclr/pull/22118

[benaadams]

i.e. this part specifically of SequenceCompareTo where its processing a non-match I'm referring to:

https://github.com/dotnet/coreclr/blob/a5c5feb8939ae6ae10d9d2b7f2bc8d43ed99bc38/src/System.Private.CoreLib/shared/System/SpanHelpers.Byte.cs#L1076-L1083

[redknightlois]

@benaadams what are the benchmark scenarios you are using for the memcmp. If you already have the code for them, better as we can talk over the same set of results :)

[benaadams]

@redknightlois since I was there... I was thinking something like the last commit https://github.com/dotnet/coreclr/pull/22127/commits/342cbe42860b92c6b1a89ab26beda2440bee46a2 (untested) on https://github.com/dotnet/coreclr/pull/22127

[benaadams]

Using changes in https://github.com/dotnet/coreclr/pull/22127

Different

|  Method |   N |      Mean |
|-------- |---- |----------:|
|  Native |  16 | 10.751 ns |
| Managed |  16 |  5.141 ns |
|  Native |  17 | 10.705 ns |
| Managed |  17 |  4.582 ns |
|  Native |  25 | 10.564 ns |
| Managed |  25 |  4.435 ns |
|  Native |  32 | 10.551 ns |
| Managed |  32 |  5.227 ns |
|  Native |  79 | 10.360 ns |
| Managed |  79 |  4.584 ns |
|  Native | 256 | 10.813 ns |
| Managed | 256 |  5.013 ns |

AlmostSameButDifferent

|  Method |   N |      Mean |
|-------- |---- |----------:|
|  Native |  16 | 11.298 ns |
| Managed |  16 |  4.717 ns |
|  Native |  17 | 13.002 ns |
| Managed |  17 |  5.557 ns |
|  Native |  25 | 12.173 ns |
| Managed |  25 |  5.548 ns |
|  Native |  32 | 12.470 ns |
| Managed |  32 |  4.613 ns |
|  Native |  79 | 16.639 ns |
| Managed |  79 |  7.081 ns |
|  Native | 256 | 21.392 ns |
| Managed | 256 | 11.007 ns |

Same

|  Method |   N |      Mean |
|-------- |---- |----------:|
|  Native |  16 | 11.471 ns |
| Managed |  16 |  4.686 ns |
|  Native |  17 | 11.454 ns |
| Managed |  17 |  4.527 ns |
|  Native |  25 | 11.966 ns |
| Managed |  25 |  4.552 ns |
|  Native |  32 | 11.751 ns |
| Managed |  32 |  3.999 ns |
|  Native |  79 | 16.089 ns |
| Managed |  79 |  5.850 ns |
|  Native | 256 | 21.342 ns |
| Managed | 256 | 10.994 ns |