vendredi 20 novembre 2020

Thread safe high performance random generator

I need a high performance random number generator that is thread-safe. I need only random bytes in the value type (which is ulong for now), not within ranges. I've used the C# built-in Random class, but it was kind of slow and not thread-safe.

Later I moved to XORShift functions that actually works very fine, but to achieve thread-safeness I need to put the calculation in lock, and that degrades the performance drastically.

What I'm using to generate a random ulong is the following:

public class Rand
{
    ulong seed = 0;
    object lockObj = new object();

    public Rand()
    {
        unchecked
        {
            seed = (ulong)DateTime.Now.Ticks;
        }
    }

    public Rand(ulong seed)
    {
        this.seed = seed;
    }

    public ulong GetULong()
    {
        unchecked
        {
            lock (lockObj)
            {
                ulong t = 0;

                t = seed;
                t ^= t >> 12;
                t ^= t << 25;
                t ^= t >> 27;
                seed = t;

                return t * 0x2545F4914F6CDD1D;
            }
        }
    }
}

This works fine and fast, but locking makes it take about 1-2us if it is called from 200 concurrent threads, otherwise calculation finishes under 100ns.

If I remove locking there is a chance two threads take the same seed and will calculate the same random which is not good for my purposes. If I'm removing the ulong t declaration and work directly on the seed then there will be a very little chance to generate the same random for two concurrent calls, but there is also a chance the value will be shifted out from the value range, like t << 25 will be called many times in a row by different threads without carrying the rotation it will become just simply 0.

I think the proper way would be if there is a shared value that may be changed by any concurrent call and work with that value in the calculation methods, since these values are atomic (at least withing CPU cores) it is not a problem if many calculations are using it in the same time, but that is a problem if this value shifts out from the bitrange.

Is there any good solution to solve this problem? I'd be thankful for any help.




Aucun commentaire:

Enregistrer un commentaire