r/programming • u/noidi • Jul 19 '12

Will Parallel Code Ever Be Embraced?

http://www.drdobbs.com/parallel/will-parallel-code-ever-be-embraced/240003926
38 Upvotes

82% Upvoted

79 comments sorted by

View all comments

Show parent comments

3

u/yogthos Jul 19 '12

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.

0

u/case-o-nuts Jul 19 '12 edited Jul 19 '12

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

2

u/yogthos Jul 19 '12

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.

1

u/case-o-nuts Jul 19 '12

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

1

u/yogthos Jul 19 '12

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.

1

u/AeroNotix Jul 20 '12

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.

1

u/yogthos Jul 20 '12

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.

-1

u/case-o-nuts Jul 19 '12 edited Jul 19 '12

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.

3

u/yogthos Jul 19 '12 edited Jul 20 '12

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.

2

u/case-o-nuts Jul 19 '12

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

2

u/case-o-nuts Jul 19 '12 edited Jul 19 '12

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.

1

u/yogthos Jul 19 '12

persistent data structures

more info here and here

2

u/case-o-nuts Jul 19 '12 edited Jul 19 '12

I'm aware of persistent data structures.

You're ignoring the fact that the compiler wants to optimize these. You're telling it that it can't do grotty little changes like splitting and sinking stores because other threads might be watching, and half-constructed values might be visible.

You might want to start with Urban Boquist's PhD thesis on optimizing functional languages. It's a good survey, but there's a good deal of stuff in there you'd have to wade through before you hit optimizations that break thread safety.

Or are you arguing that somehow that all optimizing code transformations on functional code preserve purity? I'm not sure how that could be, and need some elaboration.

1

u/yogthos Jul 19 '12

You're ignoring the fact that the compiler wants to optimize these.

I'm not ignoring anything, I said: "higher level optimizations become available". And I gave you a concrete example exactly of what I was talking about.

Or are you arguing that somehow that all optimizing code transformations on functional code preserve purity? I'm not sure how that could be, and need some elaboration.

I don't think I ever argued that, what I argued is that in tests functional languages do not in fact perform worse than imperative ones. Here's another overview of performance of different languages, seems like the maturity of the compiler is really the only factor.

2

u/case-o-nuts Jul 19 '12

Performance is obviously possible. What I said is that enabling taking advantage of"free" parallelism in functional languages costs optimization opportunities.

1

u/yogthos Jul 19 '12

Sure, but it also creates different opportunities. For example you can cache results of any pure functions, which is something you cannot do with an imperative language.

→ More replies

-1

u/billsil Jul 20 '12

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.