perl builtin sort has bad worst-case behavior

[Mark-Jason Dominus <mjd@Op.Net>]

Newsgroups: comp.lang.perl.misc
Path: monger.newsread.com!news-toy.newsread.com!netaxs.com!newsread.com!uunet!ffx.uu.net!news.research.att.com!nntp
From: "John P. Linderman" <jpl@research.att.com>
Subject: (unfortunate) performance of sort
X-Nntp-Posting-Host: gps.research.att.com
Content-Type: text/plain; charset=us-ascii
Message-ID: <387CA56D.43DBEE22@research.att.com>
Sender: nntp@research.att.com
Content-Transfer-Encoding: 7bit
Organization: AT&T Research
X-Accept-Language: en
Mime-Version: 1.0
Date: Wed, 12 Jan 2000 16:01:49 GMT
X-Mailer: Mozilla 4.51 [en] (X11; I; Linux 2.2.9 i686)
Xref: news-toy.newsread.com comp.lang.perl.misc:280860

Here's a simple test program:

    #!/usr/common/bin/perl -w

    use strict;
    use Benchmark;

    sub organpipe {
        my $size = 1 << shift;
        my @p = (1 .. int($size/2));    # increasing

        push(@p, reverse(@p));          # decreasing
        sort {$a <=> $b} @p;
    }

    my $count = 1;
    my $i;
    my @r;

    for ($i = 7; $i <= 17; $i++) {
        print("i=$i\t"); timethis($count, "\@r = &organpipe($i)");
    }

If you run it, you will notice that as the array size doubles
with each iteration, the run time quadruples (aka quadratic
behavior).  Here's output from my Linux PC running perl 5.005_03:

i=7     timethis 1:  0 wallclock secs ( 0.01 usr +  0.00 sys =  0.01
CPU)
            (warning: too few iterations for a reliable count)
i=8     timethis 1:  0 wallclock secs ( 0.01 usr +  0.00 sys =  0.01
CPU)
i=9     timethis 1:  0 wallclock secs ( 0.05 usr +  0.00 sys =  0.05
CPU)
i=10    timethis 1:  1 wallclock secs ( 0.20 usr +  0.00 sys =  0.20
CPU)
i=11    timethis 1:  1 wallclock secs ( 0.82 usr +  0.00 sys =  0.82
CPU)
i=12    timethis 1:  7 wallclock secs ( 3.26 usr +  0.00 sys =  3.26
CPU)
i=13    timethis 1: 27 wallclock secs (13.21 usr +  0.00 sys = 13.21
CPU)
i=14    timethis 1: 118 wallclock secs (58.23 usr +  0.00 sys = 58.23
CPU)
i=15    timethis 1: 500 wallclock secs (246.62 usr +  0.08 sys = 246.70
CPU)
i=16    timethis 1: 2047 wallclock secs (1009.31 usr +  0.22 sys =
1009.53 CPU)

[I edited out all but the first ``too few iterations'' warning.
One iteration is quite adequate to produce a reliable count.
I gave up waiting for i=17, the trend is clear.]

This has nothing to do with the time to initialize the array, as you
can tell by rerunning after removing the "\@r = " from the timethis
call:
evidently, somebody is clever enough to recognize that the sort
can be optimized out in this context, and run times are simply linear
in array size.

It also has little to do with the {$a <=> $b} comparison function.
GRT isn't going to save you here, it is perl's qsort implementation
that is flawed (unless, of course, my test is in error, but I think
that's unlikely).  For those not interested in a discussion of the
problem, simply be warned that perl's sort *might* go quadratic.
This wouldn't (and doesn't) keep me from using it, but it's something
that deserves attention.

[ Perl content gets very low in what follows. ]
The problem with the qsort implementation (as found in the perl5.005_63
development release pp_ctl.c) is the choice of the pivot element.
Median-of-three is a good idea, but using the middle three elements in
the partition exposes the choice to organ-pipe input (as does using
the first, last and middle elements, as I found out in one of my own
sub-optimal qsort implementations).  For organ-pipe input, all three
elements are extreme, so no matter which element is selected for the
pivot, it does a pessimal job of splitting the partition, and leaves
the (large) remaining partition in the same organ-pipe configuration.

You can complain that the organ-pipe input is artificial, but I knew
to try it because an innocent user tripped over the same problem in
that qsort implementation I wrote.  *ALL* qsort implementations will
go quadratic on some inputs (which is why my external sorts now use
merge-sort or radix-sort implementations, which don't), but they don't
have to do so on inputs as common as organ-pipe data.

Any further discussion of sort implementations might better
be taken offline.

John P. Linderman       jpl@research.att.com

---

Follow-Ups from:

Tom Hughes <tom@compton.nu>

---

[Date Prev][Date Next] [Thread Prev][Thread Next] [Date Index][Thread Index][Top&Search][Original]

---