Difference between revisions of "Talk:Parallelism vs. Concurrency"

From HaskellWiki
Jump to: navigation, search
(Initial content)
 
 
(10 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
=== Parallelism vs concurrency: what's the difference? ===
 
=== Parallelism vs concurrency: what's the difference? ===
  
'''''Visible'' side effects.'''
+
'''''Visible'' side effects:'''
  
 
* Have a look at this <del>ugly eysore</del> "prototype definition" of <code>par</code>:
 
* Have a look at this <del>ugly eysore</del> "prototype definition" of <code>par</code>:
Line 8: Line 8:
 
par    :: a -> b -> b
 
par    :: a -> b -> b
 
par x y =  case
 
par x y =  case
             unsafeLocalState (forkIO (evalIO x >> return ()))
+
             unsafeLocalState (forkIO (evaluate x >> return ()))
 
           of
 
           of
 
             !_ -> y
 
             !_ -> y
Line 16: Line 16:
  
 
<haskell>
 
<haskell>
       evalIO :: a -> IO a
+
       evaluate :: a -> IO a
       forkIO :: IO () -> IO ThreadId
+
       forkIO   :: IO () -> IO ThreadId
 
 
 
</haskell>
 
</haskell>
  
 
Assuming:
 
Assuming:
* <code>x</code> is ''well-define'' (it contains no <code>unsafe...</code> calls),
+
* <code>x</code> is ''well-defined'' (it contains no <code>unsafe...</code> calls),
 
* <code>x</code> is ''well-behaved'' (not throwing exceptions or causing errors);
 
* <code>x</code> is ''well-behaved'' (not throwing exceptions or causing errors);
  
Line 28: Line 27:
 
# <code>forkIO</code> attaches a <code>ThreadId</code> to its argument, adds it to the work-queue and returns the identifier;
 
# <code>forkIO</code> attaches a <code>ThreadId</code> to its argument, adds it to the work-queue and returns the identifier;
 
# <code>par</code> then returns <code>y</code>;
 
# <code>par</code> then returns <code>y</code>;
# Some time later, <code>forkIO</code>'s argument is called, causing <code>evalIO</code> to start evaluating <code>x</code>.
+
# Some time later, <code>forkIO</code>'s argument is called, causing <code>evaluate</code> to start evaluating <code>x</code>.
  
If <code>y</code> is still being evaluated when the evaluation of <code>x</code> commences, then we have elementary parallelism: concurrency, but with no visible side-effects.
+
If <code>y</code> is still being evaluated when the evaluation of <code>x</code> commences, then we have concurrency, but with no visible side-effects - it behaves like elementary parallelism.
 
|}
 
|}
  
* Now have a look at this <del>equally-as-ugly</del> prototype definition for <del><code>spawnIO</code></del> <code>forkIO</code>:
+
* Now have a look at this <del>nearly-as-ugly</del> prototype definition for <del><code>spawnIO</code></del> <code>forkIO</code>:
 
:{|
 
:{|
 
|<haskell>
 
|<haskell>
 
forkIO    :: IO () -> IO ThreadId
 
forkIO    :: IO () -> IO ThreadId
forkIO act =  do let t = unsafeLocalState act
+
forkIO act =  do t <- unsafeInterleaveIO act
                 case par t () of
+
                 case attachThreadId t of
                   !_ -> do i' <- itsThreadId t
+
                   Nothing -> itsThreadId t
                            case i' of
+
                  Just i  -> par t (return i)
                              Just i  -> return i
 
                              Nothing -> ioError "forkIO"
 
 
</haskell>
 
</haskell>
  
Line 48: Line 45:
  
 
<haskell>
 
<haskell>
       itsThreadId :: a -> IO (Maybe ThreadId)
+
       attachThreadId :: a -> IO (Maybe ThreadId)
 +
      itsThreadId :: a -> IO ThreadId
 
</haskell>
 
</haskell>
  
 
Assuming:
 
Assuming:
* <code>par</code> is primitive,
+
* <code>par</code>, <code>attachThreadId</code> and <code>itsThreadId</code> are primitive,
* <code>itsThreadId</code> would return <code>Nothing</code> if it's argument had not been previously used by <code>par</code>;
+
* <code>attachThreadId</code> would return <code>Nothing</code> if it's argument already has been assigned a <code>ThreadId</code>;
  
 
then:
 
then:
# Evaluating <code>par t ()</code> causes a new <code>ThreadId</code> to be attached to <code>t</code> by the implementation;
+
# A new <code>ThreadId</code> is assigned to the new (and suspended) value <code>t</code>;
# <code>itsThreadId</code> retrieves <code>i'</code>, the (possible) identifier for <code>t</code>;
+
# evaluating <code>par t i</code> causes <code>t</code> to be added to the work-queue by the implementation;
# <code>forkIO</code> then extracts and returns the identifier.
+
# the <code>ThreadId</code> for <code>t</code> is then returned;
 +
# Some time later, the implementation discovers that a <code>ThreadId</code> has been attached to <code>t</code> and uses the <code>ThreadId</code> to immediately start a new thread for evaluating <code>t</code>;
 +
 
 +
This is parallelism, but having visible side effects - it behaves like elementary concurrency.
 
|}
 
|}
  
