Concurrency Substrate and Abstract Scheduler Interface in GHC Haskell Code

lightweight concurrency in ghc n.w
1 / 28
Embed
Share

Explore lightweight concurrency, MVars, safe foreign calls, scheduler paradigms, and more in GHC Haskell code. Dive into the advancements in concurrency landscape and substrate, along with the unification of various components for enhanced performance in Haskell code.

  • Concurrency
  • Haskell Code
  • GHC
  • Lightweight
  • Scheduler
rayaanacharya
kainoagi Follow

Uploaded on | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

Download Presentation

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

E N D

Presentation Transcript

  1. Lightweight Concurrency in GHC KC Sivaramakrishnan Tim Harris Simon Marlow Simon Peyton Jones 1

  2. GHC: Concurrency and Parallelism MVars Safe foreign calls forkIO Bound threads Asynchronous exceptions Par Monad STM 2

  3. Concurrency landscape in GHC Haskell Code RTS (C Code) preemptive, round-robin scheduler + work-sharing STM MVar LWT Safe FFI and more Black Holes Scheduler OS Thread pool Capability N Capability 0

  4. Idea Haskell Code Haskell Code LWT STM+ MVar+ Scheduler+ RTS (C Code) Concurrency Substrate STM MVar LWT Safe FFI and more Black Holes Scheduler RTS (C Code) Safe FFI Black Holes OS Thread pool OS Thread pool Capability N Capability 0 Capability N Capability 0 4

  5. Where do these live in the new design? What should this be? Contributions Haskell Code Haskell Code LWT STM+ MVar+ Scheduler+ RTS (C Code) Concurrency Substrate STM MVar LWT Safe FFI and more Black Holes Scheduler RTS (C Code) Safe FFI Black Holes OS Thread pool OS Thread pool How to unify these? Capability N Capability 0 Capability N Capability 0 5

  6. Concurrency Substrate One-shot continuations (SCont) and primitive transactional memory (PTM) PTM is a bare-bones TM Better composability than CAS ---------------- PTM ---------------- data PTM a data PVar a instance Monad PTM atomically :: PTM a -> IO a newPVar :: a -> PTM (PVar a) readPVar :: PVar a -> PTM a writePVar :: PVar a -> a -> PTM () ---------------- SCont -------------- data SCont -- Stack Continuations newSCont :: IO () -> IO SCont switch :: (SCont -> PTM SCont) -> IO () getCurrentSCont :: PTM SCont switchTo :: SCont -> PTM () 6

  7. Switch PTM! Current SCont switch :: (SCont -> PTM SCont) -> IO () SCont to switch to 7

  8. Abstract Scheduler Interface Haskell Code LWT STM+ MVar+ Scheduler+ How to unify these? Concurrency Substrate Safe FFI Black Holes Primitive scheduler actions SCont {scheduleSContAction :: SCont -> PTM (), yieldControlAction :: PTM ()} Expected from every user-level thread 8

  9. Primitive Scheduler Actions (1) scheduleSContAction :: SCont -> PTM () scheduleSContAction sc = do sched :: PVar [SCont] <- -- get sched contents :: [SCont] <- readPVar sched writePVar $ contents ++ [sc] yieldControlAction :: PTM () yieldControlAction = do sched :: PVar [SCont] <- -- get sched contents :: [SCont] <- readPVar sched case contents of x:tail -> do { writePVar $ contents tail; switchTo x -- DOES NOT RETURN } otherwise -> 9

  10. Primitive Scheduler Actions (2) scheduleSContAction :: SCont -> PTM () scheduleSContAction sc = do sched :: PVar [SCont] <- -- get sched contents :: [SCont] <- readPVar sched writePVar $ contents ++ [sc] yieldControlAction :: PTM () yieldControlAction = do sched :: PVar [SCont] <- -- get sched contents :: [SCont] <- readPVar sched case contents of x:tail -> do { writePVar $ contents tail; switchTo x -- DOES NOT RETURN } otherwise -> Substrate Primitives getScheduleSContAction :: SCont -> PTM (SCont -> PTM()) setScheduleSContAction :: SCont -> (SCont -> PTM()) -> PTM() getYieldControlAction :: SCont -> PTM (PTM ()) setScheduleSContAction :: SCont -> PTM () -> PTM () 10

  11. Primitive Scheduler Actions (3) scheduleSContAction :: SCont -> PTM () scheduleSContAction sc = do sched :: PVar [SCont] <- -- get sched contents :: [SCont] <- readPVar sched writePVar $ contents ++ [sc] yieldControlAction :: PTM () yieldControlAction = do sched :: PVar [SCont] <- -- get sched contents :: [SCont] <- readPVar sched case contents of x:tail -> do { writePVar $ contents tail; switchTo x -- DOES NOT RETURN } otherwise -> Substrate Primitives getScheduleSContAction :: SCont -> PTM (SCont -> PTM()) setScheduleSContAction :: SCont -> (SCont -> PTM()) -> PTM() getYieldControlAction :: SCont -> PTM (PTM ()) setScheduleSContAction :: SCont -> PTM () -> PTM () getSSA = getScheduleSContAction setSSA = setScheduleScontAction getYCA = getYieldControlAction setYCA = setYieldControlAction Helper functions 11

  12. Building Concurrency Primitives (1) yield :: IO () yield = atomically $ do s :: SCont <- getCurrentSCont -- Add current SCont to scheduler ssa :: (SCont -> PTM ()) <- getSSA s enque :: PTM () <- ssa s enque -- Switch to next scont from scheduler switchToNext :: PTM () <- getYCA s switchToNext 12

  13. Building Concurrency Primitives (2) forkIO :: IO () -> IO SCont forkIO f = do ns <- newSCont f atomically $ do { s :: SCont <- getCurrentSCont; -- Initialize new sconts scheduler actions ssa :: (SCont -> PTM ()) <- getSSA s; setSSA ns ssa; yca :: PTM () <- getYCA s; setYCA ns yca; -- Add to new scont current scheduler enqueAct :: PTM () <- ssa ns; enqueAct } return ns 13

  14. Building MVars newtype MVar a = MVar (PVar (ST a)) data ST a = Full a [(a, PTM())] | Empty [(PVar a, PTM())] An MVar is either empty or full and has a single hole takeMVar :: MVar a -> IO a takeMVar (MVar ref) = do hole <- atomically $ newPVar undefined atomically $ do st <- readPVar ref case st of Empty ts -> do s <- getCurrentSCont ssa :: (SCont -> PTM ()) <- getSSA s wakeup :: PTM () <- ssa s writePVar ref $ v where v = Empty $ ts++[(hole, wakeup)] switchToNext <- getYCA s switchToNext Full x ((x', wakeup :: PTM ()):ts) -> do writePVar hole x writePVar ref $ Full x' ts wakeup otherwise -> atomically $ readPVar hole 14

  15. Building MVars newtype MVar a = MVar (PVar (ST a)) data ST a = Full a [(a, PTM())] | Empty [(PVar a, PTM())] An MVar is either empty or full and has a single hole takeMVar :: MVar a -> IO a takeMVar (MVar ref) = do hole <- atomically $ newPVar undefined atomically $ do st <- readPVar ref case st of Empty ts -> do s <- getCurrentSCont ssa :: (SCont -> PTM ()) <- getSSA s wakeup :: PTM () <- ssa s writePVar ref $ v where v = Empty $ ts++[(hole, wakeup)] switchToNext <- getYCA s switchToNext Full x ((x', wakeup :: PTM ()):ts) -> do writePVar hole x writePVar ref $ Full x' ts wakeup otherwise -> atomically $ readPVar hole Result will be here 15

  16. Building MVars newtype MVar a = MVar (PVar (ST a)) data ST a = Full a [(a, PTM())] | Empty [(PVar a, PTM())] An MVar is either empty or full and has a single hole takeMVar :: MVar a -> IO a takeMVar (MVar ref) = do hole <- atomically $ newPVar undefined atomically $ do st <- readPVar ref case st of Empty ts -> do s <- getCurrentSCont ssa :: (SCont -> PTM ()) <- getSSA s wakeup :: PTM () <- ssa s writePVar ref $ v where v = Empty $ ts++[(hole, wakeup)] switchToNext <- getYCA s switchToNext Full x ((x', wakeup :: PTM ()):ts) -> do writePVar hole x writePVar ref $ Full x' ts wakeup otherwise -> atomically $ readPVar hole Result will be here If the mvar is empty (1) Append hole & wakeup info to mvar list (getSSA!) (2) Yield control to scheduler (getYCA!) 16

  17. Building MVars newtype MVar a = MVar (PVar (ST a)) data ST a = Full a [(a, PTM())] | Empty [(PVar a, PTM())] An MVar is either empty or full and has a single hole takeMVar :: MVar a -> IO a takeMVar (MVar ref) = do hole <- atomically $ newPVar undefined atomically $ do st <- readPVar ref case st of Empty ts -> do s <- getCurrentSCont ssa :: (SCont -> PTM ()) <- getSSA s wakeup :: PTM () <- ssa s writePVar ref $ v where v = Empty $ ts++[(hole, wakeup)] switchToNext <- getYCA s switchToNext Full x ((x', wakeup :: PTM ()):ts) -> do writePVar hole x writePVar ref $ Full x' ts wakeup otherwise -> atomically $ readPVar hole Result will be here If the mvar is empty (1) Append hole & wakeup info to mvar list (getSSA!) (2) Yield control to scheduler (getYCA!) Wake up a pending writer, if any. wakeup is a PTM ()! MVar is scheduler agnostic! 17

  18. Interaction of C RTS and User-level scheduler Many Events that necessitate actions on the scheduler become apparent only in the C part of the RTS Haskell Code LWT STM+ MVar+ Scheduler+ Concurrency Substrate Safe FFI Black Hole Asynchronous exceptions Finalizers 18

  19. Interaction of C RTS and User-level scheduler Many Events that necessitate actions on the scheduler become apparent only in the C part of the RTS Haskell Code LWT STM+ MVar+ Scheduler+ Concurrency Substrate Re-use primitive scheduler actions! Safe FFI Black Hole Asynchronous exceptions Finalizers Pending upcall queue :: [PTM ()] Capability X Upcall Thread UT 19

  20. Blackholes Capability 0 Capability 1 T1 T2 T3 evaluating.. Thunk Running T Suspended T T Blocked 20

  21. Blackholes Capability 0 Capability 1 T1 T2 T3 thunk blackholed BH Running T Suspended T T Blocked 21

  22. Blackholes Capability 0 Capability 1 T1 T2 T3 enters blackhole BH Running T Suspended T T Blocked 22

  23. Blackholes Capability 0 Capability 1 T1 T2 T3 BH Running T Suspended T T Blocked 23

  24. Blackholes Capability 0 Capability 1 T1 T2 T3 Yield control action BH Running T Suspended T T Blocked 24

  25. Blackholes Capability 0 Capability 1 T1 T2 T3 finishes evaluation Schedule SCont action V Running T Suspended T T Blocked 25

  26. Blackholes : The Problem Capability 0 Running T T1 T2 Suspended T Switch $ \T1 -> do -- -- return T2 T Blocked BH 26

  27. Blackholes : The Problem Capability 0 Running T T1 T2 enters blackhole Suspended T Switch $ \T1 -> do -- -- return T2 T Blocked BH In order to make progress, we need to resume to T2 But, in order to resume to T2, we need to resume T2 (Deadlocked!) Can be resolved through runtime system tricks (Work in Progress!) 27

  28. Conclusions Status Mostly implemented (SConts, PTM, Simple schedulers, MVars, Safe FFI, bound threads, asynchronous exceptions, finalizers, etc.) 2X to 3X slower on micro benchmarks (programs only doing synchronization work) To-do Re-implement Control.Concurrent with LWC Formal operational semantics Building real-world programs Open questions Hierarchical schedulers, Thread priority, load balancing, Fairness, etc. STM on top of PTM PTM on top of SpecTM Integration with par/seq, evaluation strategies, etc. and more 28

Related


No related presentations.

More Related Content