hckrnws
Book review: Is parallel programming hard, and, if so, what can you do about it?
(ahelwer.ca)
146
63
by ahelwer
by ahelwer
As I understand it, the parallelism is about task execution and concurrency is about task structure. Or, as Rob Pike said:
"Concurrency is about dealing with lots of things at once. Parallelism is about doing lots of things at once."
He said that in his Concurrency is not Parallelism talk.
On the other hand, you can have concurrency without parallelism. Think a database where IO is the bottleneck, and you have multiple clients doing reading and writing at all once, potentially to the same table, in isolated transactions, on different db nodes which have to communicate. That's a lot of concurrency and nasty locks, even if you're running on a single core and wouldn't get much of a speedup from doing otherwise.
I prefer the view where "concurrent" processes (a.k.a. tasks a.k.a. threads) are those where the execution of their parts is done in an unpredictable order, i.e. they can be interleaved in an unpredictable order.
For the correctness of programs, it only matters whether some things are executed sequentially or concurrently. If they are executed concurrently, whichever order of execution happens must not change the results in any way.
For correctness, it does not matter whether in reality all the concurrent processes are executed by a single hardware thread, so none of them are ever executed simultaneously in time, or all the processes are executed in parallel, on different processor cores.
For correct concurrent programming, what matters is how the access to shared resources is controlled, using either mutual exclusion, or optimistic accesses with retries when necessary, or dynamic partitioning of the shared resource (i.e. of an array or of a queue) into disjoint parts that allow concurrent accesses.
Parallelism only matters for the achievable performance of a program. To enable parallel execution for increased performance, there are also specific programming techniques that are required, for minimizing the dependencies that force serial execution, i.e. data dependencies a.k.a. functional dependencies, flow-of-control dependencies and resource dependencies a.k.a. operational dependencies.
Something that can cause confusions between concurrency and parallelism is the difference between the program written by the programmer and how it is really executed by a modern CPU.
When the programmer writes a program that describes multiple concurrent processes, a CPU may easily execute all of them in parallel. But even when the programmer writes only a sequential program, a modern CPU with out-of-order execution will analyze the program, identify the dependencies between instructions and convert the sequential program into a set of concurrent processes that will be executed in parallel by separate hardware execution units, if possible, though they may also be executed sequentially on a single execution unit, when the others are busy.
Thus even when the programmer does not write a concurrent program, it may still have parts that are executed in parallel, but that is not parallelism without concurrency, the concurrency is introduced by the hardware scheduler, which identifies shared resources and any other dependencies that could inhibit the transformation of the sequential program into a concurrent program.
When I was a grad student studying this stuff (~20 years ago), we used "parallelism" to mean running on different cores at the same time and "concurrency" to mean preemptive multithreading on a single processor.
In the end I don't think it is too much of an issue. What confusion is really brought by conflating parallelism and concurrency? Sure, concurrent programs can be serialized onto a single core (that's how deterministic simulation testing implementations like Antithesis and record & replay implementations like Mozilla's rr operate). But there isn't some deep conceptual unlock you get by having a strict conceptual boundary between concurrency and parallelism.
True concurrency that is absolutely absent of parallelism is a bit pointless, that’s why although node is concurrent, it is explicitly designed such that it migrates parallelism to IO.
It is very important in interactive or realtime systems.
preemptive concurrency is almost as old as interactive computers. Until fairly recently, most computers were single core, but you wouldn't have wanted to use a cooperatively scheduled OS [1], especially on a multiuser machine.
[1] yes, in the '80s some popular microcomputer OSs were single threaded (DOS) or cooperatively scheduled (classic macos and 16bit windows), but even then preemptive OSs were available (amigados).
Jonathan Worthington, the author of the VM and these features, has given an excellent presentation on the concepts and their implementation.
I don't want to devalue your experience, but I am surprised to hear that. Livelock is harder to debug. Silent data corruption caused by missing or wrong synchronization is way harder to debug.
Much like we get pilots comfortable in single engine aircraft before we have them fly around in 747s and AC130s.
Then comes the parallel debugging.
Pretty soon it's 15 years later, different person, yahoo-wee bro having long moved on.
You can't unit test your way out, but if you care about the code's correctness, today there's a way.
[deleted]
[dead]
[dead]
Ask Claude, which has read all the existing literature on parallel programming, to make the program faster.
But that's the only nit
[deleted]
I agree that this distinction is hardly universal, but it seems to be growing increasingly established, and I think it is worth fighting for it.
so I find saying that we have one or the other to pretty misleading.
And even with deterministic scheduling, concurrency might be dictated by external stimuli (for example request arrival) that are not deterministic.
so our job is really to kind of look at all the possible topological sorts of that 'after' ordering, and ensure that they are all correct, and if not, add additional edges by using locks or whatever mechanism.
kind of more interested are techniques like mvcc and crdt, which make _any_ causal ordering of events (topo sort) result in a meaningful answer.
but if you look at classical simd for example, we have concurrency (and parallelism) without additional constraints, because the threads are strongly synchronized at the hardware level.
And it's worth talking about how you can have a single task run in a parallel way, for varying strictness of 'single'.
Coroutines and SIMD are far enough apart that their execution models should have different words.
If this distinction wasn't important, Python's infamous GIL would not be an issue.
[deleted]
Imagine for the simplest example of a CPU only based game. If I want to render the positions of thousands of soldiers, just do it in a loop. Why would I spawn thousands of coroutines ONLY for the coroutines to do it all in order anyway? Makes no sense.
SIMD is parallelism without concurrency.
[deleted]
not not
[dead]
Reminds me of being a young and ambitious C++ programmer 25 years ago, discovering that when you have a map and do “return m[k]”, it is not, in fact, a read-only operation when k does not exist. After which I learned that const-correctness is not just a nice-to-have, especially in multithreaded applications.
But yeah deadlocks are hardly ever a difficult issue to diagnose. They may potentially be difficult to resolve, but at that point, it very much suggests that there’s an architecture / design issue.
[deleted]
Best examples are SQLite and Jepsen test suites for dbms engines.