Scala Performance: imperative versus functional style

Question

I am new to Scala and just read the Scala Example . In chapter 2, the author has two different versions of Quicksort.

One of them is an 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 of them is a 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 of a functional style over an imperative style is brevity. But what about performance? Since it uses recursion, do we pay a performance penalty like in other imperative languages ​​like C? Or, Scala is a hybrid language, preferably the "Scala method" (functionality), thereby more efficient.

Note. The author mentioned that the functional style uses more memory.

Answer 1

It depends. If you look at the sources of Scala, in order to be workable, the “under the hood” style is often used, but in many cases it is these settings that allow you to write functional functional code. Therefore, usually you can find a functional solution that is fast enough, but you have to be careful and know what you are doing (especially regarding your data structures). For example. the concat array in the second example is not good, but probably not so bad, but using lists here and concat them with: would be superfluous.

But this is nothing more than an educated assumption if you are not really measuring performance. In complex projects, it is really difficult to predict performance, especially since things like creating objects and method calls are becoming more and more optimized by the compiler and the JVM.

I would suggest starting with a functional style. If it is too slow, profile it. Usually there is a better functional solution. If not, you can use an imperative style (or a combination of both) as a last resort.