StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POFunctional programming - is immutability expensive?
text
Body
copied!<p>The question is in two parts. The first is conceptual. The next looks at the same question more concretely in Scala.</p> <ol> <li>Does using only immutable data structures in a programming language make implementing certain algorithms/logic inherently more computationally expensive in practice? This draws to the fact that immutability is a core tenet of purely functional languages. Are there other factors that impact this? </li> <li>Let's take a more concrete example. <a href="http://en.wikipedia.org/wiki/Quicksort" rel="noreferrer">Quicksort</a> is generally taught and implemented using mutable operations on an in-memory data structure. How does one implement such a thing in a PURE functional way with a comparable computational and storage overhead to the mutable version. Specifically in Scala. I have included some crude benchmarks below. </li> </ol> <h3>More Details:</h3> <p>I come from an imperative programming background (C++, Java). I have been exploring functional programming, specifically Scala.</p> <p>Some of the primary principles of pure functional programming:</p> <ol> <li>Functions are first class citizens.</li> <li>Functions do not have side effects and hence objects/data structures are <a href="http://en.wikipedia.org/wiki/Immutable_object" rel="noreferrer">immutable</a>.</li> </ol> <p>Even though modern <a href="http://en.wikipedia.org/wiki/Java_virtual_machine" rel="noreferrer">JVMs</a> are extremely efficient with object creation and <a href="http://en.wikipedia.org/wiki/Garbage_collection_%28computer_science%29" rel="noreferrer">garbage collection</a> is very inexpensive for short lived objects, it's probably still better to minimize object creation right? At least in a single-threaded application where concurrency and locking is not an issue. Since Scala is a hybrid paradigm, one can choose to write imperative code with mutable objects if necessary. But, as someone who has spent a lot of years trying to reuse objects and minimize allocation. I would like a good understanding of the school of thought that would not even allow that.</p> <p>As a specific case, I was a little surprised by this code snippet in <a href="http://www.ibm.com/developerworks/java/library/j-scala03268.html" rel="noreferrer">this tutorial</a> <a href="http://www.tedneward.com/about.aspx" rel="noreferrer">6</a> . It has a Java version of Quicksort followed by a neat looking Scala implementation of the same.</p> <p>Here is my attempt to benchmark the implementations. I haven't done detailed profiling. But, my guess is that the Scala version is slower because the number of objects allocated is linear (one per recursion call). Is there any way chance that tail call optimizations can come into play? If I am right, Scala supports tail call optimizations for self-recursive calls. So, it should only be helping it. I am using Scala 2.8.</p> <h3>Java version</h3> <pre><code>public class QuickSortJ { public static void sort(int[] xs) { sort(xs, 0, xs.length -1 ); } static void sort(int[] xs, int l, int r) { if (r >= l) return; int pivot = xs[l]; int a = l; int b = r; while (a <= b){ while (xs[a] <= pivot) a++; while (xs[b] > pivot) b--; if (a < b) swap(xs, a, b); } sort(xs, l, b); sort(xs, a, r); } static void swap(int[] arr, int i, int j) { int t = arr[i]; arr[i] = arr[j]; arr[j] = t; } } </code></pre> <h3>Scala version</h3> <pre><code>object QuickSortS { 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 <))) } } </code></pre> <h3>Scala Code to compare implementations</h3> <pre><code>import java.util.Date import scala.testing.Benchmark class BenchSort(sortfn: (Array[Int]) => Unit, name:String) extends Benchmark { val ints = new Array[Int](100000); override def prefix = name override def setUp = { val ran = new java.util.Random(5); for (i <- 0 to ints.length - 1) ints(i) = ran.nextInt(); } override def run = sortfn(ints) } val benchImmut = new BenchSort( QuickSortS.sort , "Immutable/Functional/Scala" ) val benchMut = new BenchSort( QuickSortJ.sort , "Mutable/Imperative/Java " ) benchImmut.main( Array("5")) benchMut.main( Array("5")) </code></pre> <h3>Results</h3> <p>Time in milliseconds for five consecutive runs</p> <pre><code>Immutable/Functional/Scala 467 178 184 187 183 Mutable/Imperative/Java 51 14 12 12 12 </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload