Guido rethinking removal of cmp from sort method

[Raymond Hettinger]

On Mar 28, 8:43 am, Steven D'Aprano <steve
+comp.lang.pyt... at pearwood.info> wrote:
> Thank you for spending the time to get some hard data, but I can't
> replicate your results since you haven't shown your code. Rather than
> attempt to guess what you did and duplicate it, I instead came up with my
> own timing measurements. Results are shown here, my code follows below:
>
> [steve at sylar ~]$ python2.7 sort_test.py
> Comparison function: 12.1256039143
> Key function: 3.51603388786
> Double sort: 2.33165812492
> cmp_to_key: 28.1129128933
>
> By far the best result comes from two calls to sort. Not far off is the
> key function solution. (Admittedly, coming up with a key function for non-
> numeric data would be challenging.) The comparison function, and the
> cmp_to_key solution, are clearly *much* slower.

On Mar 28, 8:43 am, Steven D'Aprano <steve
+comp.lang.pyt... at pearwood.info> wrote:
> Thank you for spending the time to get some hard data, but I can't
> replicate your results since you haven't shown your code. Rather than
> attempt to guess what you did and duplicate it, I instead came up with my
> own timing measurements. Results are shown here, my code follows below:
>
> [steve at sylar ~]$ python2.7 sort_test.py
> Comparison function: 12.1256039143
> Key function: 3.51603388786
> Double sort: 2.33165812492
> cmp_to_key: 28.1129128933
>
> By far the best result comes from two calls to sort. Not far off is the
> key function solution. (Admittedly, coming up with a key function for non-
> numeric data would be challenging.) The comparison function, and the
> cmp_to_key solution, are clearly *much* slower.

There is less here than meets the eye.  The cmp-function dispatch in
cmp_to_key() is written in pure Python.  Essentially, the timings are
showing the already well-known fact that call forwarding is faster in
C than in pure python.

Each of the O(n log n) comparisons is run through pure Python code
that like this:

  def __lt__(self, other):
      # mycmp is nested scope variable pointing to
      # the user-defined cmp-function
      return mycmp(self.obj, other.obj) < 0

I intend to add a C version of cmp_to_key() so that no trips around
the eval-loop are needed.  It should be about as efficient as
bound_method dispatch (very fast), leaving the user-supplied cmp-
function as the dominant cost in the handful of cases where the
superfast O(n) key-function approach can't be used for some reason.

The memory overhead should either stay the same or drop slightly
(currently at 14 bytes per element on a 32-bit build and 28 bytes per
element on a 64-bit build).

Also note that running timings on Py2.7 instead of Py3.2 disadvantages
key-functions.  In 2.7, key-functions use sortwrapper objects which
were removed in 3.2 (saving memory and reducing dispatch time
considerably).  Also, in Py2.7 cmp logic is called even when a key-
function is defined (because key-function logic was wrapped around the
already existing sort with cmp-logic) so you pay the price of both
(i.e. creating a 2-tuple for cmp arguments on every call).  In Py3.x
the cmp logic is gone, making the remaining key-function logic even
faster.  IOW, key-function logic is way faster and more space
efficient in 3.2.

One of the implications of the last paragraph is that if 2.7 style cmp-
logic were reinstated in 3.3, not only would it clutter the API with
two-ways-to-do-it, it would also disadvantage make the common case
(using key-functions) run much more slowly.  In other words, the
performance mavens will have shot themselves (and us) in the foot.

Raymond