[RFC FS-1135] Random functions for collections

[Lanayx]

Let's discuss RFC FS-1135 as proposed in PR #732

[kerams]

In .NET 6 and higher Random.Shared will be used, otherwise Fsharp.Core defined shared instance

FSharp.Core does not target .NET 6 or higher though.

[Lanayx]

You are right, I moved it down to unresolved questions. If targeting .NET 6 is not on horizon, we'll need to basically copy Random.Shared implementation.

[abelbraaksma]

I think the only targets atm are NetStandard 2.0 and NetStandard 2.1. And indeed, this is not in there. I guess we can cherrypick.

[Lanayx]

Right now there is a main issue - how to call newly functions, right now we have two main options

1. With prefix (e.g. List.randomShuffle, List.randomChoice, List.randomChoices, List.randomSample)
2. Without prefix (e.g. List.shuffle, List.choice, List.choices, List.sample)

Please vote for the prefixed version with 🚀, for the short version with 🎉

[Lanayx]

Hmm, I didn't realize that Array.Parallel chose that way, in that case a module makes more sense than a prefix. If Array.Parallel didn't exist, I wouldn't go this approach, but since that design was approved, I don't have anything against it

[dsyme]

This doesn't feel right - for Parallel it's like "this is Array only parallel". For Random that doesn't apply - none of the names are in common, and if any were it would be really confusing.

[Lanayx]

I've reverted, however I don't read Array.Parallel as "this is Array only parallel" :) I read it - this is a Parallel module for Array that contains parallel operations, so I don't care about whether any names are common or not. They all could have been named just the in the same way with prefix - Array.parallelMap, Array.parallelPartition, but the submodule design was chosen. If we go with prefixes for random, it will be a diverge in approaches.

[Lanayx]

Just for reference I've asked ChatGPT 4.0 about this choice (prefixes vs submodules) and here is what it answered

[Lanayx]

@dsyme are you still thinking about it?

[abelbraaksma]

Hey @Lanayx, I'm reviewing your proposal atm (and was hoping to un-stale this RFC, it is good work and should go in!). I was wondering if you've considered to use a function as argument, as opposed to a Random type object? I.e.: randomShuffle: randomizer: (unit -> int) -> array: 'T[] -> 'T[]?

I know it would increase the surface area of the functions, and it would require an extra check (i.e., if the returned value is out of range). But considering we're in a functional language, it stands to reason that we allow users to use a function to provide the random values.

Alternatively, randomShuffle: randomizer: (unit -> float) -> array: 'T[] -> 'T[] could be considered, where the returned float value must be between 0.0 - 1.0, which is possibly less of a burden on the programmer, as the translation to an index within bounds will be done by the function implementation.

[abelbraaksma]

I've also went through several performance-related links you provided and figured out that slowness comes not because of it's API, but rather default implementation.

I've actually been meaning for years to do some perf tests myself and to test the distribution of the default implementation. But you know, priorities. I didn't look deeply into it, there's so much written on the subject of Random that I just picked several posts that I came across.

When I've more time I may take a deeper dive (esp about the lib that promises an 8x perf improvement).

I don't know if that simplicity is good or bad (for example from performance perspective)

The great thing not mentioned so far, but you hinted about it, is that a function is F# can be inlined (through InlineIfLambdaAttribute), removing any and all allocations (as you may be aware, a function has state through its closure, and to capture that state, an object is allocated. Which is why inlining is important).

I'll update the RFC accordingly soon.

Thanks, that's appreciated! ❤️

[Lanayx]

If talking about performance I meant that converting to float and back might have a performance hit which will make lambda version not suitable for such cases. For example someone could use RandomNumberGenerator.GetInt32 to sample an element from array, but instead he will have to first map that to float (range 0..1) which will eventually be converted back to int. Implementing Random based on RandomNumberGenerator would give better performance in this case.

[brianrourkeboll]

Was something like

val randomShuffleBy : randomizer:(int * int -> int) -> source:'T array -> 'T array

considered?

I.e., to enable

let shuffled = xs |> Array.randomShuffleBy (fun (lo, hi) -> Random.Shared.Next (lo, hi))

That would allow even faster perf than #732 (comment):

(Source)

| Method      | Mean     | Error     | StdDev    | Ratio |
|------------ |---------:|----------:|----------:|------:|
| Bcl         | 3.453 us | 0.0198 us | 0.0176 us |  1.00 |
| Pr          | 6.956 us | 0.0205 us | 0.0160 us |  2.02 |
| Alternative | 3.647 us | 0.0139 us | 0.0123 us |  1.06 |

It seems obvious that there is nothing valid that randomizer could do upon any given invocation in this function other than choosing a value between minValue and maxValue (or lo and hi, or whatever), so maybe an API like this would be more self-explaining than one taking a unit -> float.

But I may be missing something.

[Lanayx]

While performance improves and this is the only overload currently sufficient for random collections, the DX is not ideal: (fun (lo, hi) -> Random.Shared.Next (lo, hi)) is too long to write... But I don't have a strong opinion on this, I wonder what @abelbraaksma comments on this.

[brianrourkeboll]

the DX is not ideal: (fun (lo, hi) -> Random.Shared.Next (lo, hi)) is too long to write...

Right. You could of course write

Array.randomShuffleBy Random.Shared.Next xs

at the expense of losing the devirtualization and inlining of Random.Shared.Next.

As I mentioned in another comment elsewhere, storing the instance returned by Random.Shared in a local variable also gives you the devirtualization, but it's definitely still unwieldy and unintuitive:

let random = Random.Shared
Array.randomShuffleBy random.Next xs

[abelbraaksma]

@Lanayx, putting this in a different discussion thread, @nkeenan38 pointed out the following point in an offline discussion:

but how these functions work for sequences? The size isn’t known, right? They may even be infinite? Its not clear to me how a (non-trivial) infinite sequence is randomly sorted (or an element is randomly selected)

My take on this is that these will fail for infinite sequences (similar to sort and sortBy) and that for list and seq, the sequences will be cached. We may even use a type-test to find if a seq is a cast of an array or IList, but that's an implementation detail perhaps.

[Lanayx]

Right, shuffling shouldn't be different from sorting as regarding to handling infinite sequences

[abelbraaksma]

@Lanayx, you raised a point about what should happen when the shuffling algorithm you provide is not really shuffling. I wasn't entirely sure wrt my own answer, so I figured, let's look at the source.

You may or may not want to mention this in the RFC. It may help with adding corner cases.

Here are two examples (remember that max is exclusive, min is inclusive):

type MyRandom() =
    inherit System.Random()

    override this.Next(minv, maxv) =
        if minv = maxv then minv
        else maxv - 1

let testShuffle() =
    let xs = [|1;2;3;4;5;6;7;8|]
    MyRandom().Shuffle(xs)
    xs

> testShuffle();;
val it: int array = [|8; 1; 2; 3; 4; 5; 6; 7|]

type MyRandom() =
    inherit System.Random()

    override this.Next(minv, maxv) =minv

let testShuffle() =
    let xs = [|1;2;3;4;5;6;7;8|]
    MyRandom().Shuffle(xs)
    xs

> testShuffle();;
val it: int array = [|1; 2; 3; 4; 5; 6; 7; 8|]

Essentially, I'd suggest we just follow the .NET algorithm and translate where needed. I'm sure you've seen this before (for reference, here's the original implementation, not sure we pointed to it before: dotnet/runtime#78598):

        public void Shuffle<T>(Span<T> values)
        {
            int n = values.Length;

            for (int i = 0; i < n - 1; i++)
            {
                int j = Next(i, n);

                if (j != i)
                {
                    T temp = values[i];
                    values[i] = values[j];
                    values[j] = temp;
                }
            }
        }

I don't think we can rely on Span, unless we want to create multiple implementations, but the same applies to any other algo anyway.

[abelbraaksma]

Same applies to using the same seed, which is prob. what you want to use in your tests (yes, I'm sure this is well-known, but just figured I'd make it explicit ;) ):

let testShuffle() =
    let xs = [|1;2;3;4;5;6;7;8|]
    Random(42).Shuffle(xs)
    xs

> testShuffle();;
val it: int array = [|6; 2; 3; 1; 5; 4; 8; 7|]

> testShuffle();;
val it: int array = [|6; 2; 3; 1; 5; 4; 8; 7|]

> testShuffle();;
val it: int array = [|6; 2; 3; 1; 5; 4; 8; 7|]

