If the author has not already, I would commend to them a search of the literature (or the relevant blog summaries) for the term "implicit parallelism". This was an academic topic from a few years back (my brain does not do this sort of thing very well but I want to say 10-20 years go) where the hope was that we could just fire some sort of optimization technique at normal code which would automatically extract all the implicit parallelism in the code and parallelize it, resulting in massive essentially-free gains.
In order to do this, the first thing that was done was to analyze existing source code and determine what the maximum amount of implicit parallelism was that was in the code, assuming it was free. This attempt then basically failed right here. Intuitively we all expect that our code has tons of implicitly parallelism that can be exploited. It turns out our intuition is wrong, and the maximum amount of parallelism that was extracted was often in the 2x range, which even if the parallelization was free it was only a marginal improvement.
Moreover, it is also often not something terribly amenable to human optimization either.
A game engine might be the best case scenario for this sort of code, but once you start putting in the coordination costs back into the charts those charts start looking a lot less impressive in practice. I have a sort of rule of thumb that the key to high-performance multithreading is that the cost of the payload of a given bit of coordination overhead needs to be substantially greater than the cost the coordination, and a games engine will not necessarily have that characteristic... it may have lots of tasks to be done in parallel, but if they
One thing that might help is that state space explosion is mainly caused by mutability. Because each mutation potentially creates branching that can be difficult or impossible to statically analyze.
In other words, imperative programming with const is directly transpilable to/from functional programming.
Using modern techniques like higher order methods, scatter-gather arrays (similar to map-reduce), passing by value via copy-on-write, etc, code can be written that works like piping data between unix executables. Everything becomes a spreadsheet basically.
Which also has implications for multiprocessing. When all data is const, many of the async edge cases that we're normally forced to deal with go away. Loosely that means that we can use techniques similar to double buffering to create new mutated copies where only the part that changed was actually copied. The rest of the data can reference one source of truth. In practice, this turns out to most closely approximate optimal algorithms, where the best-effort imperative code may paint itself into a corner because logic design choices get dictated by the realities of the runtime instead of the problem domain itself, so the optimizer loses opportunities to simplify it.
I find that in my daily work, nearly all of my time is spent untangling highly-imperative mutable code. Because I must hold the entire state in my mind when mutable references (mostly to objects) are passed between functions. My higher-order method solutions often end up shorter, more readable, faster, even more efficient, but harder to explain to junior developers. So I would really like a compiler that implicitly converts imperative code like for() loops and references into const/functional code whose intermediate code (i-code) can be reduced to its simplest form.
This is also my main concern about Rust and other mainstream imperative languages like C# and even Javascript, that they encourage bare-hands methods that go away with const/functional code if the user is willing to accept a doubling or more of memory usage. Which becomes less of an issue over time as memory cost decreases.
Edit: I maybe should have said fork-join instead of scatter-gather, but they are related concepts.
I guess you can argue that instruction reordering, SMT/Hyper-threading are already eating the easy wins there. And as you said, it seems like the gains taper off at 2x.
I'm not sure why games would be a good target. They're traditionally very much tied to a single thread, because ironically, passing data to the graphics and display hardware and to multi threaded subroutines like physics all has to be synchronized.
The easiest way to do that without locking a bunch of threads is to let a single thread go as fast as possible through all that main thread work.
If you really want a game focused parallelization framework, look into the Entity Component System pattern. The developer defines the data and mutability flow of various features in the game.
Because the execution ordering is fully known, the frameworks can chunk, schedule, reorder, and fan-out, etc the work across threads with less waiting or cache misses.
"I'm not sure why games would be a good target..."
"If you really want a game focused parallelization framework, look into the Entity Component System pattern."
Exactly that. You can break a lot modern games nicely into a lot of little things being done to discrete entities very quickly. But there the problem is that it's easy for the things to be too small, meaning you don't have a lot of time to be "clever" in the code.
I'm ignoring the GPU and just looking at CPU for this. GPU is in its own world where parallelization is forced on you comprehensively, in a space forced to be amenable to that.
Yeah, ECS is the approach I've heard can get games to have sufficient parallelism. Though only if you are careful about sticking to it properly, and with careful management of the dataflow between systems. I think the main thing is, apart from the difficulty of doing the analysis in the first place, if you're writing the code without thinking about parallelism, you will tend to introduce data dependcies all over the place and changing that structure is very difficult.
This post underscores how traditional imperative language syntax just isn't that well-suited to elegantly expressing parallelism. On the other hand, this is exactly where array languages like APL/J/etc. or array-based frameworks like NumPy/PyTorch/etc. really shine.
The list summation task in the post is just a list reduction, and a reduction can automatically be parallelized for any associative operator. The gory parallelization details in the post are only something the user needs to care about in a purely imperative language that lacks native array operations like reduction. In an array language, the `reduce` function can detect whether the reduction operator is associative and if so, automatically handle the parallelization logic behind-the-scenes. Thus `reduce(values, +)` and `reduce(values, *)` would execute seamlessly without the user needing to explicitly implement the exact subdivision of work. On the other hand, `reduce(values, /)` would run in serial, since division is not associative. Custom binary operators would just need to declare whether they're associative (and possibly commutative, depending on how the parallel scheduler works internally), and they'd be parallelized out-of-the-box.
If you're willing to let go of imperative syntax, Interaction Nets[0] might be interesting to maximize parallelism where possible. I think Bend[1] is probably the most mature implementation of that idea.
Sometimes this approach means that you end up with really compact code where you need to do a lot of research and mental modelling to understand if it actually adds up to things being executed in parallel, and if that is good or not.
The article makes for an interesting technical read, and points to some very important issues, such as debugging in a multicore environment.
Even so, I encourage anyone reading this article to keep in mind that there is a massive amount of work dedicated to software support for multicore parallelism.
For anyone interested in digging deeper into multicore parallelism, I recommend taking a look at the CMU approach to teaching algorithms [1]. They teach parallel programming to second-year undergraduates by default, and the students even write parallel implementations, which can achieve good parallel speedups on a multicore system.
Moreover, they do it using either a parallel functional language or a parallel library in modern C++.
Importantly, they get this far by largely hiding details of exactly how parallel tasks are scheduled across cores. There's a scheduler that does it, much like there's a garbage collector that frees unused memory in a memory-managed language.
My experience is that multi-threading has quite abit of overhead, not necessary from the scheduling, but from the cache misses because now everything is unlikely to be in cache, so a naive parallel for can easily end up consuming a ton of CPU resources, it may indeed finish quicker, but use 5x the overall CPU time to do so.
Then there is the other issue that parallel_for suffers from, the "starter" thread has to finish the loop, and if may end up with nothing to do for some time(like when one of the helper threads get suspended..), or it might end up going off to process some other work, causing the entire loop to take much longer to finish. So parallel_for kinda sucks, and I prefer using dependency graphs when I can.
Interesting - this is the exact problem José Valim cited when creating Elixir: he was working on Rails multi-core performance in 2010 and found that "writing multi-core software, which is software that runs on all cores with Ruby, was not really straightforward."[1] Ruby's GIL meant only one thread executes at a time.
Fleury's arriving at similar conclusions from the C/systems side: make multi-core the default, not an opt-in. Though his approach still requires explicit coordination (LaneIdx(), barriers, range distribution) vs BEAM where the scheduler automatically distributes processes across cores.
Different tradeoffs for different domains, but both are reacting to the same backwards reality where we program single-core-first on multi-core hardware.
There is a deep literature on this in the High Performance Computing (HPC) field, where researchers traditionally needed to design simulations to run on hundreds to thousands of nodes with up to hundreds of CPU threads each. Computation can be defined as dependency graphs at the function or even variable level (depending on how granular you can make your threads). Languages built on top of LLVM or interpreters that expose AST can get you a long way there.
I think the actually interesting non-obvious part starts at "Redesigning Algorithms For Uniform Work Distribution". All the prior stuff done you basically get for free in a functional language that has some thread pool or futures built in, doing FP. The real question is how you write algorithms or parts of programs in a way that they lend themselves to be run in parallel as small units with results that easily merge again (parallel map reduce) or maybe don't even need to be merged again. That is the real difficult part, aside from transforming some mutating program into FP style and having appropriate data structures.
And then of course the heuristics start to become important. How much parallelism, before overhead eats the speedup?
Another question is energy efficiency. Is it more important to finish calculation as quickly as possible, or would it be OK to need some longer time, but in total calculate less, due to less overhead and no/less merging?
The thing I struggle with is that most userland applications simply don't need multiple physical cores from a capacity standpoint.
Proper use of concepts like async/await for IO bound activity is probably the most important thing. There are very few tasks that are truly CPU bound that a typical user is doing all day. Even in the case of gaming you are often GPU bound. You need to fire up things like Factorio, Cities Skylines, etc., to max out a multicore CPU.
Even when I'm writing web backends I am not really thinking about how I can spread my workload across the cores. I just use the same async/await interface and let the compiler, runtime and scheduler figure the annoying shit out for me.
Task.WhenAll tends to be much more applicable than Parallel.ForEach. If the information your code is interacting with doesn't currently reside in the same physical host, use of the latter is almost certainly incorrect.
I find async a terrible way to write interactive apps, because eventually something will take too long, and then suddenly your app jerks. So I have to keep figuring out manually which tasks need sending to a thread pool, or splitting my tasks into smaller and smaller pieces.
I’m obviously doing something wrong, as the rest of the world seems to love async. Do their programs just do no interesting CPU intensive work?
Are you using multiple threads or just a single one? Not sure why your application would "jerk" because something takes long time? If it's in a separate thread, it being async or not shouldn't matter, or if it's doing CPU intensive work or just sleeping.
If I’m using threads for each of my tasks, then why do I need async at all? I find mixing async and threads is messy, because it’s hard to take a lock in async code, as that blocks other async code from running. I’m sure this can be done well, but I failed when I tried.
Probably. In web development it's usually get data, transform data, send data. That's in both directions, client to server and viceversa. Transformations are almost always simple. Native apps maybe do something more client side on average but I won't bet anything more than a cup of coffee on that.
The approach described in this article is to reverse the good old fork/join, but it would only be practical for simple sub tasks or basic CLI tools, not entire programs.
In the end, using this style is almost the same as doing fork/join, except the setup is somewhat hidden.
Those interested can go look at all of the actual code I’ve written using these techniques, and decide for themselves whether or not it’s practical only for “simple sub tasks or basic CLI tools”:
Based on the title I would have assumed that the programming model would be inverted, but it wasn't. What is needed is something akin to the Haskell model where the evaluation order is unspecified while simultaneously allowing mutation. The way to do this would be a Rust style linear type system where you are allowed to acquire exclusive write access to a region in memory, but not be allowed to perform any side effect and all modifications must be returned as if the function was referentially transparent. This is parallel by default, because you actively have to opt into a sequential execution order if you want to perform side effects.
The barriers to this approach are the same old problems with automatic parallelization.
Current hardware assumes a sequential instruction stream with hardware threads and cores and no hardware primitive in the microsecond range to rapidly schedule code to be executed on another core. This means you must split your program into two identical programs that then are managed by the operating system. This kills performance due to excessive amount of synchronization overhead.
The other problem is that even if you have low latency scheduling, you still need to gather a sufficient amount of work for each thread. Too fine grained and you run into synchronization overhead (no matter how good your hardware is), too coarse grained and you won't be able to spread the load onto all the processors.
There is also a third problem that is lurking in the dark and many developers with the exception of the Haskell community are underestimating: Running programs in a suboptimal order can lead to a massive increase in the instantaneous memory usage to the point where the program can no longer run. Think of a program allocating memory for each request, processing it and then deallocating, then allocating again. What if it accepts all requests in parallel? It will first allocate everything, then process everything and then deallocate everything.
The main challenge here is that a lot of languages have historically treated threading as an afterthought. Python is a good example where support was so limited (due to the GIL, which they are only now in the process of removing) that people mostly just didn't bother with it and just tried to orchestrate processes instead. Languages like go and javascript are really good at async stuff but that's mostly all happening on 1 core. You can of course run these with multiple cores but you have only limited control over which core does what.
Java has had threading from v1. Fun fact, it was all green threads in 1.0. Real threads that were able to use a second CPU (if you had one) did not come until 1.1. And they've now come full circle with a way to use "virtual" threads. Which technically is what they started with 30 years ago. Java also went on a journey of doing blocking IO on threads, jumping through a lot of hoops (nio) to introduce non blocking io, and lately rearchitecting the blocking io such that you can (mostly) pretend your blocking io is non blocking via virtual threads.
That's essentially what project Loom enables. Pretty impressive from a technical point of view but it's a bit of a leaky abstraction with some ugly failure modes (e.g. deadlocks if something happens to use the synchronized keyword deep down in some library). If that happens on a single real thread running a lot of virtual threads, the whole thread and all the virtual threads on it are blocked.
There are other languages on the JVM that use a bit higher level abstractions here. I'm mainly familiar with Kotlin's coroutines. But Scala went there before them of course. What I like in Kotlin's take on this is the notion of structured concurrency where jobs fork and join in a context and can be scheduled via dispatchers as a light weight co-routine, a thread pool, or a virtual thread pool (same API, that kind of was the point of Loom). So, it kind of mixes parallelism and concurrency and treats them as conceptually similar.
Structured concurrency is also on the roadmap for Java as I understand it. But a lot of mainstream languages are stuck with more low level or primitive mechanisms; or use completely different approaches for concurrency and paralellism. That's fine for experts using this for systems programming stuff but not necessarily ideal if we are all going to do multi core by default.
IMHO structured concurrency would be a good match for python as well. It's early days with the GIL removal but the threading and multiprocess modules are a bit dated/primitive. Async was added at some point in the 3.x cycle. But doing both async & threading is going to require something beyond what's there currently.
On .NET side, there is dataflow framework based on TPL for structured concurrency, but few people are even aware it exists, it is async/await all over the place nowadays.
What I have found is that even among talented senior engineers there is massive Dunning-Kruger effect when it comes to performant architecture. They don't know how to do it, and they don't know that they don't know how to do it.
I have always wanted reasonable performance (though this
might appear like “performance programming” to a concerning
proportion of the software industry),
This hit me right in the heart.
I'm often the only person on the team who cares about performance, so I am drawn to these performance-related challenges... and it has really hurt my career, because I am then often perceived as some kind of person focused on optimization rather than delivering features.
Like the author I do not focus on performance for performance's sake. Nearly all of the time the right course of action is "do not optimize this piece of code; focus on maintainability and readability instead."
However, sometimes, you really need to design for performance from the beginning.... or you don't have a product.
At my most recent job they were trying to push lots of data through RabbitMQ/Celery for scientific work. This worked for trivial jobs (tens of megabytes) but not for moderate or large ones (hundreds of gigabytes)
To make such a product viable, you really need to consider performance from the start. Celery explicitly tells you not to pass non-trivial amounts of data around: you should be passing pointers to data (database ID's, file paths, S3 URIs, whatever) rather than the actual full-fat data.
The team really struggled with this. Their next proposed solution was "well, okay, we'll store intermediate results in the database and 'optimize' later" Great idea, but this involved 1B+ result objects. Wrong again. You are not serializing 1B+ Python objects, sending them over the wire, and performing 1B+ Redis or Postgres inserts in any reasonable amount of time or memory. Optimize and bulk insert all you want, but that's an absolute dead end.
There aren't a whole lot of options for performantly slinging around hundreds of gigabytes of data. Assuming you can't just run on a monster server with hundreds of GB of RAM (which honestly is often the right answer) you are generally going to be looking at fast on-disk formats like Parquet etc. In any event that's something you really need to design around from the start, not something you sprinkle on at the end.
They're on their second iteration of the architecture right now, and it's slower than the first iteration was. Still no viable product. Shame.
> I'm often the only person on the team who cares about performance, so I am drawn to these performance-related challenges... and it has really hurt my career, because I am then often perceived as some kind of person focused on optimization rather than delivering features.
Pro tip: always turn that kind of thing into a dollar value you can put on your annual review. "My update to X let us use Y fewer EC2 instances, saving us $Z per year." Then it's not some Don Quixote obsession, but a clear fiscal benefit to the company.
I think that software performance is the good kind of vanity metric, speed almost always translate to better end-user experience, but there is a point where it can turn into a pointless rabbit hole.
Some code should be single core; like for example, a frontend UI for a web application... You don't want to be hoarding all of the user's CPU capacity with your frontend.
But I do like implementing my backends as multi-core by default because it forces me to architect the system in a simple way. In many cases, I find it easier to implement a multi-core approach. The code is often more maintainable and secure when you don't assume that state is always available in the current process. It forces a more FP/stateless approach. Or at least it makes you think really hard about what kind of state you want to keep in memory.
In backends, you usually need to solve having concurrent requests from multiple users, regardless if you need it for performance. From that, the step to using multiple cores is sometimes very small.
I.e. you don't usually need to make a for loop parallel, you can just make sure different requests are parallel.
Imagine if your whole system followed this concept, bloating your thread count by 32x or something. Using multiple threads is not free and scheduling between them all eats performance. Not only that each thread will use up extra memory.
If the author has not already, I would commend to them a search of the literature (or the relevant blog summaries) for the term "implicit parallelism". This was an academic topic from a few years back (my brain does not do this sort of thing very well but I want to say 10-20 years go) where the hope was that we could just fire some sort of optimization technique at normal code which would automatically extract all the implicit parallelism in the code and parallelize it, resulting in massive essentially-free gains.
In order to do this, the first thing that was done was to analyze existing source code and determine what the maximum amount of implicit parallelism was that was in the code, assuming it was free. This attempt then basically failed right here. Intuitively we all expect that our code has tons of implicitly parallelism that can be exploited. It turns out our intuition is wrong, and the maximum amount of parallelism that was extracted was often in the 2x range, which even if the parallelization was free it was only a marginal improvement.
Moreover, it is also often not something terribly amenable to human optimization either.
A game engine might be the best case scenario for this sort of code, but once you start putting in the coordination costs back into the charts those charts start looking a lot less impressive in practice. I have a sort of rule of thumb that the key to high-performance multithreading is that the cost of the payload of a given bit of coordination overhead needs to be substantially greater than the cost the coordination, and a games engine will not necessarily have that characteristic... it may have lots of tasks to be done in parallel, but if they
One thing that might help is that state space explosion is mainly caused by mutability. Because each mutation potentially creates branching that can be difficult or impossible to statically analyze.
In other words, imperative programming with const is directly transpilable to/from functional programming.
Using modern techniques like higher order methods, scatter-gather arrays (similar to map-reduce), passing by value via copy-on-write, etc, code can be written that works like piping data between unix executables. Everything becomes a spreadsheet basically.
Which also has implications for multiprocessing. When all data is const, many of the async edge cases that we're normally forced to deal with go away. Loosely that means that we can use techniques similar to double buffering to create new mutated copies where only the part that changed was actually copied. The rest of the data can reference one source of truth. In practice, this turns out to most closely approximate optimal algorithms, where the best-effort imperative code may paint itself into a corner because logic design choices get dictated by the realities of the runtime instead of the problem domain itself, so the optimizer loses opportunities to simplify it.
I find that in my daily work, nearly all of my time is spent untangling highly-imperative mutable code. Because I must hold the entire state in my mind when mutable references (mostly to objects) are passed between functions. My higher-order method solutions often end up shorter, more readable, faster, even more efficient, but harder to explain to junior developers. So I would really like a compiler that implicitly converts imperative code like for() loops and references into const/functional code whose intermediate code (i-code) can be reduced to its simplest form.
This is also my main concern about Rust and other mainstream imperative languages like C# and even Javascript, that they encourage bare-hands methods that go away with const/functional code if the user is willing to accept a doubling or more of memory usage. Which becomes less of an issue over time as memory cost decreases.
Edit: I maybe should have said fork-join instead of scatter-gather, but they are related concepts.
I guess you can argue that instruction reordering, SMT/Hyper-threading are already eating the easy wins there. And as you said, it seems like the gains taper off at 2x.
I'm not sure why games would be a good target. They're traditionally very much tied to a single thread, because ironically, passing data to the graphics and display hardware and to multi threaded subroutines like physics all has to be synchronized.
The easiest way to do that without locking a bunch of threads is to let a single thread go as fast as possible through all that main thread work.
If you really want a game focused parallelization framework, look into the Entity Component System pattern. The developer defines the data and mutability flow of various features in the game.
Because the execution ordering is fully known, the frameworks can chunk, schedule, reorder, and fan-out, etc the work across threads with less waiting or cache misses.
"I'm not sure why games would be a good target..."
"If you really want a game focused parallelization framework, look into the Entity Component System pattern."
Exactly that. You can break a lot modern games nicely into a lot of little things being done to discrete entities very quickly. But there the problem is that it's easy for the things to be too small, meaning you don't have a lot of time to be "clever" in the code.
I'm ignoring the GPU and just looking at CPU for this. GPU is in its own world where parallelization is forced on you comprehensively, in a space forced to be amenable to that.
Yeah, ECS is the approach I've heard can get games to have sufficient parallelism. Though only if you are careful about sticking to it properly, and with careful management of the dataflow between systems. I think the main thing is, apart from the difficulty of doing the analysis in the first place, if you're writing the code without thinking about parallelism, you will tend to introduce data dependcies all over the place and changing that structure is very difficult.
ECS is not a game specific thing. It’s a redrawing of encapsulation boundaries which can be applied to systems broadly.
https://youtube.com/watch?v=wo84LFzx5nI
There is some recent work on this too: https://dl.acm.org/doi/10.1145/3632880
This post underscores how traditional imperative language syntax just isn't that well-suited to elegantly expressing parallelism. On the other hand, this is exactly where array languages like APL/J/etc. or array-based frameworks like NumPy/PyTorch/etc. really shine.
The list summation task in the post is just a list reduction, and a reduction can automatically be parallelized for any associative operator. The gory parallelization details in the post are only something the user needs to care about in a purely imperative language that lacks native array operations like reduction. In an array language, the `reduce` function can detect whether the reduction operator is associative and if so, automatically handle the parallelization logic behind-the-scenes. Thus `reduce(values, +)` and `reduce(values, *)` would execute seamlessly without the user needing to explicitly implement the exact subdivision of work. On the other hand, `reduce(values, /)` would run in serial, since division is not associative. Custom binary operators would just need to declare whether they're associative (and possibly commutative, depending on how the parallel scheduler works internally), and they'd be parallelized out-of-the-box.
If you're willing to let go of imperative syntax, Interaction Nets[0] might be interesting to maximize parallelism where possible. I think Bend[1] is probably the most mature implementation of that idea.
[0]: https://en.wikipedia.org/wiki/Interaction_nets [1]: https://github.com/HigherOrderCO/Bend
Sometimes this approach means that you end up with really compact code where you need to do a lot of research and mental modelling to understand if it actually adds up to things being executed in parallel, and if that is good or not.
The article makes for an interesting technical read, and points to some very important issues, such as debugging in a multicore environment.
Even so, I encourage anyone reading this article to keep in mind that there is a massive amount of work dedicated to software support for multicore parallelism.
For anyone interested in digging deeper into multicore parallelism, I recommend taking a look at the CMU approach to teaching algorithms [1]. They teach parallel programming to second-year undergraduates by default, and the students even write parallel implementations, which can achieve good parallel speedups on a multicore system.
Moreover, they do it using either a parallel functional language or a parallel library in modern C++.
Importantly, they get this far by largely hiding details of exactly how parallel tasks are scheduled across cores. There's a scheduler that does it, much like there's a garbage collector that frees unused memory in a memory-managed language.
[1] https://www.cs.cmu.edu/~15210/docs/book.pdf
Somewhat interesting read, if rather long..
My experience is that multi-threading has quite abit of overhead, not necessary from the scheduling, but from the cache misses because now everything is unlikely to be in cache, so a naive parallel for can easily end up consuming a ton of CPU resources, it may indeed finish quicker, but use 5x the overall CPU time to do so.
Then there is the other issue that parallel_for suffers from, the "starter" thread has to finish the loop, and if may end up with nothing to do for some time(like when one of the helper threads get suspended..), or it might end up going off to process some other work, causing the entire loop to take much longer to finish. So parallel_for kinda sucks, and I prefer using dependency graphs when I can.
Interesting - this is the exact problem José Valim cited when creating Elixir: he was working on Rails multi-core performance in 2010 and found that "writing multi-core software, which is software that runs on all cores with Ruby, was not really straightforward."[1] Ruby's GIL meant only one thread executes at a time.
Fleury's arriving at similar conclusions from the C/systems side: make multi-core the default, not an opt-in. Though his approach still requires explicit coordination (LaneIdx(), barriers, range distribution) vs BEAM where the scheduler automatically distributes processes across cores.
Different tradeoffs for different domains, but both are reacting to the same backwards reality where we program single-core-first on multi-core hardware.
[1] https://www.welcometothejungle.com/en/articles/btc-elixir-jo...
There is a deep literature on this in the High Performance Computing (HPC) field, where researchers traditionally needed to design simulations to run on hundreds to thousands of nodes with up to hundreds of CPU threads each. Computation can be defined as dependency graphs at the function or even variable level (depending on how granular you can make your threads). Languages built on top of LLVM or interpreters that expose AST can get you a long way there.
there's a wealth of papers and theses on these topics from the early-mid 90s, for example
https://link.springer.com/article/10.1007/BF02577777
I think the actually interesting non-obvious part starts at "Redesigning Algorithms For Uniform Work Distribution". All the prior stuff done you basically get for free in a functional language that has some thread pool or futures built in, doing FP. The real question is how you write algorithms or parts of programs in a way that they lend themselves to be run in parallel as small units with results that easily merge again (parallel map reduce) or maybe don't even need to be merged again. That is the real difficult part, aside from transforming some mutating program into FP style and having appropriate data structures.
And then of course the heuristics start to become important. How much parallelism, before overhead eats the speedup?
Another question is energy efficiency. Is it more important to finish calculation as quickly as possible, or would it be OK to need some longer time, but in total calculate less, due to less overhead and no/less merging?
Ryan is the author of the RAD Debugger: https://github.com/EpicGamesExt/raddebugger
The thing I struggle with is that most userland applications simply don't need multiple physical cores from a capacity standpoint.
Proper use of concepts like async/await for IO bound activity is probably the most important thing. There are very few tasks that are truly CPU bound that a typical user is doing all day. Even in the case of gaming you are often GPU bound. You need to fire up things like Factorio, Cities Skylines, etc., to max out a multicore CPU.
Even when I'm writing web backends I am not really thinking about how I can spread my workload across the cores. I just use the same async/await interface and let the compiler, runtime and scheduler figure the annoying shit out for me.
Task.WhenAll tends to be much more applicable than Parallel.ForEach. If the information your code is interacting with doesn't currently reside in the same physical host, use of the latter is almost certainly incorrect.
I find async a terrible way to write interactive apps, because eventually something will take too long, and then suddenly your app jerks. So I have to keep figuring out manually which tasks need sending to a thread pool, or splitting my tasks into smaller and smaller pieces.
I’m obviously doing something wrong, as the rest of the world seems to love async. Do their programs just do no interesting CPU intensive work?
Are you using multiple threads or just a single one? Not sure why your application would "jerk" because something takes long time? If it's in a separate thread, it being async or not shouldn't matter, or if it's doing CPU intensive work or just sleeping.
If I’m using threads for each of my tasks, then why do I need async at all? I find mixing async and threads is messy, because it’s hard to take a lock in async code, as that blocks other async code from running. I’m sure this can be done well, but I failed when I tried.
Probably. In web development it's usually get data, transform data, send data. That's in both directions, client to server and viceversa. Transformations are almost always simple. Native apps maybe do something more client side on average but I won't bet anything more than a cup of coffee on that.
Rest of the world doesn't love async. Just the loud opinionated people.
I think this is less innovative than it seems.
The approach described in this article is to reverse the good old fork/join, but it would only be practical for simple sub tasks or basic CLI tools, not entire programs.
In the end, using this style is almost the same as doing fork/join, except the setup is somewhat hidden.
Those interested can go look at all of the actual code I’ve written using these techniques, and decide for themselves whether or not it’s practical only for “simple sub tasks or basic CLI tools”:
https://github.com/EpicGamesExt/raddebugger/blob/c738768e411...
https://github.com/EpicGamesExt/raddebugger/blob/master/src/...
Posting a tl;dr here might stave off some of dismissive comments based only on only reading the headline.
Based on the title I would have assumed that the programming model would be inverted, but it wasn't. What is needed is something akin to the Haskell model where the evaluation order is unspecified while simultaneously allowing mutation. The way to do this would be a Rust style linear type system where you are allowed to acquire exclusive write access to a region in memory, but not be allowed to perform any side effect and all modifications must be returned as if the function was referentially transparent. This is parallel by default, because you actively have to opt into a sequential execution order if you want to perform side effects.
The barriers to this approach are the same old problems with automatic parallelization.
Current hardware assumes a sequential instruction stream with hardware threads and cores and no hardware primitive in the microsecond range to rapidly schedule code to be executed on another core. This means you must split your program into two identical programs that then are managed by the operating system. This kills performance due to excessive amount of synchronization overhead.
The other problem is that even if you have low latency scheduling, you still need to gather a sufficient amount of work for each thread. Too fine grained and you run into synchronization overhead (no matter how good your hardware is), too coarse grained and you won't be able to spread the load onto all the processors.
There is also a third problem that is lurking in the dark and many developers with the exception of the Haskell community are underestimating: Running programs in a suboptimal order can lead to a massive increase in the instantaneous memory usage to the point where the program can no longer run. Think of a program allocating memory for each request, processing it and then deallocating, then allocating again. What if it accepts all requests in parallel? It will first allocate everything, then process everything and then deallocate everything.
Everyone wants parallelism until mutexes enter the room.
The main challenge here is that a lot of languages have historically treated threading as an afterthought. Python is a good example where support was so limited (due to the GIL, which they are only now in the process of removing) that people mostly just didn't bother with it and just tried to orchestrate processes instead. Languages like go and javascript are really good at async stuff but that's mostly all happening on 1 core. You can of course run these with multiple cores but you have only limited control over which core does what.
Java has had threading from v1. Fun fact, it was all green threads in 1.0. Real threads that were able to use a second CPU (if you had one) did not come until 1.1. And they've now come full circle with a way to use "virtual" threads. Which technically is what they started with 30 years ago. Java also went on a journey of doing blocking IO on threads, jumping through a lot of hoops (nio) to introduce non blocking io, and lately rearchitecting the blocking io such that you can (mostly) pretend your blocking io is non blocking via virtual threads.
That's essentially what project Loom enables. Pretty impressive from a technical point of view but it's a bit of a leaky abstraction with some ugly failure modes (e.g. deadlocks if something happens to use the synchronized keyword deep down in some library). If that happens on a single real thread running a lot of virtual threads, the whole thread and all the virtual threads on it are blocked.
There are other languages on the JVM that use a bit higher level abstractions here. I'm mainly familiar with Kotlin's coroutines. But Scala went there before them of course. What I like in Kotlin's take on this is the notion of structured concurrency where jobs fork and join in a context and can be scheduled via dispatchers as a light weight co-routine, a thread pool, or a virtual thread pool (same API, that kind of was the point of Loom). So, it kind of mixes parallelism and concurrency and treats them as conceptually similar.
Structured concurrency is also on the roadmap for Java as I understand it. But a lot of mainstream languages are stuck with more low level or primitive mechanisms; or use completely different approaches for concurrency and paralellism. That's fine for experts using this for systems programming stuff but not necessarily ideal if we are all going to do multi core by default.
IMHO structured concurrency would be a good match for python as well. It's early days with the GIL removal but the threading and multiprocess modules are a bit dated/primitive. Async was added at some point in the 3.x cycle. But doing both async & threading is going to require something beyond what's there currently.
On .NET side, there is dataflow framework based on TPL for structured concurrency, but few people are even aware it exists, it is async/await all over the place nowadays.
What I have found is that even among talented senior engineers there is massive Dunning-Kruger effect when it comes to performant architecture. They don't know how to do it, and they don't know that they don't know how to do it.
This hit me right in the heart.I'm often the only person on the team who cares about performance, so I am drawn to these performance-related challenges... and it has really hurt my career, because I am then often perceived as some kind of person focused on optimization rather than delivering features.
Like the author I do not focus on performance for performance's sake. Nearly all of the time the right course of action is "do not optimize this piece of code; focus on maintainability and readability instead."
However, sometimes, you really need to design for performance from the beginning.... or you don't have a product.
At my most recent job they were trying to push lots of data through RabbitMQ/Celery for scientific work. This worked for trivial jobs (tens of megabytes) but not for moderate or large ones (hundreds of gigabytes)
To make such a product viable, you really need to consider performance from the start. Celery explicitly tells you not to pass non-trivial amounts of data around: you should be passing pointers to data (database ID's, file paths, S3 URIs, whatever) rather than the actual full-fat data.
The team really struggled with this. Their next proposed solution was "well, okay, we'll store intermediate results in the database and 'optimize' later" Great idea, but this involved 1B+ result objects. Wrong again. You are not serializing 1B+ Python objects, sending them over the wire, and performing 1B+ Redis or Postgres inserts in any reasonable amount of time or memory. Optimize and bulk insert all you want, but that's an absolute dead end.
There aren't a whole lot of options for performantly slinging around hundreds of gigabytes of data. Assuming you can't just run on a monster server with hundreds of GB of RAM (which honestly is often the right answer) you are generally going to be looking at fast on-disk formats like Parquet etc. In any event that's something you really need to design around from the start, not something you sprinkle on at the end.
They're on their second iteration of the architecture right now, and it's slower than the first iteration was. Still no viable product. Shame.
> I'm often the only person on the team who cares about performance, so I am drawn to these performance-related challenges... and it has really hurt my career, because I am then often perceived as some kind of person focused on optimization rather than delivering features.
Pro tip: always turn that kind of thing into a dollar value you can put on your annual review. "My update to X let us use Y fewer EC2 instances, saving us $Z per year." Then it's not some Don Quixote obsession, but a clear fiscal benefit to the company.
I think that software performance is the good kind of vanity metric, speed almost always translate to better end-user experience, but there is a point where it can turn into a pointless rabbit hole.
Some code should be single core; like for example, a frontend UI for a web application... You don't want to be hoarding all of the user's CPU capacity with your frontend.
But I do like implementing my backends as multi-core by default because it forces me to architect the system in a simple way. In many cases, I find it easier to implement a multi-core approach. The code is often more maintainable and secure when you don't assume that state is always available in the current process. It forces a more FP/stateless approach. Or at least it makes you think really hard about what kind of state you want to keep in memory.
In backends, you usually need to solve having concurrent requests from multiple users, regardless if you need it for performance. From that, the step to using multiple cores is sometimes very small.
I.e. you don't usually need to make a for loop parallel, you can just make sure different requests are parallel.
Imagine if your whole system followed this concept, bloating your thread count by 32x or something. Using multiple threads is not free and scheduling between them all eats performance. Not only that each thread will use up extra memory.