Hacker News new | past | comments | ask | show | jobs | submit login
Concurrency Is Not Parallelism (2013) [video] (youtube.com)
107 points by tosh 3 months ago | hide | past | web | favorite | 33 comments

Here's a fantastic set of cartoons explaining concurrency and parallelism:


After many years of discussions on the topic, my goto line is now the following:

"Parallelism is for performance, Concurrency is for correctness."

Clean, simple. I like it

Concurrency and parallelism are properties of the resolution with which you view your program. View a program at the distributed system level, vs the OS-scheduled level, vs the microarchitectural superscalar / OoO / SIMD level, and you will come to different conclusions about whether the program is "parallel" and/or "concurrent." These are contextual.

To be clear up-front: I agree with you. However, this line of thinking can be a bit disingenuous as it may turn into convincing someone their single threaded program in C is actually multithreaded because of OS scheduling or because it runs on a distributed k8s cluster.

It reminds me of how technically there is space between everything if you go small enough (ie cellular or atomic) and how some elementary school kids would use that to convince you that they arent touching you :)

Doesn't Simon Marlow explain the difference very well? Concurrency is implementation detail and parallelism is an execution detail?

Concurrency = logical simultaneity. Parallelism = physical simultaneity. When the former is mapped to the latter we encounter scalability. Some examples: Unix commands (cp, grep, awk, sort) do not scale on multi-core systems due to total lack of concurrency in their implementation. Quick sort scales worse than merge sort because the latter allows for more concurrency. A parallel program using a barrier between outer loop iterations (f.e. matrix inversion, or computational partial differential equations) won't scale well because barriers are antithetical to concurrency.

>Unix commands (cp, grep, awk, sort) do not scale on multi-core systems due to total lack of concurrency in their implementation.

This is not true. Unix commands are designed to be used in pipelines. Unix is actually the easiest way to run things in parallel, so easy that people don't even notice.

That isn't the individual tools showing concurrency - they are running concurrently due to the way the OS manages processes and pipelines.

The overall task has multiple things running concurrently but it doesn't have to[1] and the individual components are doing no concurrency of their own. It has the same effect in many cases because of the buffering built into how pipes are handled, for instance passing the output of gzip through gzip through gzip will happily use most of three cores (if that much CPU time is free at that moment) but try that with commands that need to block such as invocations of sort for example and you'll see that break down. One sort command in your pipeline will tie the whole lot to not scaling much beyond one core[2]. Also pipes and other trickery like xargs/parallel don't help if the task is something like "grep over this large file" - that will only scale over multiple cores at all if your implementation of grep supports a multi-threaded search (and your data is in cache or otherwise in RAM so the process isn't IO-bound).

[1] it could queue each and spool the output between to temporary storage, it is so chose [2] note that some implementations of sort, such as the GNU version seen in most (all?) linux distributions, do support their own multi-core use

Don't confuse individual commands with the operating system, which is highly concurrent. I was very specific in my statement.

The dictionary definition of concurrency contradicts this video. Concurrency is defined as "happening or existing at the same time".

I think what he means is that he's defining 'concurrent' as a sort of abstract parallelism which can run on 'n' CPU cores. It becomes concrete parallelization when you set n to 2 or more but can still be considered concurrent software architecture even if someone only ever runs their copy with n=1.

To address another comment, I agree this distinction has limited utility (assuming I understand it correctly). This context of discussing architectures which promote abstract parallelism is probably about the only place it's useful.

I agree that a strict/true interpretation of 'concurrency' (as distinct from Pike's definition) would not include time slice multi-tasking since it depends on the limits of human perception to appear as truly-concurrent/executed-in-parallel when it's actually fine-grained sequential processing.

The difference is instantaneously (parallelism) vs over a period of time (concurrency).

Edit: compare a batch system (no concurrency and no parallelism), Vs a time sharing system on an uniprocessor (concurrency) Vs a time sharing system on a multiprocessor (parallelism).

Isn't parallelism one limit case of concurrency (zero dependencies) and the opposite of full sequentialism (fully dependent) ?

That's true in one direction, but not the other.

The other angle is that concurrent programs are still concurrent on a uni-processor. Parallel programs are not.

What is a "concurrent program?" If concurrency is about program structure, does that structure have to be explicit? If I rewrite a loop to support OOE is it thereby concurrent?

A uniprocessor may be pipelined, superscalar, support SIMD, etc which would seem to satisfy the definition of parallelism. So isn't parallelism achievable on a uniprocessor?

The more I think about this stuff the less sense the distinction makes.

I would define a concurrent program as one with multiple independent flows of execution. Whether they are scheduled on multiple CPUs at the same time or just one is what makes them parallel or not.

If you look at a what happens inside a CPU then you probably could say a uniprocessor has some degree of parallelism, but this is not a common point of view AFAIK, it is too low level. Also, the execution contexts inside a pipelined CPU are not entirely independent, you can have pipeline stalls due to dependencies. This is not the case with, say, two application threads running independent tasks.

> So isn't parallelism achievable on a uniprocessor?

Of course! Normally unqualified parallelism refers to multiprocessor parallelism, but instruction level parallelism is also a thing. So is overlapping io or memory access with computation. Even memory accesses themselves can be parallelized (caches are multi ported, CPUs allow multiple outstanding cache misses), or IO (multiple disks or network cards).

From what I recall, Quake existed because of instruction level parallelism between apu and fpu. This indeed has importance.

There are several misleading comments here making the incorrect assumption that the term “concurrency” in software has something to do with time. In software design, when we talk about concurrency, we are talking about coordinating distinct logical processes (not necessarily OS processes). This term has limited similarity to the common-knowledge understanding of concurrent events “happening at the same time”. Logical (not temporal) ordering of operations is implemented using process synchronisation techniques. One of the important differences between parallelism and concurrency is that parallelism is typically restricted to almost identical process definitions which aim to exploit the physical architecture of processing units. Concurrency, however, makes fewer assumptions about the physical architecture and focuses on software design in a more abstract way with a primary objective of coordinating resource utilisation of competing processes (especially physical resources).

What is the core difference between Actor and threadpool (Boss/workers)? I do know that this is off-topic, please spare me .

A distinction isn't necessarily useful.

no kidding...it's become some convention in the last 15 or so years, but in the early 1990s working on supercomputers i had never heard of it.

In Python 3 there is the ayncio module that is concurrent (logical execution is not sequential) but not parallel (only one thread). I found the distinction very useful when I started to look into it.

I seem to remember it coming from Golang people.

I seem to remember it coming from Golang people.

The discussion existed around languages like Python, long before Golang showed up on the scene.

That's what people using CPython think.

I think most CPython folks are quite annoyed by the lack of concurrent execution! The GIL sucks.

If you ever ask Racket-lang folks about threads they will lecture you about concurrency vs parallelism endlessly, it's like a mantra they repeat to avoid realizing there is a problem.

The GIL prevents parallelism but not concurrency - that’s the whole point of this discussion.

I said concurrent execution. When being pedantic it is important to read carefully.

Being super careful about 'parallel' and 'concurrent' is super, super pedantic and pointless. They are synonyms. If two things are running concurrently, they are running in parallel. If two things are running in parallel, they are running concurrently. These are terrible words to overload with very careful definitions.

When people talk about 'concurrency' using the super careful pedantic definition, they just mean that it's possible to execute code while at the same time blocking on system calls. This isn't some kind of great feat and any language that can't do it is a toy. There is absolutely no reason to act like 'concurrency' using this definition is in any way special or worth even mentioning.

But that's not the point, is it? People get defensive about their favorite languages, so when faced with valid criticisms like "the GIL prevents you from running Python code in parallel" (which is a completely valid and actually pretty huge defect when modern computers have many cores on average) instead of just admitting the deficiency a person can be defensive and respond with stupid lectures about 'concurrency' and 'parallelism'.

I always used to read that, but in practice, threading and multiprocessing modules work just fine for concurrency and parallelism, respectively. What's the issue?

The threading module is restricted by the "Global Interpreter Lock" and cannot run truly concurrently.

My first run-in with this was when I wrote a toy brute-force birthday attack as part of a course I was doing, and realised it was only utilising one core.

The multiprocessing module works as expected, sure.

@4:05 people with lesser minds ;)

Applications are open for YC Summer 2019

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact