<div dir="ltr"><br><div style>Good to know.</div><div style><br></div><div style>What operations do you mostly do in the priority queue?</div><div style><br></div><div style>I&#39;d like to point you to the timer implementation that we did in the linux kernel ages ago.  It is basically a set of log2 slots where each slot contains timers for time [2^i..2^(i+1)&gt;.  The dlinked lists make it O(1) to remove, change, or add a timer.  The timer interrupt basically &quot;eats&quot; linked lists, and when empty &quot;splats&quot; the first free slot out over the upper slots (which is O(n) worst case).  The structure is simple and optimized for doing a lot of mutation of the timers.  It beats a heap hands down in the kernel at least.</div>

<div style><br></div><div style>Alexander</div><div style><br></div></div><div class="gmail_extra"><br><br><div class="gmail_quote">On Thu, Jan 31, 2013 at 10:34 AM, Edward Z. Yang <span dir="ltr">&lt;<a href="mailto:ezyang@mit.edu" target="_blank">ezyang@mit.edu</a>&gt;</span> wrote:<br>

<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hey Alex,<br>
<br>
Thanks for CR. At the current point in time, the overall system design<br>
is very much in flux so a lot of this code may end up not existing in the<br>
final revision.  I will be sure to up the number of comments in the final<br>
version though!<br>
<br>
Edward<br>
<br>
Excerpts from Alexander Kjeldaas&#39;s message of Thu Jan 31 01:30:39 -<a href="tel:0800%202013" value="+468002013">0800 2013</a>:<br>
<div class="HOEnZb"><div class="h5">&gt; Hi Edward, thanks for your work on the new scheduler!<br>
&gt;<br>
&gt; I have a done a super light-weight review.  I think documenting the code a<br>
&gt; little more would help readability.<br>
&gt;<br>
&gt; <a href="http://hackage.haskell.org/trac/ghc/attachment/ticket/7606/0002-Stride-scheduling-draft-11-thread-migrating-implemen.patch" target="_blank">http://hackage.haskell.org/trac/ghc/attachment/ticket/7606/0002-Stride-scheduling-draft-11-thread-migrating-implemen.patch</a><br>


