Performance of ReentrantLock and Synchronized

19 Apr 2011 by

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

Code Snippet

synchronized

synchronized(lockObject){
  // update critical section
}

ReentrantLock

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:

Throughput = \frac{Number of Call}{Duration}

Normalized throughput is calculated by a generic normalization formula.

Normalized = \frac{Throughput_{i}}{abs(min)+abs(max)}

Experiment Environment

Parameter Value
Operating Systems Windows 7
Java Sun JDK 1.6
CPU Intel Core 2 Duo 2.53GHz
RAM 4GB

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("----------------------------------");
  }
}

 

5 responses so far

  • Tex says:

    I think there is a bug in ReentrantLockPseudoRandom.java that nullifies the results: Your code recreates the ReentrantLock on every invocation of every method instead of reusing one single instance (final member). As a result, you’re not locking at all and so ReentrantLockPseudoRandom – of course – outperformes the synchronized version.

    Wrong:
    public final void setSeed(long seed) {
    Lock lock = new ReentrantLock();
    lock.lock();
    try{
    this.m_seed = (seed ^ 0x5DEECE66DL) & ((1L << 48) – 1);
    }
    finally{
    lock.unlock();
    }
    }

    Correct:
    private final Lock lock = new ReentrantLock();

    public final void setSeed(long seed) {
    lock.lock();
    try{
    this.m_seed = (seed ^ 0x5DEECE66DL) & ((1L << 48) – 1);
    }
    finally{
    lock.unlock();
    }
    }

  • Hello,

    First I want to thank you for this article. While I was reading your code I’ve realized the way you were using the ReentrantLock was wrong, because you were creating a new lock every time. If you are not using the same lock for each thread then it is similar to not having a lock. There is another comment pointing out this, but the bug is still there. It would be better if you could fix it, otherwise people might get confused if they do not read the comments.
    Thanks.
    Lasantha Kularatne

  • says:

    Dude that had been pretty entertaining as well as educational. ’:;;.

Leave a Reply