Scheduler Bypass

Scheduler bypass is an optimization where you directly specify the next task to run. Continuation-passing style often opens up an opportunity for scheduler bypass. For example, at the end of the continuation-passing example in the previous section, method execute() spawns task "a" and returns. By the execution rules in How Task Scheduling Works, that sequence causes the executing thread to do the following:

  1. Push task "a" onto the thread's deque.

  2. Return from method execute().

  3. Pop task "a" from the thread's deque, unless it is stolen by another thread.

Steps 1 and 3 introduce unnecessary deque operations, or worse yet, permit stealing that can hurt locality without adding significant parallelism. Method execute()can avoid these problems by returning a pointer to a instead of spawning it. When using the method shown in How Task Scheduling Works, a becomes the next task executed by the thread. Furthermore, this approach guarantees that the thread executes a, not some other thread.

The following example shows the changes to the example in the previous section in bold font:

struct FibTask: public task {
    ...
    task* execute() {
        if( n<CutOff ) {
            *sum = SerialFib(n);
            return NULL;
        } else {
            FibContinuation& c = 
                *new( allocate_continuation() ) FibContinuation(sum);
 
            FibTask& a = *new( c.allocate_child() ) FibTask(n-2,&c.x);
            FibTask& b = *new( c.allocate_child() ) FibTask(n-1,&c.y);
            // Set ref_count to "two children".
            c.set_ref_count(2);
            spawn( b );
            // spawn( a ); This line removed
            // return NULL; This line removed
            return &a;
        }
    }
};
For more complete information about compiler optimizations, see our Optimization Notice.