Pessimism about parallelism
esr.ibiblio.org
esr.ibiblio.org
Parallelizing our software is mostly a question of investment at this point. In my experience, there isn't a lot of software that wouldn't benefit from CPU parallelism in some way or another. The bigger issues are (a) that a lot of software simply doesn't prioritize performance, for both good and bad reasons, and (b) that a lot of foundational software has been in maintenance mode for years and there isn't enough interest or funding to improve it.
The good news is that using all cores is one of the top things you can do to get work done sooner, and as such we probably will see investment happen. My work is pretty different from AAA games, but still parallelizing a big task is not infrequently lower hanging fruit than tuning the code for one unit of work. We've paid for the whole machine (or cluster) so we might as well use it.
Browsers are an interesting instance because they have a bunch of heterogeneous tasks with weird dependencies between them, and are huge, old codebases where you have to be careful adding threading, but they still manage to make real use of threads (e.g. running expensive compilers, decoding images, rendering, etc.).
Suspect you're saying ~this re: "foundational software", but as languages, tools, and libraries keep adapting to modern hardware, I think using parallelism confidently will become easier and we'll see more of it. Ecosystems change slowly but they do change.
ESR's claim about locality particularly seems iffy. A common task with very poor locality but useful parallel implementations is garbage collection: it thrashes your CPUs' caches, but thrashing all of them at once can still get it done sooner.
Many recent GCs don't actually try to use all your cores because they run concurrent with your app and want to leave a lot of capacity for it, but Go 1.4's GC (the last non-concurrent version) used all the cores it could, and V8's Orinico does in some phases too.
How much of that utilization is doing useful work is important.
A breakdown of how that budget is spent would be a productive addition to this discussion.
rendering a web page is a special case
lot of special cases!
I know for my day job software development machine the point of diminishing returns is definitely at 4 cores (or maybe more, haven't tried yet!) 2 cores is terrible.
However when I scale down and am NOT running two databases and a web server along with visual studio, then 2 cores is fine. Also when I do that I am making a game that makes effective use of all the cores, and it wasn't hard (granted it is another special case)
This just isn't true - for some algorithms we are simply not aware of any way to effectively parallelise. No amount of investment is going to suddenly come up with a solution to that problem.
We're just lucky that games are easy to parallelise.
That just means we need new algorithms, different habits, and languages which make conncurency more accessible.
The vast majority of research into algorithms and computer science in general over the past 75 yeas has focused on single threaded linear computation.
I think the thing we can do right now is spin up threads as often as possible. It should be your default approach when writing a new function to consider how to make it functionally pure. If you can, spin that out into a new thread (Depending on the overhead in your language). Even If you can't make it functionally pure there still a good chance you can write it in a way that prevents a potential deadlock or race condition.
My argument is basically this:
1) we will find more algorithms that are better at exploiting concurrent resources.
2) as programmers we need to change our default behavior from writing linear programs and then trying to make them take advantage of concurrent hardware to writing concurrent solutions at every level of application design by default from the ground up.
With parallelism in particular, this is quite easy. Haskell's accelerate library allows you to write code using maps/folds which then runs on multiple CPU cores or a GPU (J does something similar but it's CPU-bound).
It turns out that maps and fold can already handle quite a lot.
With concurrency - well, concurrency is hard, and many basic data structures are in fact quite recent!
I can think of hundreds of inherently sequential algorithms we are using daily but nevertheless use an insignificant amount of CPU time.
Let's take binary tree traversal. Assuming a 100ns access penalty for every pointer this means we'd need a binary tree with a depth of 10000000 and this means it would have 2^10000000 elements to saturate a modern CPU core with a single query per second. That's quite a large dataset and I'm sure that even if you converted the entire universe into RAM you could never store that much data.
Haskell also has some nice qualities, though one has to use something like accelerate or repa.
That's concurrency, no?
The software is written using concurrency techniques such as threads, that work on both multicore machines and machines with a single core.
That's not right. GPUs do pretty well at tasks that have poor locality compared to CPUs, as long as there's a lot of parallelism to be exploited -- see for example ray tracing.
The reason for this is that CPUs depend on their large caches, which are useless when there is little locality, while GPUs simply switch to another warp while data is being loaded from memory, and they have much higher memory bandwidth anyway.
Also, GPUs are distinctively not systolic arrays. Hennesy's "Computer Architecture: a quantitative approach" has a good primer on Single instruction Multiple Threads (SIMT) architectures typically seen in GPUs.
Good catch, as pointed out by wikipedia:
"They are sometimes classified as multiple-instruction single-data (MISD) architectures under Flynn's taxonomy, but this classification is questionable because a strong argument can be made to distinguish systolic arrays from any of Flynn's four categories: SISD, SIMD, MISD, MIMD"
Despite what Nvidia would have you believe, a lot of VFX rendering is done on CPUs, not GPUs, and this is one of the reasons why. (For example, last I heard, Pixar does all their render work on Intel Xeons.)
The borrow checker basically doesn't even have a concept of a single-threaded program. Everything you write in Rust is required to be thread-safe. This makes Rust appear more difficult, but it's just front-loading the effort required to make the whole program thread-safe (which to me felt nearly impossible for non-trivial C programs). From there you can sprinkle Rayon all over the place, send async work over channels, etc.
The piece I'm missing is "Amdahl's-law-aware" profiler that would show not just where any code spends time, but only where the unparallelized bottlenecks spend time.
https://blog.gopheracademy.com/advent-2017/go-execution-trac...
There might already be similar tools for Rust; I know less about what's available there.
(Go folks also added some tools for tracing across RPCs, which is less relevant to what you said but just kinda independently neat: https://medium.com/observability/debugging-latency-in-go-1-1...)
Either you have a poor understanding of thread safety or Rust has solved the halting problem.
Consider the following example: you have a single global mutex, and every read/write to memory is bracketed by a lock/unlock of that mutex. The resulting code, while horribly inefficient, is technically free of data races, but that does not really give you anything interesting in terms of thread safety.
Any useful definition of thread safety requires that you can reason about program behavior in the presence of concurrency.
One such approach is the idea of interference-freedom introduced by Owicki and Gries [1]. Somewhat simplified, assuming that you have a thread A with precondition P and postcondition Q, i.e. the Hoare triple { P } A { Q }, a thread B does not interfere with thread A if the parallel execution of A and B, given the same precondition P we can still prove Q ({ P } A || B { Q }), for any interleaving of A and B.
Obviously, proving such a property is undecidable in the general case. In practice, we therefore limit ourselves to simpler models that are easier to reason about by constraining how threads can interact with one another (e.g. transactions, actor model), but even then, you can still end up with situations that are undecidable in the general case.
In practice, Rust has `unsafe {}` escape hatch that allows building of abstractions (like mutexes) for the safe majority of Rust using contained bits of as-safe-as-C code where necessary.
Theoretically yeah, but there's a lot of practical gain to be had even with that example. Other languages won't tell you if you forgot to use the mutex somewhere.
Languages like C++ and D treat this as a library design challenge, not a core language feature. Look at std::lock_guard, for example.
The thread safety is built using Send/Sync traits, which libraries for threading and synchronization primitives, atomics, etc. implement accordingly.
First, I was talking about useful definitions of thread safety. That was language-agnostic, not related to Rust. And if absence of data races were all that Rust guaranteed, then Rust indeed wouldn't be much of a help. What Rust actually does is require you to be (fairly) explicit about threads interacting with each other, which is a much stronger type of guarantee [1]. Rust comes with a default setting derived from the general shared-xor-mutable principle that threads don't mess with each other's data without permission, which makes it easier to reason about thread interaction.
Second, the OP was comparing Rust to actor languages. Actor languages also don't have data races and don't require mutexes (because the memory spaces of actors are disjoint and actors themselves are sequential). In fact, actor languages provide even stronger guarantees, as actors can only interact with each other at well-defined points. "Fearless concurrency" hails back to the 1970s. It is not a new invention, nor is it unique to Rust. It is great that Rust supports it, but I really wish people would stop talking about it being novel and unique.
[1] Which is not to say that Rust's choices don't come with tradeoffs, but then, in the area of concurrency, you cannot realistically avoid tradeoffs. In Rust's case, as with actors, the primary tradeoff is performance for safety.
What I really wish people would learn from Actors is that even if your programming language prevents trivial race conditions over shared memory or message passing primitives, none of that guarantees anything about the behavior of the system you are building once you start to compose those primitives. Gul Agha's dissertation was really eye-opening.
Are there any practical / commonly used programming languages in which you can prove thread safety with that approach for significant programs? You mention it can be undecidable even with constraints like the actor model (Erlang). Maybe you just mean edge cases not encountered in real systems, but I'm guessing it's not practical. Why do you say it's useful?
I see accidental data races a lot more than any other kind of race condition; I'd guesstimate that avoiding them gets you 90+% of the way to thread safety. Yes, you can release and reacquire the mutex in inappropriate spots (i.e., ones during which invariants are broken), but in a typical program there are a lot fewer mutexes acquisitions/releases than data accesses in general, so it's a lot more practical to audit for this. I feel a lot better with a program that has no data races than one which has no guarantees at all (most languages).
Likewise, deadlocks are also a concern, but I'd say there are relatively few spots in your code where you have to be concerned about them. (For starters, they only occur with multiple contended resources (usually mutexes), whereas data race problems can and do happen with zero or one mutexes all the time) And the behavior when they happen is more consistent and far less subtle. The latter is similar reasoning to how people say that a panic is less worrisome than undefined behavior.
Concurrency and parallelism has been what I've been working on for several decades. I have, inter alia, implemented concurrency mechanisms with strong safety guarantees for more than one language (among them two relying on shared memory [1, 2]), so yes, I think I have a pretty good idea what I'm talking about.
> I see accidental data races a lot more than any other kind of race condition;
And I didn't say otherwise. Freedom from data races (with the caveat that there are also benign data races that you sometimes want to exploit and that you want language mechanisms for) is more or less a necessary byproduct of most schemes to reason about concurrency; but on its own, its woefully inadequate for the reasons that I talked about.
> I'd guesstimate that avoiding them gets you 90+% of the way to thread safety.
If this were the case, then you'd practically never have any problem with thread safety in actor languages; that is not the case.
A simple and extremely common pattern where freedom from data races falls short is the following:
if (obj->condition())
obj->action();
> Are there any practical / commonly used programming languages in which you can prove thread safety with that approach for significant programs?
First, I am not saying that being able to formally prove properties is a necessary element of concurrency (though there are systems that do exactly that, but that's beyond the scope of what I mentioned). But even when you're reasoning about program behavior informally, that relies on the same principles. Your code assumes some precondition and wants to arrive at a postcondition and you have to be sure that other threads don't muck up what your code is trying to accomplish.
The larger point is that with just the absence of data races, we still have a combinatorial explosion of ways that threads could interact with one another: most useful concurrency schemes (including Rust's) function by cutting down on that combinatorial explosion and limiting ways in which threads can interact with one another (and thus, possibly, in undesirable ways).
[1] https://link.springer.com/chapter/10.1007/11424529_17
[2] https://onlinelibrary.wiley.com/doi/full/10.1002/cpe.3746
[3] E.g. https://dl.acm.org/citation.cfm?doid=1297027.1297042; while the paper is about software transactional memory, the mechanism extends to critical regions in general.
I prefer it for concurrency, but it's not a panacea. In particular, laziness is necessary for efficient immutable data structures, and immutable structures are a nice way to avoid some of the problems inherent in writing concurrent programs.
There are known algorithms/data structures where you either have to use immutability or laziness in order to get an efficient implementation.
I wouldn't put it like that. You can (and almost certainly do) have data structures on the stack or heap that are not thread-safe (by which I mean they suffer from data races if accessed from multiple threads).
I'd say that Rust enforces that stuff that's available to multiple threads be thread-safe. That covers global variables (which are always assumed to be available to multiple threads; maybe this is what you mean by "doesn't even have a concept of a single-threaded program"). It also covers stuff passed to another thread in other ways (passed to the thread at construction time, sent over a channel, etc).
Rust describes thread safety with two traits: "Sync" (a type for which it is safe to share references between threads) and "Send" (a type that can safely be transferred across thread boundaries). The book talks more about these here: https://doc.rust-lang.org/book/ch16-04-extensible-concurrenc...
The neat thing is these are automatically implemented when doing so is safe[1], and the compiler requires them at the key spots. You don't need to rely on some half-trusted comment or other manual annotation declaring something as thread-safe or audit all the using code if you want to make something no longer thread-safe; code just won't compile if it's expecting something to be thread-safe that isn't.
The compiler tells you what the problem is, and in most cases, fixing it is simple: wrap something in a Mutex, replace a Rc with Arc (non-atomic reference count with an atomic one), replace a RefCell with a Mutex or RwLock. If it compiles and doesn't say "unsafe", there's no data race.
This is what people mean when they say Rust has "fearless concurrency". I'm not aware of any other language that guarantees lack of data races without giving up mutability or shared state.
(There are limits to the fearlessness, of course. You can still have data races by doing something dumb in code marked "unsafe". And Rust doesn't protect you against deadlocks at all, so you need to consider lock ordering and such as you would in most other languages. You can still have contention problems because your locking is too coarse. etc.)
[1] when you're doing something unsafe you might need to manually declare something as Send and/or Sync because the compiler can't figure that on its own that doing so is safe. I've encountered this when doing FFI; another case would be when implementing synchronization primitives. Most code shouldn't have to deal with this.
Programming languages often have some level of support for necessary primitives, such as goroutines, but then hide them behind an unsuitable scheduler. On the machines where latency-hiding was originally developed as an architecture (notably Tera's MTA), optimal scheduling was done by the hardware itself which had perfect visibility into relative latency with no overhead. Things are not that simple on x86/ARM. If you want to implement effective latency-hiding, you'll be implementing an equivalent scheduler in software, and often by inference because sometimes the only way to know the true latency of something is by doing it. I don't think it is that difficult but schedule design is not something most programmers know how to do well -- it is magic buried in operating systems and libraries. Nonetheless, you see more examples of this kind of software design for performance reasons.
There are very few real-world applications that are so serial that latency-hiding is not effective at using all available cores, particularly in the server realm where the workload is inherently concurrent. The original target application for latency-hiding architectures was scaling graph analytics, which are often not amenable to more classical embarrassing parallelism.
That said, the benefits of scaling up runtime game performance are diminishing as asset costs increasingly dominate the discussion: the extra scene detail comes with a price to the production cycle, and that may be what breaks the games-graphics-tech alliance before any fundamental limits to the technology are reached.
Halide: a language for fast, portable computation on images and tensors http://halide-lang.org/
While it's true that most of the time a 4-core or more machine has idle cores, I'm not convinced this is a problem.
Yes, most of the time spent on a modern computer consists of doing things that aren't particularly computationally expensive. But our perception of the speed of a personal computer isn't based on some kind of steady state performance on batch jobs, I think that worst-case latency is a lot closer to how we perceive the speed of a computer. Of course, in specialized domains like HPC the steady state performance on batch jobs is important, but this article seems to be discussing personal computers.
Even if they come up rarely, you still hit computational bottlenecks at times when latency is important. Whether it's some bloated web page, some big Excel computation, a compilation for us programmers, or the like, there are plenty of times where you hit some kind of bottleneck in which you can make effective use of all of your cores, so even if 99% of the time you have idle cores, that 1% of the time can shape your perception of how fast your computer is.
And the fact that most of your CPUs are idle most of the time doesn't mean you are wasting power. Modern CPU cores conserve power when idle, via P-States (frequency scaling) and C-States (turning off idle cores).
It is probably true that there is a lot of software out there which could take better advantage of parallelism but doesn't, in some cases due to performance not being prioritized, in some cases due to some essential complexity of parallelizing the code, but also in many cases due to accidental complexity of parallelizing code due to unsafe languages like C and C++ that can make it quite difficult to refactor serial code into parallel without worrying about introducing significant bugs.
Multi cores could have other advantages than parallelism. On mobile, if there's 8 cores, and if the device/os is able to figure out the current load, and based on that turn off up to 7 of those 8 cores, the energy savings could be significant on the CPU side. (Depending on how much energy CPU uses compared to the radio or screen on a smartphone)
Another obvious advantage as pointed as the end of the article is individual processes running independent work next to each other. Such embarrassingly parallel work can keep all the CPU busy pretty well.
That's only true at the very high end, where you have so much data that it's not all physically close and transport time is relevant.
With the reality of stalled clock speeds and multi-core systems, people are finding the parallelism in many applications. Scaling really appears to be coming to an end - if not at 7nm then at 5 (or what they'll call 5). I don't think we're going to meaningfully exhaust our ability to exploit parallelism before then. They're not used in every application but they are used by enough things that we should have them.
The cores are not being wasted because we don't know how to parallelize computations - as evident by the scientific software run for high performance computing applications, which scales upto million cores.
Business decisions are responsible for these wastages. For example, many engineering software are licensed per core - so if you are using it on 16 cores, it costs A LOT more than using it on 4 cores. In some cases the licensing costs of the engineering software are higher than the cost of the hardware. So no one cares if few cores are wasted.
The use cases are much broader than gaming. I'd argue any kind of creative work involving graphics, audio, video, already utilizes any amount of CPU you can throw at it. Also, software like Firefox is leveraging multiple cores with their ongoing Rust rewrite of Firefox. I tend to use multiple CPUs when running software builds. There is a lot UI code that these days is written asynchronously from the ground up; meaning utilizing multiple CPUs is less of a big deal than it used to be.
But yes, you need langauges, frameworks, drivers, operating systems, etc. that can facilitate this. I'd say there is quite bit of room for improvement here still.
That does not change the fact that some software does need more, and people are wise to dimension their computers taking the largest usual load into account, not the average one.
That said, the point about memory locality is good. It is just not as important as the author makes - data tends to have locality, even physics pushes it there. But the point about non-parallelizable algorithms isn't good; who cares about the property of your algorithm? If the problems allow for parallelism (with local data), dump the algorithm and get one that scales.
Also interestingly, the authors does bother to link the limits to the von Neumann architecture, but didn't think about using the extra cores to JIT-compile the binaries into some other architecture...
It seems like this ought to be true but in practice it's not, though the problem appears to be more due to developers not paying enough attention to performance than to fundamental limitations of the hardware. I can think of very few applications that I use on a day to day basis that do not have multiple areas where I wish they performed better.
On the other side, high performance computing demands more computational power, and the only promising path forward (at this time) is parallelism. I'm not motivated by optimism, but by pragmatism.
As a sidenote, I don't understand this section:
> We look at computing for graphics, neural nets, signal processing, and Bitcoin mining, and we see a pattern: parallelizing algorithms work best on hardware that is (a) specifically designed to execute them, and (b) can’t do anything else!
The same hardware is used for all of these things, and it was only (arguably) designed specifically for graphics (and even there "specific" is not certain).
Don't forget the FPGA's, esp if bundled with CPU. They still partly work by parallelism but I think reconfigurable hardware deserves its own mention.
None of these problems have anything to do with parallelism. But everything with "shared memory multithreading". There are plenty of sane concurrency models implementations out there. Which brings me to this part:
> But the truth is, we don’t really know what the “right” language primitives are for parallelism on von-Neuman-architecture computers.
We do know what the right language primitives are. Well, at least if you follow concurrency and distributed systems, where it's not even an important question anymore, you just stick to actor model as a default choice and stop caring about these things.
These have nothing to do with shared memory multithreading. You can easily have all of these with shared nothing distributed systems.
>and insidious data corruption due to subtly unsafe orders of operation
I'll give you this though.
It's a bit contrived, because obviously the name implies that it's sequential. But yeah, sometimes that's precisely what you need.
That said, it's easy enough to get effectively correct ordering by reassembling the results in the correct order as the workers finish.
In practice, what we are interested in in particular is both a reproducible preorder and postorder ordering based on the DFS traversal, which is of use in other algorithms (such as Tarjan's algorithm for strongly connected components [1]).
This problem is P-complete and under the assumption that P != NC and under the parallelization assumptions underlying NC [3], is difficult to parallelize.
So far, this is not very controversial, but in practice, NC does not properly reflect what we think of as "inherently sequential"; especially the assumption of a polynomial number of processors is a bit odd when you're not dealing with hardware circuits.
On top of that, we often aren't interested in all possible graphs, but only specific types of graphs.
As a consequence, yes, lexicographic DFS can be parallelized for many use cases or in a fashion that we care about. As a simple example, lexicographic DFS for trees can be parallelized efficiently.
More generally, lexicographic DFS is already extremely fast if we have an existing in-memory representation of the graph (linear in the size of the representation with a small constant factor). It may take longer to construct the graph than to calculate a depth-first ordering of the vertices. In this case, we may not want to parallelize the DFS algorithm as such, but organize the construction of the graph so that we can run DFS in parallel with the construction.
This is of particular interest if we can't fit the graph in memory or if computing the edges of the graph is expensive. For example, we may not be able to parallelize the search as such, but we can instead parallelize the neighbor expansion.
The biggest issue here is that lexicographic DFS is a rather specialized problem in the family of graph search problems and many, many interesting types of graph searches can be parallelized just fine. For example, we can easily construct a parallel version of the A* algorithm; it will not explore the graph in the precisely same order, but as we are dealing with an algorithm guided by a heuristic, this is rarely a problem in practice.
[1] Though we have, contra ESR, parallel algorithms for strongly connected components in directed graphs that do not require a DFS ordering for the entire graph [2].
[2] See the previous work section of this thesis, for example: https://www.cs.vu.nl/~wanf/theses/matei.pdf
[3] https://en.wikipedia.org/wiki/NC_(complexity)#The_NC_hierarc...
http://iss.ices.utexas.edu/Publications/Papers/ICS2016.pdf
https://repository.upenn.edu/cgi/viewcontent.cgi?article=144...
1. The two processes cause frequent evictions of the CPU cache in some way that two cores can mitigate by having separate caches.
2. You are able to pin a process to a CPU core, and eliminate all the overhead of running the process scheduler.
I would be curious to see the benchmark you're referring to. My gut tells me that the performance differences come from comparing different processor families.
So, to take a super contrived example, if you have a parallel program that needs to run 1B cycles worth of instructions with 1M worth of L3 cache misses. On a single 2ghz core that might take:
(2B cycles + 130 cycles / cache miss * 1M cache misses) = 2130 M cycles (1.065 seconds @ 2ghz)
On a dual 1ghz core, both sharing a single L3 cache of the same size (so same number of L3 cache misses), that might take:
(2B cycles + 65 cycles / cache miss * 1M cache misses) = 2065 M cycles (1.0325 seconds @ 2x1ghz)
Which is slightly faster. As long as you're bound by latency rather than throughput, and can perfectly parallelize the problem, more cores instead of more raw clock speed will win out, even with identical hardware and the two cores actually sharing some stuff (the L3 cache) and ignoring the bonuses of fewer L1/L2 cache misses (because they aren't shared, "doubling" your L1/L2 cache.) The machine I'm typing this from has 4MB of L3 cache and I frequently deal with hundreds of gigs of I/O. Suffice it to say, there are a lot of L3 cache misses.
Moving away from identical hardware - slower cores can get away with less speculative execution / shorter instruction pipelines, which make things like branch mispredictions cheaper in terms of cycle counts as well. This is why modern GPUs end up with hundreds of cores getting up into the 1Ghz range or so. They deal with embarrassingly parallel workloads, and can get better performance by upping core counts than they can by upping clock speeds.
As for reducing the need for speculative execution: You're just replacing implicit parallelism with explicit parallelism. Whether or not that is a win depends on the workload and the competency of your developers. :-)
My math assumed a share L3 cache of the same size, no "twice the cache", no "half the misses". Same number of misses, but each miss is effectively half as costly, because it's only stalling half your processing power (one of your two 1 Ghz cores) for X number of nanoseconds instead of all of it (your single 2 Ghz core).
> As for reducing the need for speculative execution: You're just replacing implicit parallelism with explicit parallelism.
Yes and no. If you're already explicitly parallel (more and more common), you're just eliminating a redundant implicit mechanism that's based on frequently wrong branch prediction heuristics. One can optimize for those, but then one can argue just how "implicit" it really is...
> Whether or not that is a win depends on the workload and the competency of your developers. :-)
Of course. But there's a lot of embarrassingly parallel work out there, and improving building blocks, that don't take a geniuses to operate. Pixel shaders, farming video frames out to render farms, compiling separate C++ TUs... these are all things already made explicitly parallel on my behalf. Really maxing out the performance of a single modern ~4 GHz core is no simple feat either.
Wow, I'm still trying to wrap my head around that.
I was going to argue that in cases where there's no way to split an algorithm across multiple threads without extremely frequent IPC, pipelining can probably get better performance than multiple cores, but then I realized that I have absolutely nothing to base that claim on.
I still wouldn't opt for more cores rather than higher clock speed without first trying to benchmark my expected workloads, but you have given me some very interesting things to think about.
Given a point in the Moore's law curve, can we actually make a single core that's as fast as 10 separate cores? If yes, Will that be more power, space and cost effective?
Even if you're making a large, multi-purpose app like, say, a spreadsheet you could still subdivide zillions of little tasks into their own applications. On an OS this makes little sense because of the overhead associated with spawning new processes but on Linux it'd be great.
This is the approach Rust+Rayon are taking. Rust is in a good position to enable this because of language-level guarantees. Using "a lot of little, single-purpose" tasks means that each task has to own its memory; Unix of course enforces this separation, but this comes with some overhead. Language-level discipline can achieve much the same thing, more efficiently.
This walk the tree to find the variable, X, that occurs most often. There is a weighting issue. Occurrences higher up the tree count more.
Then I would create two expressions by substituting X = true and X = false.
Now two cores can race to see which can find a satisfying assignment first. Clearly this division can be applied recursively until all the cores are busy.
The solution is to keep partitioning until you saturate all cores. As soon as all saturated, stop partitioning and compute. As soon as any task finished, resume partitioning.
On the lower level, I used a thread pool. BTW, the infrastructure for that is built-in in Windows, see SubmitThreadpoolWork API: https://docs.microsoft.com/en-us/windows/desktop/api/threadp...
4) in the antivirus insisting on chewing each piece of IO very slowly in case it might have a virus
Not only is that awful, but something is only "coined" if other people actually use it. You can just say "I will coin this!".
Why depth-first search can't be parallelized?
There is the aspects of an application but what about system code?
If read the FlexSC paper and using multiple cores you can see some pretty incredible improvements are possible.
https://www.usenix.org/legacy/event/osdi10/tech/full_papers/...
We should also see some of this with Zircon as it gets further along and looks to leverage cores in a type of pipelining.