Index].pollSlot();
        if (r != null)
          break;
        if (++victimIndex == runners.length) victimIndex = 0;
      }
      
      Thread.currentThread().setPriority(pri);
      
    }

    if (r != null)
      r.run();
  }

}

------------- Begin Forwarded Message -------------

From: David Holmes <###@###.###>
To: "'###@###.###'" <jdk-early-access-feedback
@Sun.COM>
Subject: JIT Bug: stackOverFlowError
Date: Wed, 7 Oct 1998 11:47:10 +1000
MIME-Version: 1.0
Content-Transfer-Encoding: quoted-printable

Java version:
   java version "1.2fcs"
   Classic VM (build JDK-1.2fcs-K, native threads)

Platform: win32 (Windows NT 4.0 Service Pack 3)

Bug Category: JIT

Synopsis: With JIT enabled the sample program generates a StackOverFlowErro
r with an infinite stack trace

Problem Description:

The following program runs fine with the JIT disabled but generates a Stack
OverFlowError when the JIT is enabled.
The stack trace for this exception is an infinite loop as follows:

java.lang.StackOverflowError
        at Runner.execute(Compiled Code)
        at Fib.run(Compiled Code)
        at Runner.execute(Compiled Code)
        at Fib.run(Compiled Code)
        at Runner.execute(Compiled Code)
        at Fib.run(Compiled Code)
        at Runner.execute(Compiled Code)
        at Fib.run(Compiled Code)
        at Runner.execute(Compiled Code)
        .....


Note: Although this problem may be due to the stack size of the native thre
ads I don't believe an infinite stack
trace should be generated. Additionally the -Xss and -Xoss options to the J
VM are undocumented and appear to be
unsettable - all attempts to set them yield "bad stack size"

Program usage: java Fib 1 2

The program (written by Doug Lea) follows:

import java.util.Random;
final public class Fib implements Runnable {
        private volatile int answer = -1;
        private final int number;

        public Fib(int n) { number = n; }
        public void run() {
                if (number < 2)
                        answer = number;
                else {
                        Runner runner = (Runner)(Thread.currentThread());
                        Fib f1 = new Fib(number - 1);
                        Fib f2 = new Fib(number - 2);
                        runner.execute(f1);
                        runner.execute(f2);
                        while (f1.answer < 0 || f2.answer < 0) runner.work(
);
                        answer = f1.answer + f2.answer;
                }
        }

        public static void main(String[] args) {
                try {
                        int procs;
                        int num;
                        try {
                                procs = Integer.parseInt(args[0]);
                                num = Integer.parseInt(args[1]);
                        }catch (Exception e) {
                                System.out.println("Usage: java Fib <thread
s> <number>");
                                return;
                        }
                        long startTime = 0;
                        int result = -1;
                        long time = 0;
                        int thisResult = -1;
                        if (false) {
                                startTime = System.currentTimeMillis();
                                result = seqfib(num);
                                time = System.currentTimeMillis();
                                long stime = time - startTime;
                                double ssecs = (double)stime / 1000.0;
                                System.out.println("Seq Time: " + ssecs);
                                System.out.println("Fib: Size: " + num + "
Answer: " + result);
                        }
                        startTime = System.currentTimeMillis();
                        Fib f = new Fib(num);
                        Runner t = new Runner(f, procs);
                        t.start();
                        t.join();
                        thisResult = f.answer;
                        if (result > 0 && thisResult != result)
                                System.out.println("Wrong answer?" + result
 + "/" + thisResult);

                        result = thisResult;

                        long ptime = System.currentTimeMillis() - startTime
;
                        double secs = (double)ptime / 1000.0;
                        System.out.println("Time: " + secs);
                        System.out.println("Fib: Size: " + num + " Answer:
" + result);
                        System.exit(0);
                }catch (InterruptedException ex) {}
        }

        static int seqfib(int num) {
                if (num < 2)
                        return num;
                else
                        return seqfib(num-1) + seqfib(num-2);
        }
}

final class Runner extends Thread /* implements Executor */ {

  /**
   * Tasks are held in a deque embedded in an array of CAPACITY elements.
   * (Tasks are never lost on overflow; instead they are run directly.)
   * For speed, the capacity must be a power of two.
   **/
  static final int CAPACITY = 1024;

  /**
   * The deque is organized like a stack, but with an adjustable
   * base. Since the base may be incremented by removing the
   * bottom element, the deque array pointers (top and base)
   * circularly wrap, as in a standard bounded buffer.
   * The deque supports push, pop, and remove-base operations
   * but the code for them is mangled beyond recognition
   * in the execute and work methods.
   **/

  private final Runnable[] deque = new Runnable[CAPACITY];
  private int top = 0;
  private int base = 0;
  static final int capacityMask = CAPACITY-1; // for fast % operations

  /**

Synopsis: With JIT enabled the sample program generates a StackOverFlowErro
r with an infinite stack trace

Problem Description:

The following program runs fine with the JIT disabled but generates a Stack
OverFlowError when the JIT is enabled.
The stack trace for this exception is an infinite loop as follows:

java.lang.StackOverflowError
        at Runner.execute(Compiled Code)
        at Fib.run(Compiled Code)
        at Runner.execute(Compiled Code)
        at Fib.run(Compiled Code)
        at Runner.execute(Compiled Code)
        at Fib.run(Compiled Code)
        at Runner.execute(Compiled Code)
        at Fib.run(Compiled Code)
        at Runner.execute(Compiled Code)
        .....


Note: Although this problem may be due to the stack size of the native thre
ads I don't believe an infinite stack
trace should be generated. Additionally the -Xss and -Xoss options to the J
VM are undocumented and appear to be
unsettable - all attempts to set them yield "bad stack size"

Program usage: java Fib 1 2

The program (written by Doug Lea) follows:

import java.util.Random;
final public class Fib implements Runnable {
        private volatile int answer = -1;
        private final int number;

        public Fib(int n) { number = n; }
        public void run() {
                if (number < 2)
                        answer = number;
                else {
                        Runner runner = (Runner)(Thread.currentThread());
                        Fib f1 = new Fib(number - 1);
                        Fib f2 = new Fib(number - 2);
                        runner.execute(f1);
                        runner.execute(f2);
                        while (f1.answer < 0 || f2.answer < 0) runner.work();
                        answer = f1.answer + f2.answer;
                }
        }

        public static void main(String[] args) {
                try {
                        int procs;
                        int num;
                        try {
                                procs = Integer.parseInt(args[0]);
                                num = Integer.parseInt(args[1]);
                        }catch (Exception e) {
                                System.out.println("Usage: java Fib <threads> <number>");
                                return;
                        }
                        long startTime = 0;
                        int result = -1;
                        long time = 0;
                        int thisResult = -1;
                        if (false) {
                                startTime = System.currentTimeMillis();
                                result = seqfib(num);
                                time = System.currentTimeMillis();
                                long stime = time - startTime;
                                double ssecs = (double)stime / 1000.0;
                                System.out.println("Seq Time: " + ssecs);
                                System.out.println("Fib: Size: " + num + " Answer: " + result);
                        }
                        startTime = System.currentTimeMillis();
                        Fib f = new Fib(num);
                        Runner t = new Runner(f, procs);
                        t.start();
                        t.join();
                        thisResult = f.answer;
                        if (result > 0 && thisResult != result)
                                System.out.println("Wrong answer?" + result + "/" + thisResult);

                        result = thisResult;

                        long ptime = System.currentTimeMillis() - startTime;
                        double secs = (double)ptime / 1000.0;
                        System.out.println("Time: " + secs);
                        System.out.println("Fib: Size: " + num + " Answer: " + result);
                        System.exit(0);
                }catch (InterruptedException ex) {}
        }

        static int seqfib(int num) {
                if (num < 2)
                        return num;
                else
                        return seqfib(num-1) + seqfib(num-2);
        }
}

final class Runner extends Thread /* implements Executor */ {

  /**
   * Tasks are held in a deque embedded in an array of CAPACITY elements.
   * (Tasks are never lost on overflow; instead they are run directly.)
   * For speed, the capacity must be a power of two.
   **/
  static final int CAPACITY = 1024;

  /**
   * The deque is organized like a stack, but with an adjustable
   * base. Since the base may be incremented by removing the
   * bottom element, the deque array pointers (top and base)
   * circularly wrap, as in a standard bounded buffer.
   * The deque supports push, pop, and remove-base operations

  * but the code for them is mangled beyond recognition
   * in the execute and work methods.
   **/

  private final Runnable[] deque = new Runnable[CAPACITY];
  private int top = 0;
  private int base = 0;
  static final int capacityMask = CAPACITY-1; // for fast % operations

  /**
   * The oldest element of deque is kept in a shareable slot.
   * Even though the methods to put and take task from the slot
   * are synchronized, the slot reference itself is declared
   * as volatile. This allows non-synchronized code to check
   * to see if the slot needs to be replenished without having
   * to grab a lock.
   **/

  private volatile Runnable slot = null;

  /**
   * Take the item from the slot and return it; or null if empty
   **/

  // Faster but uncomfortable to use `this' as lock in thread subclass
  private synchronized Runnable pollSlot() {
    Runnable r = slot;
    slot = null;
    return r;
  }

  /**
   * Place a task in the slot. Called only when slot known to be null.
   **/

  private synchronized void putSlot(Runnable r) {
    slot = r;
  }

  /**
   * The array of active Runner threads. All Runners created
   * have a reference to the same array, which is not modified
   * after construction. THe root thread (the one publically constructed)
   * is always at runners[0]
   **/
  private final Runner[] runners;

  /**
   * Used to randomly choose victim threads to steal tasks from
   **/

  private final Random rng = new Random();

  /**
   * Create a new runner thread that when started will
   * execute task, as well as groupSize-1 other helper threads
   * that will execute sub-tasks generated by this thread.
   * Choosing a group size of the number of
   * CPUs on a system geneally maximizes parallelism
   * with the smallest overhead, but choosing larger
   * sizes should not introduce much degradation.
   **/
  public Runner(Runnable w, int groupSize) {
    super(w);

    runners = new Runner[groupSize];
    runners[0] = this;
    for (int i = 1; i < runners.length; ++i)
      runners[i] = new Runner(runners);

  }

  /**
   * Special constructor called internally for helper threads
   **/
  private Runner(Runner[] a) {
    runners = a;
  }

  public void run() {
    try {

  Runner root = runners[0];

      if (this == root) {

        for (int i = 1; i < runners.length; ++i) // start helpers
          runners[i].start();

        super.run();
      }

      else {
        while (root.isAlive()) {
          work();
          
          if (root.isAlive()) // avoid tight spins while idling
            Thread.sleep(1);
        }
      }

    }
    catch(InterruptedException ex) { }
  }

  /**
   * Arrange for execution of the given task, normally
   * by placing it in a work queue.
   * If the work queue is currently full, the runnable
   * is instead executed in the current thread before returning.
   **/

  public void execute(Runnable r) {

    if (slot == null) { // First, fill slot if possible

      Runnable w;
      if (base == top)
        w = r; // Empty -- add current item to slot

      else {
        w = deque[base];
        deque[base] = null;
        base = (base + 1) & capacityMask;
        
        deque[top] = r; // Also push -- stack cannot be full here
        top = (top + 1) & capacityMask;
     }

      putSlot(w);

    }
    else {
      int nextTop = (top + 1) & capacityMask;
      if (nextTop != base) { // not full -- Push current
        deque[top] = r;
        top = nextTop;
      }
      else
        r.run(); // Run if can't add to slot and can't push
    }
  }


  /**
   * Execute a task in this thread.
   * Normally used as a substitute for wait() in Runner threads,
   * called when thread would otherwise be idle or waiting for a condition.
   **/
  public void work() {

    Runnable r = null;

    if (base != top) { // Try to pop off a task
      top = (top + capacityMask) & capacityMask;
      r = deque[top];
      deque[top] = null;

      if (base != top) { // And also put one in slot
        if (slot == null) {
          Runnable w = deque[base];
          deque[base] = null;
          base = (base + 1) & capacityMask;
          putSlot(w);
        }
      }
    }
    else {
      // Try to take a task from a runner's slot (possibly even own slot)
      
      // lower priority while searching for work
      int pri = Thread.currentThread().getPriority();
 Thread.currentThread().setPriority(pri-1);
      
      // Circularly traverse starting from a random start index
      int victimIndex = rng.nextInt(runners.length);
      
      for (int i = 0; i < runners.length; ++i) {
        r = runners[victim