#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