#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): Well, I guess that's used to compress the free list, but is it really worth it? We could either uncompress the free list or untag stored pointers, I imagine. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/15665#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#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

#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): Right. Each allocation would be a full block, and would add all the entries in the block to the free list. Trying to go lock-free looks more complicated the more I think about it, but generational collection looks easy. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/15665#comment:5 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#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): One challenge is that the active entry list for a generation could jump all over the heap, making major GC more expensive than it is now when the table is well populated. Is there a sufficiently cheap way to ameliorate this? I believe there is. The trick is to have one active entry list per generation in each block, and an active block list in each generation. So now GC for a generation will always finish one block before it moves to the next, which I imagine should be much easier on the caches. We just need to reserve room for as many pointers in each block as there are GC generations, which doesn't look like too high a price to me. Can we improve concurrency, which was really what got me started thinking about this machine? I don't really know. The easiest thing would be to divide everything strictly among the capabilities. Each capability would have its own free list and its own active lists. Each block would be owned by just one capability. Only that capability would be permitted to allocate stable pointers in that block, though others could mark pointers for deletion. The trouble with that rigidity is that one capability could have loads of entries on its free list while another is flat broke and forced to allocate fresh blocks (for example, a heavy `StablePtr` allocator could migrate from one capability to another). Is there some sufficiently cheap way to tax the rich to feed the poor without too much bureaucracy? I don't see any, but I'm surely no expert. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/15665#comment:7 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#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

#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): Deletion marking in the doubly linked regime: 1. Set the key pointer to the head of the maintenance list for this block. The garbage collector can realize this as within-block and thus not a heap pointer. 2. Use CAS to set the head of the maintenance list. On failure, go back to 1. If the thread marking deletion pauses between these steps, then a concurrent maintenance pass may fail to delete the entry. That's okay; it'll be cleaned up on the next pass. Even if the thread fails altogether, that just means the entry can never be reused. Note: the maintenance routine doesn't risk ABA problems because it's the only one popping. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/15665#comment:11 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler