Class FJTaskRunner

  • All Implemented Interfaces:
    java.lang.Runnable

    public class FJTaskRunner
    extends java.lang.Thread
    Specialized Thread subclass for running FJTasks.

    Each FJTaskRunner keeps FJTasks in a double-ended queue (DEQ). Double-ended queues support stack-based operations push and pop, as well as queue-based operations put and take. Normally, threads run their own tasks. But they may also steal tasks from each others DEQs.

    The algorithms are minor variants of those used in Cilk and Hood, and to a lesser extent Filaments, but are adapted to work in Java.

    The two most important capabilities are:

    • Fork a FJTask:
        Push task onto DEQ
        
    • Get a task to run (for example within taskYield)
        If DEQ is not empty,
           Pop a task and run it.
        Else if any other DEQ is not empty,
           Take ("steal") a task from it and run it.
        Else if the entry queue for our group is not empty,
           Take a task from it and run it.
        Else if current thread is otherwise idling
           If all threads are idling
              Wait for a task to be put on group entry queue
        Else
            Yield or Sleep for a while, and then retry
        
    The push, pop, and put are designed to only ever called by the current thread, and take (steal) is only ever called by other threads. All other operations are composites and variants of these, plus a few miscellaneous bookkeeping methods.

    Implementations of the underlying representations and operations are geared for use on JVMs operating on multiple CPUs (although they should of course work fine on single CPUs as well).

    A possible snapshot of a FJTaskRunner's DEQ is:

         0     1     2     3     4     5     6    ...
      +-----+-----+-----+-----+-----+-----+-----+--
      |     |  t  |  t  |  t  |  t  |     |     | ...  deq array
      +-----+-----+-----+-----+-----+-----+-----+--
               ^                       ^
              base                    top
       (incremented                     (incremented
           on take,                         on push
        decremented                     decremented
           on put)                          on pop)
     

    FJTasks are held in elements of the DEQ. They are maintained in a bounded array that works similarly to a circular bounded buffer. To ensure visibility of stolen FJTasks across threads, the array elements must be volatile. Using volatile rather than synchronizing suffices here since each task accessed by a thread is either one that it created or one that has never seen before. Thus we cannot encounter any staleness problems executing run methods, although FJTask programmers must be still sure to either synch or use volatile for shared data within their run methods.

    However, since there is no way to declare an array of volatiles in Java, the DEQ elements actually hold VolatileTaskRef objects, each of which in turn holds a volatile reference to a FJTask. Even with the double-indirection overhead of volatile refs, using an array for the DEQ works out better than linking them since fewer shared memory locations need to be touched or modified by the threads while using the DEQ. Further, the double indirection may alleviate cache-line sharing effects (which cannot otherwise be directly dealt with in Java).

    The indices for the base and top of the DEQ are declared as volatile. The main contention point with multiple FJTaskRunner threads occurs when one thread is trying to pop its own stack while another is trying to steal from it. This is handled via a specialization of Dekker's algorithm, in which the popping thread pre-decrements top, and then checks it against base. To be conservative in the face of JVMs that only partially honor the specification for volatile, the pop proceeds without synchronization only if there are apparently enough items for both a simultaneous pop and take to succeed. It otherwise enters a synchronized lock to check if the DEQ is actually empty, if so failing. The stealing thread does almost the opposite, but is set up to be less likely to win in cases of contention: Steals always run under synchronized locks in order to avoid conflicts with other ongoing steals. They pre-increment base, and then check against top. They back out (resetting the base index and failing to steal) if the DEQ is empty or is about to become empty by an ongoing pop.

    A push operation can normally run concurrently with a steal. A push enters a synch lock only if the DEQ appears full so must either be resized or have indices adjusted due to wrap-around of the bounded DEQ. The put operation always requires synchronization.

    When a FJTaskRunner thread has no tasks of its own to run, it tries to be a good citizen. Threads run at lower priority while scanning for work.

    If the task is currently waiting via yield, the thread alternates scans (starting at a randomly chosen victim) with Thread.yields. This is well-behaved so long as the JVM handles Thread.yield in a sensible fashion. (It need not. Thread.yield is so underspecified that it is legal for a JVM to treat it as a no-op.) This also keeps things well-behaved even if we are running on a uniprocessor JVM using a simple cooperative threading model.

    If a thread needing work is is otherwise idle (which occurs only in the main runloop), and there are no available tasks to steal or poll, it instead enters into a sleep-based (actually timed wait(msec)) phase in which it progressively sleeps for longer durations (up to a maximum of FJTaskRunnerGroup.MAX_SLEEP_TIME, currently 100ms) between scans. If all threads in the group are idling, they further progress to a hard wait phase, suspending until a new task is entered into the FJTaskRunnerGroup entry queue. A sleeping FJTaskRunner thread may be awakened by a new task being put into the group entry queue or by another FJTaskRunner becoming active, but not merely by some DEQ becoming non-empty. Thus the MAX_SLEEP_TIME provides a bound for sleep durations in cases where all but one worker thread start sleeping even though there will eventually be work produced by a thread that is taking a long time to place tasks in DEQ. These sleep mechanics are handled in the FJTaskRunnerGroup class.

    Composite operations such as taskJoin include heavy manual inlining of the most time-critical operations (mainly FJTask.invoke). This opens up a few opportunities for further hand-optimizations. Until Java compilers get a lot smarter, these tweaks improve performance significantly enough for task-intensive programs to be worth the poorer maintainability and code duplication.

    Because they are so fragile and performance-sensitive, nearly all methods are declared as final. However, nearly all fields and methods are also declared as protected, so it is possible, with much care, to extend functionality in subclasses. (Normally you would also need to subclass FJTaskRunnerGroup.)

    None of the normal java.lang.Thread class methods should ever be called on FJTaskRunners. For this reason, it might have been nicer to declare FJTaskRunner as a Runnable to run within a Thread. However, this would have complicated many minor logistics. And since no FJTaskRunner methods should normally be called from outside the FJTask and FJTaskRunnerGroup classes either, this decision doesn't impact usage.

    You might think that layering this kind of framework on top of Java threads, which are already several levels removed from raw CPU scheduling on most systems, would lead to very poor performance. But on the platforms tested, the performance is quite good.

    [ Introduction to this package. ]

    See Also:
    FJTask, FJTaskRunnerGroup
    • Nested Class Summary

      Nested Classes 
      Modifier and Type Class Description
      protected static class  FJTaskRunner.VolatileTaskRef
      An object holding a single volatile reference to a FJTask.
      • Nested classes/interfaces inherited from class java.lang.Thread

        java.lang.Thread.State, java.lang.Thread.UncaughtExceptionHandler
    • Field Summary

      Fields 
      Modifier and Type Field Description
      protected boolean active
      Record whether current thread may be processing a task (i.e., has been started and is not in an idle wait).
      protected java.lang.Object barrier
      An extra object to synchronize on in order to achieve a memory barrier.
      protected int base
      Current base of DEQ.
      protected FJTaskRunner.VolatileTaskRef[] deq
      The DEQ array.
      protected FJTaskRunnerGroup group
      The group of which this FJTaskRunner is a member
      protected static int INITIAL_CAPACITY
      FJTasks are held in an array-based DEQ with INITIAL_CAPACITY elements.
      protected static int MAX_CAPACITY
      The maximum supported DEQ capacity.
      protected int runPriority
      Priority to use while running tasks
      protected int runs
      Total number of tasks run
      protected int scanPriority
      Priority to use while scanning for work
      protected int scans
      Total number of queues scanned for work
      protected int steals
      Total number of tasks obtained via scan
      protected int top
      Current top of DEQ.
      protected java.util.Random victimRNG
      Random starting point generator for scan()
      • Fields inherited from class java.lang.Thread

        MAX_PRIORITY, MIN_PRIORITY, NORM_PRIORITY
    • Constructor Summary

      Constructors 
      Modifier Constructor Description
      protected FJTaskRunner​(FJTaskRunnerGroup g)
      Constructor called only during FJTaskRunnerGroup initialization
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      protected void checkOverflow()
      Adjust top and base, and grow DEQ if necessary.
      protected void coInvoke​(FJTask[] tasks)
      Array-based version of coInvoke
      protected void coInvoke​(FJTask w, FJTask v)
      A specialized expansion of w.fork(); invoke(v); w.join();
      protected FJTask confirmPop​(int provisionalTop)
      Check under synch lock if DEQ is really empty when doing pop.
      protected FJTask confirmTake​(int oldBase)
      double-check a potential take
      protected int deqSize()
      Current size of the task DEQ
      protected FJTaskRunnerGroup getGroup()
      Return the FJTaskRunnerGroup of which this thread is a member
      protected FJTask pop()
      Return a popped task, or null if DEQ is empty.
      protected void push​(FJTask r)
      Push a task onto DEQ.
      protected void put​(FJTask r)
      Enqueue task at base of DEQ.
      void run()
      Main runloop
      protected void scan​(FJTask waitingFor)
      Do all but the pop() part of yield or join, by traversing all DEQs in our group looking for a task to steal.
      protected void scanWhileIdling()
      Same as scan, but called when current thread is idling.
      protected void setRunPriority​(int pri)
      Set the priority to use while running tasks.
      protected void setScanPriority​(int pri)
      Set the priority to use while scanning.
      protected void slowCoInvoke​(FJTask[] tasks)
      Backup to handle atypical or noninlinable cases of coInvoke
      protected void slowCoInvoke​(FJTask w, FJTask v)
      Backup to handle noninlinable cases of coInvoke
      protected void slowPush​(FJTask r)
      Handle slow case for push
      protected FJTask take()
      Take a task from the base of the DEQ.
      protected void taskJoin​(FJTask w)
      Process tasks until w is done.
      protected void taskYield()
      Execute a task in this thread.
      • Methods inherited from class java.lang.Thread

        activeCount, checkAccess, clone, countStackFrames, currentThread, dumpStack, enumerate, getAllStackTraces, getContextClassLoader, getDefaultUncaughtExceptionHandler, getId, getName, getPriority, getStackTrace, getState, getThreadGroup, getUncaughtExceptionHandler, holdsLock, interrupt, interrupted, isAlive, isDaemon, isInterrupted, join, join, join, onSpinWait, resume, setContextClassLoader, setDaemon, setDefaultUncaughtExceptionHandler, setName, setPriority, setUncaughtExceptionHandler, sleep, sleep, start, stop, suspend, toString, yield
      • Methods inherited from class java.lang.Object

        equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
    • Field Detail

      • group

        protected final FJTaskRunnerGroup group
        The group of which this FJTaskRunner is a member
      • INITIAL_CAPACITY

        protected static final int INITIAL_CAPACITY
        FJTasks are held in an array-based DEQ with INITIAL_CAPACITY elements. The DEQ is grown if necessary, but default value is normally much more than sufficient unless there are user programming errors or questionable operations generating large numbers of Tasks without running them. Capacities must be a power of two.
        See Also:
        Constant Field Values
      • MAX_CAPACITY

        protected static final int MAX_CAPACITY
        The maximum supported DEQ capacity. When exceeded, FJTaskRunner operations throw Errors
        See Also:
        Constant Field Values
      • top

        protected volatile int top
        Current top of DEQ. Generally acts just like a stack pointer in an array-based stack, except that it circularly wraps around the array, as in an array-based queue. The value is NOT always kept within 0 ... deq.length though. The current top element is always at top & (deq.length-1). To avoid integer overflow, top is reset down within bounds whenever it is noticed to be out out bounds; at worst when it is at 2 * deq.length.
      • base

        protected volatile int base
        Current base of DEQ. Acts like a take-pointer in an array-based bounded queue. Same bounds and usage as top.
      • barrier

        protected final java.lang.Object barrier
        An extra object to synchronize on in order to achieve a memory barrier.
      • active

        protected boolean active
        Record whether current thread may be processing a task (i.e., has been started and is not in an idle wait). Accessed, under synch, ONLY by FJTaskRunnerGroup, but the field is stored here for simplicity.
      • victimRNG

        protected final java.util.Random victimRNG
        Random starting point generator for scan()
      • scanPriority

        protected int scanPriority
        Priority to use while scanning for work
      • runPriority

        protected int runPriority
        Priority to use while running tasks
      • runs

        protected int runs
        Total number of tasks run
      • scans

        protected int scans
        Total number of queues scanned for work
      • steals

        protected int steals
        Total number of tasks obtained via scan
    • Constructor Detail

      • FJTaskRunner

        protected FJTaskRunner​(FJTaskRunnerGroup g)
        Constructor called only during FJTaskRunnerGroup initialization
    • Method Detail

      • getGroup

        protected final FJTaskRunnerGroup getGroup()
        Return the FJTaskRunnerGroup of which this thread is a member
      • deqSize

        protected int deqSize()
        Current size of the task DEQ
      • setScanPriority

        protected void setScanPriority​(int pri)
        Set the priority to use while scanning. We do not bother synchronizing access, since by the time the value is needed, both this FJTaskRunner and its FJTaskRunnerGroup will necessarily have performed enough synchronization to avoid staleness problems of any consequence.
      • setRunPriority

        protected void setRunPriority​(int pri)
        Set the priority to use while running tasks. Same usage and rationale as setScanPriority.
      • push

        protected final void push​(FJTask r)
        Push a task onto DEQ. Called ONLY by current thread.
      • slowPush

        protected void slowPush​(FJTask r)
        Handle slow case for push
      • put

        protected final void put​(FJTask r)
        Enqueue task at base of DEQ. Called ONLY by current thread. This method is currently not called from class FJTask. It could be used as a faster way to do FJTask.start, but most users would find the semantics too confusing and unpredictable.
      • pop

        protected final FJTask pop()
        Return a popped task, or null if DEQ is empty. Called ONLY by current thread.

        This is not usually called directly but is instead inlined in callers. This version differs from the cilk algorithm in that pop does not fully back down and retry in the case of potential conflict with take. It simply rechecks under synch lock. This gives a preference for threads to run their own tasks, which seems to reduce flailing a bit when there are few tasks to run.

      • confirmPop

        protected final FJTask confirmPop​(int provisionalTop)
        Check under synch lock if DEQ is really empty when doing pop. Return task if not empty, else null.
      • take

        protected final FJTask take()
        Take a task from the base of the DEQ. Always called by other threads via scan()
      • confirmTake

        protected FJTask confirmTake​(int oldBase)
        double-check a potential take
      • checkOverflow

        protected void checkOverflow()
        Adjust top and base, and grow DEQ if necessary. Called only while DEQ synch lock being held. We don't expect this to be called very often. In most programs using FJTasks, it is never called.
      • scan

        protected void scan​(FJTask waitingFor)
        Do all but the pop() part of yield or join, by traversing all DEQs in our group looking for a task to steal. If none, it checks the entry queue.

        Since there are no good, portable alternatives, we rely here on a mixture of Thread.yield and priorities to reduce wasted spinning, even though these are not well defined. We are hoping here that the JVM does something sensible.

        Parameters:
        waitingFor - if non-null, the current task being joined
      • scanWhileIdling

        protected void scanWhileIdling()
        Same as scan, but called when current thread is idling. It repeatedly scans other threads for tasks, sleeping while none are available.

        This differs from scan mainly in that since there is no reason to return to recheck any condition, we iterate until a task is found, backing off via sleeps if necessary.

      • run

        public void run()
        Main runloop
        Specified by:
        run in interface java.lang.Runnable
        Overrides:
        run in class java.lang.Thread
      • taskYield

        protected final void taskYield()
        Execute a task in this thread. Generally called when current task cannot otherwise continue.
      • taskJoin

        protected final void taskJoin​(FJTask w)
        Process tasks until w is done. Equivalent to while(!w.isDone()) taskYield();
      • coInvoke

        protected final void coInvoke​(FJTask w,
                                      FJTask v)
        A specialized expansion of w.fork(); invoke(v); w.join();
      • slowCoInvoke

        protected void slowCoInvoke​(FJTask w,
                                    FJTask v)
        Backup to handle noninlinable cases of coInvoke
      • coInvoke

        protected final void coInvoke​(FJTask[] tasks)
        Array-based version of coInvoke
      • slowCoInvoke

        protected void slowCoInvoke​(FJTask[] tasks)
        Backup to handle atypical or noninlinable cases of coInvoke