Performance of ReentrantLock and Synchronized

ReentrantLock and Synchronized

Synchronized keyword is famous in locking shared variables to be modified by only one thread at the specific time. However, it has performance issue while multiple threads are trying to contend for accessing shared variables. JDK 5.0 is redesigned memory model that makes it truly cross platform for multithread environment. JDK 5.0 adds java.util.concurrent package that supports various optimized concurrency tools.

In this article, I present the performance of ReentrantLock and Synchronized. Actually, the performance has been reveal in Java theory and practice: More flexible, scalable locking in JDK 5.0. However, that article did not show the source code of how to do it.

Prerequisite

• Principle of Mutual Exclusion
• Semaphore: Mutual Exclusion in Single System
• Monitor: Mutual Exclusion in Single System

Code Snippet

synchronized(lockObject){
  // update critical section
}

Lock lock = new ReentrantLock();

lock.lock();
try {
  // update critical section
}
finally {
  lock.unlock();
}

Experiment Scenario

I am going to show you the performance comparison by generating the Pseudo Random value based on Linear Congruential Generator. When generating random value, the lock on monitor is required to protect multiple thread from being generating random variable at the same time. I implement two separated pseudo random class from the same interface. One uses synchronized keyword. Another uses ReentrantLock class. Thread class called DicePlayer tries to generate random value in loop until “stop” command is signaled. We collect the number of generating random value from both implementation of pseudo random class.
A throughput is calculated by:

Normalized throughput is calculated by a generic normalization formula.

Experiment Environment

Result

The graph shows that in single thread synchronized performs better than ReentrantLock. However, while involving with multiple threads ReentrantLock is far superior than synchronized. So ReentrantLock should be used for locking monitor.

Source Code

• IPseudoRandom.java : an interface for implementing lock
• SynchronizedPseudoRandom.java : an implementation of generating random value using synchronized keyword
• ReentrantLockPseudoRandom.java : an implementation of generating random value using ReentrantLock class
• PseudoRandomFactory.java : a factory to create an instance of either SynchronizedPseuRandom or ReentrantLockPseudoRandom
• DicePlayer.java : a thread class trying to generating random value from the two random class above
• MyRandomCostMetric.java : a main class to create a test case

IPseudoRandom.java

/**
 * An interface of PseuRandom
 * @author http://lycog.com
 */
public interface IPseudoRandom {
  public void setSeed(long seed);
  public int next(int bits);
  public int nextInt(int n);
  public long getNumOfCall();
  @Override
  public String toString();
}

SynchronizedPseudoRandom.java

/**
 * Synchronized PseudoRandom implementation
 * Linear Congruential Generator (LCG)
 * @author http://lycog.com
 */
public class SynchronizedPseudoRandom implements IPseudoRandom{
  private long m_seed;
  private long m_numOfCall = 0;
  public SynchronizedPseudoRandom(){
    this(System.currentTimeMillis());
  }

  public SynchronizedPseudoRandom(long seed){
    setSeed(seed);
  }

  public final void setSeed(long seed) {
    synchronized(this){
      this.m_seed = (seed ^ 0x5DEECE66DL) & ((1L << 48) - 1);
    }
  }

  public int next(int bits) {
    synchronized(this){
      //Count how many times so threads invoke this method
      m_numOfCall++;

      m_seed = (m_seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
      return (int)(m_seed >>> (48 - bits));
    }
  }

  public int nextInt(int n) {
    if (n <= 0) {
      throw new IllegalArgumentException("n must be positive");
    }

    if ((n & -n) == n) // i.e., n is a power of 2
    {
      return (int) ((n * (long) next(31)) >> 31);
    }

    int bits, val;
    do {
      bits = next(31);
      val = bits % n;
    } while (bits - val + (n - 1) < 0);
    return val;
  }

  public long getNumOfCall(){
    return m_numOfCall;
  }

  @Override
  public String toString(){
    return "Synchronized PseudoRandom";
  }
}

ReentrantLockPseudoRandom.java

import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

/**
 * ReentrantLock PseudoRandom implementation
 * @author http://lycog.com
 */
public class ReentrantLockPseudoRandom implements IPseudoRandom{
  private long m_seed;
  private long m_numOfCall = 0;
  public ReentrantLockPseudoRandom(){
    this(System.currentTimeMillis());
  }

