Lib.fs

namespace ShuffleArray

open System
open System.Runtime.CompilerServices

/// Using System.Random.Shared.Shuffle directly.
module Bcl =
    [<MethodImpl(MethodImplOptions.NoInlining)>]
    let nullArg argumentName = nullArg argumentName

    let inline checkNonNull argName arg =
        if isNull arg then
            nullArg argName

    let shuffle arr =
        checkNonNull (nameof arr) arr

        let newArr = Array.copy arr
        Random.Shared.Shuffle newArr
        newArr

/// The code as it is in https://github.com/dotnet/fsharp/pull/17277
module Pr =
    let inline checkNonNull argName arg =
        if isNull arg then
            nullArg argName

    let inline invalidArgOutOfRangeFmt (arg:string) (format:string) paramArray =
        let msg = String.Format (format, paramArray)
        raise (new ArgumentOutOfRangeException (arg, msg))

    let private executeRandomizer (randomizer: unit -> float) =
        let value = randomizer()
        if value < 0.0 || value >= 1.0 then
            let argName = nameof randomizer
            invalidArgOutOfRangeFmt argName
                "{0}\n{1} returned {2}, should be in range [0.0, 1.0)."
                [|"Msg"; argName; value|]
        value

    let next (randomizer: unit -> float) (minValue: int) (maxValue: int) =
        int ((executeRandomizer randomizer) * float (maxValue - minValue)) + minValue

    let shuffleArrayInPlaceBy (randomizer: unit -> float) (array: array<'T>) =
        let inputLength = array.Length
        for i = 0 to inputLength - 2 do
            let j = next randomizer i inputLength
            if j <> i then
                let temp = array[i]
                array[i] <- array[j]
                array[j] <- temp

    let randomShuffleBy (randomizer: unit -> float) (source: 'T array) : 'T array =
        checkNonNull "source" source

        let result = Array.copy source

        shuffleArrayInPlaceBy randomizer result

        result

/// An adaptation of the code in the PR.
module Faster =
    [<MethodImpl(MethodImplOptions.NoInlining)>]
    let nullArg argumentName = nullArg argumentName

    let inline checkNonNull argName arg =
        if isNull arg then
            nullArg argName

    [<MethodImpl(MethodImplOptions.NoInlining)>]
    let invalidArgOutOfRangeFmt (argName:string) =
        let msg = $"Msg\n{argName} must produce values in the range [0.0, 1.0)."
        raise (ArgumentOutOfRangeException (argName, msg))

    let inline next ([<InlineIfLambda>] randomizer: unit -> float) (minValue: int) (maxValue: int) =
        int (randomizer () * float (maxValue - minValue)) + minValue

    let inline shuffleArrayInPlaceBy ([<InlineIfLambda>] randomizer: unit -> float) (array: array<'T>) =
        let inputLength = array.Length
        for i = 0 to inputLength - 2 do
            let j = next randomizer i inputLength

            if j <> i then
                if j < 0 || inputLength <= j then
                    invalidArgOutOfRangeFmt (nameof randomizer)

                let temp = array[i]
                array[i] <- array[j]
                array[j] <- temp

    let inline randomShuffleBy ([<InlineIfLambda>] randomizer: unit -> float) (source: 'T array) : 'T array =
        checkNonNull (nameof source) source
        let result = Unchecked.unbox (source.Clone())
        shuffleArrayInPlaceBy randomizer result
        result

module Alternative =
    [<MethodImpl(MethodImplOptions.NoInlining)>]
    let nullArg argumentName = nullArg argumentName

    let inline checkNonNull argName arg =
        if isNull arg then
            nullArg argName

    [<MethodImpl(MethodImplOptions.NoInlining)>]
    let invalidArgOutOfRangeFmt (argName:string) =
        let msg = $"Msg\n{argName} must produce values in the range [0.0, 1.0)."
        raise (ArgumentOutOfRangeException (argName, msg))

    let inline shuffleArrayInPlaceBy ([<InlineIfLambda>] randomizer: int * int -> int) (array: 'T array) =
        let inputLength = array.Length
        for i = 0 to inputLength - 2 do
            let j = randomizer (i, inputLength)

            if j <> i then
                if j < 0 || inputLength <= j then
                    invalidArgOutOfRangeFmt (nameof randomizer)

                let temp = array[i]
                array[i] <- array[j]
                array[j] <- temp

    let inline randomShuffleBy ([<InlineIfLambda>] randomizer: int * int -> int) (source: 'T array) : 'T array =
        checkNonNull (nameof source) source
        let result = Unchecked.unbox (source.Clone())
        shuffleArrayInPlaceBy randomizer result
        result

module TestData =
    let arr = [|0..999|]

Program.fs

module ShuffleArray.Program

open System
open BenchmarkDotNet.Attributes
open BenchmarkDotNet.Running

type Benchmarks () =
    [<Benchmark(Baseline = true)>]
    member _.Bcl () = Bcl.shuffle TestData.arr

    [<Benchmark>]
    member _.Pr () = Pr.randomShuffleBy (fun () -> Random.Shared.NextDouble ()) TestData.arr

    //[<Benchmark>]
    //member _.Faster () = Faster.randomShuffleBy (fun () -> Random.Shared.NextDouble ()) TestData.arr

    [<Benchmark>]
    member _.Alternative () = Alternative.randomShuffleBy (fun (lo, hi) -> Random.Shared.Next (lo, hi)) TestData.arr

ignore (BenchmarkRunner.Run<Benchmarks> ())