[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 had more thoughts/details on garbage collection in the no-stable-
 name-table option.

 I don't think we actually need to store an underlying object pointer in an
 SNO at all. After running the collector (before compacting), traverse the
 keys and SNOs in the SN hash table to form the new one. If the key is
 dead, do nothing. If the SNO is dead, do nothing. If both have been
 evacuated, insert the new key and new SNO into the hash table for the next
 generation.

 The main remaining problem looks unfortunate, and has to do with
 `hashStableName#`. While that has never been documented as being
 injective, it actually ''is'' injective under certain circumstances, and
 indeed it appears that real code on Hackage relies on this (see, e.g.,
 [http://hackage.haskell.org/package/stable-maps-0.0.5/docs/System-Mem-
 StableName-Map.html stable-maps]). In particular, the way it works now, we
 can implement a stable name map as `IntMap (StableName k, v)`. Because the
 map keeps the `StableName`s alive, their stable name table indices won't
 be reused. The only way to keep such code working is to make such a
 guarantee. That ''requires'' a way to allocate IDs uniquely. So we need a
 data structure that can keep track of which IDs are available and allocate
 them. Ugh.

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