[GHC] #7606: Stride scheduling for Haskell threads with priorities

[GHC]

#7606: Stride scheduling for Haskell threads with priorities
---------------------------------+------------------------------------------
    Reporter:  ezyang            |       Owner:  ezyang          
        Type:  feature request   |      Status:  new             
    Priority:  normal            |   Milestone:  7.8.1           
   Component:  Runtime System    |     Version:  7.7             
    Keywords:                    |          Os:  Unknown/Multiple
Architecture:  Unknown/Multiple  |     Failure:  None/Unknown    
  Difficulty:  Unknown           |    Testcase:                  
   Blockedby:                    |    Blocking:                  
     Related:                    |  
---------------------------------+------------------------------------------

Comment(by ezyang):

 OK, here's where we stand:

 * The sorted list implementation performs comparably to the original when
 no priority changes are involved.  However, it does not apply sleeper
 fairness (give threads that were sleeping extra timeslices), and when
 sleeper fairness is applied, we suffer from performance degradation (since
 operations on the sorted list are no longer constant time).  So if this
 implementation wants to go anywhere, it needs to be upgraded into
 something like a skip list, which can efficiently search and remove things
 inside the structure.

 * I've stamped out some of the performance bugs from the array
 implementation (mostly by adding an extra queue which we use to handle
 "must run now!" threads).  However, we suffer from a huge bottleneck
 deleteMinPQueue(), which by the accounts of perf takes up 22% of the
 runtime. Apparently logarithmically many comparisons/memory writes cost a
 lot when a lot of threads are involved. I am going to look for something
 more high performance.

-- 
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/7606#comment:24>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler