5
\$\begingroup\$

I need to generate a lot of pseudo-random numbers in my software. I'm trying to create a elegant (syntax-wise) and performant class that would allow me to generate such numbers and perform other random-related stuff (like shuffling an array). I decided to "cache" a generator for each thread and expose the methods of this cached instance through static methods.

Can you please review the following implementation? I tried to achieve the following objectives:

  1. Make it thread safe
  2. Make it convenient to use / call
  3. Make it performant

I only add xmldocs to my code after I'm satisfied with the implementation, so it's not necessary to point out that the class is lacking documentation, I will do it later. But if you believe there is a important detail that should be documented, by all means, do point it out.

About the random-labels method: it was originally called Bools(int count), but considering the context in which it is used, I decided to renamed it.

namespace Minotaur.Random {
    using System;
    using System.Buffers;
    using System.Collections.Generic;
    using System.Runtime.InteropServices;
    using Minotaur.Collections;
    using Minotaur.ExtensionMethods.Float;

    public static class ThreadStaticRandom {
        // ThreadStatic to make sure that each thread gets a Random for itself, preventing the corruption
        // of the Random object
        [ThreadStatic]
        private static Random _instance;

        // This wraps the _random variable to make sure each thread gets a Random for itself
        private static Random Instance {
            get {
                if (_instance == null)
                    _instance = new Random();

                return _instance;
            }
        }

        public static bool Bool() {
            return Instance.NextDouble() < 0.5;
        }

        public static bool Bool(float biasForTrue) {
            if (float.IsNaN(biasForTrue))
                throw new ArgumentOutOfRangeException(nameof(biasForTrue) + " can't be NaN");
            if (biasForTrue < 0 || biasForTrue > 1)
                throw new ArgumentOutOfRangeException(nameof(biasForTrue) + " must be in [0, 1] interval");

            return Uniform() < biasForTrue;
        }

        public static double Uniform() {
            return Instance.NextDouble();
        }

        public static double Uniform(float inclusiveMin, float exclusiveMax) {
            if (inclusiveMin.IsNanOrInfinity())
                throw new ArgumentOutOfRangeException(nameof(inclusiveMin) + " can't be NaN nor Infinity");
            if (exclusiveMax.IsNanOrInfinity())
                throw new ArgumentOutOfRangeException(nameof(exclusiveMax) + " can't be NaN nor Infinity");
            if (inclusiveMin > exclusiveMax)
                throw new ArgumentException(nameof(inclusiveMin) + " must be <= " + nameof(exclusiveMax));

            double range = exclusiveMax - inclusiveMin;
            range *= Uniform();

            return inclusiveMin + range;
        }

        public static int Int(int exclusiveMax) {
            return Instance.Next(minValue: 0, maxValue: exclusiveMax);
        }

        public static int Int(int inclusiveMin, int exclusiveMax) {
            return Instance.Next(minValue: inclusiveMin, maxValue: exclusiveMax);
        }

        public static bool[] RandomLabels(int count) {
            if (count < 0)
                throw new ArgumentOutOfRangeException(nameof(count) + " must be > 0");

            var labels = new bool[count];
            // Todo: if shit hits the fan (it shouldn't), check this out
            var bytes = MemoryMarshal.AsBytes<bool>(labels);
            Instance.NextBytes(bytes);
            for (int i = 0; i < bytes.Length; i++)
                bytes[i] >>= 7;

            return labels;
        }

        public static T Choice<T>(T first, T second) {
            if (Bool())
                return first;
            else
                return second;
        }

        public static T Choice<T>(IReadOnlyList<T> values) {
            if (values == null)
                throw new ArgumentNullException(nameof(values));
            if (values.Count == 0)
                throw new ArgumentException(nameof(values) + " can't be empty");

            var index = Instance.Next(minValue: 0, maxValue: values.Count);
            return values[index];
        }

        public static T Choice<T>(Array<T> values) {
            if (values == null)
                throw new ArgumentNullException(nameof(values));
            if (values.Length == 0)
                throw new ArgumentException(nameof(values) + " can't be empty");

            var index = Instance.Next(minValue: 0, maxValue: values.Length);
            return values[index];
        }

        public static T Choice<T>(ReadOnlySpan<T> values) {
            if (values.Length == 0)
                throw new ArgumentException(nameof(values) + " can't be empty");

            var index = Instance.Next(minValue: 0, maxValue: values.Length);
            return values[index];
        }

        public static T Choice<T>(T[] values) {
            if (values.Length == 0)
                throw new ArgumentException(nameof(values) + " can't be empty");

            var index = Instance.Next(minValue: 0, maxValue: values.Length);
            return values[index];
        }

