Re: [GHC] #650: Improve interaction between mutable arrays and GC

[Simon Marlow]

Switching to the new server has messed up threading for ghc-bugs emails. 
 I think the culprit is this:


References: <047.44b951cd4b5aa8536d862412c8d86...@abbot.galois.com>
In-Reply-To: <047.44b951cd4b5aa8536d862412c8d86...@abbot.galois.com>

these references point to @abbot.galois.com, rather than 
@monk.galois.com. It's not a showstopper, but it's somewhat annoying.

Can anything be done about it?

Cheers,
Simon
___
Glasgow-haskell-bugs mailing list
Glasgow-haskell-bugs@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs

Re: [GHC] #650: Improve interaction between mutable arrays and GC

[GHC]

#650: Improve interaction between mutable arrays and GC
--+-
  Reporter:  simonmar |  Owner:  igloo   
  Type:  merge| Status:  closed  
  Priority:  normal   |  Milestone:  6.12.2  
 Component:  Runtime System   |Version:  6.4.1   
Resolution:  fixed|   Keywords:  
Difficulty:  Difficult (2-5 days) | Os:  Unknown/Multiple
  Testcase:   |   Architecture:  Unknown/Multiple
   Failure:  Runtime performance bug  |  
--+-
Changes (by igloo):

  * status:  new => closed
  * resolution:  => fixed


Comment:

 Merged, along with
 {{{
 Tue Dec 22 22:20:17 GMT 2009  d...@cs.tufts.edu
   * Copying Simon M's fix for 650 to the new codegen
 }}}

-- 
Ticket URL: 
GHC 
The Glasgow Haskell Compiler
___
Glasgow-haskell-bugs mailing list
Glasgow-haskell-bugs@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs

Re: [GHC] #650: Improve interaction between mutable arrays and GC

[GHC]

#650: Improve interaction between mutable arrays and GC
--+-
  Reporter:  simonmar |  Owner:  igloo   
  Type:  merge| Status:  new 
  Priority:  normal   |  Milestone:  6.12.2  
 Component:  Runtime System   |Version:  6.4.1   
Resolution:   |   Keywords:  
Difficulty:  Difficult (2-5 days) | Os:  Unknown/Multiple
  Testcase:   |   Architecture:  Unknown/Multiple
   Failure:  Runtime performance bug  |  
--+-
Comment (by simonmar):

 Go ahead and merge, this seems to have no adverse effects in the HEAD.

-- 
Ticket URL: 
GHC 
The Glasgow Haskell Compiler___
Glasgow-haskell-bugs mailing list
Glasgow-haskell-bugs@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs

Re: [GHC] #650: Improve interaction between mutable arrays and GC

[GHC]

#650: Improve interaction between mutable arrays and GC
--+-
  Reporter:  simonmar |  Owner:  igloo   
  Type:  merge| Status:  new 
  Priority:  normal   |  Milestone:  6.12.2  
 Component:  Runtime System   |Version:  6.4.1   
Resolution:   |   Keywords:  
Difficulty:  Difficult (2-5 days) | Os:  Unknown/Multiple
  Testcase:   |   Architecture:  Unknown/Multiple
   Failure:  Runtime performance bug  |  
--+-
Comment (by igloo):

 Is the "more testing and benchmarking" done? Or is someone doing it?

-- 
Ticket URL: 
GHC 
The Glasgow Haskell Compiler___
Glasgow-haskell-bugs mailing list
Glasgow-haskell-bugs@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs

Re: [GHC] #650: Improve interaction between mutable arrays and GC

[GHC]

#650: Improve interaction between mutable arrays and GC
--+-
  Reporter:  simonmar |  Owner:  igloo   
  Type:  merge| Status:  new 
  Priority:  normal   |  Milestone:  6.12.2  
 Component:  Runtime System   |Version:  6.4.1   
Resolution:   |   Keywords:  
Difficulty:  Difficult (2-5 days) | Os:  Unknown/Multiple
  Testcase:   |   Architecture:  Unknown/Multiple
   Failure:  Runtime performance bug  |  
--+-
Changes (by igloo):

  * owner:  simonmar => igloo
  * type:  bug => merge

-- 
Ticket URL: 
GHC 
The Glasgow Haskell Compiler___
Glasgow-haskell-bugs mailing list
Glasgow-haskell-bugs@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs

Re: [GHC] #650: Improve interaction between mutable arrays and GC

[GHC]

#650: Improve interaction between mutable arrays and GC
--+-
  Reporter:  simonmar |  Owner:  simonmar
  Type:  bug  | Status:  new 
  Priority:  normal   |  Milestone:  6.12.2  
 Component:  Runtime System   |Version:  6.4.1   
Resolution:   |   Keywords:  
Difficulty:  Difficult (2-5 days) | Os:  Unknown/Multiple
  Testcase:   |   Architecture:  Unknown/Multiple
   Failure:  Runtime performance bug  |  
--+-
Comment (by simonmar):

 NB. this patch is needed too

 {{{
 Mon Dec 21 11:52:49 GMT 2009  Simon Marlow 
   * Fixes to account for the new layout of MUT_ARR_PTRS (see #650)
 }}}

-- 
Ticket URL: 
GHC 
The Glasgow Haskell Compiler___
Glasgow-haskell-bugs mailing list
Glasgow-haskell-bugs@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs

Re: [GHC] #650: Improve interaction between mutable arrays and GC

[GHC]

#650: Improve interaction between mutable arrays and GC
--+-
  Reporter:  simonmar |  Owner:  simonmar
  Type:  bug  | Status:  new 
  Priority:  normal   |  Milestone:  6.12.2  
 Component:  Runtime System   |Version:  6.4.1   
Resolution:   |   Keywords:  
Difficulty:  Difficult (2-5 days) | Os:  Unknown/Multiple
  Testcase:   |   Architecture:  Unknown/Multiple
   Failure:  Runtime performance bug  |  
--+-
Changes (by simonmar):

  * milestone:  6.14.1 => 6.12.2

Comment:

 Fixed:

 {{{
 Thu Dec 17 14:42:28 PST 2009  Simon Marlow 
   * Fix #650: use a card table to mark dirty sections of mutable arrays
   The card table is an array of bytes, placed directly following the
   actual array data.  This means that array reading is unaffected, but
   array writing needs to read the array size from the header in order to
   find the card table.

   We use a bytemap rather than a bitmap, because updating the card table
   must be multi-thread safe.  Each byte refers to 128 entries of the
   array, but this is tunable by changing the constant
   MUT_ARR_PTRS_CARD_BITS in includes/Constants.h.

 M ./compiler/codeGen/CgPrimOp.hs -2 +14
 M ./includes/Cmm.h +3
 M ./includes/HaskellConstants.hs +3
 M ./includes/mkDerivedConstants.c +1
 M ./includes/rts/Constants.h +7
 M ./includes/rts/storage/ClosureMacros.h -1 +29
 M ./includes/rts/storage/Closures.h +2
 M ./rts/PrimOps.cmm -5 +23
 M ./rts/Weak.c -2 +9
 M ./rts/sm/Scav.c -54 +123
 }}}

 I benchmarked this program, amongst others:

 {{{
 import Control.Monad
 import qualified Data.HashTable as H
 import System.Environment

 main = do
   [size] <- fmap (fmap read) getArgs
   m <- H.new (==) H.hashInt
   forM_ [1..size] $ \n -> H.insert m n n
   v <- H.lookup m 100
   print v
 }}}

 for size=100, with 6.12.1 it takes around 50s on my x86/Linux laptop,
 with the HEAD and this patch it takes 9.5s.

 We could merge this into 6.12.2 after more testing and benchmarking, as
 the changes are fairly localised.

-- 
Ticket URL: 
GHC 
The Glasgow Haskell Compiler___
Glasgow-haskell-bugs mailing list
Glasgow-haskell-bugs@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs

Re: [GHC] #650: Improve interaction between mutable arrays and GC

[GHC]

#650: Improve interaction between mutable arrays and GC
--+-
  Reporter:  simonmar |  Owner:  simonmar
  Type:  bug  | Status:  new 
  Priority:  normal   |  Milestone:  6.14.1  
 Component:  Runtime System   |Version:  6.4.1   
Resolution:   |   Keywords:  
Difficulty:  Difficult (2-5 days) | Os:  Unknown/Multiple
  Testcase:   |   Architecture:  Unknown/Multiple
   Failure:  Runtime performance bug  |  
--+-
Comment (by morrow):

 > I must be getting old, but my feeling is that tricks like this sound
 quite cool but end up being a pain in the neck in the long run.

 To be honest, the thought of dealing with that scares the crap out of me.
 :-)

-- 
Ticket URL: 
GHC 
The Glasgow Haskell Compiler___
Glasgow-haskell-bugs mailing list
Glasgow-haskell-bugs@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs

Re: [GHC] #650: Improve interaction between mutable arrays and GC

[GHC]

#650: Improve interaction between mutable arrays and GC
--+-
  Reporter:  simonmar |  Owner:  simonmar
  Type:  bug  | Status:  new 
  Priority:  normal   |  Milestone:  6.14.1  
 Component:  Runtime System   |Version:  6.4.1   
Resolution:   |   Keywords:  
Difficulty:  Difficult (2-5 days) | Os:  Unknown/Multiple
  Testcase:   |   Architecture:  Unknown/Multiple
   Failure:  Runtime performance bug  |  
--+-
Comment (by simonmar):

 cmpxchg is also only atomic with a LOCK prefix.  Typically a LOCK prefix
 adds on the order of 100 cycles, even without contention.  Apprently it's
 better on Nehalem CPUs, but still we need something that works well across
 a variety of hardware.  I don't think using byte writes are a big problem
 in practice.

-- 
Ticket URL: 
GHC 
The Glasgow Haskell Compiler___
Glasgow-haskell-bugs mailing list
Glasgow-haskell-bugs@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs

Re: [GHC] #650: Improve interaction between mutable arrays and GC

[GHC]

#650: Improve interaction between mutable arrays and GC
--+-
  Reporter:  simonmar |  Owner:  simonmar
  Type:  bug  | Status:  new 
  Priority:  normal   |  Milestone:  6.14.1  
 Component:  Runtime System   |Version:  6.4.1   
Resolution:   |   Keywords:  
Difficulty:  Difficult (2-5 days) | Os:  Unknown/Multiple
  Testcase:   |   Architecture:  Unknown/Multiple
   Failure:  Runtime performance bug  |  
--+-
Comment (by guest):

 Most of the time there won't be contention.

 How about using cmpxchg, and falling back to bts if there happened to be
 contention? Or would that also be much more expensive than byte
 operations?

-- 
Ticket URL: 
GHC 
The Glasgow Haskell Compiler___
Glasgow-haskell-bugs mailing list
Glasgow-haskell-bugs@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs

Re: [GHC] #650: Improve interaction between mutable arrays and GC

[GHC]

#650: Improve interaction between mutable arrays and GC
--+-
  Reporter:  simonmar |  Owner:  simonmar
  Type:  bug  | Status:  new 
  Priority:  normal   |  Milestone:  6.14.1  
 Component:  Runtime System   |Version:  6.4.1   
Resolution:   |   Keywords:  
Difficulty:  Difficult (2-5 days) | Os:  Unknown/Multiple
  Testcase:   |   Architecture:  Unknown/Multiple
   Failure:  Runtime performance bug  |  
--+-
Comment (by simonmar):

 Replying to [comment:19 GregoryCollins]:
 > Can you use a BTS instruction to do bitwise marking atomically? It'd be
 nice to see if there was a performance improvement, in theory you trade
 some bookkeeping complexity for 8x fewer cache line loads.

 BTS is only atomic with a LOCK prefix, and that would make it a lot more
 expensive than doing byte operations.

-- 
Ticket URL: 
GHC 
The Glasgow Haskell Compiler___
Glasgow-haskell-bugs mailing list
Glasgow-haskell-bugs@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs

Re: [GHC] #650: Improve interaction between mutable arrays and GC

[GHC]

#650: Improve interaction between mutable arrays and GC
--+-
  Reporter:  simonmar |  Owner:  simonmar
  Type:  bug  | Status:  new 
  Priority:  normal   |  Milestone:  6.14.1  
 Component:  Runtime System   |Version:  6.4.1   
Resolution:   |   Keywords:  
Difficulty:  Difficult (2-5 days) | Os:  Unknown/Multiple
  Testcase:   |   Architecture:  Unknown/Multiple
   Failure:  Runtime performance bug  |  
--+-
Comment (by GregoryCollins):

 It's a simple card-marking strategy where the card bits (actually bytes,
 for atomicity)

 Can you use a BTS instruction to do bitwise marking atomically? It'd be
 nice to see if there was a performance improvement, in theory you trade
 some bookkeeping complexity for 8x fewer cache line loads.

-- 
Ticket URL: 
GHC 
The Glasgow Haskell Compiler___
Glasgow-haskell-bugs mailing list
Glasgow-haskell-bugs@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs

Re: [GHC] #650: Improve interaction between mutable arrays and GC

[GHC]

#650: Improve interaction between mutable arrays and GC
--+-
  Reporter:  simonmar |  Owner:  simonmar
  Type:  bug  | Status:  new 
  Priority:  normal   |  Milestone:  6.14.1  
 Component:  Runtime System   |Version:  6.4.1   
Resolution:   |   Keywords:  
Difficulty:  Difficult (2-5 days) | Os:  Unknown/Multiple
  Testcase:   |   Architecture:  Unknown/Multiple
   Failure:  Runtime performance bug  |  
--+-
Comment (by simonmar):

 Replying to [comment:16 morrow]:
 > One other possible method to deal with this is to make old-generation
 pages containing mutable array data read-only via mprotect (or
 equivalent). Any later write will then cause a SIGSEGV,

 Not keen on this for a few reasons:

  * non-portability
  * too coarse-grained
  * only works for large arrays
  * GC needs to fiddle around with mprotecting pages
  * taking the signal is expensive
  * recovering from a SIGSEGV is very tricky

 I must be getting old, but my feeling is that tricks like this sound quite
 cool but end up being a pain in the neck in the long run.

-- 
Ticket URL: 
GHC 
The Glasgow Haskell Compiler___
Glasgow-haskell-bugs mailing list
Glasgow-haskell-bugs@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs

Re: [GHC] #650: Improve interaction between mutable arrays and GC

[GHC]

#650: Improve interaction between mutable arrays and GC
--+-
  Reporter:  simonmar |  Owner:  simonmar
  Type:  bug  | Status:  new 
  Priority:  normal   |  Milestone:  6.14.1  
 Component:  Runtime System   |Version:  6.4.1   
Resolution:   |   Keywords:  
Difficulty:  Difficult (2-5 days) | Os:  Unknown/Multiple
  Testcase:   |   Architecture:  Unknown/Multiple
   Failure:  Runtime performance bug  |  
--+-
Changes (by simonmar):

  * owner:  => simonmar
  * difficulty:  Moderate (less than a day) => Difficult (2-5 days)
  * milestone:  _|_ => 6.14.1

Comment:

 I worked on this problem yesterday.  So far I have a `Data.HashTable`
 benchmark that goes from 50s before the fix to 10s afterward with the
 default heap settings.  It's a simple card-marking strategy where the card
 bits (actually bytes, for atomicity) are stored after the array data.

 I want to do some more measurements and testing before I commit.  Roman
 also pointed out to me that this doesn't really fix the problem, it only
 reduces the constant factor (albeit by a lot), since we still have to
 traverse the mark bits on every GC, but I can't think of a workable
 strategy that doesn't suffer from this problem.

-- 
Ticket URL: 
GHC 
The Glasgow Haskell Compiler___
Glasgow-haskell-bugs mailing list
Glasgow-haskell-bugs@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs

Re: [GHC] #650: Improve interaction between mutable arrays and GC

[GHC]

#650: Improve interaction between mutable arrays and GC
-+--
  Reporter:  simonmar|  Owner:  
  Type:  bug | Status:  new 
  Priority:  normal  |  Milestone:  _|_ 
 Component:  Runtime System  |Version:  6.4.1   