> testShuffle();;
val it: int array = [|6; 2; 3; 1; 5; 4; 8; 7|]

[brianrourkeboll]

I wonder if there's anything to learn from OCaml's approach to this:

• Random module
• Array.shuffle
  • Implementation
  • PR & discussion: Add Array.shuffle ocaml/ocaml#12217

Proposal

Here's a wild stab at taking some inspiration from that approach that winnows the set of new APIs to three per collection type while, I think, still being relatively ergonomic and discoverable.

Script file with provisional implementation: https://gist.github.com/brianrourkeboll/9935b6aa35a2227610a4251b38404729

Proposed signature

random.fsi

namespace Microsoft.FSharp.Core

open System

[<AutoOpen>]
[<CompilationRepresentation(CompilationRepresentationFlags.ModuleSuffix)>]
module internal ThreadSafeRandom =
    type Random with
        static member internal Shared : Random

[<RequireQualifiedAccess>]
[<CompilationRepresentation(CompilationRepresentationFlags.ModuleSuffix)>]
module Random =
    val nextInt    : unit -> int
    val int        : maxValue:int -> int
    val intInRange : minValue:int -> maxValue:int -> int
    val nextFloat  : unit -> float
    val bytes      : count:int -> byte array
    val fill       : buffer:byte array -> unit

array.fsi

module Array =
    // …
    val shuffle : randomizer:(int -> int) -> array:'T array -> 'T array
    val choice  : randomizer:(int -> int) -> array:'T array -> 'T
    val choices : randomizer:(int -> int) -> count:int -> array:'T array -> 'T array
    val sample  : randomizer:(int -> int) -> count:int -> array:'T array -> 'T array

Likewise for the List and Seq modules.

Proposed implementation

random.fs

namespace Microsoft.FSharp.Core

open System
open System.Runtime.CompilerServices

[<Sealed>]
type internal ThreadSafeRandom() =
    inherit Random()

    [<DefaultValue>]
    [<ThreadStatic>]
    static val mutable private random: Random

    [<MethodImpl(MethodImplOptions.NoInlining)>]
    static member private Create() =
        ThreadSafeRandom.random <- Random()
        ThreadSafeRandom.random

    static member private LocalRandom =
        match ThreadSafeRandom.random with
        | null -> ThreadSafeRandom.Create()
        | random -> random

    override _.Next() = ThreadSafeRandom.LocalRandom.Next()
    override _.Next maxValue = ThreadSafeRandom.LocalRandom.Next maxValue
    override _.Next(minValue, maxValue) = ThreadSafeRandom.LocalRandom.Next(minValue, maxValue)
    override _.NextDouble() = ThreadSafeRandom.LocalRandom.NextDouble()
    override _.NextBytes(buffer: byte array) = ThreadSafeRandom.LocalRandom.NextBytes buffer
    override _.Sample() = raise (NotSupportedException())

[<AutoOpen>]
[<CompilationRepresentation(CompilationRepresentationFlags.ModuleSuffix)>]
module internal ThreadSafeRandom =
    // Avoid the static init check overhead on each access
    // that would happen if this were a static member val in a class.
    // See: https://github.com/dotnet/fsharp/issues/6454
    let private shared = ThreadSafeRandom()

    type Random with
        static member internal Shared: Random = shared

[<RequireQualifiedAccess>]
[<CompilationRepresentation(CompilationRepresentationFlags.ModuleSuffix)>]
module Random =
    let nextInt () = Random.Shared.Next()
    let int maxValue = Random.Shared.Next maxValue
    let intInRange minValue maxValue = Random.Shared.Next(minValue, maxValue)
    let nextFloat () = Random.Shared.NextDouble()

    let bytes count =
        if count < 0 then invalidArgOutOfRange (nameof count) count "TODO" 0
        let bytes = Microsoft.FSharp.Primitives.Basics.Array.zeroCreateUnchecked count
        Random.Shared.NextBytes bytes
        bytes

    let fill (buffer: byte array) = Random.Shared.NextBytes buffer

array.fs

module Array =
    // …
    let inline shuffle ([<InlineIfLambda>] randomizer) (array: 'T array) =
        checkNonNull (nameof array) array
    
        let array = Unchecked.unbox<'T array> (array.Clone())
    
        for i in array.Length - 1 .. -1 .. 1 do
            let j = randomizer (i + 1)
            if j < 0 || i < j then invalidArgOutOfRange (nameof randomizer) j "TODO" i
            let temp = array[i]
            array[i] <- array[j]
            array[j] <- temp
      
        array

// …Etc.

Proposed usage

let array = [|1..100|]

let shuffled = array |> Array.shuffle Random.int
let choice   = array |> Array.choice Random.int
let choices  = array |> Array.choices Random.int 33
let sample   = array |> Array.sample Random.int 33

• Pros

  • Pretty simple usage in most scenarios.

  • Relatively small API surface area (Random module + 9 additional collection functions).

  • We don't really even need the random- prefix, since randomizer is required and has a sufficiently distinct signature from the other HOFs on the collection modules with which these new functions could potentially be confused.

  • Makes explicit the choice of whether you want to have locally-nondeterministic code (by directly passing in Random.int) or instead want to parameterize your code further.

  • Perf should be good.

  • Similar API to Array.permute, etc., except without the requirement that the result be a (proper) permutation.

  • Works well out of the box with newer APIs like System.Security.Cryptography.RandomNumberGenerator.GetInt32(int toExclusive), e.g.

    array |> Array.shuffle RandomNumberGenerator.GetInt32

• Cons

  • Duplicates System.Random's API in curried form.
  • You must explicitly pass in a randomizer to the collection functions even if you don't really care about its implementation.
  • Someone who wants to use another randomization implementation (which is likely a class) may need to either use lambdas or write a small wrapper module for their implementation. (But see above for, e.g., System.Security.Cryptography.RandomNumberGenerator.GetInt32, which would work well with this approach out of the box.)

Alternatives

• Have versions taking randomizer:(int -> int) as well as versions that implicitly call Random.Shared.Next internally. We could prefix those ones with random-, since their implementation actually uses randomness.

  module Array =
      // …
      val randomShuffle : array:'T array -> 'T array
      val randomChoice  : array:'T array -> 'T
      val randomChoices : count:int -> array:'T array -> 'T array
      val randomSample  : count:int -> array:'T array -> 'T array
      val shuffle       : randomizer:(int -> int) -> array:'T array -> 'T array
      val choice        : randomizer:(int -> int) -> array:'T array -> 'T
      val choices       : randomizer:(int -> int) -> count:int -> array:'T array -> 'T array
      val sample        : randomizer:(int -> int) -> count:int -> array:'T array -> 'T array

  • Pros
    • Super-simple usage when you don't care about the implementation of the randomizer.
    • Parameterization of the randomizer when you want it.
  • Cons
    • Double the API surface area.
    • People will probably use the simple versions in scenarios where they shouldn't, leading to less testable code.

• Use the randomizer:(int -> int) approach, but don't add a Random module.

  • Pros
    • No extra module that duplicates System.Random's API in curried form.
    • Still works well with newer APIs like System.Security.Cryptography.RandomNumberGenerator.GetInt32 (or anything that follows its design).
  • Cons
    • In practice, everyone needs to write a lambda every time forever if they want maximum performance: array |> Array.randomShuffle (fun i -> Random.Shared.Next i).

• Use more verbose names, like Random.intBelow maxValue instead of Random.int maxValue.

• Stick with the current approach in the RFC.

[brianrourkeboll]

from technical perspective int -> int randomizer will work just fine, some slight modification will be needed for shuffling (were internally it requires both lower and upper bond)

It actually doesn't need to worry about the lower bound if you iterate downwards (see the sample implementation above, or compare the OCaml implementation) — then the lower bound is always 0.

[brianrourkeboll]

@Lanayx Hmm, I wonder how much of the Python implementation is driven by everything ultimately being based on the float-returning random(). In .NET, most things, including NextDouble, are actually based on NextUInt64 instead.

[Lanayx]

Almost all module functions depend on the basic function random(), which generates a random float uniformly in the half-open range 0.0 <= X < 1.0.

[brianrourkeboll]

Here's a script file to play around with: https://gist.github.com/brianrourkeboll/9935b6aa35a2227610a4251b38404729

[brianrourkeboll]

Yeah @Lanayx, I meant that I wonder how much of that fact drives various other implementation decisions (whether for ergonomic or technical reasons).