GitLab

Summary

As I queue up additional forkOn tasks, the performance seems to become O(n^2) in the number of times I call forkOn.

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 duration/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:

N	Time (seconds)
1000	0.01
2000	0.03
3000	0.07
4000	0.15
5000	0.20
6000	0.34
7000	0.44
8000	0.71
9000	0.80
10000	1.35
11000	1.53
12000	2.51
13000	2.87
14000	4.03
15000	5.61
16000	7.36
17000	9.62
18000	9.91
19000	12.16
20000	11.40

Expected behavior

I'd expect it to be O(n) or O(n log n).

Environment

• GHC version used: 8.10.1.

Optional:

• Operating System: Windows
• System Architecture: 64bit