forkOn is O(n^2)
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