News for hackers. Stuff that matters.
Re:Pessimism about parallelism by pcwalton on Wednesday December 26, 2018 @09:18AM (#18762226)
This pessimism about whether software can effectively use CPU cores beyond two is easily refuted with a simple observation: High-end games are now running pretty close to 100% CPU utilization on octa-core console hardware.

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.

Re:Pessimism about parallelism by twotwotwo on Wednesday December 26, 2018 @12:12PM (#18763212)
Yeah, what it takes to really, truly stop parallelism is an unbreakable linear chain of dependencies, like how LZ decompression needs the previous unpacked block to begin work on the next. (Not that LZ unpacking is maxing out people's CPUs these days.) That certainly exists sometimes but isn't nearly common enough to make me doubt the whole enterprise of parallelizing things.

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.

Re:Pessimism about parallelism by terrelln on Wednesday December 26, 2018 @04:39PM (#18765175)
I definitely agree that parallelism isn’t held back by fundamentally serial work. Even with LZ decompression, most algorithms entropy encode the LZ sequences, and these sequences can be decoded in parallel with the LZ decoder.
Re:Pessimism about parallelism by MaulingMonkey on Wednesday December 26, 2018 @10:45PM (#18767118)
Even if you couldn't parallelize decompression (non-entropy encodings?) there's nothing stopping you from breaking data up into multiple streams and separately (de)compression those. For games, this might be decompressing different assets simultaneously.
Re:Pessimism about parallelism by twotwotwo on Wednesday December 26, 2018 @11:12PM (#18767244)
FWIW, my aim was to give an illustrative example of what I meant by a chain of dependencies, and your garden-variety gunzip foo.gz has one. You can certainly come up with compression schemes or situations where not everything has to be serial.
Re:Pessimism about parallelism by SomeHacker44 on Wednesday December 26, 2018 @03:17PM (#18764526)
Modern GCs do a lot to improve performance by using temporal locality, not just the memory layout / access pattern locality that ESR was primarily interested in. I am no expert, but we now have multiple generation, multiple phase garbage collectors that can do useful work in parallel and have minimized the need for stop the world processing (one of ESR's intrinsically serial processes, at least from the executing program's perspective, as it may be an internally parallelizable process).
Re:Pessimism about parallelism by twotwotwo on Wednesday December 26, 2018 @11:35PM (#18767336)
Can't tell if you're agreeing or disagreeing with this, but what I was trying to say is that full GCs happen (even when generational lets you delay them), thrash your caches to trace all live pointers in your heap, and still run faster on multiple cores. That seems to be in tension with the blog post's suggestion that you need locality for parallelism.

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.

Re:Pessimism about parallelism by chrisseaton on Wednesday December 26, 2018 @01:25PM (#18763664)
> Parallelizing our software is mostly a question of investment at this point.

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.

Re:Pessimism about parallelism by gnarbarian on Wednesday December 26, 2018 @03:10PM (#18764477)
>This just isn't true - for some algorithms we are simply not aware of any way to effectively 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.

Re:Pessimism about parallelism by vmchale on Wednesday December 26, 2018 @08:54PM (#18766615)
> 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!

Re:Pessimism about parallelism by leoc on Wednesday December 26, 2018 @11:48PM (#18767394)
A lot of this discussion is recapitulating the discussion around https://en.wikipedia.org/wiki/Gustafson%27s_law , no?
Re:Pessimism about parallelism by rabidrat on Wednesday December 26, 2018 @02:44PM (#18764275)
Most software is not one algorithm. Most software is a complex system which can be parallelized in a variety of ways, some of them embarrassingly trivial.
Re:Pessimism about parallelism by chrisseaton on Wednesday December 26, 2018 @02:53PM (#18764355)
I also think most software doesn't run for example 32 independent algorithms at the same time, so some of them will have to be parallelised to use the large number of cores we're getting.
Re:Pessimism about parallelism by imtringued on Wednesday December 26, 2018 @04:04PM (#18764869)
We had decades of lazy game developers not using more than one core and CPUs kept up with the demands of those game developers. Consider that games are one of the most performance sensitive an average user is going to come in contact with then how on earth are you going to find a single inherently sequential problem that is enough to saturate an entire CPU core when even games, which consist of thousands of divisible sub-problems and therefore are easily parallelizable, were fine with just a single one?

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.

Re:Pessimism about parallelism by gameswithgo on Wednesday December 26, 2018 @03:03PM (#18764425)
Yeah but that doesn't just come up that much as an actual limiter. Like say you have a graph search algorithm that is provably non parallelize-able, ok, fine. If you only have 1 graph to search, you are stuck. But likely you have many graphs you can search and spread them around.
Re:Pessimism about parallelism by vmchale on Wednesday December 26, 2018 @08:49PM (#18766590)
Well, if you mean concurrency over parallelism, I think it's quite clear that there are many tasks that benefit from concurrency.
Re:Pessimism about parallelism by chrisseaton on Wednesday December 26, 2018 @08:58PM (#18766641)
You don't need concurrency to create parallelism, and it's the parallelism that we want, so no we don't mean concurrency.
Re:Pessimism about parallelism by llukas on Wednesday December 26, 2018 @12:19PM (#18763244)
Utilization is bad metric - ie. you may spin cores to acquire lock.

How much of that utilization is doing useful work is important.

Re:Pessimism about parallelism by ivalm on Wednesday December 26, 2018 @05:28PM (#18765462)
I mean for many games you have rendering engine/network code/audio/hard drive io/game logic be asyn to each other. A lot of game logic can then be further parallelized.
Re:Pessimism about parallelism by hinkley on Thursday December 27, 2018 @12:42PM (#18771016)
Agreed. Maxed out cores doesn’t mean progress is being made, literally or figuratively.

A breakdown of how that budget is spent would be a productive addition to this discussion.

Re:Pessimism about parallelism by nickpsecurity on Wednesday December 26, 2018 @07:57PM (#18766291)
Ill add that it can help to use languages that make expressing parallelism both easier and the default. Cray's Chapel is a good example with lots of versatility:

https://chapel-lang.org/

Re:Pessimism about parallelism by vmchale on Wednesday December 26, 2018 @08:58PM (#18766639)
Personally I'm a huge fan of J for this purpose.

Haskell also has some nice qualities, though one has to use something like accelerate or repa.

Re:Pessimism about parallelism by kace91 on Wednesday December 26, 2018 @10:04AM (#18762451)
What kind of foundational software are you referring to? Honest question.
Re:Pessimism about parallelism by pcwalton on Wednesday December 26, 2018 @10:22PM (#18766994)
libpng, to name one example off the top of my head. It doesn't even have support for SIMD on x86 yet, in 2018.
Re:Pessimism about parallelism by hinkley on Thursday December 27, 2018 @12:38PM (#18770983)
libpng should be theoretically capable of using one and a half cores per image decode. But unfortunately one of the compression techniques in the spec introduces a hazard between each line of the image, because the pixels at x-1 and y-1 are used to predict the value of next pixel. If that algorithm is used it would take some very interesting math to decode multiple lines in parallel.
Re:Pessimism about parallelism by mcguire on Wednesday December 26, 2018 @01:12PM (#18763564)
I believe games were one of ESR's special cases, which is highly parallelizable. On the other hand, most of the software in daily use isn't cpu bound on one core.
Re:Pessimism about parallelism by gameswithgo on Wednesday December 26, 2018 @03:04PM (#18764431)
games is a special case, video editing is a special case, compiling code is a special case, running a development environment with a database, web application, and browser is a special case,

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)

Re:Pessimism about parallelism by gumby on Wednesday December 26, 2018 @10:38AM (#18762611)
I don’t see what this proves or disproves. The article points out that problems that are idly metric with clearly differentiated local data are amenable to parallelization — and potentially only such. Sounds like a lot of game visuals.
Re:Pessimism about parallelism by vmchale on Wednesday December 26, 2018 @08:45PM (#18766560)
> High-end games are now running pretty close to 100% CPU utilization on octa-core console hardware

That's concurrency, no?

Re:Pessimism about parallelism by babyloneleven on Thursday December 27, 2018 @09:53AM (#18769722)
No, that's parallelism, because the cores are running in parallel.

The software is written using concurrency techniques such as threads, that work on both multicore machines and machines with a single core.

Re:Pessimism about parallelism by zozbot123 on Wednesday December 26, 2018 @09:50AM (#18762383)
100% CPU on an octacore? See, ESR was right, it's bottlenecked by serial performance. Now 800% CPU utilization would be impressive!
Re:Pessimism about parallelism by smolder on Wednesday December 26, 2018 @03:54PM (#18764797)
A multicore CPU is comprised of several cores. I don't think fully utilizing all cores means "800% CPU utilization"
Re:Pessimism about parallelism by bitwize on Wednesday December 26, 2018 @09:24PM (#18766771)
Oddly enough the load average, as reported by uptime and xload, uses just this metric: a machine with one CPU pegged has a load of 1.0. A fully utilized octa-core machine has a load of 8.0.