Mar 18, 2012

Random / Math.random() / ThreadLocalRandom

java.util.Random

java.util.Random 亂數演算法會依賴 seed 數值產生亂數,並在產生亂數後重新產生 seed,
在 Multi-thread 下為了保證在各Thread取到不同的亂數, java.util.Random 在實作上使用 optimistic locking 來同步更換 seed ,問題是若所有Thread都使用同個Random物件產生亂數,在大量競爭下會造成不斷的loop計算,進而產生效能問題


 
    public Random() {
        this(seedUniquifier() ^ System.nanoTime());
    }

    private static long seedUniquifier() {
        // L'Ecuyer, "Tables of Linear Congruential Generators of
        // Different Sizes and Good Lattice Structure", 1999
        for (;;) {
            long current = seedUniquifier.get();
            long next = current * 181783497276652981L;
            if (seedUniquifier.compareAndSet(current, next))
                return next;
        }
    }

    private static final AtomicLong seedUniquifier
        = new AtomicLong(8682522807148012L);
    public Random(long seed) {
        this.seed = new AtomicLong(initialScramble(seed));
    }

    private static long initialScramble(long seed) {
        return (seed ^ multiplier) & mask;
    }

    protected int next(int bits) {
        long oldseed, nextseed;
        AtomicLong seed = this.seed;
        do {
            oldseed = seed.get();
            nextseed = (oldseed * multiplier + addend) & mask;
        } while (!seed.compareAndSet(oldseed, nextseed));
        return (int)(nextseed >>> (48 - bits));
    }

    public int nextInt() {
        return next(32);
    }



java.lang.Math
Math.random() 是封裝單個 Random 物件的 helper method,基本上就是JVM共享同個Random物件
 
    private static Random randomNumberGenerator;

    private static synchronized Random initRNG() {
        Random rnd = randomNumberGenerator;
        return (rnd == null) ? (randomNumberGenerator = new Random()) : rnd;
    }
    public static double random() {
        Random rnd = randomNumberGenerator;
        if (rnd == null) rnd = initRNG();
        return rnd.nextDouble();
    }


因此可以改用thread-local的方法來建立獨立的Random物件,避免競爭的問題
 
    private static final ThreadLocal< Random > localRandom =
        new ThreadLocal< Random >() {
            protected Random initialValue() {
                return new Random();
            }
    };
    public static Random current() {
        return localRandom.get();
    }



 java.util.concurrent.ThreadLocalRandom
JDK7提供的 java.util.concurrent.ThreadLocalRandom,概念類似上方ThreadLocal的方法,API 使用方式如下
 
int r = ThreadLocalRandom.current().nextInt(4, 77);

References
http://docs.oracle.com/javase/7/docs/api/java/util/Random.html
http://docs.oracle.com/javase/7/docs/api/java/lang/Math.html
http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/ThreadLocalRandom.html
http://docs.oracle.com/javase/tutorial/essential/concurrency/threadlocalrandom.html
Post a Comment