5 ms·

tl;dr Parallelism implies concurrency but concurrency doesn't imply parallelism.

jules 14y ago
It's a bit more nuanced than that. Concurrency implies non determinism. For example if you have multiple threads then the result of the program is non deterministic: it may depend on the particular interleaving of the threads over time. Parallelism is about executing multiple things at the same time to improve performance. You can have parallelism without concurrency. For example a parallel map operation is parallel, but not non deterministic. It always gives the same result. Now, under the hood to implement parallel map, there is probably some concurrency involved, but that is not exposed in the interface of map. You can have concurrency without multiple threads, for example Node with asynchronous callbacks is concurrent, because the order in which those callbacks get called is non deterministic. But it does not necessarily need to run on multiple threads. Usually we don't want the end result of our program to be non deterministic, so we use synchronization primitives like locks and Go's channels to limit the non determinism in such a way that it does not affect the end result. What most people don't realize is that for concurrency to be useful, there must be parallelism. But wait, didn't I just say that in Node you have concurrency without multiple threads? Yes, but the parallelism does not need to be in your CPU! If you do an asynchronous disk read, or an asynchronous network request, the disk and other computers on your network are working in parallel with your program. Concurrency allows us to exploit that parallelism, so that the CPU can do useful work while the disk is busy reading our data. Now, you can write your program with concurrency, but if there is no parallelism anywhere in the system, that's not useful. So in practice it is the reverse: concurrency implies parallelism (but not necessarily on the CPU), but parallelism does not imply visible concurrency (though it might be hidden under the hood of a parallel construct like parallel map).
- mseepgood 14y ago
  > What most people don't realize is that for concurrency to be useful, there must be parallelism. No, as far as I understand from this and other talks, Rob Pike argues that concurrency is useful even without parallelism: it's a better way to structure software. A nice example for this is shown in his talk about lexical scanning in Go: http://www.youtube.com/watch?v=HxaD_trXwRE http://www.youtube.com/watch?v=HxaD_trXwRE
  - jules 14y ago
    I'd say concurrency is a bit overkill for that problem (i.e. threads or processes scheduled by the run time system that appears non-deterministic to the programmer). Deterministic coroutines work fine. Even Python generators are sufficient. Though perhaps "useful" is a bit too broad: maybe it should be replaced by: > What most people don't realize is that for concurrency to improve performance, there must be parallelism.
- ahelwer 14y ago
  I actually would disagree with the statement that "for concurrency to be useful, there must be parallelism." In my experience with handling asynchronous events (such as input from the user, system, or network) it's much easier to handle the input in separate threads instead of polling some buffer in your top-level logic loop. That way the time slicing problem is offloaded to the OS (or whatever thread library you're using) instead of you having to worry about getting stuck in another part of your top-level loop for too long.
  - jules 14y ago
    The reason you don't want to get stuck is because there is parallelism: between the other computers on the network and your computer, or between the between the person using the computer and your program. (this isn't really different than a disk or a network doing things in parallel with your program, only in this instance the other thing runs on flesh instead of on silicon). If the disk couldn't do things in parallel with your CPU there would be no point in avoiding to get stuck for too long in your main loop, since either one would have to wait for the other anyway.
- Scaevolus 14y ago
  Cooperative multitasking on a single CPU is concurrent, but not parallel. It's still very useful.
  - jules 14y ago
    Yes, but only because there is parallelism between the CPU and the peripherals, like disk, network and the brain of the person using the computer.
    - enneff 14y ago
      The realm of the programming language is the CPU. In the context of this talk, the terms concurrency and parallelism should refer to tasks running on CPUs. It confuses the issue greatly when you introduce the outside world, which is inherently parallel.
- nivertech 14y ago
  While parallel map is always deterministic, parallel reduce is not. I.e. if you trying to calculate a sum of a vector with real values in parallel, you will get different results each time.
ahelwer 14y ago
Sort of, but this explanation loses too much information. Concurrency is a binary relation on tasks, which looks like Task -> Task -> Bool; if true, the order in which the tasks may execute relative to one another does not matter. If false, the tasks must execute in a defined order. Astute readers will note the above function is isomorphic to the function defining whether there is an edge between two nodes in a graph (although the Bool value is flipped); indeed, task dependency graphs are a useful way of modelling concurrent systems. Concurrency has absolutely nothing to say about parallelism. If you have a computer system which is able to execute tasks in parallel, it can take advantage of information from the concurrency relation to execute two concurrent tasks in parallel. For the best implementation of this idea I've seen, I recommend taking a look at Intel's Threading Building Blocks template library.
thirsteh 14y ago
Concurrency is when you have multiple threads of control. Parallelism is when you are doing more than one thing at the same time. Multiple threads of control may do things in parallel. Another good explanation: http://ghcmutterings.wordpress.com/2009/10/06/parallelism-concurrency/ http://ghcmutterings.wordpress.com/2009/10/06/parallelism-co...
- goostavos 14y ago
  Yep.. I don't understand. Concurrency is not parallelism, yet.. parallelism requires concurrency...? I read through your linked article and didn't understand, I read through the linked article and... I still don't understand! >Now I can hear you object, but isn’t concurrency required to implement parallelism? Well, yes, it is, but concurrency is also required to implement sequentiality too! What am I missing here? Is parallelism just a well structured concurrency? Or is the sole distinction determinism vs non-determinism? How is non-determinism avoided in a parallel process (which, to my thinking, means a thread)? From my Java/Python mind, the load balancer dispatcher/worker/channel-listener seemed very similar in construction to what you would do with a Thread (or Process) and a synchronized Queue. What makes one concurrent, and the other not? I suppose, my main question is, what prevents parallelism from not being non-deterministic?
  - scott_s 14y ago
    Concurrency is a statement about a duration of time. Parallelism is a statement about a moment in time. During a one second window, did both of the tasks execute? If yes, then they are concurrent. If no, then they are not concurrent. Was there any moment in time when both tasks executing simultaneously? If yes, then they executed in parallel. If no, then they did not execute in parallel. From this, it's easy to see that if something is parallel, it must also be concurrent - in order for two tasks to execute during the same moment in time, they must also both have executed during a window of time. Concurrency without parallelism happens on machines with a single core. Processes and threads must time-share the only core. Frequently, some of these processes will have multiple threads, so the threads need to synchronize with each other, even though they don't execute at the same time. The definitions of concurrency and parallelism have nothing to do with determinism, so I don't know why others have brought it up. Concurrency and parallelism implies non-deterministic interleavings of threads and processes, but whether or not the result is deterministic is up to how we program.
chongli 14y ago
Parallelism does not require concurrency (at least not in your code). Parallelism can be handled by a library allowing your code to speed up with often minimal changes. One such example is the replacement of a sequential map function by a parallel map.

jules 14y ago

It's a bit more nuanced than that. Concurrency implies non determinism. For example if you have multiple threads then the result of the program is non deterministic: it may depend on the particular interleaving of the threads over time. Parallelism is about executing multiple things at the same time to improve performance. You can have parallelism without concurrency. For example a parallel map operation is parallel, but not non deterministic. It always gives the same result. Now, under the hood to implement parallel map, there is probably some concurrency involved, but that is not exposed in the interface of map. You can have concurrency without multiple threads, for example Node with asynchronous callbacks is concurrent, because the order in which those callbacks get called is non deterministic. But it does not necessarily need to run on multiple threads. Usually we don't want the end result of our program to be non deterministic, so we use synchronization primitives like locks and Go's channels to limit the non determinism in such a way that it does not affect the end result. What most people don't realize is that for concurrency to be useful, there must be parallelism. But wait, didn't I just say that in Node you have concurrency without multiple threads? Yes, but the parallelism does not need to be in your CPU! If you do an asynchronous disk read, or an asynchronous network request, the disk and other computers on your network are working in parallel with your program. Concurrency allows us to exploit that parallelism, so that the CPU can do useful work while the disk is busy reading our data. Now, you can write your program with concurrency, but if there is no parallelism anywhere in the system, that's not useful. So in practice it is the reverse: concurrency implies parallelism (but not necessarily on the CPU), but parallelism does not imply visible concurrency (though it might be hidden under the hood of a parallel construct like parallel map).

mseepgood 14y ago
> What most people don't realize is that for concurrency to be useful, there must be parallelism. No, as far as I understand from this and other talks, Rob Pike argues that concurrency is useful even without parallelism: it's a better way to structure software. A nice example for this is shown in his talk about lexical scanning in Go: http://www.youtube.com/watch?v=HxaD_trXwRE http://www.youtube.com/watch?v=HxaD_trXwRE
- jules 14y ago
  I'd say concurrency is a bit overkill for that problem (i.e. threads or processes scheduled by the run time system that appears non-deterministic to the programmer). Deterministic coroutines work fine. Even Python generators are sufficient. Though perhaps "useful" is a bit too broad: maybe it should be replaced by: > What most people don't realize is that for concurrency to improve performance, there must be parallelism.
