[GHC] #15665: Break up the stable pointer table

[GHC]

#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