&gt;<br>
&gt; TSO.h:<br>
&gt;<br>
&gt; Could you document ss_*?  These are all important variables in the<br>
&gt; scheduler, and not documented.  For example, the code in Threads.c for<br>
&gt; setting these is can act as some documentation, but something needs to be<br>
&gt; documented here.<br>
&gt;<br>
&gt; (Please don&#39;t point to a paper as primary documentation.)<br>
&gt;<br>
&gt;     // 64-bit to prevent overflows; only ever accessed by the task which<br>
&gt; owns TSO.<br>
&gt;   170    StgWord64 ss_pass;<br>
&gt;   171    // These are bounded above by STRIDE1, which is less than max<br>
&gt; 32-bit word.<br>
&gt;   172    // You must take out the sched_lock to write to these; reads are<br>
&gt; OK<br>
&gt;   173    StgWord ss_tickets, ss_stride, ss_remain;<br>
&gt;   174<br>
&gt;<br>
&gt; Schedule.c:<br>
&gt;<br>
&gt;   727        StgTSO *t;<br>
&gt;<br>
&gt; Rename to &#39;tso&#39; to be descriptive.<br>
&gt;<br>
&gt;   744        // go through all of the TSOs in the run queue and decide<br>
&gt; where<br>
&gt;   745        // they should go<br>
&gt;   746        // XXX We can create the new heap more efficiently O(n) by<br>
&gt; just<br>
&gt;   747        // blitting them in and then re-heapifying<br>
&gt;   748        if (!emptyRunQueue(cap)) {<br>
&gt;   749            StgWord64 k;<br>
&gt;<br>
&gt; Ditto for &#39;k&#39;.<br>
&gt;<br>
&gt;   1201 scheduleHandleThreadBlocked( Capability *cap, StgTSO *t )<br>
&gt;<br>
&gt; Rename &#39;t&#39; to &#39;tso&#39;.<br>
&gt;<br>
&gt; Schedule.h:<br>
&gt;<br>
&gt;   125 // oh no magic constant<br>
&gt;   126 #define STRIDE1 (1 &lt;&lt; 20)<br>
&gt;<br>
&gt; Document STRIDE1<br>
&gt;<br>
&gt;   147 EXTERN_INLINE void<br>
&gt;   148 annulTSO(StgTSO *tso) {<br>
&gt;   149    // hack to make some invariants with regards to block_info and<br>
&gt; _link work<br>
&gt;   150    // this is called whereever we would have stepped all over the<br>
&gt;   151    // fields in the linked list implementation<br>
&gt;   152    tso-&gt;_link = END_TSO_QUEUE;<br>
&gt;   153    tso-&gt;block_info.closure = (StgClosure*)END_TSO_QUEUE;<br>
&gt;<br>
&gt; It would be great to have a pointer to the invariants, or the invariant(s)<br>
&gt; documented.<br>
&gt;<br>
&gt;   213    tso-&gt;ss_pass += tso-&gt;ss_stride;<br>
&gt;   214    StgWord64 r;<br>
&gt;   215    if (tso-&gt;ss_pass &lt;= cap-&gt;ss_pass) {<br>
&gt;   216        // Thread is behind, it will get scheduled in front with no<br>
&gt;   217        // intervention (note that cap-&gt;ss_pass is probably nonsense,<br>
&gt;   218        // since it doesn&#39;t include *this* thread.)<br>
&gt;   219        r = tso-&gt;ss_pass;<br>
&gt;   220    } else if (tso-&gt;ss_pass - tso-&gt;ss_pass &lt;= cap-&gt;ss_pass) {<br>
&gt;<br>
&gt; This expression looks weird/magic, tso-&gt;ss_pass - tso-&gt;ss_pass is 0.<br>
&gt;<br>
&gt;   221        // Thread is in good standing, schedule it in front<br>
&gt;   222        // (next iteration, they will not be in good standing if<br>
&gt;   223        // the global pass doesn&#39;t advance by much; that is, this<br>
&gt;   224        // thread managed to cut in front of other threads which<br>
&gt;   225        // are running behind.)<br>
&gt;   226        r = cap-&gt;ss_pass;<br>
&gt;   227    } else {<br>
&gt;   228        // Thread is not in good standing, schedule it later.<br>
&gt;   229        // Eventually, global pass will advance enough that the<br>
&gt;   230        // thread will be in good standing again, and can cut<br>
&gt;   231        // to the front.<br>
&gt;   232        r = tso-&gt;ss_pass;<br>
&gt;<br>
&gt;<br>
&gt; Threads.c:<br>
&gt;<br>
&gt;   361    if (migrating) {<br>
&gt;   362        joinRunQueue(cap,tso);<br>
&gt;   363    } else {<br>
&gt;   364        appendToRunQueue(cap,tso);<br>
&gt;   365    }<br>
&gt;<br>
&gt; Space after &#39;,&#39;<br>
&gt;<br>
&gt; Select.c: and rts/win32/AsyncIO.c<br>
&gt;<br>
&gt;   309                  tso-&gt;ss_remain = 0;<br>
&gt;   310                  joinRunQueue(&amp;MainCapability,tso);<br>
&gt;<br>
&gt; Should this be an abstraction in itself?<br>
&gt;<br>
&gt;<br>
&gt; rts/Capability.h:<br>
&gt;<br>
&gt;   59    PQueue *run_pqueue;<br>
&gt;   60<br>
&gt;   61    // [SSS] Stride scheduling extensions.  The Task with this<br>
&gt;   62    // Capability has exclusive access to this variable.<br>
&gt;   63    nat ss_pass;<br>
&gt;<br>
&gt; Document ss_pass.  For example how it relates to capPassUpdate and<br>
&gt; pushOnRunQueue (the weird/magic I commented on above) and invariants.<br>
&gt;<br>
&gt;<br>
&gt; Alexander<br>
</div></div></blockquote></div><br></div>