larskuhtz
commented
9 years ago Simon Marlow describes an implementation of TQueue that avoids forcing the writer list reversal in the STM transaction by placing the pattern match on the head of the reversed list into a let binding. This way accessing the result of readTQueue still takes O(n) but since it is lazy the transaction itself only takes O(1) and thus can compete with the other queue operations in particular with writeTQueue.
The current implementation is considered a bug in stm.
Until a fix for this bug is available in a released version of stm we shall use a different queue implementation, for instance based on TChan or Chan. Also we should consider using a queue that is fair between the writers.
We may also consider using a queue with a better non-amortized worst case behavior. But for most usage scenarios the overhead of the list reversal seems acceptable as long as it doesn't influence scheduling negatively.
Standard functional queue implementations (such as
TQueueand its derivatives) with amortized constant read complexity are problematic in conjunction withSTM. Those queues are based on two lists, a read and a write list. When read list becomes empty the reader swaps both lists and reverses read list, which is the former write list. Even though the overhead of this operation is amortized over all read operations, the worst case complexity of individual read operations varies betweenO(1)andO(n)in the queue size while write operations are alwaysO(1).The concurrency model of
STMdoesn't guarantee fair scheduling. Instead concurrent threads race for shared resources and the first to commit a transaction wins while the other threads rollback their transactions and retry. For the considered queues this means that if there are frequent writes and the write list grows up to a certain critical size it is possible that the reader never succeeds to commit a read operation that involves a swap (and thus reversal) of the list. Instead the reader retries either forever or, in case of aTBQueue, until the queue is full in which case the writer retries.Even in cases where the reader manages to recover, it can still happen that a single read operation takes several orders of magnitude longer to finish than normal or than a write operation with much increased CPU load (due to continued retries of the expensive list reversal).
In tests we observed read operations that took over 20s with 80% CPU load compared to <1ms and <5% CPU load for "normal" reads. We were also able to trigger scenarios where the read would never return and >80% CPU load.