how-to-sort-faster-in-perl.tt

=title How to sort faster in Perl?
=timestamp 2012-12-11T11:45:57
=indexes map, sort, Schwartzian
=status show
=author szabgab
=index 1
=archive 1
=feed 1
=comments 1
=social 1


=abstract start

Sorting a list of files by ASCII ordering of their name works very fast. Even
if the list is long.

On the other hand, if you need to sort them based on the size of the files,
it can be much slower.

=abstract end

<h2>Sorting files according to name</h2>

This simplified code example creates a list of xml files and then sorts them according to the alphabetical order of
their names. It is fast.

<code lang="perl">

#!/usr/bin/perl
use strict;
use warnings;

my @files = glob "*.xml";

my @sorted_files = sort @files;
</code>

<h2>Sorting files by length of name</h2>

<code lang="perl">
my @sorted_length = sort { length($a) <=> length($b) } @files;
</code>

For 3000 files, this was 3 times slower than sorting by ASCII name, but was still quite fast.

<h2>Sorting files by file size</h2>

When I tried to sort the 3000 files based on their size, it took 80 times(!) the time sorting the names based on ASCII.

<code lang="perl">
my @sort_size = sort { -s $a <=> -s $b } @files;
</code>

This, of course, is not surprising. In the first case, perl only had to compare values.
In the second case perl had to compute the length of the strings before comparing them.
In the 3rd case, for every comparison, it had to go to the hard disk and fetch the size of both files.

Accessing the disk is a lot slower than accessing memory which explains the slowdown.

The question, <b>can we improve it?</b>.

The problem of accessing the disk is amplified by how sort works.

There are various sorting algorithms
in the world (<a href="http://en.wikipedia.org/wiki/Quicksort">Quicksort</a>,
<a href="http://en.wikipedia.org/wiki/Bubblesort">Bubblesort</a>,
<a href="http://en.wikipedia.org/wiki/Mergesort">Mergesort</a>, etc.)
Depending on the input, some of these can be faster, some a bit slower. Perl used to have
Quicksort, then it was switched to Mergesort. Today, if you really want, you can decide which one to
use via the <a href="http://perldoc.perl.org/sort.html">sort</a> pragma.

Regardless what you choose, on average, you will have at least N*log(N) comparisons. Which means for
N = 1000 files perl will need to access the disk 2 * 1000 * 3 = 6000 times. (Twice for every comparisons.)
For every file perl fetches the size of the file 6 times! It is a total waste of energy.

We can't avoid accessing the disk for the files sizes, and we cannot reduce the number of comparisons,
but we can reduce the number of times the disk is accessed.

<h2>Pre-fetching the size</h2>

We are going to fetch all the file sizes up-front, store them in memory,
and then run the sort on data that can be found in the memory already.

<code lang="perl">
my @unsorted_pairs = map  { [$_, -s $_] } @files;
my @sorted_pairs   = sort { $a->[1] <=> $b->[1] } @unsorted_pairs;
my @quickly_sorted_files = map  { $_->[0] } @sorted_pairs;
</code>

This might look a bit more complicated than what you'd write, but bare with me.
It will be used in a more simple way.

There are 3 steps here. In the first step we go over the list of files and for each file
we create an ARRAY reference. In the array reference we have two elements. The first one is
the name of the file, the second one is the size of the file. This will access the disk once
for every file.

In the second step, we sort the array of the small array references. When comparing two of those
small array references we fetch the element [1] of each one of them, and compare those values.
The result is another array of small array references.

In the third step we throw away the sizes and build a list of the filenames only.
What we originally wanted.


<h2>Schwartzian transform</h2>

For the above code we used 2 temporary array, that are not really necessary.
We could create a single statement that will do all the work. For this we
need to reverse the order of the statements as "data flows from right to left"
in Perl, but if we put each statement on its own line, and if we leave enough
space around the curly braces, we can have a readable piece of code.

<code lang="perl">
my @quickly_sorted_files =
    map  { $_->[0] }
    sort { $a->[1] <=> $b->[1] }
    map  { [$_, -s $_] }
    @files;
</code>

This is called the <a href="http://en.wikipedia.org/wiki/Schwartzian_transform">Schwartzian transform</a>
named after <a href="http://en.wikipedia.org/wiki/Randal_L._Schwartz">Randal L. Schwartz</a>.

When seen in code, it can be easily recognized by the map-sort-map construct.

It can be used for sorting anything, but it is especially useful when the
computation of the values to be compared is relatively heavy.

<code lang="perl">
my @sorted =
    map  { $_->[0] }
    sort { $a->[1] <=> $b->[1] }
    map  { [$_, f($_)] }
    @unsorted;
</code>


Using this algorithm for sorting the 3000 xml files the sorting became "only" 10 times slower than the
ASCII sort which means it is about 8 times faster than the code we had at the beginning.


<h2>Conclusion</h2>

Effectively we gain speed and pay by higher memory usage and code complexity.
For small arrays it is not worth it, and for large arrays it is only worth if
this change has a real impact on your program.

If the whole sorting takes up 1 second from a script that runs for 10 minutes,
then probably it is not worth the investment. On the other hand if the sorting
is a larger part of the total run-time, you should probably use the Schwartzian
transformation.

In order to find out which is the case, use <a href="https://metacpan.org/module/Devel::NYTProf">Devel::NYTProf to
profile</a> your code.

(Thanks to <a href="http://twitter.com/Smylers2">Smylers</a> for reviewing the article.)