[GHC] #15665: Break up the stable pointer table

[GHC]

#15665: Break up the stable pointer table
-------------------------------------+-------------------------------------
        Reporter:  dfeuer            |                Owner:  (none)
            Type:  feature request   |               Status:  new
        Priority:  normal            |            Milestone:  8.6.1
       Component:  Compiler          |              Version:  8.4.3
      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):

 Currently, a stable pointer table entry consists of a single pointer,
 either into the heap (if it's used) or to the next free entry (if it's
 not). Garbage collection traverses the whole table and distinguishes
 between used and free entries by whether they point into the table or not.
 This leads to a very compact table, but it tightly restricts the
 implementation. If we "uncompress" it, we use ''two'' words per entry: one
 for the payload and one for a next pointer.

 The uncompressed representation offers a lot more flexibility. We can
 immediately drop the array doubling mess. But we get a lot more
 flexibility elsewhere. In particular, we can have ''non-free'' lists, one
 per generation, along with the free list. Now when we collect a
 generation, we traverse only its non-free list, marking objects and moving
 entries to the non-free list for the next generation.

 I ''think'' we can probably even go to a nearly lock-free mechanism, using
 something like a Harris-style lock-free linked list. Here's a rough
 sketch:

 === Make a stable pointer

 Pop an entry from the free list. If the free list is empty, take a lock
 and allocate a new block of entries. Populate the entry appropriately and
 add it to the Gen0 non-free list. Perform one step of maintenance.

 === Delete a stable pointer

 Tag the entry deleted (Harris stage 1 of deletion). Possibly perform one
 step

 === Maintenance

 Traverse all the non-free lists. Physically delete (Harris stage 2) each
 entry tagged as deleted and push it onto the free list.

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