Proposal: improve System.Guid performance with LayoutKind.Explicit and static arrays

[OlegAxenow]

I am not sure about possibility to use LayoutKind.Explicit for System.Guid and to add several fields, although all proposed changes are (binary) compatible with current implementation. That's why I made a separate repository with several benchmarks.

Are these changes acceptable? If yes, I'll try to write a pull request.

Changes details

1. 5 fields added for Equals and CompareTo methods. 16 (byte) fields added for ToString and TryParseExact methods.
2. Equals and CompareTo methods have become faster due to less comparisons (with less fields).
3. ToString and TryParseExact methods have become faster due to using static arrays.

Benchmarks

• "Guid" prefix used for original System.Guid methods, "Uuid" — for FastGuid.Uuid methods.
• Equals benchmark results too good because of aggressive inlining (can be slower when inlining not available).
• For CompareTo and Equals two benchmarks used for each struct to see the difference between comparing the same and different identifiers.
• For CompareTo and Equals appropriate methods called thrice like _guid1.CompareTo(_guid2) ^ _guid2.CompareTo(_guid3) ^ _guid3.CompareTo(_guid1).
• For ToString last letter means one of the standard guid formats — D, B, N or X.

CompareTo

Method	Mean	Error	StdDev	Min	Max	Ratio
GuidDifferentCompare	8.019 ns	0.0194 ns	0.0162 ns	8.001 ns	8.063 ns	1.00
GuidSameCompare	24.242 ns	0.0817 ns	0.0764 ns	24.102 ns	24.335 ns	3.02
UuidDifferentCompare	3.862 ns	0.0056 ns	0.0053 ns	3.855 ns	3.870 ns	0.48
UuidSameCompare	13.991 ns	0.0711 ns	0.0665 ns	13.903 ns	14.110 ns	1.75

Equals

Method	Mean	Error	StdDev	Min	Max	Ratio
GuidDifferentEquals	5.866 ns	0.0185 ns	0.0173 ns	5.833 ns	5.891 ns	1.00
GuidSameEquals	7.537 ns	0.0067 ns	0.0059 ns	7.525 ns	7.549 ns	1.29
UuidDifferentEquals	2.387 ns	0.0080 ns	0.0067 ns	2.378 ns	2.401 ns	0.41
UuidSameEquals	4.034 ns	0.0138 ns	0.0129 ns	4.000 ns	4.051 ns	0.69

ToString

Method	Mean	Error	StdDev	Min	Max	Ratio
GuidToStringD	59.02 ns	0.1131 ns	0.1058 ns	58.82 ns	59.21 ns	1.00
GuidToStringB	59.08 ns	0.1472 ns	0.1377 ns	58.87 ns	59.35 ns	1.00
GuidToStringN	61.67 ns	0.0938 ns	0.0783 ns	61.56 ns	61.81 ns	1.05
GuidToStringX	68.10 ns	0.3475 ns	0.3251 ns	67.59 ns	68.69 ns	1.15
UuidToStringD	24.95 ns	0.0414 ns	0.0346 ns	24.91 ns	25.01 ns	0.42
UuidToStringB	28.32 ns	0.0455 ns	0.0404 ns	28.26 ns	28.40 ns	0.48
UuidToStringN	24.01 ns	0.0446 ns	0.0396 ns	23.96 ns	24.11 ns	0.41
UuidToStringX	33.82 ns	0.1509 ns	0.1411 ns	33.56 ns	34.04 ns	0.57

TryParseExact

Method	Mean	Error	StdDev	Median	Min	Max	Ratio
GuidTryParseExactD	295.73 ns	0.5214 ns	0.6207 ns	295.67 ns	294.35 ns	297.03 ns	1.00
GuidTryParseExactB	293.97 ns	1.0966 ns	1.3468 ns	294.20 ns	288.35 ns	295.10 ns	0.99
GuidTryParseExactN	417.32 ns	0.4367 ns	0.5522 ns	417.35 ns	416.38 ns	418.63 ns	1.41
GuidTryParseExactX	697.23 ns	1.3468 ns	1.6540 ns	697.81 ns	693.32 ns	699.37 ns	2.36
UuidTryParseExactD	39.67 ns	0.3329 ns	0.4444 ns	39.42 ns	39.30 ns	40.74 ns	0.13
UuidTryParseExactB	40.94 ns	0.2564 ns	0.3423 ns	41.07 ns	40.10 ns	41.15 ns	0.14
UuidTryParseExactN	39.86 ns	0.1022 ns	0.1217 ns	39.81 ns	39.73 ns	40.19 ns	0.13
UuidTryParseExactX	44.96 ns	0.1092 ns	0.1458 ns	45.01 ns	44.69 ns	45.13 ns	0.15

[OlegAxenow]

I forgot to mention that my parsing implementation rejects strings like these:

• "00000000-0x00-0x12-0000-000000000000"
• "00000000-0x00-0X12-0000-000000000000"
• "00000000-0x00-+123-0000-000000000000"

System.Guid implementation accepts such strings.

P.S. It's hard for me to imagine using such patterns in real-world applications...

[stephentoub]

It's fine to change the implementation to improve performance, so feel free to submit a PR along with the associated measurements, but we should not break compatibility (even if some behaviors seem odd) without a really good reason, so all of the Guid tests need to continue to pass.

[danmoseley]

It would probably be ok though if parsing unlikely cases like 00000000-0x00-+123-0000-000000000000 got slower (eg through bailing out of the fast path on an error )

[jkotas]

• Adding fields and changing Guid struct to be ExplicitLayout is likely going to break interop. Errors on Unix when changing decimal to explicit layout corert#4994 is a similar issue that was hit when similar tricks were applied to Decimal. Note that this is platform specific - you may be getting lucky on Windows x64, but it may break on Linux x64 or Windows arm64. You do not really need to add new fields to do these tricks. Instead, you can recast the structure in place. Number of places in Guid do that already - look for Unsafe.

• We are sharing the class libraries with Mono. Mono runs on big endian platforms and on platforms with strict alignment requirements. The code needs code be compatible with these platforms. We do not have automatic testing for this yet in CI. We depend on codereview to flag issues like these.

[OlegAxenow]

@stephentoub,@danmosemsft,
I'll try to do that, thank you. Did I understand correctly that passing all the tests from here is enough (except manual review for some platforms)?

@jkotas,
Of course, recasting the structure is a safer way, although a bit slower. I'll try to do that.

I was thinking of making an adaptation for arm64 later.
Can you advice me how I can test arm64 version without device for test? I was not interested in arm64 before...

[stephentoub]

Did I understand correctly that passing all the tests from here is enough

Those, and the GuidTests.netcoreapp.cs file, are the main tests we have specific to Guid. But we could of course have test gaps. And there could be other corefx test suites exercising Guid indirectly. CI in coreclr will run all of the corefx tests, including those (subject to the platform limitations @jkotas called out).

[Wraith2]

Is adding 2K of static data in corelib a good idea?
Could equals be vectorized? It seems like a 128bit comparison is exactly the kind of thing it could be used for.

[jkotas]

Can you advice me how I can test arm64 version without device for test?

Our CI system runs tests on ARM64. You can submit WIP PR to see whether the change passes on ARM64 and other platforms.

Note that this change would need to be submitted through https://github.com/dotnet/coreclr repo. The Guid implementation is in CoreLib that is part of the runtime.

[stephentoub]

Also, for parsing, make sure you're comparing against the latest in master rather than against .NET Core 2.1. dotnet/coreclr#20183 improved Guid parsing perf (though not to the same degree your metrics above cite, but maintaining compatibility).

[danmoseley]

dotnet/coreclr#20183

[OlegAxenow]

Our CI system runs tests on ARM64. You can submit WIP PR to see whether the change passes on ARM64 and other platforms.

Note that this change would need to be submitted through https://github.com/dotnet/coreclr repo. The Guid implementation is in CoreLib that is part of the runtime.

Thank you! Can I ask you a couple more questions?

I have read Contributing to .NET Core / Contributing to mscorlib library and saw this recommendation:

The type exists in both CoreCLR and CoreFX repo -> choose CoreFX.

1. Did you mean that I can submit WIP PR to CoreCLR only to test on ARM64 and should submit normal PR to CoreFX?
2. Can I use something like #ifdef _TARGET_ARM64_ or something else in Guid.cs to write different code for different chips? This is because I should use different layout sometimes. Perhaps somewhere there are recommendations for such situations?

[jkotas]

The type exists in both CoreCLR and CoreFX repo -> choose CoreFX.

That guideline is outdated/confusing - the right repo to submit this change to is CoreCLR.

Can I use something like #ifdef _TARGET_ARM64_ or something else in Guid.cs

We try to minimize the amount of platform specific code in the implementation, even if that means losing a tiny bit of performance. If you can show that the custom layout per platform has very large performance advantage, we can consider it, but I doubt that it will be the case for Guid.

[jkotas]

That guideline is outdated/confusing

Updated in dotnet/coreclr#21201

[OlegAxenow]

We try to minimize the amount of platform specific code in the implementation, even if that means losing a tiny bit of performance. If you can show that the custom layout per platform has very large performance advantage, we can consider it, but I doubt that it will be the case for Guid.

Thank you. I think I'll postpone the PR for Equals and CompareTo methods (it seems to me that it will be difficult to adapt them without hurting performance, if on some platforms the Guid takes more than 16 bytes).

I'll think about how to adapt TryParseExact. I have some ideas on how to maintain compatibility and not lose much in performance. And the static array can be made less than 512 bytes.

[GSPP]

System.Guid implementation accepts such strings.

That is... unfortunate. Maybe we should have a Guid parsing mode that is strict about it's input. I had always assumed that parsing a Guid would be sufficient validation for that string. It turns out it allows crazy strings.

[stephentoub]

Maybe we should have a Guid parsing mode that is strict about it's input

There is: TryParseExact with any of the formats other than X is very strict... X is just more forgiving than you'd expect.

[OlegAxenow]

There is: TryParseExact with any of the formats other than X is very strict... X is just more forgiving than you'd expect.

More precisely, other than "X" and "D". My examples above assume format "D".
I still can't imagine using such patterns in real applications, but I believe that someone can use this.

Maybe it is worth adding two more strict formats (with other letters)?

[stephentoub]

More precisely, other than "X" and "D"

Ah, I forgot about D. Which also means the others except for N.

[OlegAxenow]

More precisely, other than "X" and "D"

Ah, I forgot about D. Which also means the others except for N.

:)

What do you think about adding strict formats?
This will maintain backward compatibility and add the ability to rely on strict formats explicitly.

[stephentoub]

I've not heard of the existing ones causing any actual problems, and while it's great to make things as fast as possible, parsing perf is already significantly improved for 3.0, and it's not clear to me that introducing new formats to make it much faster will significantly move the needle on any real workloads. I'd want to see evidence of real apps suffering before we invested in additional formats.

[OlegAxenow]

I did not mean performance. I'll adapt my changes to existing logic.

For me, the problem is input data validation. For example, "00000000-0x00-+123-0000-000000000000" is not what I expect from input data in my projects.
From the documentation it is also not very obvious that such strings will be accepted.

[Wraith2]

if on some platforms the Guid takes more than 16 bytes

Is this likely? and if so how would you detect it? I've got a vectorised version of Equals which is 50% faster but it would need to be able to detect this in a jit const way to get the speedup effectively.

[OlegAxenow]

if on some platforms the Guid takes more than 16 bytes

Is this likely? and if so how would you detect it? I've got a vectorised version of Equals which is 50% faster but it would need to be able to detect this in a jit const way to get the speedup effectively.

I do not know the details (I decided to adapt the parsing first and such detection is not required for parsing). I made my conclusions based on this answer by @jkotas:

• Adding fields and changing Guid struct to be ExplicitLayout is likely going to break interop. dotnet/corert#4994 is a similar issue that was hit when similar tricks were applied to Decimal. Note that this is platform specific - you may be getting lucky on Windows x64, but it may break on Linux x64 or Windows arm64. You do not really need to add new fields to do these tricks. Instead, you can recast the structure in place. Number of places in Guid do that already - look for Unsafe.
• We are sharing the class libraries with Mono. Mono runs on big endian platforms and on platforms with strict alignment requirements. The code needs code be compatible with these platforms. We do not have automatic testing for this yet in CI. We depend on codereview to flag issues like these.

[Wraith2]

Looking at the current Equals implementation I don't think it would be correct if all platforms didn't have a contiguous layout. It calculates offsets from the first field which would be incorrect if there were ever padding. Even though the layout is sequential the fields are all blittable and can be obviously packed as they are, I'd be surprised if anything required more space.

[jkotas]

Guid is 16 bytes on all platforms and it is not going to change. I was talking specifically about breaking nature of adding fields and ExplicitLayout for interop because that is what the FastGuid prototype has done. It added fields but have not changed Guid size.

[OlegAxenow]

Thank you for the clarification!
In a day or two I will need to discuss the details of the proposed changes for parsing. Is it better to do here or create a separate issue?

[OlegAxenow]

I added PR dotnet/runtime#22465.

The results of all the checks I will find out tomorrow. I'm not sure when I will be available, so I apologize in advance if I can’t quickly respond to comments.

[OlegAxenow]

Should I do something else with the PR dotnet/runtime#22465?

[OlegAxenow]

Unfortunately, PR is too unstable in term of performance in different environments.

[stephentoub]

Thank you for working on it!