Validation of STM transactions by the scheduler causes large overhead. Potentially preventing progress.
## Summary
The scheduler performing validation of STM transactions in every scheduler loop might lead to scheduler time dominating a programs runtime.
## Details
When a thread returns to the scheduler we call `schedulePostRunThread` which will validate active transactions through `stmValidateNestOfTransactions`. `stmValidateNestOfTransactions` itself will call `validate_and_acquire_ownership` on the current transaction, and all the transactions that enclose it with the options `acquire_all: true` and `retain_ownership` false.
`validate_and_acquire_ownership` will then walk over all the tvars in the transaction log, lock them and check their expected values against their actual ones. If any don't pass the check we ultimately condemn the whole transaction. So far so good. In this case this will never happens as we only perform reads.
This is already bad with just one capability:
* As the number as TVars increases performance of each read slows down, resulting in fewer reads per second. (See https://gitlab.haskell.org/ghc/ghc/-/issues/24410)
* As read performance decreases we return to the scheduler more frequently relative to the progress made by the transaction because of context switches. Each time we return to the scheduler we pay the full cost of `validate_and_acquire_ownership` which *also* scales with the number of TVars in the transaction.
But especially with multiple capabilities this get's worse:
* Each thread will perform the `validate_and_acquire_ownership` check whenever the thread returns to the scheduler. This means scheduling will take longer.
* As we spend more time in the scheduler code, less time is spent on productive work in between context switches. This means we end up using more cycles on overhead per unit of work.
* In the worst case most of the runtime is spent doing validation of transactions, with little time spent doing productive work that progresses the transactions.
* If two threads perform validation in parallel they might also run into https://gitlab.haskell.org/ghc/ghc/-/issues/24446 preventing either thread to progress.
---
Some napkin math:
In the example I'm looking at we deal with 100k tvars. According to "Evaluating the Cost of Atomic Operations on Modern Architectures" a cas takes on the order of 10-100ns.
Near the end during each context switch we will perform 400k cas operations. As both threads will perform one cas each to lock and unlock each tvar.
If we assume 50ns for each cas this means a full context switch, just from the cost of the cas, will take somewhere around 20ms. By default our context switch frequency is also 20ms.
I think it's plausible that we run into situations where we get:
* x: Mutator is runnings
* x+0ms: Ticker triggers context switch:
* x+0-19ms: Scheduler is running `validate_and_acquire_ownership`
* x+19-20ms: Mutator runs - we perform a handful of reads
* x+20ms: Ticker triggers another context switch.
This would repeat until eventually the runtime of the scheduler crosses 20ms, so we would "lose" one context switch, and the mutator would get a full 20ms slice to perform reads. But before we get there we might spend a long time during which 95%+ of the time is spent on scheduler overhead.
However it's hard to confirm this, as any kind of instrumentation causes enough overhead to majorly distorts this pattern. And https://gitlab.haskell.org/ghc/ghc/-/issues/24446 also affects this.
## Steps to reproduce
So far I investigated this using this as reproducer:
```haskell
{-# LANGUAGE NumericUnderscores #-}
{-# LANGUAGE ScopedTypeVariables #-}
module Main where
import Control.Concurrent (ThreadId, myThreadId, forkIO)
import Control.Concurrent.STM (STM, atomically, newTVar, readTVar, TVar(..))
import Data.IORef (IORef, modifyIORef', newIORef, readIORef)
import GHC.IO (unsafePerformIO)
import System.IO (hFlush, stdout)
import Data.Time.Clock
import Control.Concurrent.MVar
import Control.Monad
main = do
let nums = [
10_000 :: Int
-- ,50_000
,100_000
-- ,150_000
-- ,200_000
-- ,300_000
-- ,400_000
]
forM_ nums $ \tvar_count -> do
print $ "Measuring: " ++ show tvar_count
(tvars :: [TVar Int]) <- atomically $ mapM (newTVar) [1 .. tvar_count]
putStrLn "Created TVars"
start_time <- getCurrentTime
s1 <- runAsync $ atomically $ do
readTList tvars
s2 <- runAsync $ atomically $ do
readTList tvars
s1 <- takeMVar s1
s2 <- takeMVar s2
print $ "done, " ++ show (s1,s2)
done_time <- getCurrentTime
print $ done_time `diffUTCTime` start_time
runAsync :: (IO a) -> IO (MVar a)
runAsync act = do
mvar <- newEmptyMVar
_tid <- forkIO $ do
r <- act
putMVar mvar r
return mvar
readTList tvars = do
values <- mapM readTVar tvars :: STM [Int]
!s <- return $! sum values
return $! s
```
## Expected behavior
Scheduling performance should not be significantly affected by the number of tvars involved in transactions.
## Environment
* GHC version used:
Optional:
* Operating System:
* System Architecture:
issue