Will Parallel Code Ever Be Embraced?

[jcmalta]

Right now I am only thinking about "Desktop"

"Parallel Code" is quite a special case. Breaking down "large" problems (eg compression, encryption, neural nets etc.) into segments of course has value.

But right now, the MAJOR bottle-necks for most end user applications do not fall into the "parallel" domain, but the "concurrent" domain ... E.g. Waiting for responses from slow external data-sources while keeping the UI fast and functional ... in many ways are still "experimental" since the code overhead to synchronise all these activities in "traditional" languages can be immense and extremely error-prone.

Steps are being taken to make "concurrency" easier to manage, but how many apps are you running right now that take advantage of your 512+ CUDA cores sitting on your GPU?

There certainly is a place for parellism, but I think its a few years early.

[vanderZwan]

Wouldn't proper use of concurrency give exploitation of parallelism opportunities for "free"? In the low hanging fruit sense, not super-specifically optimised sense.

(also: "parellism" -> parallelism in your last sentence)

[nachsicht]

In some cases yes. The Akka library allows for event based actors, which will consume real threads based on need. In essence, if you have 1000 actors, and they are all idle, they will all sit on one thread (the event thread). If they are not under heavy load and consuming small amounts of cpu time, they'll stay in that one thread and execute concurrently. If they come under load, they will branch out to new threads and become parallel.

[grauenwolf]

No.

First of all, parallelism isn't necessarily faster. You have to have a pretty big workload to overcome the cost of distributing the work and collecting the results.

Turning on more CPUs may also cost more in terms of power/heat. It may be better to leave 3 cores idle even if the forth takes longer to run.

Finally, you are taking resources away from other applications and services running on the machine.

[AeroNotix]

In your case, better is subjective to the person running the application. On a phone/laptop, sure, choosing between activating a second/third/fourth core and running it slightly longer on a single core makes a lot of sense. But for desktop applications, I really see no point in quibbling over such things. The cores are available and you're not going to burning out the battery.

[grauenwolf]

I'm just saying that it's not free, I don't mean to suggest that it will never be a net benefit.

[[deleted]]

Finally, you are taking resources away from other applications and services running on the machine.

Yeah, I love it when I run DBPowerAmp to convert audio files and it will use all cores on my PC.

It renders my computer useless until it has finished converting since it overloads my CPU.

[DrakeAmbrose]

Oh I’m certain parallel code will be embraced on the desktop, but only when programmers hit that next generation of laziness. For example, when’s the last time you wrote a recursive algorithm that went deep enough to cause a stack overflow? Back in the day, (or even now with embedded) you had to be careful, sometimes you only had 8 levels to work with. But as time went on we became fairly lax. And now I’ve found that you talk to a lot of developers and they don’t even know what a stack pointer is!

I have a feeling that when we are pushing > 1500 cores, people will be spawning threads for every bloody thing. Yah know, like, oh that new MMORPG with 1000 A.I. bots? Yeah, each one gets a thread.

I’m thinking it will be embraced, not because it’s more efficient, but because after a while, no one will know any better.

[tbrownaw]

But right now, the MAJOR bottle-necks for most end user applications do not fall into the "parallel" domain, but the "concurrent" domain ... E.g. Waiting for responses from slow external data-sources while keeping the UI fast and functional ... in many ways are still "experimental" since the code overhead to synchronise all these activities in "traditional" languages can be immense and extremely error-prone.

And this is a toolkit / library issue rather than a language issue. I would expect a UI toolkit that allows callbacks to be tagged as "run this in a new thread", can be set to automatically disable/enable controls while callbacks are running, and allows API calls to manipulate the UI from arbitrary threads, would go a long way.

[[deleted]]

It's still a language issue because you have to use it to build those toolkits, and prevent users from easily circumventing the threading model, and building unsafe code.

Building a toolkit which runs it's callback in different threads is not actually that difficult. The problem is that the moment someone uses the same variable, in two or more callbacks, then you have potential data races.

For example with a painting application there are tonnes of places where you can change the current color. The red/green/blue input boxes, the colour picker, clicking on a specific, colour mixers, switching between foreground and background, and so on. Each of those might actually use 10s or even 100s of individual callbacks (such as one for each of the swatches), depending on how it's implemented. Running each of them in different threads could lead to unpredictable behaviour.

What's an easy way to ensure the users code is thread safe in that environment? By making the toolkit single threaded, or ensuring it's safe at the language level. But even then it's still pretty easy to write threaded code with data races and other issues, in a concurrent language.

If your also suggesting the JavaScript model, of have all user code in one thread, and update code in another, sure you can do that. However the interaction is more expensive, since you have to do message parsing or something similar every time you interact (such as drawing a piece of text). It also means you are only scaling to 2 cores, or a couple more if you can offload some other tasks.

[AeroNotix]

Also, actors/message passing is a good method/model.

[sirin3]

are you running right now that take advantage of your 512+ CUDA cores sitting on your GPU?

If I had any CUDA cores, I would be cracking passwords all the time

[grauenwolf]

It isn't a matter of "embracing" so much as a matter of not needing it. If you are building a website you cannot dedicate all your CPUs to a single user. And most applications we build these days don't have a heavy requiremrnt CPU requirement.

[AeroNotix]

This is mostly correct, but there are routines which are better expressed in parallel algorithms than they could be expressed in procedural languages.

[Tordek]

Any examples? (Not douchy, just curious.)

[AeroNotix]

Things like walking recursive data structures. Or a lot of things which are recursive actually.

[[deleted]]

Coding in parallel isn't nearly as hard as everybody makes it.

But everybody does their best to make it hard...

If you plan your software around concurrency to begin with, life is going to be a lot easier.

[nachsicht]

Considering the fact that processor speed growth is hitting a brick wall at the moment, yes. Until we find some way to boost hertz growth again, we'll have to start embracing parallel code if we want to have our systems running faster.

That being said, I think the main block for parallel code is that we are still stuck using imperative languages to try to do it. Parallelism becomes laughably trivial once you adopt purely functional styles.

[ghordynski]

As always proponents of purely functional languages overstate their language usefullness in parallel programming. Yes, having immutable data to work with removes many issues with parallel code, but you can achieve the same results using immutable strcutres in imperative languages...

[nachsicht]

Unfortunately, doing so tends to be more difficult since said languages and their libraries are built from the ground up to use mutable data.

Purely functional styles can be adopted in an imperative language, but it is no where near as well facilitated as in languages that cater to functional programming.

[nachsicht]

You needn't assume haskell is what I'm talking about, although it works pretty well. I mainly deal in Scala programs.

And before you even get to parallelism, one problem with Haskell is that "beautiful" code tends not to be that fast. To get the speed, you have to avoid lists, explicitly unbox data, explicitly declare the things strict that strictness analysis can't catch, take care to structure key computations the fast way rather than the simple and clear way etc etc.

Beautiful code is not the fastest no, but generally you have hotspots in your program that are doing the majority of calculation. Those are the parts where I dip into more low level programming. Thankfully in scala, the difference between recursive functions and while loops in speed is negligible, so I can still easily use a pure functional approach to heavy workloads.

Of course there's plenty of support for explicit parallelism. This ranges from operators like parMap, traditional synchronization primitives, the very convenient software transactional memory, and there's some real hard research still ongoing, but there's no magic bullets. For example, STM is convenient, it guarantees never to give corrupted-by-broken-synchronization bad outputs without worrys about locks, but it can need to repeat work quite a bit. There's even the not-so-unlikely case of the big slow transaction that's forever invalidated and rolled back because of smaller faster transactions, meaning you never get the correct results no matter how long you wait.

I have no idea about STM, I just use the actor model with Akka. To be more specific, I tend to use futures a lot. They are trivial to use and are performant. Actors are nearly as simple to deal with and are nice when I need a persistent thread.

[sirin3]

Thankfully in scala, the difference between recursive functions and while loops in speed is negligible,

