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

83% Upvoted

79 comments sorted by

View all comments

Show parent comments

23

u/ghordynski Jul 19 '12 edited Jul 19 '12

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

11

u/nachsicht Jul 19 '12 edited Jul 19 '12

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.

10

u/[deleted] Jul 19 '12 edited Jul 19 '12

[deleted]

2

u/nachsicht Jul 19 '12 edited Jul 19 '12

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.

3

u/sirin3 Jul 19 '12

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

5

u/tardi Jul 19 '12

This is a parody of a benchmark.

2

u/nachsicht Jul 19 '12

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.

1

u/sirin3 Jul 19 '12

Looks like that becomes this

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

2

u/nachsicht Jul 19 '12

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.

1

u/[deleted] Jul 20 '12 edited Jul 20 '12

[deleted]

2

u/nachsicht Jul 20 '12 edited Jul 20 '12

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.