Is parallel programming hard, and, if so, what can you do about it?
mirrors.edge.kernel.org
mirrors.edge.kernel.org
The former and what this book is about deals with the problem of parallelizaing a single sequential program. There usually is strong interaction or dependencies between elements and progress needs synchronization. E.g. timestep iterations in real-time simulations that need synchronization with data communication after each timestep. These simulation also tend to get way to big to be run on a single machine, lest a single thread, and get scaled up to millions of cores/threads in supercomputers.
Concurrent programming is what most developers working with the internet are more familiar with. You have mostly independent tasks that you want to run concurrently. "A concurrent system is one where a computation can advance without waiting for all other computations to complete." [2] E.g. nginx serving thousands of user requests at the same time.
The problem domains have a lot of overlap on the basics (e.g. threading), however the focus is very different. Things like synchronization (mutex, barriers), cache locality and memory bandwith & latency play a central role in parallel programming, while concurrent programming focuses more on the engineering challenge of distributing independent tasks across multiple threads or machines.
> A.6 What is the Difference Between “Concurrent” and “Parallel”?
> From a classic computing perspective, “concurrent” and “parallel” are clearly synonyms. However, this has not stopped many people from drawing distinctions between the two, and it turns out that these distinctions can be understood from a couple of different perspectives.
> The first perspective treats “parallel” as an abbreviation for “data parallel”, and treats “concurrent” as pretty much everything else. From this perspective, in parallel computing, each partition of the overall problem can proceed completely independently, with no communication with other partitions. In this case, little or no coordination among partitions is required. In contrast, concurrent computing might well have tight interdependencies, in the form of contended locks, transactions, or other synchronization mechanisms.
> This of course begs the question of why such a distinction matters, which brings us to the second perspective, that of the underlying scheduler. Schedulers come in a wide range of complexities and capabilities, and as a rough rule of thumb, the more tightly and irregularly a set oparallel processes communicate, the higher the level of sophistication required from the scheduler. As such, parallel computing’s avoidance of interdependencies means that parallel-computing programs run well on the least-capable schedulers. In fact, a pure parallel-computing program can run successfully after being arbitrarily subdivided and interleaved onto a uniprocessor. In contrast, concurrent computing programs might well require extreme subtlety on the part of the scheduler.
I do think the differentation make sense from a perspective of problem classes, as also evident from the comments here. Running independent problems in parallel to better utilize hardware ressources is very different from running problems in parallel in timesteps that have strong dependencies in regards to progress of the overall computation. And that's not a problem of the scheduler, but a much more general concept.
It doesn't sound to me like the author has the whole web service parallelism/concurrency in mind that is very apparent in the comments here.
This applies to all sorts of ambiguous terms used very generously in the witchcraft of "applied computer science". Other examples include "object-oriented programming", "statically- or dynamically-typed language", "interpreted language", "dependency inversion", a bunch of "software patterns" and more. All this terminology is meaningless because there's never a way to tell if a language is object-oriented or not, if it's statically-typed or not and so on. Parallel vs concurrent is just one of those things where emotional attachment won over any attempt at rational thinking.
It's not about spectrum. It's about inability of a lot of people to critically assess information coming from otherwise reputable sources.
Also, what reputable sources are you even talking about? That is also such an unwarranted personal attack you've attached as well.
For example, even python which is dynamically typed, is strongly typed also, so you now have to not just know the distinction between statically typed and dynamically typed but also between strong and weak. Then stray away slightly from vanilla python interpreter/runtime to any of the other flavors and you now have to reason about compile time, runtime, interpretation time, bytecode, interop with jvm etc. So there is a point that the language is a way of expressing something and the implementation is where the devilish details lie. You can argue jython isn't python or whatever and that's all well and good, but you can't really discuss all of this with other reasonable humans without getting into the details of implementation. Sure, for a leetcode level of understanding it doesn't matter much, but try to do something sufficiently complicated like build an os extension in python that interops with your c++ based api and you'll have to think about the implementation of the projections, and then port it to arm and you'll have to think about it all over again.
concurrent is about logical independence, parallel is about physical independence
Anyways. The way I see it used today, it's applied to language runtimes incapable or severely crippled when it comes to parallel / concurrent execution. Eg. Python, JavaScript etc. In such environments programmers are offered a mechanism that has many downsides of parallel / concurrent programming (eg. unpredictable order of execution) without the benefits of parallel / concurrent programming (ie. nothing actually happens at the same time, or only sleep is possible at the same time etc.)
I feel like this distinction, while a nonsense idea at its core, became so popular due to the popularity of language runtimes with disabilities and their users needing to validate their worth by adding features to their languages their runtimes are inherently incapable of implementing.
Similar situation happened with ML-style types. Python, for example, works very poorly with this add-on, but the desire to match features of other languages led Python developers to add those types anyways. Similarly, TypeScript and a bunch of similar languages, especially in Web.
Parallelism is a physical thing, concurrency is a logical thing.
Fundamentally the difficulty is all about synchronization. People can try to split hairs and say there are two terms for two different things but ultimately it doesn't matter because the underlying problem is the same.
Yes it does. If you have two threads which (for whatever reason) are sharing memory and they can be run in an arbitrary order, you have to deal with memory synchronization. If it's a single core machine, you still need to synchronize your memory access. Mutexes and semaphores predate systems with multiple processors.
Parallelism is a physical thing, concurrency is a logical thing.
So by your own definition, wouldn't multi-core concurrency be parallelism?
The point I'm trying to make is down to brass tacks, single core concurrency is a lot simpler than multi core concurrency, because you don't need any hardware cooperation.
Concurrency isn’t necessarily parallel.
There are still plenty of single core systems out there running concurrent software, even today, for example embedded systems.
The claim you repeat is meaningless. A program is either parallel / concurrent or not. The situation you describe (when there's a single processor core) isn't parallel or concurrent. In some sense, it emulates concurrent / parallel execution because it imitates the unpredictable ordering of code execution, which sure has its uses... but the whole point of dealing with this unpredictable ordering is that we actually want parallelism / concurrency. The emulation on its own is worthless.
a program which is not written as concurrent can never be executed as parallel
a program which is written as concurrent can be executed as parallel, or not
> The situation you describe (when there's a single processor core) isn't parallel or concurrent.
a program running on a single core can never be parallel, but it can be concurrent
concurrent is a logical property, parallel is a physical property
Unless of course you're running multiple independent instances of it, each with different parameters, which I gather is a pretty common way of running long running CPU- intensive operations on large data sets. Presumably there's often some final separate step that may be needed to combine the results once they're all finished, which if run manually obviates any concurrency concerns at the software level.
("a program [as executed]" is a single instance (process) of a binary)
If only these "Gophers" knew anything about computing history!
Even in modern times, we have something like the first generation raspberry pi zero, it has a single ARM core, and it multitasks fine.
It not nonsense. In C or C++ lots of code can be made parallel using OpenMP and inserting some #pragma statements above for loops. This does not work for things like running a UI in one thread and some other work in another thread, perhaps displaying results as they are found. These are quite different types of parallelism.
I mean, great... you discovered a somewhat useful library: OpenMP... so what? How does this factoid affect the validity of the definition of code parallelism?
The terminology used might be terrible since they're originally synonyms. Differentiating between the two is very useful though.
With just concurrency, you can have a system, e.g. an event processing system, where each event happens, is processed to completion, and then the next event is processed. Events can be of different types and can have different handlers. Events can be arrive (or be delivered) in different orders. The context-switching points are known (in this case, the beginning and end of event processing). As such, any computation between context switching points appears to happen atomically (i.e. no partial update, no internal reordering).
Parallelism is a different model.
There are no well-defined, limited set of interaction points between computations. A computation could literally be interrupted at any machine-level instruction and another computation start running. Suddenly, the number of possible interactions is huge--almost beyond comprehension. Locks, transactions, or other synchronization mechanisms are necessary in order to create larger atomic regions (and defend against race conditions). Worse, with weak memory models, which most modern multi-core hardware have, means that interleaving alone is not enough to explain the possible interactions between threads. It's possible with weak memory models that writes from another computation appear in different orders to different threads. Weak memory models make avoiding race conditions absolutely paramount.
What are you modeling?
The way you use "concurrency" it's indistinguishable from code without any signs of parallelism. From your "definition", concurrency is just any code. Such definitions are called "trivial" if you don't want to offend the author, and "worthless" if you are honest.
Your attempt at defining "parallelism" is even worse... You start by calling it undefined, and then proceed throwing poorly connected verbs and nouns...
Let me make it simple:
Parallel or concurrent code is code that doesn't require time interval between instructions (this is in contrast to Von Neumann model, where it's necessary to have a non-zero time span between instructions).
Here. That's it. No "but hardware", no "there are no well-defined" etc.
I wouldn't normally put such a fine point on it, but in this thread you've managed to make a lot of noise and calls lots of things "nonsense". If you're after emotional responses and heated discussion, that's tantamount to trolling, and you should stop.
a program which is parallel actively demonstrates multiple paths of execution during runtime -- it is a physical property of the program as executed
tl;dr: every parallel program is concurrent, not every concurrent program is parallel
Not necessarily true. In many cases of concurrent programming, you don’t actually care about performance, you care about multiple different things happening seemingly at the same time (sure faster is nice, but not stuttering or freezing is more important). For example on a single core multitasking system (either in the past or on an embedded system today), you want multiple different tasks all running together, but this is achieved by giving them all a little chunk of execution one after the other — time slicing. The tasks are running concurrently, they all make progress together, but they share the same single thread of execution, they don’t happen in parallel. Yet one doesn’t block another, which is the important thing here.
I mean may e you “want” maximum performance, but that’s not what’s most important. Not having one task block another is what’s important.
Parallel programming is pretty much always about making things faster, by running then in parallel at the same time. The main benefit of doing that is that they both complete faster.
That is an entirely different set of problems than having to deal with a computation that has close dependencies and now you need synchronization and communication to progress the compuation. You don't only have to think about how to synchronize your computation, you also have to think about how to distribute your data to begin with to minimize the need for synchronization. An entire set of problems that just don't exist in the former case.
To pick up a word you used: In one case you have many independent tasks and you want to run them as quickly as possible. In the other case you have a single task and you think about how to split that up to make it faster.
The distinction matters because the focus is different: they’re different topics. With concurrent programming you deal with synchronisation and topics like lock-freedom and wait-freedom. In parallel programming the main focus is about work distribution and scheduling to process it faster.
Concurrency was the kind of thing worried about in OS design or Unix programming styles whether on a time-sharing system or some small scale multi-processing system. Coordination of heterogeneous sequential programs on some shared resources.
Parallelism was the topic of high-performance computing with combined use of many hardware resources to accelerate a single algorithm.
Of course these are simplifying abstractions, and real systems can get into the murky gray area that is both concurrent and parallel.
From the developer's perspective it's a massive upside to not have to manage low-level details and just define how the event loop will call their code.
Any modern web browser has plenty of parallel execution behind the scenes, but the developer (and user) will just see concurrency which is much simpler to reason about. The order of execution doesn't matter if the things being executed aren't dependent. What matters more is that there's only one thread to think about. If they are dependent they shouldn't have been parallelized in the first place, so they're not.
The distinction I learned was: any time you have multiple logical threads of execution you have concurrency, any time you have multiple computations happening simultaneously, you have parallelism.
Multithreaded programming on a single core computer is concurrent, but not parallel. Vector processing is parallel, but not concurrent.
I like this distinction as it also splits the different problem domains quite well. And I don't think it contradicts my definition as much as you might think.
When you have an embarrassingly parallel program you do not have to deal with the problems that come from data dependencies and synchronization of your simultaenously running compuations on different threads/machines. You do not really have to think about your computation running in parallel, but just about how to put them into different execution environments to run them concurrently. So you end up doing "concurrent programming".
When you do not have an embarrassingly parallel program, you still use the base concepts of running something concurrently (e.g. threads), but now your main focus shifts on how the multiple compuations can happen simultaneously. Now you end up doing "parallel programming" or parallel computation.
In the end, the terminolgy here is less than ideal. My main point was that some kind of distinction matters as TFA clearly discusses different topics from what many people think about from a web dev perspective (e.g. async, futures, etc.)
Wouldn’t it be nice if we could come up with a better word for this that doesn’t literally overlap with ‘parallel’ and doesn’t need to deviate so far from it’s dictionary definition?
Personally I think of JavaScript as ‘asynchronous’, and I know this as a term of art means a programming model, but it’s a lot easier to see that async can be done with a single thread and isn’t necessarily parallel, right?
What problems exist that generate events or commands faster than 500 million per second? This is potentially the upper bar for 1 thread if you are clever enough.
Latency is the real thing you want to get away from. Adding more than one CPU into the mix screws up the hottest possible path by ~2 orders of magnitude. God forbid you have to wait on the GPU or network. If you have to talk to those targets, it had better be worth the trip.
AAA games, Google search, Weather simulation, etc? I mean it depends on what level of granularity you’re talking about, but many problems have a great deal going on under the hood and need to be multi threaded.
The cases you noted are great examples of things that do justify going across the PCIe bus or to another datacenter.
If individual threads were dramatically slower the architecture would get unpleasant by necessity. Consider the abomination that is out of order execution on a modern CPU.
Each channel can be mixed in parallel, 44,100 samples per second is not much per channel and mixing isn't difficult.
Also most can be cached and don't need to be mixed or filtered in real time because they haven't been changed from the last play.
Same for searches. Difficulty there is size of search space, not searches coming in. Right?
However, once you get into simulations you have billions (or multiple orders of magnitude more) elements interacting with each other. When you simulate a wave every element depends on it's neighbors and the finer the granularity the more accurate your simulation (in theory at least).
That is all to say that millions of events still feels like a lot. I am not shocked to know it can and does happen.
So the game would have to be programmed so that conveyor belts and train tracks can be placed at region boundaries and that there is a hidden buffer to teleport things between regions. Now you need an algorithm to divide your graph to both minimize the imbalance between the number of nodes in the subgraph but also to minimize the edges between subgraphs.
It would take some careful work to ensure that items didn't get duplicated or lost at junctions, and a back-pressure system for conveyor belt queues. Electrical signals would be transmitted at some speed limit.
In large systems, parallel / concurrent applications are the baseline. If you have to replicate your data as its being generated into geographically separate location there's no way you can do it in a single thread...
few programs are CPU-bound, most programs are bottlenecked on I/O waits like these
Typically, some of the tasks run on different cores. The LMAX disruptor is designed such that there is no huge delay due to cache coherency. It is slow to sync the cache of one core to the cache of another core when both cores write to the same address in RAM. The LMAX disruptor is designed that each memory location is (mostly) written to by at most thread/core.
How is the LMAX disrupter relevant for programs with 1 core?
It is not relevant outside the problem area of needing to communicate between threads. The #1 case I use it for is MPSC where I have something like an AspNetCore/TCP frontend and a custom database / event processor / rules engine that it needs to talk to.
Think about something like speeding up a compiler or a web server or a spreadsheet. There's no 50-line function that you can spend a few hours optimising and speed up the whole thing.
That's part of the reason why Python programs (except maths heavy stuff like ML) tend to be so slow despite everyone saying "just write your hot code in C". You can't because there is no hot code.
These days Python is being used for everything, even things without hot loops as you note. Yet the advice persists.
I teach parallel programming to graduates and the first exercise we give them is a sequential optimization for exactly that reason. Think about if your algorithm is efficient before thinking about all the challenges that come with parallelization.
You have to be very careful about what 'big enough' means. In practice, Strassen multiplication is not faster than the naive algorithm until you get to the point where you're multiplying matrices with hundreds of rows/columns. Additionally, naive matrix multiplication is well suited to GPUs, while Strassen multiplication on the GPU requires temporary buffers and multiple jobs and sequencing and whatnot.
As a general rule, matrix multiplication with complexity better than the naive algorithm should probably not be used. Do naive matrix multiplication on the CPU. If you need it to be faster, do naive matrix multiplication on the GPU. If you need it to be faster, the numerical stability of your problem has probably already come a gutser and will get worse if you switch to Strassen or any of the other asymptotically faster algorithms.
And the algorithms faster than Strassen? Forget about it. After Strassen multiplication was invented, about a dozen or so other algorithms came along, slowly reducing that O(n^2.8) to about O(n^2.37188) or so. (most recently in 2022; this is still an area of active research) The problem is that for any of these algorithms to be faster than Strassen, you need matrices that are larger than what you can keep in memory. There is no big enough input that will fit in the RAM of a modern computer. One estimate I've heard is that if you convert every atom in the observable universe into one bit of RAM, and you use that RAM to multiply two 10^38 by 10^38 matrices to get a third 10^38 by 10^38 matrix, you're still better off using the O(n^2.8) Strassen multiplication instead of the state of the art O(n^2.37188) algorithm. The constant slowdown in the other algorithms really are that bad.
Sure, this might be the case from a theoretical point of view (as per definition) but this completely disregards the hidden constants that come to light when actually implementing an algorithm. There's a reason why for instance a state-of-the-art matrix multiplication algorithm [0] can be completely useless in practice: The input data will never become large enough in order to amortize the introduced overhead.
On Windows, OSX and iOS the OS userland already implements general, and relatively easy to use, thread pools. On Windows, see CreateThreadpoolWork, WaitForThreadpoolWorkCallbacks, etc. It’s easier to use threads with locks while someone else is managing these threads. On Apple, the pool is called “grand central dispatch” and does pretty much the same thing.
Modern Windows kernel supports interesting synchronization APIs like WaitOnAddress, WakeByAddressSingle which allow to implement locks without the complexity or performance overhead of maintaining special synchronization objects.
Linux kernel implements performant and scalable message queues, see mq_overview(7). And it has synchronization objects like eventfd() and pidfd_open() which allow to integrate locks or other things into poll/epoll based event loops.
https://github.com/apple/swift-corelibs-libdispatch
Here’s a simple echo server:
https://github.com/williamcotton/c_playground/blob/master/sr...
Here’s a simple multithreaded database pool:
https://github.com/williamcotton/express-c/blob/master/src/d...
dispatch_group can do waits without blocking threads, but asynchronicity is overrated, and dispatch's design makes it easy to overdo. Having default global concurrent queues was probably a mistake.
Swift concurrency is a more modern design here.
I spotted a bug in it though which may manifest itself depending on platform.
Posix message queues (the `mq_*` functions) are much slower than optimized shared memory queues using typical atomics and have semantics that are unexpected to most (they persist like files after process termination, because of what they are designed to be used for, they have system level limits on size and size of items, etc).
A simple benchmark vs rust's `std::sync::mpsc` queue shows `std::sync::mpsc` is 28.6 times faster when using 1 producer and 1 consumer, and is 37.32 times faster with 2 producers and 1 consumer.
As a historical note, Rust used to have green threads but they were abandoned a long time ago. This is a good talk about both the differences between different forms of concurrency/async and Rusts history with them: https://www.infoq.com/presentations/rust-2019/ (includes a transcript)
I have no idea about Tokyo. I don’t program Rust, and the feedback I read about async/await was mixed.
Functional programming better aligns with the requirements, which is how you arrive at Erlang and Elixir. Every map() function can be trivially replaced with the concurrent cmap(), because the side effects that would make it non-trivial are impossible to express.
Given that Moore's law as it applied to single threaded performance is dead and in the ground, it makes a lot of sense to start paying more attention to systems that treat concurrency as more than an afterthought.
So that again keeps green threads (and thus mass concurrency without parallelism) in the niche category.
go programs definitely saturate modern server-class CPUs
[0] https://en.m.wikipedia.org/wiki/Message_Passing_Interface
[0] https://www.nas.nasa.gov/SC22/research/project12.html
[1] https://www.sciencedirect.com/science/article/abs/pii/S00219...
It is common knowledge in the field to optimize a simulation for the largest number of cores it can efficiently use, so simulation cases are not just blindly thrown more cores without a justification given by the scalability. Your initial claim that parallelization doesn't get you much is flawed, parallelization is the only thing that enables scalable engineering analysis.
I've gotten more reading and cleaning done in the last week than I have in maybe years.
I'm moving this week and won't have internet for a few days. I look forward to the relative break.
I wonder if an ISP could forge a product like noon till 7 (or even 4am till 9am) when few people use bandwidth. Perhaps combined with a very slow connection the rest of the day.
If you're interested in concurrent programming this book won't give you much. The topics focus on the parallelization of a sequential algorithm and go into detail about things like synchronization (locking, barriers), important HW details (like caches and CPU pipelining) and algorithmic approaches. Imagine a weather simulation and not concurrent requests to a web server.
My assessment is that the latter is nowhere near “solved” (hesitant to use that word because craft unlike eg proofs is about trade offs), in the sense that concurrency differs a lot across our tools (languages, runtimes etc) and it even differs quite substantially within the main paradigms, like coroutines, async, green threads, native threading etc.
If we compare with other advanced language features like say memory management, we’ve come much further, imo (GC, RAII, ref counting, manual are pretty much all well understood as well as the stack-heap duality, adopted basically universally). With concurrency we have, if we’re being generous, merely mutices as the common ground. Even “simple” notification mechanisms and ownership transfer across tasks would vary greatly across languages and often be quite contrived.
If you want a good overview, I'd recommend reading the roadmap in section 1.1. Also, I know a 600 page book (400 pages if you exclude appendixes) is a bit long, but I really enjoyed both the material presented and the style in which it was written. Hopefully that makes the length feel a bit less intimidating.
I did a quick flip through and realized that I'm never going to be doing low level multithreading, so I don't need to deal with OS layer stuff. There were some other ideas too, might be worth flipping to relevant areas.
Heck, if I do end up using it, I'll likely read a summary when I'm dealing with it.
There are some ideas that I havent heard of, which was alright, but again, since my current language(python) handles it and I am used to doing multithreading using those libraries, I don't get a ton of value out of reading the fundamentals. (opportunity cost)
99% of mine, is responding to closures for network events and device responses.
When you do that, synchronizing is one way to deal with things (wait for the other thing to finish), or completion testing (is the thing ready for the next step?). Basically, they are the same thing.
You are also not always guaranteed a standard context, but modern languages make it easy to hook to one. In the "old days," we used to use RefCons (Reference Context hooks).
Then we just have to sync our knowledge.
Go with goroutines and channels
Clojure with core.async
F# with Hopac
It would be a very interesting project to roll your own in C# using Microsoft Robotics Studio's CCR (Coordination and Concurrency Runtime) (though I speculate those are buffered channels by default).
Concurrency means that you can have multiple tasks running in the same time period, Parallelism means you have multiple tasks running at the same time.
The most obvious demonstration of this is that you can (and many languages do) have single threaded concurrency.
I did some grad course work in parallel programming and there's really no way to not make it "brutal", because to really do it in a way that increases performance you need to really understand some low-level performance issues.
Parallelism is used to solve CPU bound problems. Obvious examples are things like efficient matrix multiplication. However this is what make Parallel programming so hard. There's a lot of nuance working effectively with multiple cores/threads that makes even "embarrassingly parallel" problems sometimes fail to see benefits from naive parallel programming (for example if your parallel solution requires something as little as more frequent visits to l2 cache instead of l1 you can see performance degradation).
So parallelism and concurrency ultimately solve two very different domains of problems.
I agree however they do ultimateively solve two very different domains of problems and there is a lot of confusion going on here.
On a side note: matrix multiplcation is generally not a CPU bound problem, but a memory bound one.
Looking into the future, parallelism is one of the only remaining techniques for scaling classical computing. Processors have stopped getting faster. Instead, they're getting fatter (more cores).
Parallel computing cares about what should be parallel, i.e., actually implementing parallelism. For most programmers, this job can (and probably should) be left to the scheduler, whose job is to translate concurrency into reasonably sane parallelism.
The scheduler comes with overhead, though, that can be avoided with hand-spun parallelism. I like to think about it like manual memory management: for most programs and programmers, using a garbage collector that a memory management expert wrote is easier/better than manually allocating and freeing memory, but there are performance gains to be had if you don't.
I think most "application" type programs would benefit from being able to manage state in terms of higher level transactional operations and let their runtime take care of serializing and avoiding deadlock and race conditions. Developers in those spaces have come to rely on garbage collection in their runtimes, I see no reason why they couldn't come to also rely on a fully isolated MVCC transaction model (and only get access to non-transactional memory in exceptional circumstances). Bonus points if said transactions tie back to the persistent RDBMS transaction as well.
There are too many minefields in manual lock management and the tools remain fairly low level. Ownership management in languages like Rust helps, following a discipline like an actor/CSP approach helps, etc. but in the end if there's shared state and there's parallel work, there's potential for trouble.
https://joeduffyblog.com/2010/01/03/a-brief-retrospective-on...
> What do we do with atomic blocks that do not simply consist of pure memory reads and writes? (In other words, the majority of blocks of code written today.)
If you could just get programmers to stop mutating, you could get STM (which incidentally would give you back the ability to mutate)
It features "speculative execution" which practically is STM. Known names like Tim Sweeney and Simon Peyton Jones are behind that.
I don't necessarily want the whole memory model of the runtime or VM to offer transactions necessarily. What I think is a good idea is to offer an overall framework -- within which higher level applications can be written -- that brings transactional semantics with it. Basically a set of collections and data transformation and communications and process coordination libraries that work in harmony with an underlying MVCC storage layer -- rather than baking a transactional atomic keyword down to the syntactical level of the language or the memory model of the VM/runtime.
Put another way: I wouldn't necessarily give users the STM facilities. I would use lower level STM facilities to construct a higher level toolkit, and only expose that. Basically an RDBMS in-process -- without the SQL language boundary -- to be frank.
Yes, users could escape it easily, and start doing inconsistent things. But that's on them, same as any other framework.
Provide the pattern and tools in a nice coherent box and don't try to take over the whole world.
We're already there! You don't need an STM framework in order to leave consistency up to the user.
While the primary benefit is in thinking "these things should happen together or not at all" rather than thinking about locks, there's another feature I always forget about, which is retrying.
Retrying let's you 'nope' out of a transaction, and try again as soon as something changes without busy-waiting.
We were building a web-based email client, and PG didn’t like the idea. He pulled our team aside during one of the batch-wide Tues night dinners and suggested we pivot to building something that could take single threaded programs and quickly/easily make them multi-threaded.
No one on our team knew anything about threading (none of us had even graduated college). So we kept working on the email client, now defunct.
PG brought us in a back room where the Stripe founders were waiting (I think they were speaking that night). We were brainstorming ideas with them, and one of the brothers recommended we build something having to do with phones and calling people (don’t remember the idea anymore).
PG was not very happy when he heard we weren’t going to pivot and kept on working on a new email client :)
An automatically parallelizing compiler that works in general is one of the holy grails of computer science. They have been extensively researched for decades and we have little to show for it. If anyone managed to make one it would instantly render the entire computer industry obsolete.
We have systems that work in specialized cases with a whole lot of manual intervention. Even then, the executable is often less efficient than the serial version.
But I’m sure the hoped-for result was just another one of those specialized tools, specialized for some Y Combinator niche. Which is also probably an unrealistic idea for a team that isn’t interested in that sort of thing, but at least isn’t totally ridiculously stupid.
Even if threads are cheap, you still have to decide when to parallelize something. If the section is short enough, splitting up the work will make your program slower because you have to wait for the new thread to be scheduled and then for the launching thread to be scheduled.
These are just the problems to get you started. They are not big barriers but they are big enough to make it not be the default.
The next problem is dynamic runtime behaviour. A parallel program can exhibit far more weird behaviours due to the nature of interleaved execution. This means that you will want a strong ownership model for your data and so far only Rust does it competently. Instanced locks are difficult to get right. Static locks are almost trivial but only if you can guarantee that your critical section never calls code that invokes the same lock. Recursive locks are a bad idea but not using them means you need to have two sets of methods. One is the public synchronized method that library users call and the other is the private unsynchronized method that actually does most of the work. It's very ugly to work with locks.
The other problem is that a lot of problems are genuinely difficult to parallelize. It is better to parallelize hierarchically where each hierarchy is still single threaded. This way you can maintain the illusion of mostly single threaded code. The alternative often requires a bespoke architecture. There are hardly any generalized solutions. You need to be an expert at parallel programming.
> I no longer remember what was so difficult about it
You or (your libraries) probably stopped mutating things. No mutation means you can rely on values you used several lines ago.
This is the perennial HN discussion whenever the word 'functional' comes up. "But x=x+1 is simple to teach to beginners" is the rallying cry. Well, this is why not.
Also, > the need for locks
This goes away if you don't mutate.
The observation, which I don't think I saw being made twenty years ago (I could be wrong) is that you shouldn't mix these two things. No multiple references with mutation. In theory you can safely do so in serial programs if you were careful enough, in practice you won't be careful enough and we should write fewer serial programs than we do, so why not reject this outright.
Rust is one particular (and notably successful) attempt to make a programming language about this big idea, but it's the idea in Val and several other newer languages. There are a lot of unknowns about the best way to approach this, but "Just pretend it's not important" is not a correct answer.
Regarding your point, shared xor mutable is nice, but databases are an example of a shared mutable (and even concurrent!) yet safe resource, so other models are possible.
Yes, it is possible because programmers have accepted the bargain that they must write purely-functional SQL.
Then the db is able to decide how best to optimise/apply/retry/copy-on-write/abort as necessary.
If SQL allowed you to directly mutate things, it would break everything. You couldn't 'LIMIT 10' if your loop might want to increment some data in row 40082.
Previous discussions:-
https://news.ycombinator.com/item?id=22030928 (2020)
https://news.ycombinator.com/item?id=34859102 HN discussion (2023)
Then there is the physics engine view to all things. Data is just sand washing against the shoreline of parallel computation instances and interaction, is just sticking these dataparticles together, taking them out of the general flow to be interacted on in unison, carrying the resolution authority within them as long as they are "clumbed" together. Data is just particles, the programs interacting on it are just a limited number of program cells, traversing it and interaction clumps it together, making the processing of it slower, but also centralized to computation node. A centralized node, processing a huge clump of interacting data, even throws a sort of "relativity" shadow, as other, smaller, non interacting data, is processed faster and leaping ahead in the interactions.
I am really interested in parallel, asynchronous, multithreading, coroutine, futures programming so it's what I spend my days thinking about and blogging about it. I hope you sense my excitement in this comment about this topic. I'm looking for a programming model that parallelises easily and doesn't require much effort, so this PDF seems relevant to me. I really should try be a user of languages like Erlang, Inko, Pony and Go but I am too interested in the mechanism of these languages!
I am also learning from Erlang and Go, nginx and LMAX disruptor.
I don't focus on number crunching parallelisation, I let libraries and frameworks parallelise matrix multiplication such as BLAS. I'm interested in rote system parallelisation architecture. For example, PHP and nodejs is not a parallel language but how PHP is hosted in FastCGI processes means it can be executed multiple times by nginx so it is in effect parallel across requests. Unfortunately PHP and nodejs cannot create threads or use a thread pool within a request.
I want heavy CPU tasks of a request to not block other requests or the event loop and heavy IO requests to not block the event loop. I am a pre-beginner in Rust but I think you can use Rayon for CPU heavy tasks and Tokio for async IO parallelisation.
Here's a system diagram that I'm thinking about lately: https://github.com/samsquire/ideas5/blob/main/NonblockingRun...
The design is that we have three groupings of thread types. The application starts up some application threads which are not associated with a request, these service multiconsumer multiproducer thread safe ringbuffers in lightweight threads with a Go-erlang-like lightweight process runtime. (My simple lightweight thread runtime is https://github.com/samsquire/preemptible-thread) We also multiplex multiple network clients sockets across a set number of kernel threads which I call control threads. Their responsibility is to dispatch work to a work stealing thread pool ASAP which has its own group of threads. So we pay a thread synchronization cost ONCE per IO which is the dispatch from the control thread to a thread pool thread. (Presumably this is fast, because the thread pool threads are all looping on a submission queue)
We split all IO and CPU tasks into two halves: submit and handle reply. I assume you can use liburing or epoll in the control threads. The same with CPU tasks and use ringbuffers to communicate between threads. We can always serve client's requests because we're never blocked on handling someone else's request. The control thread is always unblocked.
I think this article is good regarding Python's asyncio story: https://charlesleifer.com/blog/asyncio/
I think the best multithreaded architecture is to never rely on synchronization, because it doesn't scale. Try and separate your task so the work is more like a tree than a graph, so that you don't need to communicate between branches. You can shard your data and work independently and merge at the end, similar to mapreduce.
That's not parallel programming though. Parallell programming deals with the parallelization of a single sequential algorithm or program (e.g. weather simulation) across multiple threads, CPU or machines, usually with the requirement of real time synchronization. When you paralellize independent tasks (async, coroutines, futures) a whole lot of problems just don't exist and others go more into focus.
I'm not working on novel parallel algorithms that solve computer science problems, I am interested in parallelism as a general principle for coordinating systems activities.
When I get time to delve into parallel algorithms then I'll work on that, at the moment there's a lot of work in just cordinating and scheduling parallel tasks.
I am also interested in this area of database internals such as parallel query execution and concurrency control and wait/lockfree algorithms
I feel it is complicated and wide space and we deceive ourselves to think we know everything or hubris, which I expressly avoid doing.
I have dealt with concurrency in PHP (good times with Laravel Horizon) in a couple of different ways and in NodeJS (never feels good, to me). The BEAM has some great primitives for concurrency and the book mentioned above walks the reader through them at a good pace. I read it cover to cover and it really enriched my mental model of how to use concurrency and async.
[1] https://pragprog.com/titles/sgdpelixir/concurrent-data-proce...
Still a great read for people primary interested in GPGPU though, since a lot of knowledge transfers well.
- Arrays of 64 byte Structures with C. (client)
- Java. (server)
Everything else is not atomic.
- Arrays of 64 byte Structures with C. (client)
All you need for parallelism is to spawn threads and give each thread a range of an array to work on. You don't need each element to be atomic because you aren't synchronizing on each element.
What makes you think you need specific data and a specific language?
- Java. (server)
This makes even less sense. A language doesn't matter and how it's used doesn't matter.
Where did you get this idea? Can you link something?
Everything else is not atomic.
I think you don't understand what parallelism means. Read about openMP, it is very simple.
I suspect any language wanting to offer this as the default behavior for `for` loops will end up being a language like Java, Erlang, or SmallTalk - the language spec includes a "virtual" runtime that allows it to assume such flexibility in behavior, and capacity to "create/run threads/processes" that otherwise requires an OS (as in, you start leaving the perimeter of a programming language).
But if each OS-scheduled CPU was really a cluster of for instance 1 fast + 64 slow cores then it could have special instructions to split a low-level loop on these slow cores and to facilitate blocking and rejoining back into a single stream. A 'parallel branch' instruction could take index, limit, and estimated instruction count and the CPU itself could decide whether to run it in a single fast stream or in parallel on slow cores.
There's some technical challenges like the size of a register file (so probably uninterruptible), but this may be where we're going since there's diminishing returns from making a single CPU faster and there's lots of opportunity for parallel processing that GPUs are too clumsy for.
Still, deciding where to run such things are not trivial, the time it takes to decide what would be faster could actually be more than the time it takes to just run it.
And this is assuming that the code in the loop is thread safe, otherwise you will summon every concurrency bug on the planet.