views:

175

answers:

1

I'm new to Scala and was just reading Scala By Example. In chapter 2, the author has 2 different versions of Quicksort.

One is imperative style:

def sort(xs: Array[Int]) {
    def swap(i: Int, j: Int) {
        val t = xs(i); xs(i) = xs(j); xs(j) = t
    }
    def sort1(l: Int, r: Int) {
        val pivot = xs((l + r) / 2)
        var i = l; var j = r
        while (i <= j) {
            while (xs(i) < pivot) i += 1
            while (xs(j) > pivot) j -= 1
            if (i <= j) {
                swap(i, j)
                i += 1
                j -= 1
            }
        }
        if (l < j) sort1(l, j)
        if (j < r) sort1(i, r)
    }
    sort1(0, xs.length - 1)
}

One is functional style:

def sort(xs: Array[Int]): Array[Int] = {
  if (xs.length <= 1) xs
  else {
    val pivot = xs(xs.length / 2)
    Array.concat(
      sort(xs filter (pivot >)),
           xs filter (pivot ==),
      sort(xs filter (pivot <)))
  }
}

The obvious advantage the functional style has over imperative style is conciseness. But what about performance? Since it uses recursion, do we pay for the performance penalty just like we do in other imperative languages like C? Or, Scala being a hybrid language, the "Scala way" (functional) is preferred, thus more efficient.

Note: The author did mention the functional style does use more memory.

+5  A: 

It depends. If you look in the Scala sources, there is often an imperative style used "under the hood" in order to be performant - but in many cases exactly these tweaks allow you write performant functional code. So usually you can come up with a functional solution that is fast enough, but you must be careful and know what you do (especially concerning your data structures). E.g. the array concat in the second example is not nice, but probably not too bad - but using Lists here and concat them with ::: would be overkill.

But that is not more than educated guessing if you don't actually measure the performance. In complex projects it's really hard to predict the performance, especially as things like object creation and method calls get more and more optimized by the compiler and the JVM.

I'd suggest to start out with the functional style. If it is too slow, profile it. Usually there is a better functional solution. If not, you can use the imperative style (or a mix of both) as a last resort.

Landei
But it kind of defeats the purpose right? I mean, Scala is hailed as the first language that bridges functional and object programming. But, if you can't be sure that programming the functional way will be efficient, then people who care about performance will end up doing Scala the "Java" way?
ShaChris23
Look at the examples. Which one looks easier to comprehend? The functional style actually tells you what the algorithm does: "choose a pivot element, sort the smaller elements, sort the bigger elements and put everything together". This is a huge advantage over the imperative example, which is mainly concerned about loop variables and array indices. So if the functional style works well, we are usually golden, but we still have the imperative style as fall back solution. However don't set object-oriented == imperative. Classes and objects can work great in a functional context.
Landei
In any large project, you will find that very little of the code actually has to be screamingly efficient. In those cases, it is true that you will often need to fall back to imperative constructs. Scala supports that. The rest of the time, you are better off coding in such a way that your design is as clearly evident in your code as possible. That may be either functional, procedural, object-oriented, or some combination thereof. Scala supports all of those.
Dave Griffith
@ShaChris23 What did you expect? Ofcourse you can't be sure that programming the functional way will always be efficient, just like writing a program in an imperative or OO style will not always be efficient. Functional programming is not a silver bullet that will automatically make your program efficient, and that doesn't have anything to do with Scala itself. In any programming style you don't get efficiency for free, you still have to think about it yourself.
Jesper
Thank you @Landei, @Dave, and @Jesper for all the thoughtful comments.
ShaChris23