#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: #7670 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by dfeuer): How can we use entries as efficiently as possible? When allocating, we are always better off allocating into a block with a non-empty free list if we have one. But which one should we pick? If we pick one with a long free list, then we'll be able to stick with it for a while before we have to pick another, which should make allocation efficient. On the flip side, we may want to slowly concentrate live entries to be able to offer blocks to other threads. I don't feel like I have a clue how to manage that balance as yet. How should we focus our maintenance work? I'm not really sure. The simplest thing seems to be to just go through all the blocks in the order they were added and then go back to the beginning. We should probably keep "deletion pending" counts (updated with FAA) per block to avoid traversing blocks with very little maintenance work available--I believe setting the right threshold there should improve the worst-case block allocation behavior. Speaking of worst-case block allocation behavior.... Doing maintenance work (deleting marked-deleted blocks) only on stable pointer allocation and GC) seems to be pretty important for controlling complexity if we want to avoid licking. But it can cause trouble for certain patterns of allocation and deallocation. A thread could use up all its capacity, so all its free lists are empty, then delete almost all its stable pointers, leaving its free lists still empty. Allocating a new stable pointer could naively allocate a fresh block, which would be most unfortunate. We might want to find a block with lots of pending deletions, perform them all, and then continue. But maintaining a lock-free priority queue of blocks with lots of pending deletions sounds too hard. Hrm... Perhaps we can detect this situation with a global counter and use the garbage collector to clean it up? Not so pretty, but maybe. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/15665#comment:9 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler