1. 26 May, 2011 1 commit
    • Duncan Coutts's avatar
      Rearrange shutdownCapability code slightly · 68b76e0e
      Duncan Coutts authored
      This is mostly for the beneift of having sensible places to put tracing
      code later. We want a code path that has somewhere to trace (in order):
       (1) starting up all capabilities;
       (2) N * starting up an individual capability;
       (3) N * shutting down an individual capability;
       (4) shutting down all capabilities.
      This has to work in both threaded and non-threaded modes.
      
      Locations (1) and (2) are provided by initCapabilities and
      initCapability respectively. Previously, there was no loccation for (4)
      and while shutdownCapability should be usable for (3) it was only called
      in the !THREADED_RTS case.
      
      Now, shutdownCapability is called unconditionally (and the body is
      conditonal on THREADED_RTS) and there is a new shutdownCapabilities that
      calls shutdownCapability in a loop.
      68b76e0e
  2. 11 Apr, 2011 1 commit
    • Simon Marlow's avatar
      Refactoring and tidy up · 1fb38442
      Simon Marlow authored
      This is a port of some of the changes from my private local-GC branch
      (which is still in darcs, I haven't converted it to git yet).  There
      are a couple of small functional differences in the GC stats: first,
      per-thread GC timings should now be more accurate, and secondly we now
      report average and maximum pause times. e.g. from minimax +RTS -N8 -s:
      
                                          Tot time (elapsed)  Avg pause  Max pause
        Gen  0      2755 colls,  2754 par   13.16s    0.93s     0.0003s    0.0150s
        Gen  1       769 colls,   769 par    3.71s    0.26s     0.0003s    0.0059s
      1fb38442
  3. 11 Nov, 2010 1 commit
  4. 01 Nov, 2010 1 commit
  5. 25 Nov, 2010 1 commit
  6. 17 Jun, 2010 1 commit
  7. 25 May, 2010 1 commit
  8. 20 May, 2010 1 commit
  9. 01 Apr, 2010 1 commit
    • Simon Marlow's avatar
      Change the representation of the MVar blocked queue · f4692220
      Simon Marlow authored
      The list of threads blocked on an MVar is now represented as a list of
      separately allocated objects rather than being linked through the TSOs
      themselves.  This lets us remove a TSO from the list in O(1) time
      rather than O(n) time, by marking the list object.  Removing this
      linear component fixes some pathalogical performance cases where many
      threads were blocked on an MVar and became unreachable simultaneously
      (nofib/smp/threads007), or when sending an asynchronous exception to a
      TSO in a long list of thread blocked on an MVar.
      
      MVar performance has actually improved by a few percent as a result of
      this change, slightly to my surprise.
      
      This is the final cleanup in the sequence, which let me remove the old
      way of waking up threads (unblockOne(), MSG_WAKEUP) in favour of the
      new way (tryWakeupThread and MSG_TRY_WAKEUP, which is idempotent).  It
      is now the case that only the Capability that owns a TSO may modify
      its state (well, almost), and this simplifies various things.  More of
      the RTS is based on message-passing between Capabilities now.
      f4692220
  10. 29 Mar, 2010 1 commit
    • Simon Marlow's avatar
      New implementation of BLACKHOLEs · 5d52d9b6
      Simon Marlow authored
      This replaces the global blackhole_queue with a clever scheme that
      enables us to queue up blocked threads on the closure that they are
      blocked on, while still avoiding atomic instructions in the common
      case.
      
      Advantages:
      
       - gets rid of a locked global data structure and some tricky GC code
         (replacing it with some per-thread data structures and different
         tricky GC code :)
      
       - wakeups are more prompt: parallel/concurrent performance should
         benefit.  I haven't seen anything dramatic in the parallel
         benchmarks so far, but a couple of threading benchmarks do improve
         a bit.
      
       - waking up a thread blocked on a blackhole is now O(1) (e.g. if
         it is the target of throwTo).
      
       - less sharing and better separation of Capabilities: communication
         is done with messages, the data structures are strictly owned by a
         Capability and cannot be modified except by sending messages.
      
       - this change will utlimately enable us to do more intelligent
         scheduling when threads block on each other.  This is what started
         off the whole thing, but it isn't done yet (#3838).
      
      I'll be documenting all this on the wiki in due course.
      5d52d9b6
  11. 11 Mar, 2010 1 commit
    • Simon Marlow's avatar
      Use message-passing to implement throwTo in the RTS · 7408b392
      Simon Marlow authored
      This replaces some complicated locking schemes with message-passing
      in the implementation of throwTo. The benefits are
      
       - previously it was impossible to guarantee that a throwTo from
         a thread running on one CPU to a thread running on another CPU
         would be noticed, and we had to rely on the GC to pick up these
         forgotten exceptions. This no longer happens.
      
       - the locking regime is simpler (though the code is about the same
         size)
      
       - threads can be unblocked from a blocked_exceptions queue without
         having to traverse the whole queue now.  It's a rare case, but
         replaces an O(n) operation with an O(1).
      
       - generally we move in the direction of sharing less between
         Capabilities (aka HECs), which will become important with other
         changes we have planned.
      
      Also in this patch I replaced several STM-specific closure types with
      a generic MUT_PRIM closure type, which allowed a lot of code in the GC
      and other places to go away, hence the line-count reduction.  The
      message-passing changes resulted in about a net zero line-count
      difference.
      7408b392
  12. 09 Mar, 2010 1 commit
    • Simon Marlow's avatar
      Split part of the Task struct into a separate struct InCall · 7effbbbb
      Simon Marlow authored
      The idea is that this leaves Tasks and OSThread in one-to-one
      correspondence.  The part of a Task that represents a call into
      Haskell from C is split into a separate struct InCall, pointed to by
      the Task and the TSO bound to it.  A given OSThread/Task thus always
      uses the same mutex and condition variable, rather than getting a new
      one for each callback.  Conceptually it is simpler, although there are
      more types and indirections in a few places now.
      
      This improves callback performance by removing some of the locks that
      we had to take when making in-calls.  Now we also keep the current Task
      in a thread-local variable if supported by the OS and gcc (currently
      only Linux).
      7effbbbb
  13. 16 Feb, 2010 1 commit
  14. 02 Dec, 2009 1 commit
  15. 01 Dec, 2009 1 commit
    • Simon Marlow's avatar
      Make allocatePinned use local storage, and other refactorings · 5270423a
      Simon Marlow authored
      This is a batch of refactoring to remove some of the GC's global
      state, as we move towards CPU-local GC.  
      
        - allocateLocal() now allocates large objects into the local
          nursery, rather than taking a global lock and allocating
          then in gen 0 step 0.
      
        - allocatePinned() was still allocating from global storage and
          taking a lock each time, now it uses local storage. 
          (mallocForeignPtrBytes should be faster with -threaded).
          
        - We had a gen 0 step 0, distinct from the nurseries, which are
          stored in a separate nurseries[] array.  This is slightly strange.
          I removed the g0s0 global that pointed to gen 0 step 0, and
          removed all uses of it.  I think now we don't use gen 0 step 0 at
          all, except possibly when there is only one generation.  Possibly
          more tidying up is needed here.
      
        - I removed the global allocate() function, and renamed
          allocateLocal() to allocate().
      
        - the alloc_blocks global is gone.  MAYBE_GC() and
          doYouWantToGC() now check the local nursery only.
      5270423a
  16. 09 Sep, 2009 1 commit
  17. 05 Aug, 2009 1 commit
  18. 02 Aug, 2009 1 commit
    • Simon Marlow's avatar
      RTS tidyup sweep, first phase · a2a67cd5
      Simon Marlow authored
      The first phase of this tidyup is focussed on the header files, and in
      particular making sure we are exposinng publicly exactly what we need
      to, and no more.
      
       - Rts.h now includes everything that the RTS exposes publicly,
         rather than a random subset of it.
      
       - Most of the public header files have moved into subdirectories, and
         many of them have been renamed.  But clients should not need to
         include any of the other headers directly, just #include the main
         public headers: Rts.h, HsFFI.h, RtsAPI.h.
      
       - All the headers needed for via-C compilation have moved into the
         stg subdirectory, which is self-contained.  Most of the headers for
         the rest of the RTS APIs have moved into the rts subdirectory.
      
       - I left MachDeps.h where it is, because it is so widely used in
         Haskell code.
       
       - I left a deprecated stub for RtsFlags.h in place.  The flag
         structures are now exposed by Rts.h.
      
       - Various internal APIs are no longer exposed by public header files.
      
       - Various bits of dead code and declarations have been removed
      
       - More gcc warnings are turned on, and the RTS code is more
         warning-clean.
      
       - More source files #include "PosixSource.h", and hence only use
         standard POSIX (1003.1c-1995) interfaces.
      
      There is a lot more tidying up still to do, this is just the first
      pass.  I also intend to standardise the names for external RTS APIs
      (e.g use the rts_ prefix consistently), and declare the internal APIs
      as hidden for shared libraries.
      a2a67cd5
  19. 26 Apr, 2009 1 commit
  20. 13 Mar, 2009 1 commit
    • Simon Marlow's avatar
      Instead of a separate context-switch flag, set HpLim to zero · 304e7fb7
      Simon Marlow authored
      This reduces the latency between a context-switch being triggered and
      the thread returning to the scheduler, which in turn should reduce the
      cost of the GC barrier when there are many cores.
      
      We still retain the old context_switch flag which is checked at the
      end of each block of allocation.  The idea is that setting HpLim may
      fail if the the target thread is modifying HpLim at the same time; the
      context_switch flag is a fallback.  It also allows us to "context
      switch soon" without forcing an immediate switch, which can be costly.
      304e7fb7
  21. 12 Jan, 2009 1 commit
    • Simon Marlow's avatar
      Keep the remembered sets local to each thread during parallel GC · 6a405b1e
      Simon Marlow authored
      This turns out to be quite vital for parallel programs:
      
        - The way we discover which threads to traverse is by finding
          dirty threads via the remembered sets (aka mutable lists).
      
        - A dirty thread will be on the remembered set of the capability
          that was running it, and we really want to traverse that thread's
          stack using the GC thread for the capability, because it is in
          that CPU's cache.  If we get this wrong, we get penalised badly by
          the memory system.
      
      Previously we had per-capability mutable lists but they were
      aggregated before GC and traversed by just one of the GC threads.
      This resulted in very poor performance particularly for parallel
      programs with deep stacks.
      
      Now we keep per-capability remembered sets throughout GC, which also
      removes a lock (recordMutableGen_sync).
      6a405b1e
  22. 02 Dec, 2008 1 commit
  23. 28 Nov, 2008 1 commit
  24. 21 Nov, 2008 1 commit
    • Simon Marlow's avatar
      Use mutator threads to do GC, instead of having a separate pool of GC threads · 3ebcd3de
      Simon Marlow authored
      Previously, the GC had its own pool of threads to use as workers when
      doing parallel GC.  There was a "leader", which was the mutator thread
      that initiated the GC, and the other threads were taken from the pool.
      
      This was simple and worked fine for sequential programs, where we did
      most of the benchmarking for the parallel GC, but falls down for
      parallel programs.  When we have N mutator threads and N cores, at GC
      time we would have to stop N-1 mutator threads and start up N-1 GC
      threads, and hope that the OS schedules them all onto separate cores.
      It practice it doesn't, as you might expect.
      
      Now we use the mutator threads to do GC.  This works quite nicely,
      particularly for parallel programs, where each mutator thread scans
      its own spark pool, which is probably in its cache anyway.
      
      There are some flag changes:
      
        -g<n> is removed (-g1 is still accepted for backwards compat).
        There's no way to have a different number of GC threads than mutator
        threads now.
      
        -q1       Use one OS thread for GC (turns off parallel GC)
        -qg<n>    Use parallel GC for generations >= <n> (default: 1)
      
      Using parallel GC only for generations >=1 works well for sequential
      programs.  Compiling an ordinary sequential program with -threaded and
      running it with -N2 or more should help if you do a lot of GC.  I've
      found that adding -qg0 (do parallel GC for generation 0 too) speeds up
      some parallel programs, but slows down some sequential programs.
      Being conservative, I left the threshold at 1.
      
      ToDo: document the new options.
      3ebcd3de
  25. 19 Nov, 2008 1 commit
  26. 06 Nov, 2008 3 commits
  27. 24 Oct, 2008 1 commit
  28. 23 Oct, 2008 1 commit
  29. 22 Oct, 2008 2 commits
    • Simon Marlow's avatar
    • Simon Marlow's avatar
      Refactoring and reorganisation of the scheduler · 99df892c
      Simon Marlow authored
      Change the way we look for work in the scheduler.  Previously,
      checking to see whether there was anything to do was a
      non-side-effecting operation, but this has changed now that we do
      work-stealing.  This lead to a refactoring of the inner loop of the
      scheduler.
      
      Also, lots of cleanup in the new work-stealing code, but no functional
      changes.
      
      One new statistic is added to the +RTS -s output:
      
        SPARKS: 1430 (2 converted, 1427 pruned)
      
      lets you know something about the use of `par` in the program.
      99df892c
  30. 15 Sep, 2008 1 commit
    • berthold@mathematik.uni-marburg.de's avatar
      Work stealing for sparks · cf9650f2
      berthold@mathematik.uni-marburg.de authored
         Spark stealing support for PARALLEL_HASKELL and THREADED_RTS versions of the RTS.
        
        Spark pools are per capability, separately allocated and held in the Capability 
        structure. The implementation uses Double-Ended Queues (deque) and cas-protected 
        access.
        
        The write end of the queue (position bottom) can only be used with
        mutual exclusion, i.e. by exactly one caller at a time.
        Multiple readers can steal()/findSpark() from the read end
        (position top), and are synchronised without a lock, based on a cas
        of the top position. One reader wins, the others return NULL for a
        failure.
        
        Work stealing is called when Capabilities find no other work (inside yieldCapability),
        and tries all capabilities 0..n-1 twice, unless a theft succeeds.
        
        Inside schedulePushWork, all considered cap.s (those which were idle and could 
        be grabbed) are woken up. Future versions should wake up capabilities immediately when 
        putting a new spark in the local pool, from newSpark().
      
      Patch has been re-recorded due to conflicting bugfixes in the sparks.c, also fixing a 
      (strange) conflict in the scheduler.
      cf9650f2
  31. 19 Sep, 2008 1 commit
  32. 09 Sep, 2008 1 commit
    • Simon Marlow's avatar
      Fix race condition in wakeupThreadOnCapability() (#2574) · d572aed6
      Simon Marlow authored
      wakeupThreadOnCapbility() is used to signal another capability that
      there is a thread waiting to be added to its run queue.  It adds the
      thread to the (locked) wakeup queue on the remote capability.  In
      order to do this, it has to modify the TSO's link field, which has a
      write barrier.  The write barrier might put the TSO on the mutable
      list, and the bug was that it was using the mutable list of the
      *target* capability, which we do not have exclusive access to.  We
      should be using the current Capabilty's mutable list in this case.
      d572aed6
  33. 19 Aug, 2008 1 commit
  34. 23 Jul, 2008 1 commit
  35. 24 Apr, 2008 1 commit
  36. 16 Apr, 2008 1 commit
  37. 24 Jul, 2007 1 commit
    • Simon Marlow's avatar
      hs_exit()/shutdownHaskell(): wait for outstanding foreign calls to complete before returning · 681aad99
      Simon Marlow authored
      This is pertinent to #1177.  When shutting down a DLL, we need to be
      sure that there are no OS threads that can return to the code that we
      are about to unload, and previously the threaded RTS was unsafe in
      this respect.
      
      When exiting a standalone program we don't have to be quite so
      paranoid: all the code will disappear at the same time as any running
      threads.  Happily exiting a program happens via a different path:
      shutdownHaskellAndExit().  If we're about to exit(), then there's no
      need to wait for foreign calls to complete.
      681aad99