        public static void Shuffle<T>(Span<T> values) {
            if (values.Length == 0)
                throw new ArgumentException(nameof(values) + " can't be empty");

            var rng = Instance;
            int n = values.Length;
            while (n > 1) {
                n--;
                int k = rng.Next(n + 1);
                var temp = values[k];
                values[k] = values[n];
                values[n] = temp;
            }
        }

        public static void Shuffle<T>(T[] values) {
            if (values == null)
                throw new ArgumentNullException(nameof(values));
            if (values.Length == 0)
                throw new ArgumentException(nameof(values) + " can't be empty");

            var rng = Instance;
            int n = values.Length;
            while (n > 1) {
                n--;
                int k = rng.Next(n + 1);
                var temp = values[k];
                values[k] = values[n];
                values[n] = temp;
            }
        }

        public static void CopyRandomElements<T>(ReadOnlySpan<T> from, Span<T> to, int count) {
            if (count < 0)
                throw new ArgumentOutOfRangeException(nameof(count) + " must be >= 0");
            if (from.Length < count)
                throw new ArgumentException(nameof(from) + " must have at least 'count' elements");
            if (to.Length < count)
                throw new ArgumentException(nameof(to) + "must have at least 'count' elements");

            var rentedBuffer = ArrayPool<int>.Shared.Rent(minimumLength: from.Length);
            var indexes = rentedBuffer.AsSpan().Slice(
                start: 0,
                length: from.Length);

            for (int i = 0; i < indexes.Length; i++)
                indexes[i] = i;

            Shuffle(indexes);

            for (int i = 0; i < count; i++)
                to[i] = from[indexes[i]];

            ArrayPool<int>.Shared.Return(rentedBuffer);
        }

        public static T[] SelectRandomElements<T>(ReadOnlySpan<T> from, int count) {
            if (count < 0)
                throw new ArgumentOutOfRangeException(nameof(count) + " must be >= 0");

            var randomlySelected = new T[count];
            CopyRandomElements(
                from: from,
                to: randomlySelected,
                count: count);

            return randomlySelected;
        }
    }
}
\$\endgroup\$
7
\$\begingroup\$

As far as I'm aware, using ThreadStatic like this is fine, and will give you the guarantees you need.

Overall design

Your class is doing 2 things:

  • Managing Random instances across threads
  • Providing methods to query the Random instance

I would much prefer to see all the fun methods usable on any Random instance, either wrapping it in another class or just provided as extension methods.

This would leave the ThreadStaticRandom as a tiny little class with a very well defined role.

I suppose the benefit of your design is that it is impossible for someone to mishandle an instance of Random by passing it to another thread, but at the same time it rules out any hope of having reproducible results.

RandomLabels

I do think this is a bad method name. I would never think to look at RandomLabels when I was looking for Bools. If you want to call a method called RandomLabels from a specific piece of code, then consider an extension method for that purpose.

I don't like the implementation either. NextBytes() is having to consume a lot of entropy only for you to throw must of it away. A alternative solution which doesn't depend on what I presume is an implementation detail (too lazy to check if it is even a correct assumption) would be to sample bits from integers. This won't consume any more heap space, and may well be faster.

Documentation

I would take issue with your plan to add documentation after writing the methods: writing documentation forces you to be explicit about what the method does (as opposed to how it does it), and I would never be happy with an implementation when I havn't explicitly declared what it is going to do. It's also very easy to 'write documentation later', but that has a habit of not happening (not that I should wish to suggest you wouldn't get around to it!). Part of the joy of inline documentation is that it is easy to do it inline and as you write the methods.

I won't suggest any details that need to be pointed out, because that would be a long list. I would argue you should always provide your documentation for review, because it means we can spot things that are missing (instead of trying to guess what you might forget), and check that it matches the implementation. For example, I don't know whether CopyRandomValues is correct because no-where is it specified that it should sample without replacement.

Misc

  • You have a lot of good argument validation, but you could do with a few more null checks in places (e.g. in Choice). Also consider using the constructor for ArgumentException which takes two parameters: the parameter name and the message. This makes it that little bit easier to scan when something goes wrong. SelectRandomElements should check that from.Length >= count.

  • I don't think you need overloads for T[] when you have ReadOnlySpan<T> or Span<T>: this would just reduce the redundancy a bit. (This can't be quite true of course, because it depends on an implicit conversion, which means it won't work if the caller is depending on some other implicit conversion, but then you can at least call Shuffle<T>(Span<T>) from Shuffle<T>(T[]) to reduce duplication). Of course, the cost of simplification would be some unnecessary overhead when handling arrays.

  • float biasForTrue should probably be a double.

  • I'd be temped to ditch the count parameters in CopyRandomValues methods: if the caller want a particular count, they can slice their spans accordingly. This will remove any possible confusion about whether this is a count or an offset and generally give the caller less opportunity to mess up.

\$\endgroup\$
4
\$\begingroup\$

I have not much to add to VisualMelon's answer.

You could use some more compact notation. For instance,

private static Random Instance {
    get {
        if (_instance == null)
            _instance = new Random();

        return _instance;
    }
}

..could be written as:

 private static Random Instance => _instance ?? (_instance = new Random());

The name Instance suggests a shared instance across app domain. A more suitable name would be Current (Thread.CurrentThread, CultureInfo.CurrentCulture, etc..).

 private static Random CurrentRandom => _instance ?? (_instance = new Random());

You are not consistent in using this convenience method:

public static double Uniform() {
    return Instance.NextDouble();
}

You call it here:

public static bool Bool(float biasForTrue) {
    // .. arg checks

    return Uniform() < biasForTrue;
}

..but not here:

public static bool Bool() {
    return Instance.NextDouble() < 0.5;
}

You could also use the shorthand notation here:

 public static bool Bool() => Uniform() < 0.5;
\$\endgroup\$
  • 2
    \$\begingroup\$ Thanks for the feedback! I really didn't notice the inconsistencies in my calls. About compacting the code... Maybe it is just me, but I feel weird "returning the result of an assignment". I think I prefer, in this case, the more prolix approach. \$\endgroup\$ – Trauer Aug 20 at 15:25
  • \$\begingroup\$ private static Random Instance => _instance ?? (_instance = new Random()); - should be done with the Lazy<T> class rather than this race condition-prone methodology. \$\endgroup\$ – Jesse C. Slicer Aug 22 at 0:05
  • \$\begingroup\$ @JesseC.Slicer I don't think there is a race going on, since the instance is declared ThreadStatic. But it needs to get verified. \$\endgroup\$ – dfhwze Aug 22 at 4:49
2
\$\begingroup\$

Your shuffle implementation suffers from a deceptive flaw. It will currently only allow up to a maximum of 2^32 permutations on the initial shuffle. To put that into perspective, a standard deck of cards has 52! permutations, which is vastly beyond orders of magnitudes more.

If you look at the method in isolation, you will understand why.

            var rng = Instance;
            int n = values.Length;
            while (n > 1) {
                n--;
                int k = rng.Next(n + 1);
                var temp = values[k];
                values[k] = values[n];
                values[n] = temp;
            }

The Random instance will always be seeded with some Int32 value. Given a specified array to be shuffled along with any seed and the algorithm, the sequence generated is completely deterministic.

What does all of that actually imply? Lets say you have a blackjack program with only 1 thread. Lets assume as a user, I don't know the seed, but I do know the algorithm and the first shuffled deck sequence. Because there are only 2^32 permutations, I can easily pre-calculate all of them based upon every possible seed. Once I find the sequence that matches the shuffled deck, I now also know the seed used. Once I know the seed used, I can now calculate every subsequent shuffled deck.

\$\endgroup\$
  • 1
    \$\begingroup\$ Good point! The seed in your example could be found in just a couple of hours. Whether the OP should use a cryptographically secure PRNG instead depends on the intended use-cases, but this is definitely something that should at least be documented. \$\endgroup\$ – Pieter Witvoet Aug 22 at 8:42
2
\$\begingroup\$

One small thing I noticed is that all your Choice methods that take in a list of some sort are basically the same structure.

public static T Choice<T>(IReadOnlyList<T> values) {
    if (values == null)
        throw new ArgumentNullException(nameof(values));
    if (values.Count == 0)
        throw new ArgumentException(nameof(values) + " can't be empty");

    var index = Instance.Next(minValue: 0, maxValue: values.Count);
    return values[index];
}

public static T Choice<T>(Array<T> values) {
    if (values == null)
        throw new ArgumentNullException(nameof(values));
    if (values.Length == 0)
        throw new ArgumentException(nameof(values) + " can't be empty");

    var index = Instance.Next(minValue: 0, maxValue: values.Length);
    return values[index];
}

public static T Choice<T>(ReadOnlySpan<T> values) {
    if (values.Length == 0)
        throw new ArgumentException(nameof(values) + " can't be empty");

    var index = Instance.Next(minValue: 0, maxValue: values.Length);
    return values[index];
}

public static T Choice<T>(T[] values) {
    if (values.Length == 0)
        throw new ArgumentException(nameof(values) + " can't be empty");

    var index = Instance.Next(minValue: 0, maxValue: values.Length);
    return values[index];
}

Can any of these be combined? There might be a common interface many of these different collections implement, such as IEnumerable, or ICollection. That might not handle all the input types you expect, but it could reduce the number of Choice methods you have.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.