Rendered at 12:06:55 GMT+0000 (Coordinated Universal Time) with Cloudflare Workers.
criddell 16 hours ago [-]
This review seems to equate parallelism and concurrency as the same thing and they are not.
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.
Jtsummers 16 hours ago [-]
That's a useful interpretation of the two terms, but it's far from universal and the two have often been used fairly interchangeably over the decades. It's been much more useful as a distinction when someone discussing it announces that that is how they're separating the two concepts, instead of trying to force other people to adopt that particular pair of definitions.
miki123211 3 hours ago [-]
You can have parallelism without much concurrency. Think parsing a bunch of files, where you have a `fn parse(path) -> AST` which does not rely on global state. Parallelizing something like this is trivial, with no mutexes in sight, and can be great for performance in many situations.
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.
packetlost 9 hours ago [-]
Frankly the software industry suffers heavily from a lack in standardized terminology. The precise definition of parallelism vs concurrency is one that I think is incredibly important. You are doing your peers a disservice by using them interchangeably, they are not.
adrian_b 2 hours ago [-]
The 2 terms have been used inconsistently in the past and some authors have even alternated between them during their lifetime.
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.
ahelwer 16 hours ago [-]
That battle has unfortunately been lost and different sources give different definitions, often exactly swapped. This was discussed in one of the HN posts linked in the article: https://news.ycombinator.com/item?id=36318280
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.
Athas 16 hours ago [-]
I think there is a deep conceptual unlock: concurrency is about semantics, whilst parallelism is an operational property. I use this distinction a lot in my own work. Concurrent programming primitives are inherently non-deterministic (and usually about handling non-deterministic events), on top of which we must then establish some kind of properties (sometimes determinism to some extent). Many interesting parallel operations are however completely deterministic, and the fact that they are parallel is a property of their assigned cost model (and hopefully implementation, in practice).
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.
convolvatron 11 hours ago [-]
I don't like the essential characteristic of concurrency being nondeterminism. its really that multiple processes are running concurrently. if we don't have serializing operations, we have arbitrary execution order. but if we do then we can introduce the necessary determinism while still being (largely) concurrent in evaluation. and if those logically concurrent processes are physically concurrent then we have parallelism. so the first is necessary but not sufficient for the latter.
so I find saying that we have one or the other to pretty misleading.
gpderetta 3 hours ago [-]
deterministic scheduling is possible, but most theoretical concurrency models assume non-determinism.
And even with deterministic scheduling, concurrency might be dictated by external stimuli (for example request arrival) that are not deterministic.
Dylan16807 1 hours ago [-]
It's really important to get people to recognize that concurrency can happen on a single core or a single task-switching thread. You don't necessarily need to split off parallelism to explain that, but it helps.
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.
jerf 15 hours ago [-]
Personally I think it's not a good idea to think too rigidly about and try to draw a huge distinction between the two. They're on a continuum and sometimes I'd say some things aren't even strictly speaking "between" them either. Sitting down and trying to classify code into "parallel" and "concurrent" is as likely to do harm as to do any good.
packetlost 9 hours ago [-]
I firmly disagree, they are not a continuum, they are binary properties of what they describe. Code can have concurrency primitives, but parallelism primitives must necessarily come from the environment the code executes in, whether it's multiple code streams on a multicore processor or process parallelism provided by an operating system. Programs that are parallel are necessarily also concurrent (if they must communicate between parallel executions), but the inverse is not necessarily true.
If this distinction wasn't important, Python's infamous GIL would not be an issue.
16 hours ago [-]
bryanrasmussen 5 hours ago [-]
in the English vernacular when you deal with something you do something.
mkehrt 14 hours ago [-]
As other comments have pointed out, this is just not true in general usage.
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.
wiml 13 hours ago [-]
That's the same distinction, made in the same way, isn't it?
wongarsu 6 hours ago [-]
With the rise of async there is once again lots of cooperative multitasking being used, not just preemptive multithreading
But that's the only nit
mkehrt 12 hours ago [-]
Well, we were using it to talk about things like cache invalidation and lax memory models rather than properties of algorithms.
Jtsummers 13 hours ago [-]
Pretty much, yes.
13 hours ago [-]
threethirtytwo 5 hours ago [-]
Yeah although they say something like nodejs is not parallel but concurrent it’s not technically true from a systems standpoint. There are actually tons of operations happening at the same time. It’s just all delegated to IO.
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.
gpderetta 3 hours ago [-]
> True concurrency that is absolutely absent of parallelism is a bit pointless
It is very important in interactive or realtime systems.
afdbcreid 7 hours ago [-]
Parallelism without concurrency is useless, and concurrency without parallelism is usually cooperative and does not have the same challenges. So in essence, the title is correct.
gpderetta 3 hours ago [-]
> concurrency without parallelism is usually cooperative
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).
afdbcreid 3 hours ago [-]
Right, I forgot about multithreading on one core.
bolangi 15 hours ago [-]
The Raku language (formerly Perl 6) and its underlying VM has features to support parallel programming, concurrency and asynchrony, designed to make common cases relatively easy to code and avoid pitfalls.
Jonathan Worthington, the author of the VM and these features, has given an excellent presentation on the concepts and their implementation.
Should have been titled "Is Parallel Programming What Can You Hard, And, If So, Do About It?"
nnevatie 5 hours ago [-]
The plural of a mutex is "deadlock"
crooked-v 15 hours ago [-]
Don't dead, open inside.
13 hours ago [-]
ozarkerD 16 hours ago [-]
world! hello
igsomething 16 hours ago [-]
I do agree with your comment.
not not
mlvljr 13 hours ago [-]
[dead]
anonymousDan 16 hours ago [-]
I would probably recommend the art of multiprocessor programming (herlihy and shavitz) as a good starting point for concurrent programming. There is also " A primer on memory consistency and cache coherence" (Nagarajan et al) if you want to get more into the interaction between memory consistency and coherence.
RossBencina 4 hours ago [-]
I can recommend "Shared Memory Synchronization," by Michael L. Scott for an introduction to nuts-and-bolts level detail.
bob1029 5 hours ago [-]
We should make developers prove they can use one core responsibility before we hand them 64.
Much like we get pilots comfortable in single engine aircraft before we have them fly around in 747s and AC130s.
trylist 5 hours ago [-]
They're fundamentally different skills in my view. It's helicoptors vs fixed wing, rather than single engine vs multi engine
bob1029 4 hours ago [-]
Rotary vs fixed wing is more like GPU vs CPU programming. Within each you still need to understand the capabilities of the machine before you can go wide effectively.
pjc50 4 hours ago [-]
Many of the pieces of software which people claim are miserably slow are using one core irresponsibly. Usually because they're operating in a "only one thread can touch the UI" environment and that thread keeps blocking on everything.
hoistway 9 hours ago [-]
Spent days tracking down a deadlock that only manifested under specific load. Definitely hard, even with good tooling.
kccqzy 9 hours ago [-]
What kind of tooling were you using? IMO, deadlocks are some of the easiest concurrency bugs to diagnose. If you can see the thread stacks, it is easy to see threads are blocked from acquiring a lock. If you can attach a debugger, it is easy to see which locks are involved. Then you can pretty much figure things out using the straightforward guideline that if multiple locks are involved, they must be acquired in the same order in all code paths.
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.
gpderetta 3 hours ago [-]
Agree completely. But they become harder when you eschew standard constructs like threads and mutexes and bring-your-own losing nice things like debugger supports and stack traces. Now your logical tasks might be deadlocked, while your threads appear to be running correctly. This is surprisingly common this day with async runtimes and less than stellar debugging support.
stingraycharles 7 hours ago [-]
> Silent data corruption caused by missing or wrong synchronization is way harder to debug.
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.
afdbcreid 7 hours ago [-]
They are, if you can attach a debugger. If only one thread is stuck and in production... Not so much (but there are still much harder bugs).
gpderetta 3 hours ago [-]
ah, that's probably a missed wakeup problem! Much nastier. Still seeing where your thread is blocked might hint you to where the missing signal should have been.
afdbcreid 3 hours ago [-]
I didn't mean literally a single thread, just that not the whole application is hang.
gpderetta 2 hours ago [-]
So I actually had this exact issue where we suspected a deadlock, but the application was limping along and we couldn't justify attaching a debugger. I managed to confirm my suspicions with judicious use of perf and /proc/<pid>/task/<tid>/wchan .
tancky 4 hours ago [-]
Writing concurrent code is fun. The problem is that debugging it feels like trying to catch a ghost that only haunts your system at 3 AM on a Saturday.
ghenna 4 hours ago [-]
I remember a music producer dreaming of a keyboard player with just one finger.
Mbarley 12 hours ago [-]
Debugging race conditions feels like chasing ghosts; often makes me just reach for a message queue.
gpderetta 3 hours ago [-]
... until you realize you can have race conditions with queues as as well.
dosisking 6 hours ago [-]
Nothing beats serial programming imo
kazinator 17 hours ago [-]
Nope! Parallel programming is all yahoo, wee, look at that go!
Then comes the parallel debugging.
Pretty soon it's 15 years later, different person, yahoo-wee bro having long moved on.
theendisney 14 hours ago [-]
Give each dev their own core.
thomasahle 17 hours ago [-]
Parallel programming is a great application for LLM correctness proofs in Lean.
You can't unit test your way out, but if you care about the code's correctness, today there's a way.
vitalnodo 14 hours ago [-]
As I found out recently, there's a lighter option: model checkers like Spin. You describe your synchronization logic in a small modeling language (Promela), and Spin tries every possible interleaving of that model.
tintor 16 hours ago [-]
Mix of different types of tests helps.
Best examples are SQLite and Jepsen test suites for dbms engines.
My experience has been the opposite. If lean had linear types (or separation types), it would be, but as it is, Lean's just a little bit too focused on talking about results to tidily talk about how those results are computed.
winwang 9 hours ago [-]
I don't know. For many operations, you can encode "how" by saying "under any permutation of this sequence of applications". At least, for EREW machines.
raheemm 15 hours ago [-]
Even though I'm not a programmer I really enjoyed reading this book review.
17 hours ago [-]
hizlikovboy27 6 hours ago [-]
[flagged]
tobin1994 10 hours ago [-]
[dead]
drnick1 15 hours ago [-]
What can you do about it?
Ask Claude, which has read all the existing literature on parallel programming, to make the program faster.
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.
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.
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.
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.
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.
But that's the only nit
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.
https://www.youtube.com/watch?v=JpqnNCx7wVY
not not
Much like we get pilots comfortable in single engine aircraft before we have them fly around in 747s and AC130s.
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.
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.
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.
Best examples are SQLite and Jepsen test suites for dbms engines.
https://jepsen.io/
Ask Claude, which has read all the existing literature on parallel programming, to make the program faster.