[GHC] #15642: Improve the worst case performance of weak pointers

[GHC]

#15642: Improve the worst case performance of weak pointers
-------------------------------------+-------------------------------------
           Reporter:  dfeuer         |             Owner:  (none)
               Type:  feature        |            Status:  new
  request                            |
           Priority:  normal         |         Milestone:  8.8.1
          Component:  Runtime        |           Version:  8.6.1-beta1
  System                             |
           Keywords:                 |  Operating System:  Unknown/Multiple
       Architecture:                 |   Type of failure:  Runtime
  Unknown/Multiple                   |  performance bug
          Test Case:                 |        Blocked By:
           Blocking:                 |   Related Tickets:
Differential Rev(s):                 |         Wiki Page:
-------------------------------------+-------------------------------------
 Garbage collecting weak pointers involves repeatedly traversing the weak
 pointer list, checking which keys are still alive, and in response marking
 the relevant values and finalizers live. This works well in most cases,
 but if there are long chains of weak pointers, it's terrible. I wonder if
 we can do something about that without significantly hurting performance
 elsewhere. Here's the (probably naive) idea:

 1. Maintain a hash table mapping weak pointer keys to lists of weak
 pointers. This replaces the current weak pointer list.

 2. Use a bit in the info table pointer of every heap object to indicate
 whether that object is referenced from any `Weak#`. This is the weakest
 link: if we don't have a spare bit there, or don't want to use one, then I
 think this whole idea is sunk.

 When creating a weak pointer, set the appropriate bit in the key and
 insert the key and pointer into the hash table. When performing early
 finalization, clear the bit in the key if no other `Weak#` points to it.

 When performing garbage collection: check the bit in each object as it is
 marked. If the bit is set, move the key and its attached `Weak#`s from the
 hash table into a new hash table (or an association list that gets turned
 into a hash table after evacuation or whatever), and mark all the linked
 weak pointer targets and finalizers live. In the end, the old hash table
 contains only unreachable objects. Now mark those objects live (for
 finalization and in case of resurrection), and queue up the finalizers.

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