#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