  public ReentrantLockPseudoRandom(long seed){
    setSeed(seed);
  }

  public final void setSeed(long seed) {
    Lock lock = new ReentrantLock();

    lock.lock();
    try{
      this.m_seed = (seed ^ 0x5DEECE66DL) & ((1L << 48) - 1);
    }
    finally{
      lock.unlock();
    }
  }

  public int next(int bits) {
    Lock lock = new ReentrantLock();

    lock.lock();
    try{
      //Count how many times so threads invoke this method
      m_numOfCall++;

      m_seed = (m_seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
      return (int)(m_seed >>> (48 - bits));
    }
    finally{
      lock.unlock();
    }
  }

  public int nextInt(int n) {
    if (n <= 0) {
      throw new IllegalArgumentException("n must be positive");
    }

    if ((n & -n) == n) // i.e., n is a power of 2
    {
      return (int) ((n * (long) next(31)) >> 31);
    }

    int bits, val;
    do {
      bits = next(31);
      val = bits % n;
    } while (bits - val + (n - 1) < 0);
    return val;
  }

  public long getNumOfCall(){
    return m_numOfCall;
  }

  @Override
  public String toString(){
    return "ReentrantLock PseudoRandom";
  }
}

PseudoRandomFactory.java

/**
 * A factory to create an instance of PseudoRandom
 * @author http://lycog.com
 */
public class PseudoRandomFactory {
  public static  IPseudoRandom create(IPseudoRandom T){
    return T;
  }
}

DicePlayer.java

/**
 * Dice Player to roll the dice
 * @author http://lycog.com
 */
public class DicePlayer extends Thread{
  private IPseudoRandom m_random;
  private volatile boolean m_stop = false;

  public DicePlayer(IPseudoRandom random){
    m_random = random;
  }

  @Override
  public void run(){
    while(!m_stop){
      m_random.nextInt(6);
    }
  }

  public void requestStop(){
    m_stop = true;
  }
}

MyRandomCostMetric.java

/**
 * Main class for testing random implementation
 * of ReentrantLock and Synchronized PseudoRandom
 * @author http://lycog.com
 */
public class MyRandomCostMetric {
  public static void main(String[] args){
    //Experimental loop
    final int NUM_OF_TESTS = 5;
    //Number players thread
    final int[] NUM_OF_PLAYERS = new int[]{1,2,4,6,8,10,12,14};

    for(int player_idx=0;player_idx<NUM_OF_PLAYERS.length;player_idx++){
      //Running test for certain times
      for(int test_idx=0; test_idx<NUM_OF_TESTS; test_idx++){
        /**
         * Create PseudoRandom classes. It can be either
         * SynchronizedPseudoRandom or ReentrantLockPseudoRandom class
         */
        //IPseudoRandom random = PseudoRandomFactory.create(new SynchronizedPseudoRandom());
        IPseudoRandom random = PseudoRandomFactory.create(new ReentrantLockPseudoRandom());

        //Perform Test
        performTest(random, NUM_OF_PLAYERS[player_idx]);
      }
    }
  }

  /**
   * Perform Test
   * @param random
   * @param num_of_players
   */
  private static void performTest(IPseudoRandom random, int num_of_players){
    //Create players thread
    final DicePlayer[] player = new DicePlayer[num_of_players];

    //Start dice player thread
    for(int i=0;i < player.length; i++) {
      player[i] = new DicePlayer(random);
      player[i].start();
    }

    //Each thread attempts to get Random for DURATION
    final long DURATION = 60*1000; // 1 minute
    try {
      Thread.sleep(DURATION);
    } catch (InterruptedException ex) {
      ex.printStackTrace();
    }

    //Send stop signal to all threads
    for(int i=0; i<player.length; i++){
      player[i].requestStop();
    }

    //Wait for all threads to finish
    for(int i=0; i<player.length; i++){
      try {
        player[i].join();
      } catch (InterruptedException ex) {
        ex.printStackTrace();
      }
    }

    //Display the throughput information
    System.out.println("Random Implementor = " + random.toString());
    System.out.println("Num of Player = " + num_of_players);
    System.out.println("Num of call = " + random.getNumOfCall());
    System.out.println("Throughput  = " + random.getNumOfCall()/DURATION);
    System.out.println("----------------------------------");
  }
}