Name: joT67522 Date: 01/14/98


The following relates to running a threading/synchronisation benchmark
put together by Doug Lea. The benchmark can be accessed via:
http://gee.cs.oswego.edu/dl/t17/

but I have included the source below.

The benchmark performs a number of multithreading tests and the
number of threads can be varied. The benchmark was run on a Pentium
Pro 180 under NT4.0 (SP3). The following is extracted from some email
with Doug Lea:

" I have found something quite bizarre that Josh and Tim might be
interested in exploring. It must indicate a bug somewhere but I do
not know where. Here are the test results for JDK 1.2 beta 2 with 4
threads:

  D:\TEMP\Java>java ThreadTest17 4
  nthreads = 4 iterations = 1048576 (262144 iterations per thread)
  No sharing: time = 8703ms (8299ns per iteration)
  All sharing: time = 522906ms (498682ns per iteration)
  Taking turns: time = 60171ms (57383ns per iteration)

The number for All Sharing is not a mistake - but something strange
is happening. The program appears to be 'hanging' effectively. If I look
at the process/threads using Task Manager or pstat then none of the
threads are doing anything! pstat indicates 4 ready threads but they
don't run. I can't understand what is happening. Using 8 threads takes
half as long, and by the time you get to 64 you have the figures I gave
previously (2 threads took only 8360ms). Very peculiar."

Further information. Using Process Viewer from the win32 SDK I observed
that the 4 user application threads were slowly advancing but getting very
little CPU time; in addition the were experiencing tens of thousands of
context switches!

The benchmark program is as follows:

/*
  a small performance test
  Wed Jan 7 09:30:26 1998 Doug Lea (dl at gee)
*/

class Obj {
  int count = 0;
  Semaphore semaphore = new Semaphore(1);
  Obj next;
  Obj current = null;

  void inc() throws InterruptedException {
    semaphore.require();
    doInc();
    semaphore.provide();
  }

  synchronized void doInc() {
    ++count;
  }


  synchronized void turn() throws InterruptedException {
    waitForTurn();
    doInc();
    giveUpTurn();
  }

  synchronized void waitForTurn() throws InterruptedException {
    while (current == null) wait();
  }

  synchronized void giveUpTurn() {
    current = null;
    next.setTurn();
  }

  synchronized void setTurn() {
    current = this;
    notify();
  }

}
        
public class ThreadTest17 {
  public static void main(String[] args) {
    int nthreads = 64;
    int iterations = 1024 * 1024;

    if (args.length > 0) {
      try { nthreads = Integer.parseInt(args[0]); }
      catch (NumberFormatException ex) {}
    }

    if (args.length > 1) {
      try { iterations = Integer.parseInt(args[1]); }
      catch (NumberFormatException ex) {}
    }

    System.out.print("nthreads = " + nthreads);
    System.out.print(" iterations = " + iterations);
    int ipt = iterations / nthreads;
    System.out.println(" (" + ipt + " iterations per thread)");


    if (iterations % nthreads != 0) {
      System.out.println("Must have evenly divisible iterations");
      System.exit(-1);
    }

    long itime = independent(nthreads, iterations);
    long itpi = 1000000 * itime / iterations;
    System.out.print("No sharing: time = " + itime + "ms");
    System.out.println(" (" + itpi + "ns per iteration)");

    long stime = shared(nthreads, iterations);
    long stpi = 1000000 * stime / iterations;
    System.out.print("All sharing: time = " + stime + "ms");
    System.out.println(" (" + stpi + "ns per iteration)");

    long ttime = turns(nthreads, iterations);
    long ttpi = 1000000 * ttime / iterations;
    System.out.print("Taking turns: time = " + ttime + "ms");
    System.out.println(" (" + ttpi + "ns per iteration)");

  }

  static long independent(int nthreads, int iterations) {
    Obj[] objs = new Obj[nthreads];
    for (int i = 0; i < nthreads; ++i) objs[i] = new Obj();
    return runthreads(objs, iterations);
  }

  static long shared(int nthreads, int iterations) {
    Obj obj = new Obj();
    Obj[] objs = new Obj[nthreads];
    for (int i = 0; i < nthreads; ++i) objs[i] = obj;
    return runthreads(objs, iterations);
  }

  static long runthreads(Obj[] objs, int iterations) {

    int iters = iterations / objs.length;

    Thread[] threads = new Thread[objs.length];

    for (int k = 0; k < objs.length; ++k) {
      threads[k] = new Thread(new IncLoop(objs[k], iters));
    }

    long startTime = System.currentTimeMillis();
    for (int k = 0; k < threads.length; ++k) threads[k].start();

    try {
      for (int k = 0; k < threads.length; ++k) threads[k].join();
    }
    catch(InterruptedException ex) {
      System.out.println("Interrupted");
      return -1;
    }

    long endTime = System.currentTimeMillis();
    long tm = endTime - startTime;
    return tm;
  }

  static long turns(int nthreads, int iterations) {
    Obj[] objs = new Obj[nthreads];
    for (int i = 0; i < nthreads; ++i)
      objs[i] = new Obj();

    for (int i = 0; i < nthreads; ++i)
      objs[i].next = objs[(i+1)%nthreads];

    int iters = iterations / objs.length;

    Thread[] threads = new Thread[objs.length];

    for (int k = 0; k < objs.length; ++k) {
      threads[k] = new Thread(new TurnLoop(objs[k], iters));
    }

    long startTime = System.currentTimeMillis();
    for (int k = 0; k < threads.length; ++k) threads[k].start();

    objs[0].setTurn();

    try {
      for (int k = 0; k < threads.length; ++k) threads[k].join();
    }
    catch(InterruptedException ex) {
      System.out.println("Interrupted");
      return -1;
    }

    long endTime = System.currentTimeMillis();
    long tm = endTime - startTime;
    return tm;
  }

}


class IncLoop implements Runnable {
  final Obj obj;
  final int iters;
  IncLoop(Obj t, int i) { obj = t; iters = i; }
  public void run() {
    try {
      for(int i = iters; i > 0; --i) obj.inc();
    }
    catch(InterruptedException ex) { return; }
  }
}

class TurnLoop implements Runnable {
  final Obj obj;
  final int iters;
  TurnLoop(Obj t, int i) { obj = t; iters = i; }
  public void run() {
    try {
      for(int i = iters; i > 0; --i) obj.turn();
    }
    catch(InterruptedException ex) { return; }
  }
}

class Semaphore {
  private int permits_;

  public Semaphore(int initial) { permits_ = initial; }

  public synchronized void require() throws InterruptedException {
    if (permits_-- <= 0) wait();
  }

  public synchronized void provide() {
    if (permits_++ < 0) notify();
  }
}
(Review ID: 23084)
======================================================================