#24 MersenneTwister not thread safe

[Anonymous]

The MersenneTwister is not thread safe (as I interpret the documentation claiming). It is shown by the below Unit Test. The main problem with the implementation in the MersenneTwister class is the gobal field mti which is updated in the nextXXX() methods.

If there is a context switch between the if (mti >= N) instruction and the y = mt[mti++]; instruction where anoother thread increments the mti field from 623 to 624 we can get an ArrayIndexOutOfBoundsException:624.

~~~~
import static org.junit.Assert.fail;

import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveAction;

import org.junit.Test;

public class BasicRDistTest {

static jdistlib.rng.RandomEngine sharedMt = new jdistlib.rng.MersenneTwister();
//static jdistlib.rng.RandomEngine sharedMt = new jdistlib.rng.RandomCMWC();

class MTSampler extends RecursiveAction {
    final static long serialVersionUID = 1L;
    int startIdx = -1;
    int endIdx = -1;
    double [] store;
    int limit = 10;

    public MTSampler(int startClass, int endClass, double []  store) {
        this.store = store;
        this.startIdx = startClass;
        this.endIdx = endClass;
    }

    @Override
    protected void compute() {
        if ( (endIdx-startIdx) <= limit ) {
            for (int classNo = startIdx; classNo < endIdx; classNo++) {
                for (int i = 0; i < 1000; i++) {                            
                    store[classNo] = jdistlib.Uniform.random(0, 60, sharedMt);
                }
            }
        }
        else {
            int range = (endIdx-startIdx);
            int startClass1 = startIdx;
            int endClass1 = startIdx + (range / 2);
            int startClass2 = endClass1;
            int endClass2 = endIdx;
            invokeAll(new MTSampler(startClass1, endClass1, store),
                    new MTSampler(startClass2, endClass2, store));
        }
    }
}

@Test
public void testParJDistlibUnif1() {
    //int noLoops = 150_000_000;
    //int noLoops = 15_000_000;
    int noLoops = 150_000;
    double [] samples = new double[noLoops]; 
    long start = System.currentTimeMillis();
    MTSampler mts = new MTSampler(0, noLoops, samples);

    ForkJoinPool samplerPool = new ForkJoinPool();
    try {
        samplerPool.invoke(mts);
    } catch (Exception e) {
        e.printStackTrace();
        fail("Exception: " + e);
    }
    System.out.println("Sampling took: " + (System.currentTimeMillis() - start) + " milliseconds...");
}

}

[Roby Joehanes]

You are absolutely right. Sean Luke's MersenneTwister was not meant to be shared across multiple threads because if we were to make each nextXXX a synchronized routine, there is a significant performance penalty. Typically, what you can do is to have each thread instantiate its own instance of MersenneTwister with salted seed. At least that is what I am doing.

[Anonymous]

Ok, perhaps it would be good to document this on the "front page", where at least I got the impression that it was thread safe.

[Anonymous]

Good job on this library btw! :)

Cheers!

[Roby Joehanes]

Noted. Thanks. Adding thread safety feature (by synchronized keyword) really is not worth doing. People should be instantiating an MT in each thread rather than sharing one MT object. The current MT implementation in JDistlib (up to v0.4.1) is Sean Luke's MersenneTwisterFast, which is not thread safe. Maybe later I can add the thread safe version.

[Roby Joehanes]

I just added a thread-safe version of MersenneTwister, called MersenneTwisterSafe. Will be released with the next version (v0.4.6 or 0.5.0).