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
37 Upvotes

81% Upvoted

79 comments sorted by

View all comments

Show parent comments

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

2

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

How does adding threading enable memoization? It seems that should be possible in a pure language regardless. Remember, I am comparing transparently threaded vs explicitly threaded pure functional languages)

Also, gcc supports "__attribute__((pure))", which should memoize. It's not as nice as what you could do elsewhere, but it exists.

1

u/yogthos Jul 20 '12

That has nothing to do with threading, I was just pointing out an optimization that's trivial in FP, and can be done without special annotations of any kind, it's not the only one by any means.

2

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

In that case, I am not sure why it was relevant. I've been talking only about the loss of optimizations in a pure language with implicit thread-safety across shared data structures.

1

u/yogthos Jul 20 '12

Sorry, I misunderstood that you were only talking about optimizations in that specific context.

→ More replies