Concurrency Is Not Parallelism (2013)
blog.golang.org
blog.golang.org
The term "Parallelism" these days is synonymous with "CPU Parallelism." Parallelism has existed for a long time. For example, network cards have been able to do I/O parallelism for seemingly forever. Could you imagine if a computer could only have a single network request running at a time? Therefore, what parallelism (read: CPU Parallelism) means is CPU execution happening at literally the same time. Emphasis on literally.
Concurrency is how we make sense of and communicate the above mess. In the days of single cores, we mostly cared about concurrency as a way to communicate I/O parallelism in a manageable way. Now we use concurrency to express both forms of parallelism in our programs. Good implementations of concurrency (Erlang) make all of this transparent to the user. Bad implementations of concurrency (Node.js) have the user doing all of the work (callbacks).
Node's a single-threaded reactor pattern event loop, whereas Erlang/OTP is an SMP-enabled virtual machine with a preemptive scheduler that manages lightweight actors called processes, all isolated from each other with their own stack and heap, that can be cheaply spawned and communicate only via message passing. On top of that, Erlang offers location transparency for processes and easy node distribution out of the box. OTP then provides a framework for fault tolerance and reusable components by supplying generic behaviors (server, FSM, etc.), supervisors for monitoring and restarting processes when they crash, endpoints for hot code reloading, and more.
You should try it one day. There's really nothing else like it, even if its underlying concepts aren't necessarily novel - but they're well combined and largely obscure in mainstream practice. A lot of platforms have tried to implement their own equivalent actor model approaches (Celluloid for Python, Akka for Scala...), but none reach the same level.
That is really a unique property of the BEAM VM. Most languages built on it Erlang, Elixir, LFE, Joxa, etc can take advantage of that.
Often when telling someone technical about how you can have processes that behave like OS processes -- fully isolated heap, and if one crashes it doesn't affect the others, and which are also very lightweight -- only a few KB of memory overhead, they think there is some trick or misunderstanding. Like "sure but they are just green threads" or "they can't be just a few KB of memory, processes have to be bigger than that".
Isn't there a saying something to the effect of "an advanced enough technology looks to many as indistiguishable from magic".
However, of the definitions I did find, the ones referenced in the Clojure documentation seemed most reasonable - from memory, something like the difference between coordination of simultaneous tasks, and their execution.
This definition allows for the existence of concurrent systems without formal concurrency primitives - every action game deals with race conditions even though the gameplay loop is typically single threaded, because it has to code apparently independent agents against a global shared-state environment, and the order in which these agents process data matters. In most instances there is no crisis for the game if the situation is left poorly specified - it may slightly bias some elements or defer events by an additional frame - but for certain things it can blow up into a showstopper bug with physics or cutscene triggers, or harm responsiveness.
This correlates with a common trope from students who encounter the agents problem for the first time - they try to run each AI on a thread, further pushing away their ability to direct concurrency, while "gaining" parallel performance(not really, of course).
Concurrency is a possible feature of an abstract machine, exposed as a programming-language-design paradigm. A language can target a platform that "has concurrency", and this heavily shapes the language. You can end up "coding Go/Erlang in C"—writing concurrent code in your head for a concurrent abstract machine, then translating it to your target language.
Parallelism, meanwhile, is a VM/runtime/platform implementation detail.
Concurrency is the ordering and dependency (or lack of) between two (or more) paths of executions. Parallelism is the doing of work in parallel. They describe two different things. A program can be either concurrent only, parallel only, or both, and there's where the confusion come in.
What about multithreading? If a single core switches between tasks I can see that not being true parallelism, but what about multi core?
A multi-core CPU is basically multiple CPUs. The details (multicores share the same die, use the same caches, etc.) are mostly irrelevant here.
A multi-core CPU for all intents and purposes has multiple CPU's. For the discussion on concurrency and parallelism, the distinction is on one execution unit vs multiple execution units.
Nitpick: SMT[0] (implemented as Hyper-Threading by Intel) is in fact parallelism for threads on a single CPU.
[0]: http://en.wikipedia.org/wiki/Simultaneous_multithreading
In this particular analogy, if the goal is to consume the food as quickly as possible, this may be the most efficient solution.
Parallelism: the two threads are running simultaneously on two CPUs. There is concurrency too since there are multiple threads.
> Concurrency: [...] There is no parallelism.
> Parallelism: [...] There is concurrency too since ...
Oops, contradiction! :)
Edit: I should have written more clearly that having concurrency doesn't imply parallelism.
In grad school, we used concurrency to mean interleaved, single processor threading, while parallelism meant multiprocessor.
I've heard other people use this distinction to mean fork-join style concurrency vs. shared memory parallelism.
Can we just accept that these two words mean roughly the same thing and stop trying to get one community's niggling technical distinction to be accepted as gospel?
Perhaps in your domain/language this distinction isn't important but it is for some of us. The patterns you use to work with concurrent vs parallel code differ, which means it is an important distinction to understand.
Nobody can agree on them so let's just assume they mean the same thing and move to more interesting discussions, shall we?
Concurrency and parallelism need different abstractions; try using actors for parallelism or MPI for concurrency! If they mean the same thing, how do we distinguish between them as is absolutely necessary?
Erlang
> or MPI for concurrency
Go uses channels as a message passing interface for the "composition of independently executing processes"
Saying concurrency and parallelism are equivalent basically invalidates all design decisions made by these systems.
They make full use of all CPU cores since they implemented SMP support: http://erlang.2086793.n4.nabble.com/Some-facts-about-Erlang-...
> ditto for Go Channels
Go has a user-space M:N scheduler that distributes its "goroutines" among multiple OS threads and therefore multiple cores.
Erlang is about both.
Those are not either or. Concurrency sits at a higher level of abstraction -- at the problem domain. "I'll create an actor for this request, another actor for that, maybe another one for monitoring". These are concurrent units.
Parallelism happens if my machine has more than one CPU and these concurrency units will actaully execute at the same time. Or maybe I have a single CPU only. I'll have not parallelism. They'll be sequenced and scheduled in and out of the single CPU in some small or larger time slices. But they'll not execute in parallel.
So maybe I am running my machine in 1989 (Erlang was doing work back then too) with only a single CPU. I still want to create many concurrent units of work. Or maybe I am running in 2015 and I have 64 core machine and I specifically choose Erlang because I expect to get lots of parallelism for cheap as my concurrent units are largely independent of each other.
Concurrency is necessary property of the work as defined, parallelism is an opportunistic property. Confusing the two concepts can lead to people trying to do HPC work with Erlang.
If you are working on an HPC workload, you wouldn't choose Erlang, but you might get a happy speed up for a standard distributed application. Parallelism is strictly about performance, concurrency is about correctness. When you go off and do a HPC or big data program, you might play with MPI, CUDA, MapReduce, or maybe just roll something yourself. No one goes...we should do that in Erlang! Likewise, when you go off and do a concurrent distributed system, Actors make a lot of sense given the concurrency requirements involved (who would think of using CUDA for that?).
Perhaps the problem is not about concurrency and parallelism, but different kinds of computations.
Erlang uses parallelism for fault-tolerance purposes, because you need several physical machines running in parallel on different sites to achieve outstanding fault-tolerance. MPI/CUDA/MapReduce uses parallelism for performance reasons.
I do not know if it is true as I couldn't find the source, but I remember reading that aircrafts run all computations in parallel on three different architectures (Power and two others), using three different algorithms, to ensure that the results are not compromised either by a faulty algorithm, or a CPU bug. In that case parallelism is used for safety.
From wiki [1]:
> Parallel computing is a form of computation in which many calculations are carried out simultaneously, operating on the principle that large problems can often be divided into smaller ones, which are then solved concurrently ("in parallel").
...
Parallel computer programs are more difficult to write than sequential ones,[5] because concurrency introduces several new classes of potential software bugs, of which race conditions are the most common.
And the article for concurrency [2]:
> In computer science, concurrency is a property of systems in which several computations are executing simultaneously, and potentially interacting with each other. The computations may be executing on multiple cores in the same chip, preemptively time-shared threads on the same processor, or executed on physically separated processors.
[1] http://en.wikipedia.org/wiki/Parallel_computing
[2] http://en.wikipedia.org/wiki/Concurrency_(computer_science)
Concurrency is a problem (doing things at the same time leads to resource contention), while parallelism is a performance technique. Fault tolerance is something else altogether, and can apply to concurrency problems as well as parallel speedups. Doing things in parallel as a form of redundancy isn't really parallelism...in general, the word parallelism != "in parallel" while concurrency != "concurrently," though they are definitely related.
Phew.
You're right that Erlang is not the best choice for HPC, but you're wrong about the motive. There's nothing inherently inefficient about the actor model. Erlang's low performance comes from unrelated technical choices (bytecode running on a VM, shitty string handling, etc.).
Look, you can implement the actor model using MPI for inter-actor communication: https://github.com/poconbhui/mpi-actor
And hard-core HPC people are talking about the actor model in Cray's Chapel language: http://chapel.cray.com/education/cs380p-actors.pdf
Shared memory is also quite nice when you can afford it in non-distributed settings (never use MPI on just one machine!). If your problem can fit in GPU memory, CUDA will do wonders.
Is chapel still around? I thought the Darpa money ran out.
I don't think it is that complicated.
Concurrency is a property of the algorithm or problem space. Things can happen independent of each other. Two or more client requests can read a file. Logically they don't have to wait for each other. There is no sequential dependence. These could be represented in code as two threads, two futures, promises, Goroutines, Tasks, callback chains, actors etc <insert favorite concurrency primitive>.
Parallelism is a property of the execution environment. "Can the concurrent parts of the program execute at the same time?" The machine happens to have 2 CPU cores and two requests arriving at the same time can execute at the some time. Or it has only one CPU and even though they can execute at the same time, they don't. One might be blocked waiting for another or they might be preempted by the scheduler every milliseconds, execute a bit, then switch to another.
EDIT: Here is Joe Armstrong's interpretation. Which is similar to this and includes a cute diagram with coffee machines:
http://joearms.github.io/2013/04/05/concurrent-and-parallel-...
He knows what he is talking about, he is the father of Erlang.
Concurrency in Go is based on Communicating Sequential Processes (CSP) by Hoare; this was originally published in 1978. Reading CSP you see all the ideas are abstractly formalized in math terms: there really is no notion of multiple streams of execution occurring at the same time (i.e., multiple hardware threads). So, a distinction is made between things cooperating (concurrency in their parlance) and things running at the same time (parallelism).
To continue this idea, parallelism, again using their terms, really is an implementation of the more abstract concept of concurrency. That is, given a description of concurrent processes communicating you can run them in parallel (and reason about their correctness).
If you do not make the distinction, regardless of the terms you use, you remove the layers of abstraction necessary to reason about complex systems (separation of high level concepts and their implementation).
1. http://en.wikipedia.org/wiki/Concurrent_computing#Introducti...
2. http://docs.oracle.com/cd/E19455-01/806-5257/6je9h032b/index...
I never said that, just that a lot of people have different definitions for these words, all contradicting each other. So in effect, these words have become meaningless.
They don't mean the same thing, and that is a poisonous attitude to have. Parallelism is about performance. Concurrency is about synchronization. The difference might not matter to you, but for certain things (programming language design, library design, system architecture) it is paramount.
One thing nearly everyone agrees on: a single-core processor cannot do parallelism, but it's perfectly capable of concurrency. How do you reconcile that with your view that they are the same?
The difference matters very much to me, what is silly is that nobody agrees on which one is concurrency and which one is parallelism. In this thread alone, I found two people with a different definition from yours.
On a two lane highway on each lane several cars can move forward one after the other concurrently AND on the other lane other cars can move in parallel to them.
___
One CPU (core) having one program counter pc executes one instruction after an other and keeps track of the position in the instruction current by increasing the pc. With special code it is possible to make the pc jump to an completely unrelated code block and later make it jump back to the first code block. The core sees and executes one current of instructions but the code-blocks, the intentions of the code-blocks can be quite unrelated. There can be several concurrent code-blocks managed (usually by the OS, Kernel) interlaced into the instruction current the CPU core executes.
If there are several cpu execution cores several instruction currents with their own interlaced code-blocks can be processed in parallel.
___
Hey! At least I tried ;)
Concurrency and parallelism are very general, vague terms that mean approximately the same thing: processing of some unspecified kind happening simultaneously.