[GHC] #7670: StablePtrs should be organized by generation for efficient minor collections

[GHC]

#7670: StablePtrs should be organized by generation for efficient minor
collections
-------------------------------------+-------------------------------------
        Reporter:  ezyang            |                Owner:  (none)
            Type:  bug               |               Status:  new
        Priority:  normal            |            Milestone:
       Component:  Runtime System    |              Version:  7.7
      Resolution:                    |             Keywords:
Operating System:  Unknown/Multiple  |         Architecture:
                                     |  Unknown/Multiple
 Type of failure:  None/Unknown      |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by dfeuer):

 I've been thinking about the `StableName#` representation some, and I
 really don't like the redundancy between stable name objects and stable
 name table entries. I can think of two approaches to fixing this: get rid
 of the stable name table or get rid of stable name objects.

 === Get rid of the stable name table

 This is my preferred approach, if it's workable, because it seems almost
 absurdly simple. Suppose we have one counter to generate IDs (the results
 of `hashStableName#`) and one hash table per generation mapping heap
 pointers to stable name objects. A stable name object would look like

 {{{
 StableNameObject:
 Header
 ID  -- for hashStableName#
 Underlying object, treated as a weak reference
 }}}

 `makeStableName#` would check the hash table for the appropriate
 generation to see if there's already a stable name object (SNO). If not,
 it gets a fresh `ID` and builds the SNO.

 Garbage collecting the hash tables, roughly speaking:

 Perform a normal collection, leaving the underlying object pointers
 pointing to from-space. Traverse all the hash table entries in the table
 for the generation currently being collected. For each SNO pointer in the
 table, check the SNO for liveness. If it's alive, get the to-space address
 of its underlying object, edit the SNO accordingly, and insert it into the
 hash table for the next generation. If the underlying object is dead, null
 out that field.

 Is this too simple, or just simple enough? I don't really understand the
 idea of per-capability lists--how do you know which one a particular
 target should be inserted into? But presumably if we did that, we'd
 partition the ID space by high bit to give each capability its own
 counter.

 === Get rid of stable name objects

 1. Change the stable name table to a representation that can grow without
 moving. Guess: an array of arrays, where each array is either empty or
 twice the size of the one to its left.

 2. Add a heap object-style header to each stable name table entry. So each
 entry will look like

 {{{
 SNTableEntry:
 Header
 Index (for hashStableName#)
 Underlying object
 }}}

 Now a `StableName#` becomes a pointer directly into the stable name table.
 The garbage collector can recognize the closure type and handle it
 specially. Note that stable name table entries pointing to old objects
 will always be put in the old-generation stable name table. I don't know
 enough about the garbage collector to say exactly how that should work.
 The free list can probably just run through the headers.

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