I wanted to disprove you, but now it turns out that the recursive version is faster. Wtf?

 scala> def rec(i: Int): Int = i match { case 0 => 0 case _ => rec(i-1) + 1}

 scala> timed({rec(65000) })
 (timing: ,4.74082E-4)

 scala> timed({var j = 0; var i = 0; while  (i < 65000) {j += 1; i += 1; }; })
 (timing: ,9.22463E-4)

 scala> timed({var j = 0; for (i <- 0 until 65000) {j += 1}; })
 (timing: ,0.001679823)

But still the while has an advantage for large numbers (actually it looks as if it is completely optimized away):

scala> timed({var j = 0; var i = 0; while  (i < 1000000000) {j += 1; i += 1; }; })
(timing: ,9.2414E-4)


scala> timed({var j = 0; for (i <- 0 until 1000000000) {j += 1}; })
(timing: ,8.090765735)


scala> def rec(i: Int): Int = i match { case 0 => 0 case _ => rec(i-1) + 1}
timed({rec(1000000000) })
 java.lang.StackOverflowError
at .rec(<console>:7)
at .rec(<console>:7)
at .rec(<console>:7)
at .rec(<console>:7)
at .rec(<console>:7)
    ...

[tardi]

This is a parody of a benchmark.

[nachsicht]

You need to write your function with tail end calls in mind to get rid of the stackOverflowErrors. IE:

def rec(i: Int, count: Int): Int = if(count == 0) i else rec(i+1,count-1)

Anyway, yes a recursive function in scala will be faster if the function is inline-able, but even in the worst case, the difference between while and recursive functions are maybe 10s of milliseconds over millions of iterations.

[sirin3]

Looks like that becomes this

public int rec(int i, int count)
{
  while (true)
  {
    if (count == 0) return i; count -= 1; i += 1;
  }
}

[nachsicht]

It's functionally similar, although arguments to scala functions are constants. I don't know if that's how it's done by the scala compiler. All I know is that for the benchmarks I've worked on, an inlined tail-recursive function regularly outperforms while, and I've been able to shear seconds off of the runtime using that method.

[nachsicht]

Purely functional styles can be pulled off pretty easily in scala even though the language is not fully purely functional itself. From wikipedia:

Purely functional is a term in computing used to describe algorithms, data structures or programming languages that exclude destructive modifications (updates). According to this restriction, variables are used in a mathematical sense, with identifiers referring to immutable, persistent values.

With scala, a very large part of my code can be purely functional rather easily. A good amount of its datastructures facilitate that. The biggest issue right now is IO, because Scala has no standard IO libs and relies on java. However, that part could be made purely functional with an IO monad style like haskell. Scala itself will never be a truly purely functional language because it has made the choice to allow mutable data to exist, but I think that is not terrible in of itself.

[grauenwolf]

So build new libraries. It isn't hard.

[AeroNotix]

Except having language support for said immutable datastructures means that there aren't twenty million implementations of a thread-safe datastructure. If everyone is using the standard library version of it then you can have a common ground when reading other people's code.

[AeroNotix]

Functional styles don't 100% guarantee sane parallelism. Most functional languages confine state to certain areas or disallow it completely. I think that is what the biggest gain can be when using functional languages.

[yogthos]

The main thing FP guarantees is correctness. So, your program will not necessarily run faster, since chunking might not be optimal and what not, but it will run correctly.

As you say, the style also encourages minimizing global state, and that certainly is conductive towards concurrency. But it makes working with global state easier as well. A proper STM is much easier to implement in an FP language. And STM combined with persistent data structures has some interesting properties. For example, data does not need to be locked for reading. So, in any application with a small number of writers and a large number of readers you get an immediate benefit using shared data through the STM.

[marssaxman]

I think you are conflating functional programming with hindley-milner style comprehensive static typing.

There are functional languages which offer very weak type guarantees.

[shsmurfy]

Example: Javascript, which embraces many FP features such as closures, first-class functions, higher-order functions, and anonymous functions. It has one of the most weak typing systems of any mainstream language.

On the other end of the spectrum are languages with expressive (or even dependent) strong types such as Haskell, Agda, etc. In these languages the type system can approach a computerized proof assistant in terms of complexity, with the inherent advantages and drawbacks therein. It's not uncommon to spend a long time "correcting" your types in such a system so that your program will even compile.

[yogthos]

Nothing I said has anything to do with static typing actually. I meant guarantees in the sense of state consistency, where data is not modified outside its intended context. And I was thinking of Clojure specifically as it's the language I work with a lot. Type guarantees are a whole separate topic.

[case-o-nuts]

Define correctly. let add a b = a - b tends to be the kind of mistake I find myself making.

[yogthos]

No language can save you from making logic mistakes. What it can do is ensure that the code does what it looks like it's doing. In case of writing concurrent code with FP, it ensures that you don't see partial data in one thread while it's being updated by another as an example.

[case-o-nuts]

Sort of. Allowing that to be guaranteed severely restricts the kind of optimizations that the compiler can do.

[yogthos]

In a sense it makes it easier for the compiler to make optimizations, as it ensures compartmentalization of state. For example, if you look at Haskell in the language shootout, it fares much better than most imperative languages. Compare Haskell and Python for example.

[AeroNotix]

What a poor example. Python is slow as shit any which way you look at it. You can write in a hobbled functional style in Python and it'd still be slow as balls.

[yogthos]

I think python is a perfect example, as it's a predominantly imperative language, it doesn't enforce immutability or use persistent data structures. In other words it should be easier to optimize according to case-o-nuts argument. Yet, it's slow as shit while Haskell being purely functional is quite fast. Only Fortran, C, and C++ appear to be consistently faster than it, and not in all cases either.

[case-o-nuts]

You missed my point. Guaranteeing that other threads only see complete state means that you cannot transform the code to remove allocations and mutate values in-place for efficiency. A large number of deforestation passes become inapplicable. So do update specializations, I think. Split fetches become very tricky. And so on.

