>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.

> 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!

A lot of this discussion is recapitulating the discussion around https://en.wikipedia.org/wiki/Gustafson%27s_law , no?

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.

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.

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.

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.

Well, if you mean concurrency over parallelism, I think it's quite clear that there are many tasks that benefit from concurrency.

You don't need concurrency to create parallelism, and it's the parallelism that we want, so no we don't mean concurrency.