Scala Performance: imperative vs functional style

Question

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.

Answer 1

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.