Can either of these prototypes ever go mainstream?
+
Can either prototype definition potentially go mainstream?
* As shown by it's type signature, <code>par</code> is supposed to be pure: avoiding the use of <code>unsafeLocalState</code> means making it primitive;
+
* As shown by it's type signature, <code>par</code> is meant to have no visible effects: avoiding the use of <code>unsafeLocalState</code> means making it primitive;
* Considering it's already <code>IO</code>-based, <code>forkIO</code> without <code>unsafeLocalState</code> seems more likely.
+
* While the use of <code>unsafeInterleaveIO</code> may annoy some, it being one of the earlier Haskell extensions means it's widely available.
 +
 
 +
For now, using a primitive <code>par</code> (and others) to define <code>forkIO</code> looks like the simplest option...but if using <code>unsafeInterleaveIO</code> ''really does'' annoy you, how about [[IO in action|this]]:
  
[[IO, partible-style|This]] looks interesting:
+
:<haskell>
<haskell>
+
forkIO      :: (OI -> ()) -> OI -> ThreadId
forkIO      :: (OI -> ()) -> IO -> ThreadId
 
 
forkIO act u =  let !(u1:u2:u3:_) = parts u in
 
forkIO act u =  let !(u1:u2:u3:_) = parts u in
 
                 let t            = act u1 in
 
                 let t            = act u1 in
                 case par t () of
+
                 case attachThreadId t u2 of
                   !_ -> case itsThreadId t u2 of
+
                   Nothing -> itsThreadId t u3
                          Just i  -> i
+
                  Just i  -> par t i
                          Nothing -> ioError "forkIO" u3
 
 
</haskell>
 
</haskell>
  
 
-- [[User:Atravers|Atravers]] Tue Apr 20 06:04:10 UTC 2021
 
-- [[User:Atravers|Atravers]] Tue Apr 20 06:04:10 UTC 2021
 
----
 
----

Latest revision as of 21:29, 14 June 2022

Parallelism vs concurrency: what's the difference?

Visible side effects:

  • Have a look at this ugly eysore "prototype definition" of par:
par     :: a -> b -> b
par x y =  case
             unsafeLocalState (forkIO (evaluate x >> return ()))
           of
             !_ -> y

where:

      evaluate :: a -> IO a
      forkIO   :: IO () -> IO ThreadId

Assuming:

  • x is well-defined (it contains no unsafe... calls),
  • x is well-behaved (not throwing exceptions or causing errors);

then:

  1. forkIO attaches a ThreadId to its argument, adds it to the work-queue and returns the identifier;
  2. par then returns y;
  3. Some time later, forkIO's argument is called, causing evaluate to start evaluating x.

If y is still being evaluated when the evaluation of x commences, then we have concurrency, but with no visible side-effects - it behaves like elementary parallelism.

  • Now have a look at this nearly-as-ugly prototype definition for spawnIO forkIO:
forkIO     :: IO () -> IO ThreadId
forkIO act =  do t <- unsafeInterleaveIO act
                 case attachThreadId t of
                   Nothing -> itsThreadId t
                   Just i  -> par t (return i)

where:

      attachThreadId :: a -> IO (Maybe ThreadId)
      itsThreadId :: a -> IO ThreadId

Assuming:

  • par, attachThreadId and itsThreadId are primitive,
  • attachThreadId would return Nothing if it's argument already has been assigned a ThreadId;

then:

  1. A new ThreadId is assigned to the new (and suspended) value t;
  2. evaluating par t i causes t to be added to the work-queue by the implementation;
  3. the ThreadId for t is then returned;
  4. Some time later, the implementation discovers that a ThreadId has been attached to t and uses the ThreadId to immediately start a new thread for evaluating t;

This is parallelism, but having visible side effects - it behaves like elementary concurrency.

Can either prototype definition potentially go mainstream?

  • As shown by it's type signature, par is meant to have no visible effects: avoiding the use of unsafeLocalState means making it primitive;
  • While the use of unsafeInterleaveIO may annoy some, it being one of the earlier Haskell extensions means it's widely available.

For now, using a primitive par (and others) to define forkIO looks like the simplest option...but if using unsafeInterleaveIO really does annoy you, how about this:

forkIO       :: (OI -> ()) -> OI -> ThreadId
forkIO act u =  let !(u1:u2:u3:_) = parts u in
                let t             = act u1 in
                case attachThreadId t u2 of
                  Nothing -> itsThreadId t u3
                  Just i  -> par t i

-- Atravers Tue Apr 20 06:04:10 UTC 2021