Skip to content

GitLab

  • Projects
  • Groups
  • Snippets
  • Help
    • Loading...
  • Help
    • Help
    • Support
    • Community forum
    • Submit feedback
  • Sign in / Register
GHC
GHC
  • Project overview
    • Project overview
    • Details
    • Activity
    • Releases
  • Repository
    • Repository
    • Files
    • Commits
    • Branches
    • Tags
    • Contributors
    • Graph
    • Compare
    • Locked Files
  • Issues 4,391
    • Issues 4,391
    • List
    • Boards
    • Labels
    • Service Desk
    • Milestones
    • Iterations
  • Merge Requests 376
    • Merge Requests 376
  • Requirements
    • Requirements
    • List
  • CI / CD
    • CI / CD
    • Pipelines
    • Jobs
    • Schedules
    • Test Cases
  • Operations
    • Operations
    • Incidents
    • Environments
  • Analytics
    • Analytics
    • CI / CD
    • Code Review
    • Insights
    • Issue
    • Repository
    • Value Stream
  • Wiki
    • Wiki
  • Snippets
    • Snippets
  • Members
    • Members
  • Activity
  • Graph
  • Create a new issue
  • Jobs
  • Commits
  • Issue Boards
Collapse sidebar
  • Glasgow Haskell Compiler
  • GHCGHC
  • Issues
  • #18221

Closed
Open
Opened May 23, 2020 by Neil Mitchell@ndmitchellReporter

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

image

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
Assignee
Assign to
None
Milestone
None
Assign milestone
Time tracking
None
Due date
None
Reference: ghc/ghc#18221