Skip to content

Path.GetRandomFileName() is 7 times slower on Linux compared to Windows #31271

Open

Description

@adamsitnik

Path.GetRandomFileName() is 7 times slower on Linux compared to Windows.

Slower diff/base Windows Median (ns) Linux Median (ns) Modality
System.IO.Tests.Perf_Path.GetRandomFileName 7.48 100.47 751.86

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.IO.Tests.Perf_Path.GetRandomFileName
  1. Build CoreCLR locally: https://github.com/dotnet/performance/blob/master/docs/profiling-workflow-corefx.md#Build
  2. Create a small repro app: https://github.com/dotnet/performance/blob/master/docs/profiling-workflow-corefx.md#repro
  3. Use PerfCollect to identify issue https://github.com/dotnet/performance/blob/master/docs/profiling-workflow-corefx.md#PerfCollect
  4. Solve the issue

Activity

  1. stephentoub commented on Oct 23, 2019

    @stephentoub
    Member

    The bulk of the cost of GetRandomFileName is presumably in getting the randomness, which is also the only part of the code that's platform-specific and differs between platforms.
    https://github.com/dotnet/coreclr/blob/master/src/System.Private.CoreLib/shared/Interop/Unix/System.Native/Interop.GetRandomBytes.cs
    https://github.com/dotnet/coreclr/blob/master/src/System.Private.CoreLib/shared/Interop/Windows/BCrypt/Interop.BCryptGenRandom.GetRandomBytes.cs
    I'm not sure how much that can realistically be improved. Maybe dotnet/corefx#37906 will help.

  2. am11 commented on Oct 30, 2019

    @am11
    Member

    An alternative to OS based random could be managed implementation of http://vigna.di.unimi.it/ftp/papers/xorshift.pdf, based on George Marsaglia's simple xor-shift pseudo random. e.g. https://github.com/bewaretech/PEA.NET/blob/40f851db/src/PEA/PEA/Util/FastRandom.cs#L149, which claims:

    ///  2) Faster than System.Random. Up to 8x faster, depending on which methods are called.
    
  3. transferred this issue fromdotnet/corefxon Feb 1, 2020
  4. AaronRobinsonMSFT commented on Feb 1, 2020

    @AaronRobinsonMSFT
    Member
  5. lpereira commented on Feb 3, 2020

    @lpereira
    Contributor

    There's some work improving it already in #1433. It should improve performance ever so slightly (as it doesn't always XOR with the result of srand() -- it only does so when it detects that the OS method didn't produce good enough numbers according to a simple heuristic).

    Since that function doesn't necessarily needs cryptographically-secure numbers, I can use the current method (that requires a syscall on Linux) just to seed a RNG that's entirely in userspace. Probably something in the family of xorshift, as it requires very little state and is, for many non-cryptographic purposes, good enough. Will do a follow-up patch implementing this.

  6. stephentoub commented on Feb 3, 2020

    @stephentoub
    Member

    From the docs:
    https://docs.microsoft.com/en-us/dotnet/api/system.io.path.getrandomfilename?view=netcore-3.1
    "The GetRandomFileName method returns a cryptographically strong, random string that can be used as either a folder name or a file name."

  7. lpereira commented on Feb 3, 2020

    @lpereira
    Contributor

    Ah. GetRandomBytes() isn't supposed to generate cryptographically secure numbers, so maybe GetRandomFileName() shouldn't be using it in the first place?

    Since GetRandomBytes() is internal, maybe it could be renamed to GetEntropyForSeeding(), and a PRNG using something from System.Security.Cryptography (AesCcm as it's already implemented, or something like ChaCha20, which is used by OpenSSH-portable to implement arc4random(), or even RandomNumberGenerator) could be used instead?

    For places where crypto-safe numbers aren't needed, GetEntropyForSeeding() can be used to kickstart something fast-but-not-crypto-safe.

    This way, we clear up this confusion, keep in the managed code for longer, and go down to the native side of things when needed.

  8. stephentoub commented on Feb 6, 2020

    @stephentoub
    Member

    so maybe GetRandomFileName() shouldn't be using it in the first place?

    Probably.

  9. jkotas commented on Feb 6, 2020

    @jkotas
    Member

    The output of Path.GetRandomFileName has 8 bytes in it. I believe that it is misleading to say that it returns cryptographically strong string. It depends on how you are using this string. I think we should remove the cryptographically strong part from the docs.

    GetRandomBytes() isn't supposed to generate cryptographically secure numbers

    FWIW, here is a discussion how we ended up with this: dotnet/corefx#16652 . The output of it are cryptographically strong bytes (for some definitions of cryptographically strong) on all platforms we care about.

  10. removed
    untriagedNew issue has not been triaged by the area owner
    on Feb 27, 2020
  11. JeremyKuhne commented on Feb 27, 2020

    @JeremyKuhne
    Member

    Triage: We should be clearer in the docs around using the terms "cryptographically strong" (probably remove it). Changing the the heuristics here should be done with caution as it will potentially cause undesirable consequences. If we can be confident in the distribution of names, and we don't change the set of characters that are used, than changing this would probably be fine.

  12. DeerBear commented on Apr 3, 2020

    @DeerBear

    What's wrong with reading from /dev/urandom as a seed?

  13. added this to the Future milestone on Jun 29, 2020
  14. am11 commented on Sep 21, 2024

    @am11
    Member
    Benchmark
    using System;
    using System.IO;
    using System.Diagnostics;
    using BenchmarkDotNet;
    using BenchmarkDotNet.Attributes;
    
    namespace rand1
    {
        [MemoryDiagnoser(false)]
        public class Benchmarks
        {
    
            [Benchmark]
            public string GetRandomFileName() => Path.GetRandomFileName();
    
            [Benchmark]
            public string GetRandomFileName2() => RandomFileNameGenerator.Get();
        }
    
        file static class RandomFileNameGenerator
        {
            private const int KeyLength = 8;
    
            private static ReadOnlySpan<byte> Base32Char => "abcdefghijklmnopqrstuvwxyz012345"u8;
            private static readonly object _syncState = new object();
    
            public static uint _x = (uint)Environment.TickCount;
            private static uint _y = 842502087;
            private static uint _z = 3579807591;
            private static uint _w = 273326509;
    
            public static unsafe string Get()
            {
                byte* buffer = stackalloc byte[8];
    
                lock(_syncState)
                    NextBytes(buffer);
    
                return string.Create(
                   12, (IntPtr)buffer, (span, key) => // 12 == 8 + 1 (for period) + 3
                       Populate83FileNameFromRandomBytes((byte*)key, KeyLength, span));
            }
    
            // implementation of http://vigna.di.unimi.it/ftp/papers/xorshift.pdf, based on George Marsaglia's simple xor-shift pseudo random.
            // https://github.com/bewaretech/PEA.NET/blob/40f851db/src/PEA/PEA/Util/FastRandom.cs#L149 (Apache 2.0)
            private static unsafe void NextBytes(byte* buffer)
            {
                uint x = _x, y = _y, z = _z, w = _w;
                int i = 0;
                uint t;
                for (int bound = KeyLength - 3; i < bound;)
                {
                    t = (x ^ (x << 11));
                    x = y; y = z; z = w;
                    w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
    
                    buffer[i++] = (byte)w;
                    buffer[i++] = (byte)(w >> 8);
                    buffer[i++] = (byte)(w >> 16);
                    buffer[i++] = (byte)(w >> 24);
                }
    
                if (i < KeyLength)
                {
                    t = (x ^ (x << 11));
                    x = y; y = z; z = w;
                    w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
    
                    buffer[i++] = (byte)w;
                    if (i < KeyLength)
                    {
                        buffer[i++] = (byte)(w >> 8);
                        if (i < KeyLength)
                        {
                            buffer[i++] = (byte)(w >> 16);
                            if (i < KeyLength)
                            {
                                buffer[i] = (byte)(w >> 24);
                            }
                        }
                    }
                }
    
                _x = x; _y = y; _z = z; _w = w;
            }
    
            // existing helper https://github.com/dotnet/runtime/blob/529804afcd9a84499945467c8d04b21a6f674cbd/src/libraries/System.Private.CoreLib/src/System/IO/Path.cs#L794
            private static unsafe void Populate83FileNameFromRandomBytes(byte* bytes, int byteCount, Span<char> chars)
            {
                // This method requires bytes of length 8 and chars of length 12.
                Debug.Assert(bytes != null);
                Debug.Assert(byteCount == 8, $"Unexpected {nameof(byteCount)}");
                Debug.Assert(chars.Length == 12, $"Unexpected {nameof(chars)}.Length");
    
                byte b0 = bytes[0];
                byte b1 = bytes[1];
                byte b2 = bytes[2];
                byte b3 = bytes[3];
                byte b4 = bytes[4];
    
                // write to chars[11] first in order to eliminate redundant bounds checks
                chars[11] = (char)Base32Char[bytes[7] & 0x1F];
    
                // Consume the 5 Least significant bits of the first 5 bytes
                chars[0] = (char)Base32Char[b0 & 0x1F];
                chars[1] = (char)Base32Char[b1 & 0x1F];
                chars[2] = (char)Base32Char[b2 & 0x1F];
                chars[3] = (char)Base32Char[b3 & 0x1F];
                chars[4] = (char)Base32Char[b4 & 0x1F];
    
                // Consume 3 MSB of b0, b1, MSB bits 6, 7 of b3, b4
                chars[5] = (char)Base32Char[
                        ((b0 & 0xE0) >> 5) |
                        ((b3 & 0x60) >> 2)];
    
                chars[6] = (char)Base32Char[
                        ((b1 & 0xE0) >> 5) |
                        ((b4 & 0x60) >> 2)];
    
                // Consume 3 MSB bits of b2, 1 MSB bit of b3, b4
                b2 >>= 5;
    
                Debug.Assert((b2 & 0xF8) == 0, "Unexpected set bits");
    
                if ((b3 & 0x80) != 0)
                    b2 |= 0x08;
                if ((b4 & 0x80) != 0)
                    b2 |= 0x10;
    
                chars[7] = (char)Base32Char[b2];
    
                // Set the file extension separator
                chars[8] = '.';
    
                // Consume the 5 Least significant bits of the remaining 3 bytes
                chars[9] = (char)Base32Char[bytes[5] & 0x1F];
                chars[10] = (char)Base32Char[bytes[6] & 0x1F];
            }
        }
    }

    Note: unix is currently (in main) using non-crypto random and windows using crypto random, while the proposed managed implementation is non-crypto random.

    Windows:

    // * Summary *

    BenchmarkDotNet v0.14.0, Windows 11 (10.0.22631.4169/23H2/2023Update/SunValley3)
    13th Gen Intel Core i7-1365U, 1 CPU, 12 logical and 10 physical cores
    .NET SDK 8.0.400
    [Host] : .NET 9.0.0 (9.0.24.46307), X64 RyuJIT AVX2
    Job-XTXYQT : .NET 9.0.0 (9.0.24.46307), X64 RyuJIT AVX2

    Toolchain=.NET 9.0

    Method Mean Error StdDev Allocated
    GetRandomFileName 45.42 ns 0.265 ns 0.235 ns 48 B
    GetRandomFileName2 18.11 ns 0.202 ns 0.189 ns 48 B

    Linux (same machine using WSL):

    // * Summary *

    BenchmarkDotNet v0.14.0, Ubuntu 24.04 LTS (Noble Numbat) WSL
    13th Gen Intel Core i7-1365U, 1 CPU, 12 logical and 6 physical cores
    .NET SDK 8.0.108
    [Host] : .NET 9.0.0 (9.0.24.46307), X64 RyuJIT AVX2
    Job-LAVSVF : .NET 9.0.0 (9.0.24.46307), X64 RyuJIT AVX2

    Toolchain=.NET 9.0

    Method Mean Error StdDev Median Allocated
    GetRandomFileName 581.59 ns 7.980 ns 18.653 ns 574.64 ns 48 B
    GetRandomFileName2 23.60 ns 0.926 ns 2.732 ns 24.66 ns 48 B

    Mac:

    // * Summary *

    BenchmarkDotNet v0.14.0, macOS Sonoma 14.6.1 (23G93) [Darwin 23.6.0]
    Apple M1 Pro, 1 CPU, 10 logical and 10 physical cores
    .NET SDK 8.0.401
    [Host] : .NET 9.0.0 (9.0.24.46307), Arm64 RyuJIT AdvSIMD
    Job-SESMBK : .NET 9.0.0 (9.0.24.46307), Arm64 RyuJIT AdvSIMD

    Toolchain=.NET 9.0

    Method Mean Error StdDev Allocated
    GetRandomFileName 47.82 ns 0.210 ns 0.164 ns 48 B
    GetRandomFileName2 16.74 ns 0.188 ns 0.157 ns 48 B

    It can be further improved (vectorization, light-weight or no locking etc.), but is the implementation heading in the right direction?

    Update: lock-free with `[ThreadStatic]` performing slightly better on osx-arm64:
        file static class RandomFileNameGenerator2
        {
            private const int KeyLength = 8;
    
            private static ReadOnlySpan<byte> Base32Char => "abcdefghijklmnopqrstuvwxyz012345"u8;
    
            [ThreadStatic] private static uint _x;
            [ThreadStatic] private static uint _y;
            [ThreadStatic] private static uint _z;
            [ThreadStatic] private static uint _w;
            [ThreadStatic] private static bool _isInitialized;
    
            private static void InitializeState()
            {
                if (!_isInitialized)
                {
                    var seed = (uint)Environment.TickCount;
                    _x = seed;
                    _y = seed ^ 842502087;
                    _z = seed ^ 3579807591;
                    _w = seed ^ 273326509;
                    _isInitialized = true;
                }
            }
    
            public static unsafe string Get()
            {
                InitializeState(); // Ensure each thread initializes its state once
    
                byte* buffer = stackalloc byte[KeyLength];
                NextBytes(buffer);
    
                return string.Create(
                    12, (IntPtr)buffer, (span, key) =>
                        Populate83FileNameFromRandomBytes((byte*)key, KeyLength, span));
            }
    
            // implementation of http://vigna.di.unimi.it/ftp/papers/xorshift.pdf, based on George Marsaglia's simple xor-shift pseudo random.
            // https://github.com/bewaretech/PEA.NET/blob/40f851db/src/PEA/PEA/Util/FastRandom.cs#L149 (Apache 2.0)
            private static unsafe void NextBytes(byte* buffer)
            {
                uint x = _x, y = _y, z = _z, w = _w;
                int i = 0;
                uint t;
                for (int bound = KeyLength - 3; i < bound;)
                {
                    t = (x ^ (x << 11));
                    x = y; y = z; z = w;
                    w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
    
                    buffer[i++] = (byte)w;
                    buffer[i++] = (byte)(w >> 8);
                    buffer[i++] = (byte)(w >> 16);
                    buffer[i++] = (byte)(w >> 24);
                }
    
                if (i < KeyLength)
                {
                    t = (x ^ (x << 11));
                    x = y; y = z; z = w;
                    w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
    
                    buffer[i++] = (byte)w;
                    if (i < KeyLength)
                    {
                        buffer[i++] = (byte)(w >> 8);
                        if (i < KeyLength)
                        {
                            buffer[i++] = (byte)(w >> 16);
                            if (i < KeyLength)
                            {
                                buffer[i] = (byte)(w >> 24);
                            }
                        }
                    }
                }
    
                _x = x; _y = y; _z = z; _w = w;
            }
    
            // existing helper https://github.com/dotnet/runtime/blob/529804afcd9a84499945467c8d04b21a6f674cbd/src/libraries/System.Private.CoreLib/src/System/IO/Path.cs#L794
            private static unsafe void Populate83FileNameFromRandomBytes(byte* bytes, int byteCount, Span<char> chars)
            {
                // This method requires bytes of length 8 and chars of length 12.
                Debug.Assert(bytes != null);
                Debug.Assert(byteCount == 8, $"Unexpected {nameof(byteCount)}");
                Debug.Assert(chars.Length == 12, $"Unexpected {nameof(chars)}.Length");
    
                byte b0 = bytes[0];
                byte b1 = bytes[1];
                byte b2 = bytes[2];
                byte b3 = bytes[3];
                byte b4 = bytes[4];
    
                // write to chars[11] first in order to eliminate redundant bounds checks
                chars[11] = (char)Base32Char[bytes[7] & 0x1F];
    
                // Consume the 5 Least significant bits of the first 5 bytes
                chars[0] = (char)Base32Char[b0 & 0x1F];
                chars[1] = (char)Base32Char[b1 & 0x1F];
                chars[2] = (char)Base32Char[b2 & 0x1F];
                chars[3] = (char)Base32Char[b3 & 0x1F];
                chars[4] = (char)Base32Char[b4 & 0x1F];
    
                // Consume 3 MSB of b0, b1, MSB bits 6, 7 of b3, b4
                chars[5] = (char)Base32Char[
                        ((b0 & 0xE0) >> 5) |
                        ((b3 & 0x60) >> 2)];
    
                chars[6] = (char)Base32Char[
                        ((b1 & 0xE0) >> 5) |
                        ((b4 & 0x60) >> 2)];
    
                // Consume 3 MSB bits of b2, 1 MSB bit of b3, b4
                b2 >>= 5;
    
                Debug.Assert((b2 & 0xF8) == 0, "Unexpected set bits");
    
                if ((b3 & 0x80) != 0)
                    b2 |= 0x08;
                if ((b4 & 0x80) != 0)
                    b2 |= 0x10;
    
                chars[7] = (char)Base32Char[b2];
    
                // Set the file extension separator
                chars[8] = '.';
    
                // Consume the 5 Least significant bits of the remaining 3 bytes
                chars[9] = (char)Base32Char[bytes[5] & 0x1F];
                chars[10] = (char)Base32Char[bytes[6] & 0x1F];
            }
        }
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    HackathonIssues picked for Hackathonarea-System.IOhelp wanted[up-for-grabs] Good issue for external contributorsos-linuxLinux OS (any supported distro)tenet-performancePerformance related issue

    Type

    No type

    Projects

    No projects

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions