#9539: TQueue can lead to thread starvation -------------------------------------+------------------------------------- Reporter: jwlato | Owner: ekmett Type: bug | Status: new Priority: normal | Milestone: Component: Core Libraries | Version: 7.8.2 Resolution: | Keywords: stm Operating System: Unknown/Multiple | Architecture: Type of failure: None/Unknown | Unknown/Multiple Blocked By: | Test Case: Related Tickets: | Blocking: | Differential Revisions: -------------------------------------+------------------------------------- Changes (by jonsterling): * cc: core-libraries-committee@… (added) Comment: We (PivotCloud) are running up against this problem currently (it is causing live-locking in our production code) and are curious if a patch would be accepted to make the change described in the ticket (i.e. change the case statement to a let binding). Incidentally, in Simon Marlowe's book, he explicitly mentions that one should use a lazy let here instead of a case statement, but somehow this did not make it into the actual implementation of TQueue. See http://chimera.labs.oreilly.com/books/1230000000929/ch10.html#CO37-2 Also, I don't know how releases for STM work---is it plausible that we could fix this quickly and get out a new version of STM, or would a better path forward for our immediate need be to just make a custom (copy-and- paste) version of TQueue with this fix? We are happy to submit a patch in either case. Thanks! Jon Sterling & Lars Kuhtz PivotCloud Inc -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9539#comment:2 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9539: TQueue can lead to thread starvation -------------------------------------+------------------------------------- Reporter: jwlato | Owner: ekmett Type: bug | Status: new Priority: normal | Milestone: Component: Core Libraries | Version: 7.8.2 Resolution: | Keywords: stm Operating System: Unknown/Multiple | Architecture: Type of failure: None/Unknown | Unknown/Multiple Blocked By: | Test Case: Related Tickets: | Blocking: | Differential Revisions: -------------------------------------+------------------------------------- Comment (by simonpj): * I'm all for fixing bugs in the STM library -- thank you! * Simon M is the expert. * I think the Core Libraries Committee makes the decision. * In any patch, ''please'' comment the relevant point carefully, referring to this ticket, so that no one changes it back! Simon -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9539#comment:4 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9539: TQueue can lead to thread starvation -------------------------------------+------------------------------------- Reporter: jwlato | Owner: ekmett Type: bug | Status: new Priority: normal | Milestone: Component: Core Libraries | Version: 7.8.2 Resolution: | Keywords: stm Operating System: Unknown/Multiple | Architecture: Type of failure: None/Unknown | Unknown/Multiple Blocked By: | Test Case: Related Tickets: | Blocking: | Differential Revisions: -------------------------------------+------------------------------------- Comment (by jonsterling): Is there any update on this ticket? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9539#comment:6 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9539: TQueue can lead to thread starvation -------------------------------------+------------------------------------- Reporter: jwlato | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: Core Libraries | Version: 7.8.2 Resolution: | Keywords: stm Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by arybczak): * Attachment "0001-Make-definition-of-readTQueue-consistent-with- readTB.patch" added. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9539 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9539: TQueue can lead to thread starvation -------------------------------------+------------------------------------- Reporter: jwlato | Owner: (none) Type: bug | Status: closed Priority: normal | Milestone: Component: Core Libraries | Version: 7.8.2 Resolution: fixed | Keywords: stm Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by simonmar): * status: patch => closed * resolution: => fixed Comment: Looks like this was applied. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9539#comment:10 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9539: TQueue can lead to thread starvation -------------------------------------+------------------------------------- Reporter: jwlato | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: Core Libraries | Version: 7.8.2 Resolution: | Keywords: stm Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by dfeuer): * status: closed => new * resolution: fixed => Comment: I'm 90% confident this is not actually fixed. We now get good results from `atomically $ do {...; readTQueue q}`. Unfortunately, I believe the exact same problem will still occur as soon as we go a little further, with `atomically $ do {... ; !x <- readTQueue q; return x}`. I believe the only true solution is to base `TQueue` on a real-time queue rather than an amortized one. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9539#comment:12 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9539: TQueue can lead to thread starvation -------------------------------------+------------------------------------- Reporter: jwlato | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: Core Libraries | Version: 7.8.2 Resolution: | Keywords: stm 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): Working through this some more, I think we need 1. A real-time queue, to prevent the starvation problem 2. That allows `N` reads or writes to occur without contention. The simple scheduled real-time queue Okasaki describes won't do the trick, because both reads and writes inspect and modify the schedule each time. We need something a bit more flexible. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9539#comment:14 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9539: TQueue can lead to thread starvation -------------------------------------+------------------------------------- Reporter: jwlato | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: Core Libraries | Version: 7.8.2 Resolution: | Keywords: stm 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): Sorry to be thinking out loud so long... I suspect the trick is for the read end and the write end to each have an ''estimate'' of the queue balance. Start with the usual Okasaki concept: {{{#!hs data PlainQueue a = PlainQueue !(TVar Int) !(TVar [a]) !(TVar [a]) }}} where the `Int` is the difference in length between the front list (read end) and the rear list. We would rotate the queue when that counter goes to -1. But the `TVar Int` is a contention point. So let's try this: {{{#!hs data End a = End !Int [a] data Queue a = Queue { prev_len :: !(TVar Int) , front :: !(TVar (End a)) , rear :: !(TVar (End a))} }}} When the queue is rotated, the `prev_len` counter is set to the length of the queue. The front of the queue holds a count of how many items have been ''removed'' (read) since the last rotation, while the rear holds a count of how many items have been ''added''. When we've added half as many items as we had at the last rotation, or we've removed half as many as we had at the last rotation, we rotate the queue. (Ratios subject to further analysis). The idea is that we can be sure that the balance factor will be in a fixed range when we rotate, even though neither end can see the other. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9539#comment:16 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9539: TQueue can lead to thread starvation -------------------------------------+------------------------------------- Reporter: jwlato | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: Core Libraries | Version: 7.8.2 Resolution: | Keywords: stm 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 YitzGale): Here is an alternative safer proposal: We retain the well-understood behavior and performance of the classic functional queue. But we ensure that the amortized cost of the occasional reverse is shared fairly by the read and write ends of the queue. We do that by placing a singleton buffer in the middle, between the read and write buffers. Whoever first finds the middle buffer unavailable pays the price that time. Here is a simplistic initial implementation: {{{#!hs data TQueue a = TQueue !(TVar [a]) !(TMVar a) !(TVar [a]) readTQueue :: TQueue a -> STM a readTQueue (TQueue read middle write) = readTVar read >>= \case x:xs -> pure x <* writeTVar read xs _ -> takeTMVar middle `orElse` (readTVar write >>= \case [] -> retry ys -> do writeTVar write [] let z:zs = reverse ys pure z <* writeTVar read zs ) writeTQueue :: TQueue a -> a -> STM () writeTQueue (TQueue read middle write) x = (do putTMVar middle x readTVar write >>= \case [] -> pure () ys -> do -- read must be empty in this case. -- strict reverse to ensure we pay the amortization price -- here and not in a read operation. writeTVar read $! reverse ys writeTVar write [] ) `orElse` modifyTVar' write (x :) }}} The above code depends on the invariant that if the write buffer is non- empty and the middle is empty, then the read buffer is empty. We can observe that this is true because a read operation will only empty the middle if there is no data left in the read buffer, and once that happens the read buffer will remain empty until the next time that the write buffer is emptied. But the type does not enforce that invariant. Here is a safer implementation with a type which cannot represent the impossible state, but requires a few more cheap TVar operations: {{{#!hs newtype TQueue a = TQueue (TVar (TQueue' a)) data TQueue' a = TQueueR !(TVar [a]) -- middle and write are empty | TQueueW !(TVar (NonEmpty a)) -- read and middle are empty | TQueueM !(TVar [a]) !(TVar a) !(TVar [a]) -- middle is non-empty readTQueue :: TQueue a -> STM a readTQueue (TQueue tvq) = readTVar tvq >>= \case TQueueR tvr -> readTVar tvr >>= \case x:xs' -> pure x <* writeTVar tvr xs' _ -> retry TQueueW tvw -> do ys <- readTVar tvw let z :| zs = NE.reverse ys pure z <* (newTVar zs >>= writeTVar tvq . TQueueR) TQueueM tvr tvm tvw -> readTVar tvr >>= \case x:xs' -> pure x <* writeTVar tvr xs' _ -> readTVar tvm <* (readTVar tvw >>= \case y : ys -> newTVar (y :| ys) >>= writeTVar tvq . TQueueW _ -> writeTVar tvq (TQueueR tvr) -- empty ) writeTQueue :: TQueue a -> a -> STM () writeTQueue (TQueue tvq) x = readTVar tvq >>= \case TQueueR tvr -> do tvm <- newTVar x tvw <- newTVar [] writeTVar tvq (TQueueM tvr tvm tvw) TQueueW tvw -> do ys <- readTVar tvw -- strict reverse to ensure we pay the amortization price -- here and not in a read operation. tvr <- newTVar $! (reverse $ NE.toList ys) tvm <- newTVar x tvw' <- newTVar [] writeTVar tvq (TQueueM tvr tvm tvw') TQueueM _ _ tvw -> modifyTVar' tvw (x :) }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9539#comment:18 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9539: TQueue can lead to thread starvation -------------------------------------+------------------------------------- Reporter: jwlato | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: Core Libraries | Version: 7.8.2 Resolution: | Keywords: stm 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): Yitz, I ''suspect'' my approach will be somewhat more robust than yours. Both should prevent writers from overwhelming readers, but mine should (I believe) also prevent the queue from freezing up altogether as a result of contention over unrelated `TVar`s. The real-time versions (see especially `RTTQueue1`) make this really simple; there's never a giant blob of queue maintenance work for ''any'' thread. The amortized version helps more subtly, by ensuring that queue maintenance work is "saved" across transaction failures through the power of thunk update. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9539#comment:20 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

Replying to [comment:12 dfeuer]:

...

I'm 90% confident this is not actually fixed. We now get good results from `atomically $ do {...; readTQueue q}`. Unfortunately, I believe the exact same problem will still occur as soon as we go a little further, with `atomically $ do {... ; !x <- readTQueue q; return x}`. I believe the only true solution is to base `TQueue` on a real-time queue rather than an amortized one.

The original fix is straightforward, maybe we should add some documents to stop people from explicit forcing the list reverse during transaction? The point is that after transaction finished, forcing thunk will only bring contention on blackhole, which will not stop consumer from making

#9539: TQueue can lead to thread starvation -------------------------------------+------------------------------------- Reporter: jwlato | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: Core Libraries | Version: 7.8.2 Resolution: | Keywords: stm 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): Replying to [comment:21 winter]: progress, thus solving the original issue perfectly.

In fact, the basic requirement for using `TQueue` is that you should

have fast enough consumers, with this requirement met, as long as we give consumers chances to do the `reverse`, the list will not accumulate and each blackholing should be short. The original "fix" only works if 1. The value pulled from the queue isn't needed to finish the transaction, and 2. The thread only needs to pull one value from the queue. So it fixes the problem ''in its original context'', but not in any larger settings. Since the whole point of STM is to be "compositional", I don't think this can honestly be called a fix. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9539#comment:22 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9539: TQueue can lead to thread starvation -------------------------------------+------------------------------------- Reporter: jwlato | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: Core Libraries | Version: 7.8.2 Resolution: | Keywords: stm 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 WrenThornton): While not necessarily a solution to the problems with `TQueue` itself, users running into issues with overactive writers can always use stm- chans's `TBMQueue` which is a bounded (and closable) variant of `TQueue` which has already been vetted by various folks. (Though of course if folks find infelicities with the current implementation, I'm always open to receive patches and bugreports.) On the whole, from my experience in this domain, it's too much to expect a single implementation to satisfy all users' needs. Things like realtime queues certainly have their place, as do bare-bones queues, and explicitly bounded queues, as do queues where popping is forever and the element gets dropped on the floor in the event of transaction rollback, and so on. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9539#comment:24 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler