▲ 146 points
back
91 comments
1. Try process level I/O, such pipes, sockets, and the like. Have Linux deal with the concurrency problem, not you. (Note: the BASH & background job works in so many cases it ain't funny). Also try fork/join parallelism models like OpenMP. These are all far easier than dipping down to a lower level.
2. Try a mutex
3. If that doesn't work, try adding a condition variable.
4. If that still doesn't work, try an atomic in default sequentially consistent mode or equivalent (ex: Java volatile, InterlockedAdd, and the like). Warning: atomics are very subtle. Definitely have a review with an expert if you are here.
5. If that still doesn't work, consider lock free paradigms. That is, combinations of atomics and memory barriers.
6. If that still doesn't work, publish a paper on your problem lol.
---------
#1 is my most important piece of advice. There was a Blender render I was doing, like 2.6 or something old a few years ago. Blenders parallelism wasn't too good and only utilized 25% of my computer.
So I ran 4 instances of headless Blender. Bam, 100% utilization. Done.
Don't overthink parallelism. It's stupid easy sometimes, as easy as a & on the end of your shell command.
The Oracle database has adopted process-level parallelism, utilizing System V IPC. Threading is used on Windows for performance reasons, but each client gets its own server pid by default on UNIX.
This architecture expresses the original design intentions of "Columbus UNIX."
"CB UNIX was developed to address deficiencies inherent in Research Unix, notably the lack of interprocess communication (IPC) and file locking, considered essential for a database management system... The interprocess communication features developed for CB UNIX were message queues, semaphores and shared memory support. These eventually appeared in mainstream Unix systems starting with System V in 1983, and are now collectively known as System V IPC."
This approach has realized some degree of success.
Postgres also uses a multi process architecture. But I think that turned out to be a mistake for something like a database, on modern systems.
There are other reasons, but the biggest problem is that inter process context switches are considerably more expensive than intra process ones. Far less efficient use of the TLB being a big part of that. It used to be worse before things like process context identifiers, but even with them you're wasting a large portion of the TLB by storing redundant information.
> utilizing System V IPC
Hmm, that's a bit more complex than what I'd put at #1. I'd probably put System V IPC closer to #2 ("use a mutex") levels of complications.
System V Shared memory + Semaphores is definitely "as complicated" as pthread mutexes and semaphores.
But messages, signals, pipes, and other process-level IPC is much simpler. I guess SystemV IPC exists for that shady region "between" the high level stuff, and the complex low-level mutexes / semaphores.
Maybe "1.75", if I were to put it in my list above somewhere. Closer to Mutexes in complexity, but still simpler in some respects. Depends on what bits of System V IPC you use, some bits are easier than others.
---------
The main benefit of processes is that startup and shutdown behavior is very well defined. So something like a pipe, mmap, and other I/O has a defined beginning and end. All sockets are closed() properly, and so forth.
SystemV throws a monkey wrench into that, because the semaphore or shared memory is "owned by Linux", so to speak. So a sem_post() is not necessarily going to be sem_wait(), especially if a process dies in a critical region.
4 is a mistake. The fundamental primitive for multiprocessing is message passing and release/acquire is just that, basically release is send and acquire is receive. If you have to go lock free, there are well-known patterns to communicate from one thread to another, and you should use those instead of just a sequentially consistent atomic.
The best solution, however, is just to split your data and use coarse-grained mutexes.
> and you should use those instead of just a sequentially consistent atomic.
Ehhh... sometimes the best solution to the "bank account parallelism" problem is just:
atomic_int bobs_bank_account_balance;
// Thread#1
bobs_bank_account_balance += 100; // Depositing $100 in a sequentially consistent way.
// In Thread#2
bobs_bank_account_balance -= 100; // Withdrawing $100 in a sequentially consistent way.
If not, then yeah, you move onto more complex paradigms. But always try the dumb and simple solutions first, before trying the harder stuff.
----------
This case is super common, that its even optimized in GPU programming. I've seen atomics like this become optimized into a prefix-sum routine by the compiler.
Yes, this means you can have thousands of GPU-threads / shaders performing atomic adds / subtracts in GPU-space, and the atomic will be surprisingly efficient.
The problem is that this paradigm doesn't always work. It takes skill to know when paradigms fail or succeed, and its sometimes very subtle. (That's why I say: try this, but... speak with an expert when doing so). There might be a subtle race condition. But in the cases where this works, absolutely program in this way.
OpenMP is so dead simple it's insane. Had a class on Parallel Computing (mainly for super computers / scientific computing) and while at the beginning I thought it'd be super hard, in the end it was just slapping #pragma omp parallel on everything
There is also: Try factoring out pure functions and run those in parallel.
This is my favourite technique.
Keep state in messages. Keep functions pure.
There can be drawbacks but for most types of tasks this works very well.
>Try process level I/O, such pipes, sockets, and the like.
This.
> Have Linux deal with the concurrency problem, not you.
Not just Linux. We did this with our Windows app rewrite. IPC with pipes is fast as hell, just works, and it greatly simplified parallelism for us.
But why do you need a seperate process? You can do the same with threads and queues. The only advantage I can think of is sandboxing, i.e. preventing a misbehaving task from taking down your whole app.
Level 0. Use infra like kafka, and eventing to replicas.
I bet someone else has that link at hand where someone does parallel processing in shell with a fracture of the memory and CPU
Related:
“Is Parallel Programming Hard, and, If So, What Can You Do About It?” v2 Is Out - https://news.ycombinator.com/item?id=26537298 - March 2021 (75 comments)
Is parallel programming hard, and, if so, what can you do about it? - https://news.ycombinator.com/item?id=22030928 - Jan 2020 (85 comments)
Is Parallel Programming Hard, and, If So, What Can You Do About It? [pdf] - https://news.ycombinator.com/item?id=9315152 - April 2015 (31 comments)
Is Parallel Programming Hard, And, If So, What Can You Do About It? - https://news.ycombinator.com/item?id=7381877 - March 2014 (26 comments)
Is Parallel Programming Hard, And, If So, What Can You Do About It? - https://news.ycombinator.com/item?id=2784515 - July 2011 (39 comments)
Multi-threaded programming has been of particular interest to me for decades (since my early years programming for OS/2). Whenever I write code, I look for ways to do things in parallel.
My new data management system is highly parallel. I am always finding tasks that take minutes to complete and getting them down to just seconds (when running on multi-core CPUs) by getting multiple threads working together on the same problem.
Just yesterday, I found a task that was taking over 12 minutes to finish (inserting 125 million key/value pairs into a data store) and was able to get it to do the same task in just 37 seconds (running on my 16 core/32 thread CPU) by spinning off multiple threads.
Use an actor model language -- by far the sanest way. Message passing is intuitive to human experience.
1. Elixir (Erlang)
2. Scala/Akka
3. Pony
I am biased because this is my research area, but I have to respectfully disagree. Actor models are awful, and the only reason it's not obvious is because everything else is even more awful.
But if you look at e.g., the recent work on task-based models, you'll see that you can have literally sequential programs that parallelize automatically. No message passing, no synchronization, no data races, no deadlocks. Read your programs as if they're sequential, and you immediately understand their semantics. Some of these systems are able to scale to thousands of nodes.
An interesting example of this is cuNumeric, which allows you to take sequential Python programs that use NumPy, and by changing one line (the import statement), run automatically on clusters of GPUs. It is 100% pure awesomeness.
https://github.com/nv-legate/cunumeric
(I don't work on cuNumeric, but I do work on the runtime framework that cuNumeric uses.)
>the recent work on task-based models, you'll see that you can have literally sequential programs that parallelize automatically
Can you provide some details please? I am not quite clear what you mean.
While not for clusters AFAICT, Rayon (Rust lib) auto parallizes loops. It is used in Programming Rust by O'Reilly in a great example. Forgive the RESF response please.
It is a pity Concurrent ML didn't take off. F# has a great library called Hopac that implements it, but it is 50 times less popular than its closest competitor Rx.
Also seconding that other post. Actor models and async concurrency are only useful if you need to send messages between machines, but otherwise you want to use synchronous concurrency as it is easier to deal with.
It’s not always easy, things can get confusing when you start sending messages to yourself
Came here to say just this. In particular, _immutable_ message passing.
4. D
Section 2.3.3 is definitely worth reading carefully.
I've both increased efficiency and removed bugs by rewriting a system that someone thought the only way to make faster was to add more threads, when optimising algorithms and data layout resulted in much more gains.
There are three ways to 'scale' a computer program. The first is optimizing the algorithms and data structures which is discussed in the section you noted. Make your code run as fast as possible using a single thread even when the amount of data you are processing gets extremely large. The second is taking advantage of better hardware (more cores, bigger L2 and L3 caches, SSDs, etc.) which includes spinning off threads to do single tasks in parallel. The third is a 'scale out' architecture where the application is spread out across multiple machines.
With all the cloud infrastructure available today, too many programmers focus on the third option (which can mask inefficiencies in the first two) when they could get as good or better performance at a cheaper price by focusing on the other options instead.
Its interesting that while Moore's law saturated many years ago there is still no parallel programming style that hits some sweet spot between productivity and performance for multicore cpus (and thus gets more adopted for mainstream development)
Its not clear if this means there is not such "optimum" or simply it is not something anybody cares about
people focused a lot on gpus but thats not easy either
That's because there's really two conflicting goals to parallel programming.
1. Maximizing utilization of CPUs / GPUs / compute resources-- The "obvious" goal. You want as much code running in parallel as possible to accomplish some task faster.
2. Maximizing the utilization of SSDs / Hard Drives / Ethernet / I/O as much as possible -- Less obvious, but in I/O constrained problems, its not so much the CPU you're focused on, as much as it is the I/O you're trying to maximize.
Processes and threads are classically designed to solve #2, _not_ #1. Yes, we abuse processes and threads to make #1 go faster, but it really wasn't their original point.
When you perform a read() on a socket / Hard drive / whatever, it makes sense to "swap out" the process and find something else to do. This is optimizing #2, trying to run as many processes as possible to maximize the number of requests going to your I/O centers.
In contrast, if you're trying to perform a dense matrix-multiplication on AVX512 or GPU space or whatever, all this task-switching is completely useless and processes are detrimental to your goal, not beneficial. Its completely the wrong tool to use.
Bonus points: 4x GPUs working with a CPU (say, 64-core CPU) will run into both #1 and #2 problems simultaneously. Hurrah!
------------
Of course, today there's event driven code, coroutines, Golang threads, fibers, epoll... lots of tools to help you out on these tasks. But as the computer world grows more nuanced, it grows more complex. Its harder to figure out which tool to reach for in your toolbox.
Maybe there should be an IDE plugin that after you run your code once it makes a list of recommendations for parallelisation, including the possibilities "please rewrite this in language X and style Y" or "forget about it"
> Processes and threads are classically designed to solve #2, _not_ #1.
Do you have a source for this?
But there is a dominant parallel programming style. In fact, it actually boils down to one of two styles:
* Here's a list of things. Run the same bit on code for every item in the list of things. (Slight adjustment is necessary if you need to something like a reduction tree).
* Here's a graph of tasks, with dependencies expressed as edges. Run as much as you can in parallel.
What makes parallel programming difficult is two main things. First, the way to achieve parallelism is highly dependent on the size of the tasks, with designs for one scale being horribly bad ideas at different scales. Second, there's a pretty severe penalty when communication between tasks is involved (and, notably, two tasks both wanting to read the same data can cause pain, not just read/write or write/write conflicts).
The first type is what people used to call "embarrassingly parallel". While it should be easy to have this solved by now across the board (after all most cpus are multicore now), arguably it is still not quite trivial or uniform, depending on which language or stack one works with.
The second case where there is data exchange between tasks is indeed the real challenge as the problem is basically open ended. The MPI approach conceptually can handle many cases but is maybe too much overhead to be the default programming paradigm. Which brings back to the question of low hanging opportunities. Eg He mentions in the book SQL and I think inner loop vectorisation is another example. But those are rather special 'graphs'
This is exactly what the BEAM and OTP do for Erlang/Elixir IMO.
In order to have parallel programming work effectively, you have to enforce a set of rules that ensures it always works reliably. You can’t add it on after the fact and that’s why it’s such a hard problem outside of the BEAM.
I dont know much at all about erlang but if it cracked this shouldnt it be more prominent in HPC type applications? Is there some other tradeoff?
I think it's because shared memory concurrency is easy to start on in lots of popular languages. But it doesn't take long until you're in a tricky mess of locks.
Actor style based on explicit communication and no shared memory is a lot easier to work with (IMHO), but it's not as easy to get started on because it's not as simple as pthread_create and go.
No shared memory will also mean that actor style is slower-than-single-thread-slow, when the "message-size to processing-per-actor ratio" is not right.
Actors and message passing is great for problems where it fits and worse than useless where it doesn't
Parallel programs are often way less efficient. Sure, communication is expensive and parallelism requires communication. On the other hand, they're often 2x less efficient or more. Poor scaling means you go beyond X-number of core/nodes (often a lower number than you'd like) and 90, 95, 99 % of the extra CPU power you throw at the application is burnt up in pure overhead.
I have a small project in Ruby to explore different concurrency and parallelism strategies: https://github.com/rickhull/miner_mover
I use OS threads + non-blocking IO with concurrent package for shared data in Java. The performance is incredible.
If I wanted to get a little more performance per watt I would probably rewrite it in C with arrays of atomic variables.
But you need a VM with GC to be able to be productive during the day and sleep at night, so probably not...
Now, if you could reduce the overhead of OS threads by using lightweight processes instead ... Wait a moment, isn't that what Erlang does? Well, project Lumen might help you out on the JVM at some point.
With NIO there is no OS overhead like context switches because you only need one thread per core as long as everything is async.
Erlang is single threaded unless you copy memory between threads.
The only step left for Java to implement (after io_uring file stuff) is user-space networking.
Its isnt hard but you need to change your programming standpoint. To write parallel code you need to think more about data alignment, dependency and flow. Its quite different than typical object/behaviour oriented programming.
Funny. I've been reading this for the past six months and just finished today.
Life is weird.
And, did you like it? I guess you did, otherwise you wouldn't waste six months on it. But can you share in a few words what you think of this book?
Silly me for thinking that people wouldn't care about my opinion.
It's a great book. Some things could be better, of course, but it's a free book, so the quality to price ratio is off the charts, and not just because it's free. I would have happily paid $75 for it, maybe more.
That said, it's a book that requires you to care about the Linux kernel, where the author's experience is. If that's a problem, then you won't get as much out of it.
The book is best used as a reference after reading through it once. I would do a medium-deep read the first time. This will tell you the concepts you need to look up later, what techniques exist, etc.
This is because the book delves into detail about various techniques to get concurrency. The philosophy is to do the easiest thing that works, which is great, but it does mean it talks about details. Thus, it's best as a reference later after absorbing the surface level.
However, that medium-deep read is still necessary for you to know what you need to look for later when you need details.
I hope that helps.
I use ZIO (http://zio.dev) for Scala which makes parallel programming trivial.
Wraps different styles of asynchronicity e.g. callbacks, futures, fibers into one coherent model. And has excellent resource management so you can be sure that when you are forking a task that it will always clean up after itself.
Have yet to see anything that comes close whilst still being practical i.e. you can leverage the very large ecosystem of Java libraries.
Try using libthread on plan9, no locks.
My solution is to only solve problems that are embarrassingly parallel, like graphics (one pixel = one thread) or physics simulations (one object = one thread), and escape the pain of synchronisation.
I use channels to send messages between threads in Nim. It works quite well.