forkOn is O(n^2)
As I queue up additional
forkOn tasks, the performance seems to become O(n^2) in the number of times I call
Steps to reproduce
GHC 8.10.1 on Windows. Given the program:
import System.Time.Extra import Control.Concurrent import Control.Monad import Data.IORef import System.Environment main :: IO () main = do [x] <- getArgs let n = read x :: Int bar <- newEmptyMVar count <- newIORef (0 :: Int) (d, _) <- duration $ do replicateM_ n $ do forkOn 0 $ do v <- atomicModifyIORef' count $ \old -> (old + 1, old + 1) when (v == n) $ putMVar bar () takeMVar bar putStrLn $ showDuration d
This program uses the
extra library for the
showDuration functions, but those can be replaced by any timing functions you wish, or timing the binary itself.
Compile that program with
ghc --make -O2 Main -threaded and run with
main 10000 +RTS -N4. Vary the value 10000 from 10K to 200K. Observe that the time taken by the program increases quadratically (although with additional variation at the higher numbers). Given runs in 10K steps over that interval, averaging three runs, my times and a graph were:
I'd expect it to be O(n) or O(n log n).
- GHC version used: 8.10.1.
- Operating System: Windows
- System Architecture: 64bit