StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>You have raised multiple questions. I try to answer them in a logical order:</p> <h2>No stack overflow in the Stream version</h2> <p>You did not really ask this one, but it leads to some interesting observations.</p> <p>In the Stream version you are using <code> #:: merge(...)</code> inside the <code>merge</code> function. Usually this would be a recursive call and might lead to a stack overflow for big enough input data. But not in this case. The operator <code>#::(a,b)</code> is implemented in <code>class ConsWrapper[A]</code> (there is an implicit conversion) and is a synonym for <code>cons.apply[A](hd: A, tl: ⇒ Stream[A]): Cons[A]</code>. As you can see, the second argument is call by name, meaning it is evaluated lazily. </p> <p>That means <code>merge</code> returns a newly created object of type <code>cons</code> which will eventually call merge again. In other words: The recursion does not happen on the stack, but on the heap. And usually you have plenty of heap.</p> <p>Using the heap for recursion is a nice technique to handle very deep recursions. But it is much slower than using the stack. So you traded speed for recursion depth. This is the main reason, why using <code>Stream</code> is so slow. </p> <p>The second reason is, that for getting the length of the <code>Stream</code>, Scala has to materialize the whole <code>Stream</code>. But during sorting the <code>Stream</code> it would have to materialize each element anyway, so this does not hurt very much.</p> <h2>No stack overflow in List version</h2> <p>When you are changing Stream for List, you are indeed using the stack for recursion. Now a Stack overflow could happen. But with sorting, you usually have a recursion depth of <code>log(size)</code>, usually the logarithm of base <code>2</code>. So to sort 4 billion input items, you would need a about 32 stack frames. With a default stack size of at least 320k (on Windows, other systems have larger defaults), this leaves place for a lot of recursions and hence for lots of input data to be sorted.</p> <h2>Faster functional implementation</h2> <p>It depends :-)</p> <p>You should use the stack, and not the heap for recursion. And you should decide your strategy depending on the input data:</p> <ol> <li>For small data blocks, sort them in place with some straight forward algorithm. The algorithmic complexity won't bite you, and you can gain a lot of performance from having all data in cache. Of course, ou could still hand code <a href="http://en.wikipedia.org/wiki/Sorting_network" rel="nofollow">sorting networks</a> for the given sizes.</li> <li>If you have numeric input data, you can use <a href="http://en.wikipedia.org/wiki/Radix_sort" rel="nofollow">radix sort</a> and handle the work to the vector units on you processor or your GPU (more sophisticated algorithms can be found in <a href="http://http.developer.nvidia.com/GPUGems2/gpugems2_chapter46.html" rel="nofollow">GPU Gems</a>).</li> <li>For medium sized data blocks, you can use a divide-and-conquer strategy to split the data to multiple threads (only if you have multiple cores!)</li> <li>For huge data blocks use merge sort and split it of in blocks that fit in memory. If you want, you can distribute these blocks on the network and sort in memory.</li> </ol> <p>Don't use swap and use your caches. Use mutable data structures if you can and sort in place. I think that functional and fast sorting does not work very well together. To make sorting really fast, you will have to use stateful operations (e.g. in-place mergesort on mutable arrays).</p> <p>I usually try this on all my programs: Use pure functional style as far as possible but use stateful operations for small parts when feasible (e.g. because it has better performance or the code just has to deal with lots of states and becomes much better readable when I use <code>var</code>s instead of <code>val</code>s).</p>

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