Resolution:  |   Keywords:  
Difficulty:  Moderate (less than a day)  | Os:  Unknown/Multiple
  Testcase:  |   Architecture:  Unknown/Multiple
   Failure:  Runtime performance bug |  
-+--
Comment (by morrow):

 One other possible method to deal with this is to make old-generation
 pages containing mutable array data read-only via mprotect (or
 equivalent). Any later write will then cause a SIGSEGV, which is caught by
 an installed signal handler which then unprotects that page and marks it
 as dirty (however this needs to be done). A benefit of this is that any
 future writes to that page need no write barrier. Some limitations of this
 are that this reserves the SIGSEGV handler for the RTS, and this can only
 provide PAGE_SIZE granularity (which for large arrays is nevertheless a
 large improvement). What are people's thoughts on this? Is this (or some
 variation on this) an option given GHC's RTS?

-- 
Ticket URL: 
GHC 
The Glasgow Haskell Compiler___
Glasgow-haskell-bugs mailing list
Glasgow-haskell-bugs@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs

Re: [GHC] #650: Improve interaction between mutable arrays and GC

[GHC]

#650: Improve interaction between mutable arrays and GC
-+--
  Reporter:  simonmar|  Owner:  
  Type:  bug | Status:  new 
  Priority:  normal  |  Milestone:  _|_ 
 Component:  Runtime System  |Version:  6.4.1   
Resolution:  |   Keywords:  
Difficulty:  Moderate (less than a day)  | Os:  Unknown/Multiple
  Testcase:  |   Architecture:  Unknown/Multiple
   Failure:  Runtime performance bug |  
-+--
Changes (by blarsen):

 * cc: blarsen (added)

-- 
Ticket URL: 
GHC 
The Glasgow Haskell Compiler___
Glasgow-haskell-bugs mailing list
Glasgow-haskell-bugs@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs

Re: [GHC] #650: Improve interaction between mutable arrays and GC

[GHC]

#650: Improve interaction between mutable arrays and GC
-+--
  Reporter:  simonmar|  Owner:  
  Type:  bug | Status:  new 
  Priority:  normal  |  Milestone:  _|_ 
 Component:  Runtime System  |Version:  6.4.1   
Resolution:  |   Keywords:  
Difficulty:  Moderate (less than a day)  | Os:  Unknown/Multiple
  Testcase:  |   Architecture:  Unknown/Multiple
   Failure:  Runtime performance bug |  
-+--
Comment (by simonmar):

 See [wiki:Commentary/Rts/Storage/GC/RememberedSets] for more background on
 this.

-- 
Ticket URL: 
GHC 
The Glasgow Haskell Compiler___
Glasgow-haskell-bugs mailing list
Glasgow-haskell-bugs@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs

Re: [GHC] #650: Improve interaction between mutable arrays and GC

[GHC]

#650: Improve interaction between mutable arrays and GC
-+--
  Reporter:  simonmar|  Owner:  
  Type:  bug | Status:  new 
  Priority:  normal  |  Milestone:  _|_ 
 Component:  Runtime System  |Version:  6.4.1   
Resolution:  |   Keywords:  
Difficulty:  Moderate (less than a day)  | Os:  Unknown/Multiple
  Testcase:  |   Architecture:  Unknown/Multiple
   Failure:  Runtime performance bug |  
-+--
Changes (by sclv):

 * cc: sclv (added)

-- 
Ticket URL: 
GHC 
The Glasgow Haskell Compiler___
Glasgow-haskell-bugs mailing list
Glasgow-haskell-bugs@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs

Re: [GHC] #650: Improve interaction between mutable arrays and GC

[GHC]

#650: Improve interaction between mutable arrays and GC
-+--
Reporter:  simonmar  |Owner:  
Type:  run-time performance bug  |   Status:  new 
Priority:  normal|Milestone:  _|_ 
   Component:  Runtime System|  Version:  6.4.1   
Severity:  normal|   Resolution:  
Keywords:|   Difficulty:  Moderate (1 day)
Testcase:|   Os:  Unknown/Multiple
Architecture:  Unknown/Multiple  |  
-+--
Changes (by ganesh):

 * cc: ganesh (added)

-- 
Ticket URL: 
GHC 
The Glasgow Haskell Compiler___
Glasgow-haskell-bugs mailing list
Glasgow-haskell-bugs@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs

Re: [GHC] #650: Improve interaction between mutable arrays and GC

[GHC]

#650: Improve interaction between mutable arrays and GC
-+--
Reporter:  simonmar  |Owner:  
Type:  run-time performance bug  |   Status:  new 
Priority:  normal|Milestone:  _|_ 
   Component:  Runtime System|  Version:  6.4.1   
Severity:  normal|   Resolution:  
Keywords:|   Difficulty:  Moderate (1 day)
Testcase:|   Os:  Unknown/Multiple
Architecture:  Unknown/Multiple  |  
-+--
Changes (by ertai):

 * cc: ertai (added)

-- 
Ticket URL: 
GHC 
The Glasgow Haskell Compiler___
Glasgow-haskell-bugs mailing list
Glasgow-haskell-bugs@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs

Re: [GHC] #650: Improve interaction between mutable arrays and GC

[GHC]

#650: Improve interaction between mutable arrays and GC
-+--
Reporter:  simonmar  |Owner:  
Type:  run-time performance bug  |   Status:  new 
Priority:  normal|Milestone:  _|_ 
   Component:  Runtime System|  Version:  6.4.1   
Severity:  normal|   Resolution:  
Keywords:|   Difficulty:  Moderate (1 day)
Testcase:|   Os:  Unknown/Multiple
Architecture:  Unknown/Multiple  |  
-+--
Changes (by dons):

 * cc: dons (added)

-- 
Ticket URL: 
GHC 
The Glasgow Haskell Compiler___
Glasgow-haskell-bugs mailing list
Glasgow-haskell-bugs@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs

Re: [GHC] #650: Improve interaction between mutable arrays and GC

[GHC]

#650: Improve interaction between mutable arrays and GC
--+-
 Reporter:  simonmar  |  Owner:  
 Type:  run-time performance bug  | Status:  new 
 Priority:  normal|  Milestone:  _|_ 
Component:  Runtime System|Version:  6.4.1   
 Severity:  normal| Resolution:  
 Keywords:| Difficulty:  Moderate (1 day)
 Testcase:|   Architecture:  Unknown 
   Os:  Unknown   |  
--+-
Changes (by simonmar):

  * type:  task => run-time performance bug
  * milestone:  6.10 branch => _|_

-- 
Ticket URL: 
GHC 
The Glasgow Haskell Compiler___
Glasgow-haskell-bugs mailing list
Glasgow-haskell-bugs@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs

Re: [GHC] #650: Improve interaction between mutable arrays and GC

[GHC]

#650: Improve interaction between mutable arrays and GC
+---
 Reporter:  simonmar|  Owner:  
 Type:  task| Status:  new 
 Priority:  normal  |  Milestone:  6.10 branch 
Component:  Runtime System  |Version:  6.4.1   
 Severity:  normal  | Resolution:  
 Keywords:  | Difficulty:  Moderate (1 day)
 Testcase:  |   Architecture:  Unknown 
   Os:  Unknown |  
+---
Changes (by simonmar):

  * milestone:  6.8 branch => 6.10 branch

-- 
Ticket URL: 
GHC 
The Glasgow Haskell Compiler___
Glasgow-haskell-bugs mailing list
Glasgow-haskell-bugs@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs

Re: [GHC] #650: Improve interaction between mutable arrays and GC

[GHC]

#650: Improve interaction between mutable arrays and GC
+---
 Reporter:  simonmar|  Owner:  
 Type:  task| Status:  new 
 Priority:  normal  |  Milestone:  6.8 
Component:  Runtime System  |Version:  6.4.1   
 Severity:  normal  | Resolution:  
 Keywords:  | Difficulty:  Moderate (1 day)
 Testcase:  |   Architecture:  Unknown 
   Os:  Unknown |  
+---
Changes (by igloo):

  * milestone:  => 6.8
  * testcase:  =>

-- 
Ticket URL: 
GHC 
The Glasgow Haskell Compiler___
Glasgow-haskell-bugs mailing list
Glasgow-haskell-bugs@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs

Re: [GHC] #650: Improve interaction between mutable arrays and GC

[GHC]

#650: Improve interaction between mutable arrays and GC
---+
  Reporter:  simonmar  |  Owner: 
  Type:  task  | Status:  new
  Priority:  normal|  Milestone: 
 Component:  Runtime System|Version:  6.4.1  
  Severity:  normal| Resolution: 
  Keywords:| Os:  Unknown
Difficulty:  Moderate (1 day)  |   Architecture:  Unknown
---+
Changes (by simonmar):

  * milestone:  6.6 =>

Comment:

 Dropped milestone.  Some of this work has been done in 6.6 already:
 mutable arrays are only traversed during GC if they were modified since
 the last GC (although they remain on the mutable list), and IORefs are
 only placed on the mutable list when they are modified.  Threads are also
 marked as clean/dirty to avoid traversing a thread's stack if it hasn't
 run since the last GC.

 The main thing missing is restricting the traversal of an array to just
 the parts that were modified, using card-marking or similar.

-- 
Ticket URL: 
GHC 
The Glasgow Haskell Compiler___
Glasgow-haskell-bugs mailing list
Glasgow-haskell-bugs@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs

Re: [GHC] #650: Improve interaction between mutable arrays and GC

[Simon Marlow]

Jan-Willem Maessen wrote:


On Jan 11, 2006, at 6:21 AM, GHC wrote:


#650: Improve interaction between mutable arrays and GC
--- 
+

Reporter:  simonmar|Owner:
Type:  task|   Status:  new
Priority:  normal  |Milestone:  6.6
   Component:  Runtime System  |  Version:  6.4.1
Severity:  normal  | Keywords:
  Os:  Unknown |   Difficulty:  Moderate (1 day)
Architecture:  Unknown |
--- 
+
This is the result of a discussion between myself and Simon PJ a  few 
weeks

 ago, inspired by recent discoveries of poor performance with mutable
 arrays (eg. see Data.Hash discussion on glasgow-haskell-users around
 October 2005).

 Note that all this applies to mutable arrays of pointers, i.e.  
`IOArray`
 and `STArray`, ''not'' to unboxed arrays, i.e. `IOUArray` and  
`STUArray`.

...
 === The Problem ===

 The problem is that mutable arrays are always completely traversed on
 every GC.  To get around this, we can keep an array in a frozen  
state and

 thaw it just before writing, then freeze it again afterward.  This  is a
 bit inconvenient, not to mention unsafe with multiple threads  unless 
