[issue11707] Create C version of functools.cmp_to_key()

[Raymond Hettinger]

Raymond Hettinger  added the comment:

I agree (and was going back and forth between +0 and -0).

--
status: open -> closed

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11707] Create C version of functools.cmp_to_key()

[Georg Brandl]

Georg Brandl  added the comment:

I would have to say that this looks hardly a trivial speed patch, and chances 
are we cannot guarantee 100% behavior compatibility with the pure-Python 
version.

If you disagree with these two points, then I'm okay with it going in.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11707] Create C version of functools.cmp_to_key()

[Raymond Hettinger]

Raymond Hettinger  added the comment:

Georg, would you opine on whether this should to into 3.2.1?

--
status: closed -> open

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11707] Create C version of functools.cmp_to_key()

[Filip Gruszczyński]

Filip Gruszczyński  added the comment:

I see. Thanks :-)

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11707] Create C version of functools.cmp_to_key()

[Raymond Hettinger]

Raymond Hettinger  added the comment:

Georg, do you care to opine on whether this should go into 3.2.1?  (I don't 
have any preference).

There is a big thread on comp.lang.python where a number of people seem to be 
very concerned about the efficiency of cmp_to_key().  OTOH, we almost never 
backport performance patches unless the speed is so slow as to be unusable.

--
assignee: rhettinger -> georg.brandl
nosy: +georg.brandl
resolution:  -> accepted

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11707] Create C version of functools.cmp_to_key()

[Raymond Hettinger]

Raymond Hettinger  added the comment:

> why keyobject_type needed traverse function?

I used to know this but don't any more.  It might not be necessary.  Most of 
the types I write all use GC so it may just be habit.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11707] Create C version of functools.cmp_to_key()

[Filip Gruszczyński]

Filip Gruszczyński  added the comment:

I have a follow-up question: why keyobject_type needed traverse function? From 
what I read in docs I assumed it is required for GC tracked types. Why was it 
required here and how it is used?

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11707] Create C version of functools.cmp_to_key()

[Raymond Hettinger]

Raymond Hettinger  added the comment:

> functools_cmp_to_key() doesn't 
> check that the argument is a callable.

I don't think that is necessary; it will fail with a TypeError when the attempt 
is made to call it.  This is the approach we take elsewhere (look at the 
built-in filter() function for example).

That being said, if you really think the early check is necessary, feel free to 
check it in.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11707] Create C version of functools.cmp_to_key()

[STINNER Victor]

STINNER Victor  added the comment:

functools_cmp_to_key() doesn't check that the argument is a callable.

>>> table=list(range(3))
>>> table.sort(key=functools.cmp_to_key(3))
Traceback (most recent call last):
  File "", line 1, in 
TypeError: 'int' object is not callable

PyCallable_Check() should be used, something like:

if (!PyCallable_Check(cmp)) {
PyErr_SetString(PyExc_TypeError, "parameter must be callable");
return NULL;
}

--
nosy: +haypo

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11707] Create C version of functools.cmp_to_key()

[Roundup Robot]

Roundup Robot  added the comment:

New changeset 76ed6a061ebe by Victor Stinner in branch 'default':
Issue #11707: Fix compilation errors with Visual Studio
http://hg.python.org/cpython/rev/76ed6a061ebe

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11707] Create C version of functools.cmp_to_key()

[Raymond Hettinger]

Raymond Hettinger  added the comment:

Thanks for the patch Filip.

Closing this.  If anyone wants to lobby the RM for a 3.2 backport, feel free to 
re-open and assign to the release manager for consideration.

--
status: open -> closed

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11707] Create C version of functools.cmp_to_key()

[Roundup Robot]

Roundup Robot  added the comment:

New changeset a03fb2fc3ed8 by Raymond Hettinger in branch 'default':
Issue #11707: Fast C version of functools.cmp_to_key()
http://hg.python.org/cpython/rev/a03fb2fc3ed8

--
nosy: +python-dev

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11707] Create C version of functools.cmp_to_key()

[Raymond Hettinger]

Raymond Hettinger  added the comment:

Attaching cleaned-up version of the patch, making it more like the pure python 
version:

* Made 'obj' a member so it is an accessible field
* Accept keyword arguments
* Create arg tuple like was done in the Py2.7 code
* Create the zero only once
* Expanded tests to cover all code paths

--
Added file: http://bugs.python.org/file21538/11707_4.patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11707] Create C version of functools.cmp_to_key()

[Raymond Hettinger]

Raymond Hettinger  added the comment:

Attaching timing code.

Results with and without patch (as cleaned-up):

  7.1 seconds without patch
  3.2 seconds with patch

--
Added file: http://bugs.python.org/file21537/time_cmp_to_key.py

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11707] Create C version of functools.cmp_to_key()

[Raymond Hettinger]

Raymond Hettinger  added the comment:

I'm working on cleaning-up (and speeding-up) the patch.  I'll post new timings 
once that's done.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11707] Create C version of functools.cmp_to_key()

[Filip Gruszczyński]

Filip Gruszczyński  added the comment:

Here are some example performance results:

def cmp(x, y):
return y - x

sorted(range(1, 1000), key=cmp_to_key(cmp))

'''
C version:
real0m19.994s
user0m8.053s
sys 0m1.044s

Python version:
real0m28.825s
user0m28.046s
sys 0m0.728s

'''


def cmp(x, y):
x = int(x)
y = int(y)
return (x > y) - (y > x)

sorted([str(i) for i in reversed(range(1, 200))], key=cmp_to_key(cmp))

'''
Python version

real0m15.930s
user0m15.629s
sys 0m0.284s

C version

real0m10.880s
user0m10.585s
sys 0m0.284s
'''

There is some performance gain. I don't know however, if it's enough to use C 
version instead of Python, that's for Raymond to decide.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11707] Create C version of functools.cmp_to_key()

[Raymond Hettinger]

Raymond Hettinger  added the comment:

I was only aiming for Py3.3.  

If someone wanted to push for a backport to 3.2, it would be up to the release 
manager to decide whether a performance booster would be worth the risk of 
introducing a bug in a point release.

ISTM that if someone really cared about performance, they would probably 
already be using an O(n) key-function approach.  This patch eliminates most of 
the overhead for calling a cmp-function, but it can't do anything about the 
body of the user-supplied cmp-function which will dominate the running time if 
it does anything useful.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11707] Create C version of functools.cmp_to_key()

[Terry J. Reedy]

Terry J. Reedy  added the comment:

[Question from python-list]
Would a C version only be for 3.3 or backported to 3.2 and 2.7. The rationale 
for backport to 2.7 is that .cmp_to_key was added to 2.7 to aid transition to 
3.x. A faster version would make use in 2.7 more inviting.

I understand that there is concern that performance enhancements may have 
unforseen effects.

--
nosy: +terry.reedy

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11707] Create C version of functools.cmp_to_key()

[Raymond Hettinger]

Raymond Hettinger  added the comment:

FWIW, the PSF is working towards getting electronic signatures for contributor 
agreements.  In the mean time, a scan or photo would work just fine.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11707] Create C version of functools.cmp_to_key()

[Filip Gruszczyński]

Filip Gruszczyński  added the comment:

I worked a little on the tests. Only then I have noticed, that cmp_to_key tests 
weren't run, so I have encountered some problems, when I finally turned them 
on. I have added some of my tests, fixed some things in the patch and now it 
seems to work fine. I have added traverse method and decrease reference counts 
in dealloc.

I haven't had yet time to run some performance tests, but I'll try to do that.

I'll try to submit contributor agreement. It's a pity, that I can't send a 
signed copy through email. It'll take some time, before it comes from Poland.

--
Added file: http://bugs.python.org/file21523/11707_3.patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11707] Create C version of functools.cmp_to_key()

[Raymond Hettinger]

Raymond Hettinger  added the comment:

Filip, can you please submit a contributor agreement?

http://docs.python.org/devguide/coredev.html#sign-a-contributor-agreement

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11707] Create C version of functools.cmp_to_key()

[Nick Coghlan]

Changes by Nick Coghlan :


--
nosy: +ncoghlan

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11707] Create C version of functools.cmp_to_key()

[Raymond Hettinger]

Raymond Hettinger  added the comment:

Nice work.  There are a few nits (dealloc and traverse need to address both 
python objects in the struct).  I will look at the patch in detail when I get a 
chance (in the next week or so).

It would be great if more tests were added (in general, C equivalents require 
more testing than their pure Python counterparts).

If you get a chance, it would be great if we could see some timings to 
demonstrate that we're getting a significant improvement (that being the 
primary motivation for the patch).

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11707] Create C version of functools.cmp_to_key()

[Filip Gruszczyński]

Filip Gruszczyński  added the comment:

Ok, here is patch that keep python implementation of cmp_to_key if C version 
can't be imported.

Thanks again for you help :-)

--
Added file: http://bugs.python.org/file21505/11707_2.patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11707] Create C version of functools.cmp_to_key()

[Eric Smith]

Eric Smith  added the comment:

I haven't had time to look at this in detail, but the concept appears sound. 
I'll try to devote some time to it, but hopefully someone else on 
core-mentorship with more familiarity with this code will also be able to 
review it.

One thing: You don't want to delete the pure Python version, as that can be 
used by alternate implementations. You want to leave it in place, and then 
after it try to import the C version. If the import fails, the Python version 
will be used, if it succeeds, the C version will be used. I'm reasonably sure 
there are examples of testing both implementations elsewhere in the stdlib. 
Maybe ask on core-mentorship for pointers.

Thanks for working on this!

--
nosy: +eric.smith

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11707] Create C version of functools.cmp_to_key()

[Filip Gruszczyński]

Filip Gruszczyński  added the comment:

Here is a patch that passes functools tests. I'll be happy to work on it 
further.

--
keywords: +patch
Added file: http://bugs.python.org/file21504/11707.patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11707] Create C version of functools.cmp_to_key()

[Daniel Stutzbach]

Changes by Daniel Stutzbach :


--
nosy: +stutzbach

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11707] Create C version of functools.cmp_to_key()

[Daniel Urban]

Changes by Daniel Urban :


--
nosy: +durban

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11707] Create C version of functools.cmp_to_key()

[Filip Gruszczyński]

Changes by Filip Gruszczyński :


--
nosy: +gruszczy

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11707] Create C version of functools.cmp_to_key()

[Raymond Hettinger]

New submission from Raymond Hettinger :

For cases where the underlying comparison function is in C (strcoll for 
example), the pure Python dispatch in cmp_to_key dominates running time.  This 
can be reduced considerably by writing cmp_to_key in C, making its overhead as 
low or lower than the cost of bound method dispatch.

--
assignee: rhettinger
components: Interpreter Core
keywords: easy
messages: 132448
nosy: rhettinger
priority: low
severity: normal
stage: needs patch
status: open
title: Create C version of functools.cmp_to_key()
type: performance
versions: Python 3.3

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com