Code review, new scheduler:

31 Jan 2013

      Hi Edward, thanks for your work on the new scheduler!

I have a done a super light-weight review.  I think documenting the code a
little more would help readability.

http://hackage.haskell.org/trac/ghc/attachment/ticket/7606/0002-Stride-sched...

TSO.h:

Could you document ss_*?  These are all important variables in the
scheduler, and not documented.  For example, the code in Threads.c for
setting these is can act as some documentation, but something needs to be
documented here.

(Please don't point to a paper as primary documentation.)

    // 64-bit to prevent overflows; only ever accessed by the task which
owns TSO.
  170    StgWord64 ss_pass;
  171    // These are bounded above by STRIDE1, which is less than max
32-bit word.
  172    // You must take out the sched_lock to write to these; reads are
OK
  173    StgWord ss_tickets, ss_stride, ss_remain;
  174

Schedule.c:

  727        StgTSO *t;

Rename to 'tso' to be descriptive.

  744        // go through all of the TSOs in the run queue and decide
where
  745        // they should go
  746        // XXX We can create the new heap more efficiently O(n) by
just
  747        // blitting them in and then re-heapifying
  748        if (!emptyRunQueue(cap)) {
  749            StgWord64 k;

Ditto for 'k'.

  1201 scheduleHandleThreadBlocked( Capability *cap, StgTSO *t )

Rename 't' to 'tso'.

Schedule.h:

  125 // oh no magic constant
  126 #define STRIDE1 (1 << 20)

Document STRIDE1

  147 EXTERN_INLINE void
  148 annulTSO(StgTSO *tso) {
  149    // hack to make some invariants with regards to block_info and
_link work
  150    // this is called whereever we would have stepped all over the
  151    // fields in the linked list implementation
  152    tso->_link = END_TSO_QUEUE;
  153    tso->block_info.closure = (StgClosure*)END_TSO_QUEUE;

It would be great to have a pointer to the invariants, or the invariant(s)
documented.

  213    tso->ss_pass += tso->ss_stride;
  214    StgWord64 r;
  215    if (tso->ss_pass <= cap->ss_pass) {
  216        // Thread is behind, it will get scheduled in front with no
  217        // intervention (note that cap->ss_pass is probably nonsense,
  218        // since it doesn't include *this* thread.)
  219        r = tso->ss_pass;
  220    } else if (tso->ss_pass - tso->ss_pass <= cap->ss_pass) {

This expression looks weird/magic, tso->ss_pass - tso->ss_pass is 0.

  221        // Thread is in good standing, schedule it in front
  222        // (next iteration, they will not be in good standing if
  223        // the global pass doesn't advance by much; that is, this
  224        // thread managed to cut in front of other threads which
  225        // are running behind.)
  226        r = cap->ss_pass;
  227    } else {
  228        // Thread is not in good standing, schedule it later.
  229        // Eventually, global pass will advance enough that the
  230        // thread will be in good standing again, and can cut
  231        // to the front.
  232        r = tso->ss_pass;

Threads.c:

  361    if (migrating) {
  362        joinRunQueue(cap,tso);
  363    } else {
  364        appendToRunQueue(cap,tso);
  365    }

Space after ','

Select.c: and rts/win32/AsyncIO.c

  309                  tso->ss_remain = 0;
  310                  joinRunQueue(&MainCapability,tso);

Should this be an abstraction in itself?

rts/Capability.h:

  59    PQueue *run_pqueue;
  60
  61    // [SSS] Stride scheduling extensions.  The Task with this
  62    // Capability has exclusive access to this variable.
  63    nat ss_pass;

Document ss_pass.  For example how it relates to capPassUpdate and
pushOnRunQueue (the weird/magic I commented on above) and invariants.

Alexander

Code review, new scheduler:

Alexander Kjeldaas