extra

 locking is used.



Yes.  I'd love it if "freeze" and "thaw" just affected types plus  
(perhaps) the ability for mutations to occur in the first place (so  
that I don't freeze in one thread and mutate in another).


Given that virtually every object access in GHC involves a hidden  read 
barrier (entering a thunk is effectively a read barrier which  checks 
computedness), I'm not too worried about the costs of a write  barrier 
for mutation in the IO monad.  I'd welcome some up-front cost  to avoid 
the GC problems.


I probably should have mentioned this to you, but we've implemented a 
partial solution to this already:


  http://www.haskell.org//pipermail/cvs-ghc/2006-January/028009.html
  http://www.haskell.org//pipermail/cvs-ghc/2006-January/028010.html

You should think seriously about keeping a write list for arrays as  an 
alternative to cards or a full scan, as Bulat suggested.  There  are 
card/write list hybrids.


If you put a card mark in the block table, there's no particular need  
to modify the array representation beyond adding a "dirty" bit.  The  
write barrier would look something like this:

  * Set array's dirty bit
  * Set card mark on appropriate block
  * Store pointer into array
Then during GC we scan the dirty blocks of dirty arrays.


I quite agree, and this is exactly what I'd planned to do (eventually).

Having a dirty bit per array in addition to the per-block bit has two 
benefits: it means you don't have to look at every block descriptor in a 
clean array, and secondly when there are multiple small arrays in a 
single block we won't end up scanning all of them if one of them is 
written to.


Small arrays will fit in a block and will be scanned completely.   
Larger arrays will span more than one block and benefit from the card  
marks.   But there's no need to actually distinguish these cases if

you're using cards.

Note also that we can keep multiple card flags in the block  descriptor, 
so there's actually opportunity for tuning here.  It's  trading off 
up-front bit-twiddling for lower GC overhead, though.


Do bear in mind that it's big arrays which really seem to be causing  
the trouble here.  So I think some solution which does work  
proportional to the amount of mutation is in order.


For IORefs the game is utterly different; I'm not sure what to do  about 
them.  You'd like to avoid traversing a list of all the IORefs  at each 
collection.  Very tricky.  Here it might be worth scanning  just the 
dirty blocks.


The IORef write barrier we implemented seems to work pretty well: when 
an IORef is written to, it is put on the mutable list iff it was 
previously clean.  The write barrier didn't decrease performance 
measurably for a program that did a lot of IORef manipulations, but the 
GC load was much reduced (see nofib/gc_bench).


Cheers,
Simon
___
Glasgow-haskell-bugs mailing list
Glasgow-haskell-bugs@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs

Re: [GHC] #650: Improve interaction between mutable arrays and GC

[Jan-Willem Maessen]

On Jan 11, 2006, at 6:21 AM, GHC wrote:


#650: Improve interaction between mutable arrays and GC
--- 
+

Reporter:  simonmar|Owner:
Type:  task|   Status:  new
Priority:  normal  |Milestone:  6.6
   Component:  Runtime System  |  Version:  6.4.1
Severity:  normal  | Keywords:
  Os:  Unknown |   Difficulty:  Moderate (1 day)
Architecture:  Unknown |
--- 
+
This is the result of a discussion between myself and Simon PJ a  
few weeks

 ago, inspired by recent discoveries of poor performance with mutable
 arrays (eg. see Data.Hash discussion on glasgow-haskell-users around
 October 2005).

 Note that all this applies to mutable arrays of pointers, i.e.  
`IOArray`
 and `STArray`, ''not'' to unboxed arrays, i.e. `IOUArray` and  
`STUArray`.

...
 === The Problem ===

 The problem is that mutable arrays are always completely traversed on
 every GC.  To get around this, we can keep an array in a frozen  
state and
 thaw it just before writing, then freeze it again afterward.  This  
is a
 bit inconvenient, not to mention unsafe with multiple threads  
unless extra

 locking is used.


Yes.  I'd love it if "freeze" and "thaw" just affected types plus  
(perhaps) the ability for mutations to occur in the first place (so  
that I don't freeze in one thread and mutate in another).


Given that virtually every object access in GHC involves a hidden  
read barrier (entering a thunk is effectively a read barrier which  
checks computedness), I'm not too worried about the costs of a write  
barrier for mutation in the IO monad.  I'd welcome some up-front cost  
to avoid the GC problems.



 === Solutions ===


You should think seriously about keeping a write list for arrays as  
an alternative to cards or a full scan, as Bulat suggested.  There  
are card/write list hybrids.


If you put a card mark in the block table, there's no particular need  
to modify the array representation beyond adding a "dirty" bit.  The  
write barrier would look something like this:

  * Set array's dirty bit
  * Set card mark on appropriate block
  * Store pointer into array
Then during GC we scan the dirty blocks of dirty arrays.

Small arrays will fit in a block and will be scanned completely.   
Larger arrays will span more than one block and benefit from the card  
marks.  But there's no need to actually distinguish these cases if  
you're using cards.


Note also that we can keep multiple card flags in the block  
descriptor, so there's actually opportunity for tuning here.  It's  
trading off up-front bit-twiddling for lower GC overhead, though.


Do bear in mind that it's big arrays which really seem to be causing  
the trouble here.  So I think some solution which does work  
proportional to the amount of mutation is in order.


For IORefs the game is utterly different; I'm not sure what to do  
about them.  You'd like to avoid traversing a list of all the IORefs  
at each collection.  Very tricky.  Here it might be worth scanning  
just the dirty blocks.


Perhaps there ought to be an IORef list per block?

-Jan-Willem Maessen

[Who's very interested in seeing this solved well...]

___
Glasgow-haskell-bugs mailing list
Glasgow-haskell-bugs@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs

Re[2]: [GHC] #650: Improve interaction between mutable arrays and GC

[Bulat Ziganshin]

Hello GHC,

Thursday, January 12, 2006, 5:52:28 PM, you wrote:

G> #650: Improve interaction between mutable arrays and GC

G>  This also affects IORefs, which are essentially single-element IOArrays.
G>  I just noticed that GHC often has a large number of IORefs hanging around
G>  in the heap from the typechecker, and the cost of traversing the mutable
G>  list can dominate minor GCs.

Simon, i have another one solution of this problem: on EACH write to
IOArray/STArray/IORef/STRef save an address of updated value in some
list. then, on minor GC scan this list and promote values reachable
from these array elements to the next generation

this may be slower, but at least it will be "fair" solution - amount
of additional work is directly proportional to number of writes, not
the total size of all IOArrays

i think that me must first collect examples of applications which
really suffers from this problem, to be able to make well-founded
solution. that i send you is just an artifical one (sorry, but it is
very close to my real application, which works very fast except for
these GCs), we can also add loop in descending order and loop in
random order to these artifical bencmarks. real applications may be
some working with HashTable and even GHC itself

one more suggestion - may be GHC can be speed up by replacing IORefs
by implicit parameters? it can also help to make GHC a library and to
run several compilations in parallel on multi-core cpus


-- 
Best regards,
 Bulatmailto:[EMAIL PROTECTED]



___
Glasgow-haskell-bugs mailing list
Glasgow-haskell-bugs@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs

Re: [GHC] #650: Improve interaction between mutable arrays and GC

[GHC]

#650: Improve interaction between mutable arrays and GC
---+
  Reporter:  simonmar  |  Owner: 
  Type:  task  | Status:  new
  Priority:  normal|  Milestone:  6.6
 Component:  Runtime System|Version:  6.4.1  
  Severity:  normal| Resolution: 
  Keywords:| Os:  Unknown
Difficulty:  Moderate (1 day)  |   Architecture:  Unknown
---+
Old description:

> This is the result of a discussion between myself and Simon PJ a few
> weeks ago, inspired by recent discoveries of poor performance with
> mutable arrays (eg. see Data.Hash discussion on glasgow-haskell-users
> around October 2005).
>
> Note that all this applies to mutable arrays of pointers, i.e. `IOArray`
> and `STArray`, ''not'' to unboxed arrays, i.e. `IOUArray` and `STUArray`.
>
> === Current implementation ===
>
> There are two primitive types: `MutArray#` and `Array#`. We convert
> between them with:
> {{{
>unsafeFreezeArray# :: MutArr# s a -> State# s -> (# State# s, Array# a
> #)
>unsafeThawArray# :: Array# a -> State# s -> (# State# s, MutArr# s a
> #)
> }}}
>
> An Arr# is not normally on the old-gen mutable list, unless (a) it has
> pointers to young gen objects, or (b) it has been recently frozen.  The
> implementation of `unsafeFreezeArray#` is a single write to the header
> word of the array.  The implementation of `unsafeThawArray#` is slightly
> more complex: if the array was not already on the mutable list (indicated
> by the value of the header), then we add it.  Also, we change the header
> word to indicate that the array is now mutable.
>
> A `MutArr#` is ''always'' on the mutable list.
>
> Objects pointed to by Array# are ''eagerly promoted'' to the generation
> in which the Array# resides, with the aim that the Array# can then be
> removed from the mutable list.
>
> It is only safe to write to a `MutArr#`, so if multiple threads are
> accessing an array, they should ''not'' be doing thaw/freeze tricks
> without extra locking around the array (such behaviour can cause the GC
> to crash).
>
> === The Problem ===
>
> The problem is that mutable arrays are always completely traversed on
> every GC.  To get around this, we can keep an array in a frozen state and
> thaw it just before writing, then freeze it again afterward.  This is a
> bit inconvenient, not to mention unsafe with multiple threads unless
> extra locking is used.
>
> Furthermore, a modified array is ''completely'' scanned, whereas for
> larger arrays it would be much better to just scan the part of the array
> that had been modified (known in the GC literature as "card-marking").
>
> The benefit of the current approach is that writing to a mutable array is
> a single write instruction, whereas to do card-marking or something else
> requires a write-barrier.  The unsafeThaw/write/unsafeFreeze sequence
> amounts to a write barrier, so if this is a common technique we should
> provide an easy way to do it, possibly making it the default.
>
> === Solutions ===
>
> Leaving aside card-marking for now, let's think about incorporating the
> write barrier in the write operation.
>
> Suppose that mutable arrays are ''always'' kept on the mutable list, but
> the header word indicates whether the array needs to be scanned or not
> (eg. we have `MUT_ARR_DIRTY`, `MUT_ARR_CLEAN`).  The array write op
> should (a) set the header to `MUT_ARR_DIRTY`, and (b) do the write.  The
> GC turns `MUT_ARR_DIRTY` into `MUT_ARR_CLEAN` when everything the array
> points to is in the same generation (or older).
>
> Downsides to this:
>
>   * intitialising a mutable array, or doing block writes, will be
> more painful, because each write will have the write barrier
> (perhaps not too painful)
>
> How does freezing/thawing interact with this?  We currently create
> immutable arrays by starting with a `MutArr#`, intitialising it, and then
> freezing it to make an `Arr#`.  We can still do this, exactly as now (and
> with the same thread-unsafety), but initialization will be a bit slower
> due to the write barrier.
>
> === Block writes ===
>
> We could try to provide for "block writes", by allowing a thread to
> "open" the array for modification, and then "close" it again after it had
> finished writing, with all writes in between being done without a write
> barrier.  This would replace unsafeThaw/unsafeFreeze.
>
> To do this safely, we would have to use some kind of synchronisation on
> the open/close; techniques that we came up with were to increment
> (atomically) a counter in the array header, or to allocate a new heap
> object pointing to the array in the current thread's allocation area.
>
> === Card marking ===
>
> We could refine the write barrier so that it marks just part of the array
> as dirty, instead of

[GHC] #650: Improve interaction between mutable arrays and GC

[GHC]

#650: Improve interaction between mutable arrays and GC
---+
Reporter:  simonmar|Owner:  
Type:  task|   Status:  new 
Priority:  normal  |Milestone:  6.6 
   Component:  Runtime System  |  Version:  6.4.1   
Severity:  normal  | Keywords:  
  Os:  Unknown |   Difficulty:  Moderate (1 day)
Architecture:  Unknown |  
---+
This is the result of a discussion between myself and Simon PJ a few weeks
 ago, inspired by recent discoveries of poor performance with mutable
 arrays (eg. see Data.Hash discussion on glasgow-haskell-users around
 October 2005).

 Note that all this applies to mutable arrays of pointers, i.e. `IOArray`
 and `STArray`, ''not'' to unboxed arrays, i.e. `IOUArray` and `STUArray`.

 === Current implementation ===

 There are two primitive types: `MutArray#` and `Array#`. We convert
 between them with:
 {{{
unsafeFreezeArray# :: MutArr# s a -> State# s -> (# State# s, Array# a
 #)
unsafeThawArray# :: Array# a -> State# s -> (# State# s, MutArr# s a #)
 }}}

 An Arr# is not normally on the old-gen mutable list, unless (a) it has
 pointers to young gen objects, or (b) it has been recently frozen.  The
 implementation of `unsafeFreezeArray#` is a single write to the header
 word of the array.  The implementation of `unsafeThawArray#` is slightly
 more complex: if the array was not already on the mutable list (indicated
 by the value of the header), then we add it.  Also, we change the header
 word to indicate that the array is now mutable.

 A `MutArr#` is ''always'' on the mutable list.

 Objects pointed to by Array# are ''eagerly promoted'' to the generation in
 which the Array# resides, with the aim that the Array# can then be removed
 from the mutable list.

 It is only safe to write to a `MutArr#`, so if multiple threads are
 accessing an array, they should ''not'' be doing thaw/freeze tricks
 without extra locking around the array (such behaviour can cause the GC to
 crash).

 === The Problem ===

 The problem is that mutable arrays are always completely traversed on
 every GC.  To get around this, we can keep an array in a frozen state and
 thaw it just before writing, then freeze it again afterward.  This is a
 bit inconvenient, not to mention unsafe with multiple threads unless extra
 locking is used.

 Furthermore, a modified array is ''completely'' scanned, whereas for
 larger arrays it would be much better to just scan the part of the array
 that had been modified (known in the GC literature as "card-marking").

 The benefit of the current approach is that writing to a mutable array is
 a single write instruction, whereas to do card-marking or something else
 requires a write-barrier.  The unsafeThaw/write/unsafeFreeze sequence
 amounts to a write barrier, so if this is a common technique we should
 provide an easy way to do it, possibly making it the default.

 === Solutions ===

 Leaving aside card-marking for now, let's think about incorporating the
 write barrier in the write operation.

 Suppose that mutable arrays are ''always'' kept on the mutable list, but
 the header word indicates whether the array needs to be scanned or not
 (eg. we have `MUT_ARR_DIRTY`, `MUT_ARR_CLEAN`).  The array write op should
 (a) set the header to `MUT_ARR_DIRTY`, and (b) do the write.  The GC turns
 `MUT_ARR_DIRTY` into `MUT_ARR_CLEAN` when everything the array points to
 is in the same generation (or older).

 Downsides to this:

   * intitialising a mutable array, or doing block writes, will be
 more painful, because each write will have the write barrier
 (perhaps not too painful)

 How does freezing/thawing interact with this?  We currently create
 immutable arrays by starting with a `MutArr#`, intitialising it, and then
 freezing it to make an `Arr#`.  We can still do this, exactly as now (and
 with the same thread-unsafety), but initialization will be a bit slower
 due to the write barrier.

 === Block writes ===

 We could try to provide for "block writes", by allowing a thread to "open"
 the array for modification, and then "close" it again after it had
 finished writing, with all writes in between being done without a write
 barrier.  This would replace unsafeThaw/unsafeFreeze.

 To do this safely, we would have to use some kind of synchronisation on
 the open/close; techniques that we came up with were to increment
 (atomically) a counter in the array header, or to allocate a new heap
 object pointing to the array in the current thread's allocation area.

 === Card marking ===

 We could refine the write barrier so that it marks just part of the array
 as dirty, instead of the whole array.  The natural choice is to put the
 mark bit in the block descriptor for the cur