Guid.NewGuid() is 10x slower on Linux compared to Windows

[adamsitnik]

Guid.NewGuid() is 10 times slower on Linux compared to Windows.

Slower	diff/base	Windows Median (ns)	Linux Median (ns)	Modality
System.Tests.Perf_Guid.NewGuid	9.52	77.99	742.10

The contributor who wants to work on this issue should:

1. Run this simple benchmark from dotnet/performance repository and confirm the problem

git clone https://github.com/dotnet/performance.git
python3 ./performance/scripts/benchmarks_ci.py -f netcoreapp5.0 --filter System.Tests.Perf_Guid.NewGuid

2. Build CoreCLR locally: https://github.com/dotnet/performance/blob/master/docs/profiling-workflow-corefx.md#Build
3. Create a small repro app: https://github.com/dotnet/performance/blob/master/docs/profiling-workflow-corefx.md#repro
4. Use PerfCollect to identify issue https://github.com/dotnet/performance/blob/master/docs/profiling-workflow-corefx.md#PerfCollect
5. Solve the issue

[stephentoub]

This has been discussed and investigated several times:
https://github.com/dotnet/corefx/issues/3573#issuecomment-163703825
dotnet/coreclr#16643 (comment)

[GrabYourPitchforks]

Our Guid.NewGuid() implementation on Windows delegates to CoCreateGuid, which as an implementation detail creates GUIDs in batches and caches them. Our Guid.NewGuid() implementation on non-Windows creates new GUIDs on-demand without caching. That probably explains the perf difference.

Edit: Apparently the implementation detail has changed since the last time I looked at it. Both Windows and non-Windows call the PRNG directly every time, at least on latest Win10.

[adamsitnik]

On MacOS it's "only" 2.3x slower

[GrabYourPitchforks]

If this is a perf-critical scenario we could have a thread-local cache, as suggested in one of the other linked issues. To be honest it has been several years since I've come across such a scenario.

[adamsitnik]

I've used VTune to profile a small repro:

static void Main(string[] args)
{
    for (int i = 0; i < 10_000_000; i++)
        Consume(Guid.NewGuid());
}

[MethodImpl(MethodImplOptions.NoInlining)]
static void Consume<T>(in T _) { }

Most of the time is spent in libc_read which reads n bytes from given FD (file descriptor?). I stopped there.

@GrabYourPitchforks I am not a security expert, but why can not we use managed Random implementation to generate the bytes for Guid?

public class Randomness
{
    Random _random = new Random();
    unsafe byte[] _bytes = new byte[sizeof(Guid)];
    
    [Benchmark(Baseline = true)]
    public Guid NewGuid() => Guid.NewGuid();

    [Benchmark]
    public Guid FromRandom()
    {
        _random.NextBytes(_bytes);
        
        return new Guid(_bytes);   
    }
}

BenchmarkDotNet=v0.12.0, OS=ubuntu 18.04
Intel Xeon CPU E5-1650 v4 3.60GHz, 1 CPU, 12 logical and 6 physical cores
.NET Core SDK=3.0.100
[Host] : .NET Core 3.0.0 (CoreCLR 4.700.19.46205, CoreFX 4.700.19.46214), X64 RyuJIT
DefaultJob : .NET Core 3.0.0 (CoreCLR 4.700.19.46205, CoreFX 4.700.19.46214), X64 RyuJIT

Method	Mean	Error	StdDev	Ratio
NewGuid	802.5 ns	1.38 ns	1.23 ns	1.00
FromRandom	128.7 ns	1.69 ns	1.58 ns	0.16

[GrabYourPitchforks]

The Random class doesn't provide appropriate distribution. I have a separate email out to the rest of the security crew asking why the implementation uses the syscall arc4random instead of getrandom.

[stephentoub]

@GrabYourPitchforks:
dotnet/corefx#37906
dotnet/corefx#29455

[lpereira]

As a side note here: arc4random(3) isn't a syscall, at least in FreeBSD or OpenBSD (they're both in section 3 of the manual -- libraries -- and not section 2 -- system calls). The actual implementation varies; it might be related to the RC4 cipher, but might not (OpenBSD uses ChaCha20), so it's kind of difficult to determine their performance characteristics.

If this is absolutely something where performance is important, one could use a faster PRNG and use the current methods just to seed (and maybe reseed it every now and then). It's kind of tricky to find a general purpose PRNG, though, as there are various considerations that have to be taken into account.

[iSazonov]

one could use a faster PRNG and use the current methods just to seed (and maybe reseed it every now and then).

After reviewing related issues and PRs and I agree with @lpereira

I believe that preferred solution should be on managed code - one for all platforms (Differences in implementation always cause problems - some Unix libs is already removed from .Net.) using HW intrinsics for RDRAND/RDSEED. Perhaps RDRAND is too slow but we could use RDSEED per thread and an fast xor-shift PRNG with fallback to current code if these instructions are not supported by CPU.
Sometime community doesn't trust to RDRAND/RDSEED but every *BSD/Linux clone has unique implementation of arc4random/urandom - how can we trust its?!

PS: proposed workaround with caching will not work since performance losses occur mainly when reading from urandom. I guess a perf win will be ~2% on socket open-close.

PS2: the same approach could be used for #31271 Path.GetRandomFileName() is 7 times slower on Linux compared to Windows

[adamsitnik]

@iSazonov as a performance guy, I like your idea but I am not sure if our security experts are going to like it

@GrabYourPitchforks @bartonjs what is your opinion about having our own implementation of random that would use HW intrinsics for RDRAND/RDSEED?

[bartonjs]

Having a custom random number generator is contrary to our software security designs. Even if it were OK for us to take a dependency on those CPU instructions directly, the perf data I saw for them suggests that they take about 750ns (possibly amortizes to less with pipelining if you are doing a lot of random data), which wouldn't really speed things up.

I think this is just one of those things where we say "yep, the OSes are different". Most contexts that I've seen wouldn't really consider 1us for generating a GUID to be unacceptably slow, so I'm not sure that this is something to invest in.

[iSazonov]

@adamsitnik @bartonjs Thanks for clarify! But this answer raises even more questions.

so I'm not sure that this is something to invest in.

The GetRandomBytes() is shared by some APIs (I found 5 references - NewGuid, HashCode, Marvin, Path.GetRandomFileName(), Random). So investments here will give a multiple effect.
Also if .Net has different behavior or/and performance on different platforms I'd said that it is very-very bad UX. Here we see too much difference to ignore it.
In PowerShell repo we already have questions (it is not related to NewGuid) like why my script works more slow on Unix than Windows.

Having a custom random number generator is contrary to our software security designs.

Perhaps there was a misconception with "custom". I meant that .Net could use an approved PRNG with seeding from RDSEED. If the HW is still slow the PRNG could improve performance.
I just can not help but ask how this Windows CoCreateGuid() method works so fast? :-) Can MSFT share the experience?