ahelwer 14y ago
I actually would disagree with the statement that "for concurrency to be useful, there must be parallelism." In my experience with handling asynchronous events (such as input from the user, system, or network) it's much easier to handle the input in separate threads instead of polling some buffer in your top-level logic loop. That way the time slicing problem is offloaded to the OS (or whatever thread library you're using) instead of you having to worry about getting stuck in another part of your top-level loop for too long.
- jules 14y ago
  The reason you don't want to get stuck is because there is parallelism: between the other computers on the network and your computer, or between the between the person using the computer and your program. (this isn't really different than a disk or a network doing things in parallel with your program, only in this instance the other thing runs on flesh instead of on silicon). If the disk couldn't do things in parallel with your CPU there would be no point in avoiding to get stuck for too long in your main loop, since either one would have to wait for the other anyway.
Scaevolus 14y ago
Cooperative multitasking on a single CPU is concurrent, but not parallel. It's still very useful.
- jules 14y ago
  Yes, but only because there is parallelism between the CPU and the peripherals, like disk, network and the brain of the person using the computer.
  - enneff 14y ago
    The realm of the programming language is the CPU. In the context of this talk, the terms concurrency and parallelism should refer to tasks running on CPUs. It confuses the issue greatly when you introduce the outside world, which is inherently parallel.
nivertech 14y ago
While parallel map is always deterministic, parallel reduce is not. I.e. if you trying to calculate a sum of a vector with real values in parallel, you will get different results each time.

ahelwer 14y ago

Sort of, but this explanation loses too much information. Concurrency is a binary relation on tasks, which looks like Task -> Task -> Bool; if true, the order in which the tasks may execute relative to one another does not matter. If false, the tasks must execute in a defined order. Astute readers will note the above function is isomorphic to the function defining whether there is an edge between two nodes in a graph (although the Bool value is flipped); indeed, task dependency graphs are a useful way of modelling concurrent systems. Concurrency has absolutely nothing to say about parallelism. If you have a computer system which is able to execute tasks in parallel, it can take advantage of information from the concurrency relation to execute two concurrent tasks in parallel. For the best implementation of this idea I've seen, I recommend taking a look at Intel's Threading Building Blocks template library.

thirsteh 14y ago

Concurrency is when you have multiple threads of control. Parallelism is when you are doing more than one thing at the same time. Multiple threads of control may do things in parallel. Another good explanation: http://ghcmutterings.wordpress.com/2009/10/06/parallelism-concurrency/ http://ghcmutterings.wordpress.com/2009/10/06/parallelism-co...

goostavos 14y ago
Yep.. I don't understand. Concurrency is not parallelism, yet.. parallelism requires concurrency...? I read through your linked article and didn't understand, I read through the linked article and... I still don't understand! >Now I can hear you object, but isn’t concurrency required to implement parallelism? Well, yes, it is, but concurrency is also required to implement sequentiality too! What am I missing here? Is parallelism just a well structured concurrency? Or is the sole distinction determinism vs non-determinism? How is non-determinism avoided in a parallel process (which, to my thinking, means a thread)? From my Java/Python mind, the load balancer dispatcher/worker/channel-listener seemed very similar in construction to what you would do with a Thread (or Process) and a synchronized Queue. What makes one concurrent, and the other not? I suppose, my main question is, what prevents parallelism from not being non-deterministic?
- scott_s 14y ago
  Concurrency is a statement about a duration of time. Parallelism is a statement about a moment in time. During a one second window, did both of the tasks execute? If yes, then they are concurrent. If no, then they are not concurrent. Was there any moment in time when both tasks executing simultaneously? If yes, then they executed in parallel. If no, then they did not execute in parallel. From this, it's easy to see that if something is parallel, it must also be concurrent - in order for two tasks to execute during the same moment in time, they must also both have executed during a window of time. Concurrency without parallelism happens on machines with a single core. Processes and threads must time-share the only core. Frequently, some of these processes will have multiple threads, so the threads need to synchronize with each other, even though they don't execute at the same time. The definitions of concurrency and parallelism have nothing to do with determinism, so I don't know why others have brought it up. Concurrency and parallelism implies non-deterministic interleavings of threads and processes, but whether or not the result is deterministic is up to how we program.

chongli 14y ago

Parallelism does not require concurrency (at least not in your code). Parallelism can be handled by a library allowing your code to speed up with often minimal changes. One such example is the replacement of a sequential map function by a parallel map.