[Python-Dev] Sorting

[Tim Peters]

[Tim]
> ...
> There's also a significant systematic regression in timsort's +sort case,
> ... also a mix of small regressions and speedups in 3sort.
> These are because, to simplify experimenting, ...(and as many as
> N-1 temp pointers can be needed, up from N/2).  That's all repairable,
> it's just a PITA to do it.

It's repaired, and those glitches went away:

> timsort
>  i    2**i  *sort  \sort  /sort  3sort  +sort  ~sort  =sort  !sort
> 15   32768   0.17   0.01   0.02   0.01   0.01   0.05   0.01   0.02
> 16   65536   0.24   0.02   0.02   0.02   0.02   0.09   0.02   0.04
> 17  131072   0.54   0.05   0.04   0.05   0.05   0.19   0.04   0.09
> 18  262144   1.17   0.09   0.09   0.10   0.10   0.38   0.09   0.18
> 19  524288   2.56   0.18   0.17   0.20   0.20   0.79   0.17   0.36
> 20 1048576   5.54   0.37   0.35   0.37   0.41   1.62   0.35   0.73

Now at

  15   32768   0.17   0.01   0.01   0.01   0.02   0.09   0.01   0.03
  16   65536   0.24   0.02   0.02   0.02   0.02   0.09   0.02   0.04
  17  131072   0.53   0.05   0.04   0.05   0.05   0.18   0.04   0.09
  18  262144   1.17   0.09   0.09   0.10   0.09   0.38   0.09   0.18
  19  524288   2.56   0.18   0.18   0.19   0.19   0.78   0.17   0.36
  20 1048576   5.53   0.37   0.35   0.36   0.37   1.60   0.35   0.74

In other news, an elf revealed that Perl is moving to an adaptive stable
mergesort(!!!harmonic convergence!!!), and sent some cleaned-up source code.
The comments reference a non-existent paper, but if I change the title and
the year I find it here:

   Optimistic sorting and information theoretic complexity.
   Peter McIlroy.
   SODA (Fourth Annual ACM-SIAM Symposium on Discrete Algorithms), pp
   467-474, Austin, Texas, 25-27 January 1993.

Jeremy got that for me, and it's an extremely relevant paper.  What I've
been calling galloping he called "exponential search", and the paper has
some great analysis, pretty much thoroughly characterizing the set of
permutations for which this kind approach is helpful, and even optimal.
It's a large set <wink>.

Amazingly, citeseer finds only one reference to this paper, also from 1993,
and despite all the work done on adaptive sorting since then.  So it's
either essentially unknown in the research community, was shot full of holes
(but then people would have delighted in citing it just to rub that in <0.5
wink>), or was quickly superceded by a better result (but then ditto!).

I'll leave that a mystery.

I haven't had time yet to study the Perl code.  The timsort algorithm is
clearly more frugal with memory:  worst-case N/2 temp pointers needed, and,
e.g., in +sort it only needs (at most) 10 temp pointers (independent of N).
That may or may not be good, though, depending on whether the Perl algorithm
makes more effective use of the memory hierarchy; offhand I don't think it
does.  OTOH, timsort has 4 flavors of galloping and 2 flavors of binary
search and 2 merge routines, because the memory-saving gimmick can require
merging "from the left" or "from the right", depending on which run is
smaller.  Doubling the number of helper routines is what "PITA" meant in the
quote at the start <wink>.

One more bit of news:  cross-box performance of this stuff is baffling.
Nobody else has tried timsort yet (unless someone who asked for the code
tried an earlier version), but there are Many Mysteries just looking at the
numbers for /sort under current CVS Python.  Recall that /sort is the case
where the data is already sorted:  it does N-1 compares in one scan, and
that's all.  For an array with 2**20 distinct floats that takes 0.35 seconds
on my Win98SE 866MHz Pentium box, compiled w/ MSVC6.  On my Win2K 866MHz
Pentium box, compiled w/ MSVC6, it takes 0.58(!) seconds, and indeed all the
sort tests take incredibly much longer on the Win2K box.  On Fred's faster
Pentium box (I forget exactly how fast, >900MHz and <1GHz), using gcc, the
sort tests take a lot less time than on my Win2K box, but my Win98SE box is
still faster.

Another Mystery (still with the current samplesort):  on Win98SE, !sort is
always a bit faster than *sort.  On Win2K and on Fred's box, it's always a
bit slower.  I'm leaving that a mystery too.  I haven't tried timsort on
another box yet, and given that my home machine may be supernaturally fast,
I'm never going to <wink>.