Thread

Book review: Is parallel programming hard, and, if so, what can you do about it?

149 points · 66 comments · ahelwer

criddell · 1790278663 · focus · HN ↗
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.
1. Jtsummers · 1790279871 · focus · HN ↗
  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.
  1. packetlost · 1790306926 · focus · HN ↗
    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.
  2. miki123211 · 1790325938 · focus · HN ↗
    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.
2. ahelwer · 1790279929 · focus · HN ↗
  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: <a href="https://news.ycombinator.com/item?id=36318280">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.
  1. Athas · 1790281604 · focus · HN ↗
    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 · 1790298005 · focus · HN ↗
    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 · 1790326078 · focus · HN ↗
    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.
    convolvatron · 1790356915 · focus · HN ↗
    Im not saying arrival order isn't a key consequence of concurrency in many cases, it's just not the same as concurrency itself. I guess the point for me is that when we're programming or when we're using models, we define the partial ordering. so if an event arrives from outside and causes a message to be put in the queue, the read of that event by another thread is still after the external event.
    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.
    gpderetta · 1790679611 · focus · HN ↗
    I would say that classical simd with explicit vector registers is plain parallelism, not concurrency. You can build concurrent abstractions on top of it (ISPC, any of the high level GPU languages), but when you move beyond simple simd hardware and have multiple hardware threads executing simd groups on multiple cpus, possibly with the ability to migrate threads between groups, the strong synchronization is a bit lost. But I'll admit I'm not an expert.
  2. [deleted] · 1790282026 · focus · HN ↗
    [deleted]
  3. jerf · 1790282523 · focus · HN ↗
    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 · 1790307412 · focus · HN ↗
    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.
    kccqzy · 1790364940 · focus · HN ↗
    I completely agree. Even in classic Python with GIL, the programmer would still have to understand concepts from concurrent programming. The asyncio package has to provide types such as Lock, Condition, Semaphore, even when it uses just one thread. The threading package on the other hand uses OS threads, and yet it provides its own version of types such as Lock, Condition, Semaphore, even if it is protected by the Python GIL. The GIL is preventing meaningful parallelism in Python, but it remains the programmer’s responsibility to use concurrency tools correctly.
  4. Dylan16807 · 1790333666 · focus · HN ↗
    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.
3. mkehrt · 1790287689 · focus · HN ↗
  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.
  1. wiml · 1790291283 · focus · HN ↗
    That's the same distinction, made in the same way, isn't it?
    [deleted] · 1790291308 · focus · HN ↗
    [deleted]
    Jtsummers · 1790292011 · focus · HN ↗
    Pretty much, yes.
    mkehrt · 1790294925 · focus · HN ↗
    Well, we were using it to talk about things like cache invalidation and lax memory models rather than properties of algorithms.
    wongarsu · 1790316935 · focus · HN ↗
    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
4. afdbcreid · 1790313148 · focus · HN ↗
  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.
  1. gpderetta · 1790325826 · focus · HN ↗
    > 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 · 1790328422 · focus · HN ↗
    Right, I forgot about multithreading on one core.
  2. MaxBarraclough · 1790363651 · focus · HN ↗
    > Parallelism without concurrency is useless
    SIMD is parallelism without concurrency.
5. bryanrasmussen · 1790320175 · focus · HN ↗
  in the English vernacular when you deal with something you do something.
6. threethirtytwo · 1790320780 · focus · HN ↗
  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.
  1. gpderetta · 1790325907 · focus · HN ↗
    > True concurrency that is absolutely absent of parallelism is a bit pointless
    It is very important in interactive or realtime systems.
    threethirtytwo · 1790363349 · focus · HN ↗
    I disagree. You don't need concurrency. Say for a video game with many things happening all at once. You think you need concurrency... but you don't.
    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.
    gpderetta · 1790679274 · focus · HN ↗
    how do you implement, for example, a general purpose OS kernel without concurrency?
    For some tasks, the static scheduling you described is appropriate (although you could still consider it a form of concurrency), but it needs complete cooperation between tasks and an overall design.
    But as soon as you need some sort of fairness, responsiveness, and tasks that are not designed for full cooperation if not outright hostile, you need not only concurrency, but full preemption.
    threethirtytwo · 1790861451 · focus · HN ↗
    In the game it seems like everything is concurrent but all of that was built without using concurrency primitives.
    Same thing with the OS. You can build in concurrency without using concurrency primitives because it’s not needed. Right? Let’s say when building an os I had access to spawn go routines in a single threaded context and I used that to build the os. It would be pretty pointless right? You would use a loop here and iterate over the tasks to build the concept of “threading” you wouldn’t need go routines.
    It’s strange to talk about it at this level because what’s going on is your implementing “concurrency” from no concurrency. Is having a loop iterate over tasks really concurrency? I would say no, because people think of concurrency like using a threading primitive. If you didn’t fork or activate a call back or await something you didn’t activate “concurrency”.
    Concurrency is a higher level concept that only exists where primitives for using concurrency exist.
    Thus It makes More sense to frame my argument from the application layer. Without parallelism, concurrency is pointless in the sense that the usage of concurrency primitives given to you by the framework or the OS is pointless.
7. adrian_b · 1790330203 · focus · HN ↗
  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.

Open on Hacker News to reply ↗

Unofficial Hacker News client; not affiliated with Y Combinator.