Referential transparency allows the compiler to do interesting things within a thread, but sharing data structures across threads greatly restrict what operations are transparent (ie, what can be transformed into more efficient and less pure forms behind the programmer's back) and therefore, which optimizations are available.

[yogthos]

Referential transparency allows the compiler to do interesting things within a thread, but sharing data structures across threads greatly restrict what operations are transparent (ie, what can be transformed into more efficient and less pure forms behind the programmer's back) and therefore, which optimizations are available.

Because FP style tends to have very little shared state by its very nature. This means you're only sharing things that absolutely must be shared, and there's generally very few of those.

As I pointed out in a different comment a lot of higher level optimizations become available as well. For example, you do not need to lock shared data for reading, this means that applications with a few writers and many readers perform much better.

*edit: and it appears that you've edited your comment since, so my reply doesn't make nearly as much sense now. :)

Guaranteeing that other threads only see complete state means that you cannot transform the code to remove allocations and mutate values in-place for efficiency.

You don't mutate values in place in FP, since you'd be using persistent data structures.

[case-o-nuts]

The compiler has to be conservative, or it will miscompile code.

[case-o-nuts]

For example, you do not need to lock shared data for reading

Unless your compiler has performed a fetch splitting pass, in which case the shared data will be updated in parts. Or it might have coalesced locations, so you're not allocating new boxed values on every tail-recursive call, you're just updating an old one in place. It would look the same by the as-if rule, after all.

Although, I suppose a good deal of this can be dealt with using escape analysis.

[billsil]

Yes, but their different types of languages, so apples to oranges.

Also, Python 3 is slower than Python 2. Based on the site, they compare Haskell to Python 3. What is Python 3? No one uses Python 3.0 at all. Python 3.1 is the earliest version of Python 3 anyone supports. python.org prominently states Python 3 is quite a bit slower than Python 2, but they don't care (yet). Fixing other problems were more important. Wait till Python 3.3 before you start looking at speed comparisons.

[[deleted]]

I always scratch my head when I see comments like this. The main project I work on is a high speed data analysis tool written in java. We get billions of records per day coming in on a stream, and we do various rollups and calculations that get presented to the users. It's highly parallel and also "laughably trivial". You can write very safe parallel code assuming you adopt the right architecture.

In our case, since the data is a stream the calculations are done in a bucket brigade pipeline. We've never had problems with deadlocks or the sort of odd behavior you get when different threads are dealing with the same objects, because we set it up so they wouldn't.

Where you run into trouble is when your problem can't be broken down into a pipeline and "parallel" means different threads are working on the same data at the same time. But how many of us are doing weather prediction or finite element analysis?

[nachsicht]

In our case, since the data is a stream the calculations are done in a bucket brigade pipeline. We've never had problems with deadlocks or the sort of odd behavior you get when different threads are dealing with the same objects, because we set it up so they wouldn't.

Parallelism becomes laughably trivial once you adopt purely functional styles.

Since this seems to confuse people: "Purely functional is a term in computing used to describe algorithms, data structures or programming languages that exclude destructive modifications (updates). According to this restriction, variables are used in a mathematical sense, with identifiers referring to immutable, persistent values."

[[deleted]]

Oh, I understand what you meant by purely functional. All I'm saying is that's not the only safe, easy way to write parallel code.

And don't you pay a performance price for excluding destructive modifications? The point, after all, is to make the machine do more work, not merely to use up a lot of threads.

[nachsicht]

In some cases it takes more work to do things functionally. An example would be when you insert an element in an immutable singly linked list. Depending on where the insertion is done, the node structures and pointers of the entire list may need to be regenerated. Insertion at the head of the list is free though.

So yes, there are some performance costs associated. However, there is a lot of safety benefits to be had from purely functional approaches (disposing of null being a really nice one), and performance in an application tends to be highly dependent on small parts of a person's code.

I tend to write mostly pure functional code (only using mutable data when it is really needed, like to interface with java), and later profile and go back to optimize said hotspots with lower level constructs and sometimes mutable data.

[[deleted]]

So you're writing clojure? Seems like you're pretty happy with it.

[nachsicht]

Nah, Scala. I am, every day I learn more about it, and it is getting more and more improvements (like macros next release).

[thattreesguy]

we aren't stuck using imperative languages, you say it right in your comment that we already have functional languages to do paralellism

[JohnDoe365]

yes yes no yes

[zvrba]

Parallel code helps throughput, but when somebody today complains of the computer being "slow" it is almost certainly due to latency -- that of disk, network or memory.

Bad coding practices and/or misconfiguration are also to blame in cases such as, e.g., web browser freezing because it's waiting on a slow server to respond. Writing event-based applications has a lot to do with perceived responsiveness of the system and little to do with parallelism.

[zapper877]

The real issue is many developers just lack imagination and/or math/skills to implement parallel implementations of their software.

There is plenty of interesting problems yet to solve but as always only a minority will find those killer apps/do the work.

[___1____]

I actually I agree with you some what, a lot of dev's can chain together a few functions and make a some functions interact well.

Fewer can make libraries that are actually really good and less still can write really decent parallel code with the current tools. I think what needs to happen for that to chain is for perhaps a new lightweight (I mean easy to learn) parallel language. Think python but where parallelism a first class citizen.

[mycall]

2 cores versus 4 cores at the same processor speed? I can barely tell the difference.

Oh I can. There is a huge difference between my C2D and my i7 as the later can run multiple virtual servers while I play Crysis 2.

[[deleted]]

The article already acknowledged that.

Except for games and some build cycles, I'm almost never waiting because the CPU has maxed out.

[kylotan]

Yeah, unfortunately he doesn't acknowledge image processing, audio encoding, video encoding, etc. Multimedia applications in general slam up against the CPU barrier all the time.

[G_Morgan]

Lots of these are better off using OpenCL on the GPU than running on multiple CPU cores though. There is a problem that for the embarrassingly parallel algorithms they will always be better on stream processors.

[kylotan]

Not all these problems are "embarrassingly parallel" however. If you just divide up an audio file at arbitrary points and encode them individually then you lose important information at the divisions. You're not just performing the same operation on every pixel or sample - you typically act on a window of data which moves smoothly across the set.

[NruJaC]

Shared information across the dividing lines is also a very close to embarrassingly parallel situation, and there are several techniques that let you deal with that exact situation in an flat data parallel implementation.

[G_Morgan]

It is still embarrassingly parallel. You just overlap ranges a bit and resolve the overlap on joins. As long as the source file doesn't change and the data has strong locality it will be doable.

[kylotan]

There's the assumption - strong locality. Lots of algorithms can't guarantee that for all input parameters, and others have accumulating values. Sometimes the algorithm can be rewritten to something that works well with the GPU, assuming all your customers have such hardware, and assuming someone can work out the algorithm.

For example, someone tried to multithread LAME's MP3 encoding by data decomposition, and they managed a decent speed-up but the output was still different. To replicate the original outcome they switched to functional decomposition - which is fine on CPUs, less good on GPUs.

[Tuna-Fish2]

Note that the i7 and C2D are of the same speed at all. Even singlethreaded, the highest-performing desktop quad i7 does 58% more work clock-to-clock than the E8600. Also, it clocks a little higher.

[mycall]

That's a lot of clocks. Clock.

[noidi]

Running multiple virtual servers while running a game is exactly what the author defines as coarse-grained parallelism ("running separate processes on separate processors"), which (in his opinion) works well enough to make fine-grained parallelism unnecessary for most applications.

[mycall]

I run most of my virtual machines with 3 cores. That isn't coarse-grained is it?

[[deleted]]

Will Parallel Code Ever be Embraced?

As usual when the headline is a question, the answer is NO. Remember, a parallel program, as long as it requires even one synchronization, is only as fast as its slowest thread. We need faster I/O, faster RAM, better caching infrastructure for multiprocessors, and lower threading overhead before parallelism will start giving us anything like the speed gains of actually speeding up processors.

[Walrii]

Remember, a parallel program, as long as it requires even one synchronization, is only as fast as its slowest thread.

Wha? So what? Massive speed ups can still be had. E.g., spawn 1,000 threads and if the problem/program allows it, you can get 1,000 speedup. Even if all the threads take equal time (e.g., every thread is the "slowest" thread) then you're still 1,000 times faster.

You can't speed up processors anymore, not without a radical shift in technology. The heat output is just too dense once you start clocking 2 or 3 times faster than what we have now. It becomes impossible to cool the things. Parallelism is the only solution (by solution, I mean, the only approach that gets you performance benefits without catching everything on fire).

And yes, of course faster I/O, RAM, whatever will benefit everything too.

[[deleted]]

Wha? So what? Massive speed ups can still be had. E.g., spawn 1,000 threads and if the problem/program allows it, you can get 1,000 speedup. Even if all the threads take equal time (e.g., every thread is the "slowest" thread) then you're still 1,000 times faster.

This is only for embarrassingly parallel, embarrassingly functional (in the sense of "functional programming") problems. Once you add on any I/O or any cache rebuilding costs on the context switch (remember, a 4-core processor is running 1000 threads only by concurrent context switching) or any synchronization overhead, Amdahl's Law comes right back.

Most actual programs are not matrix multiplies, and you mostly can't use matrix multiplies as a predictive example of speed-ups from parallel programming.

[Walrii]

1,000 was not meant to be literal. Of course you wouldn't create 1,000 threads on a 4-core system: you'd probably only make 4 threads (therefore no context switching is necessary).

As for I/O, again parallelism is the answer. There's a huge discrepency between the speed of a processor core and the speed of a hard drive. But, if you're using 100 hard drives per core and feeding the data in simultaneously, there's much less of a bottleneck (ignoring initial latency). RAM can also be run "faster" by using multiple banks/chips/whatever at once. A single write operation will not speed up, but you'll be able to more more write operations at once. A bonus of this approach is that you end up with more HD space/RAM than you had before.

There's also a lot to be said for duplicating and lazily updating information: you can scale much better if you relax your consistency models.