[issue9915] speeding up sorting with a key

Antoine Pitrou added the comment: Thank you! -- ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.pyt

[issue9915] speeding up sorting with a key

Changes by Daniel Stutzbach : -- components: +Interpreter Core -Library (Lib) resolution: -> accepted stage: patch review -> committed/rejected status: open -> closed ___ Python tracker

[issue9915] speeding up sorting with a key

Daniel Stutzbach added the comment: Committed as r86937. Thanks again for reviewing! Although I do not anticipate any problems, I will keep an eye on the buildbots just in case. Antoine, regarding "ms->alloced = (list_size + 1) / 2;", I ended up adding an extensive comment after all. -

[issue9915] speeding up sorting with a key

Raymond Hettinger added the comment: AP: I've already given my blessing to the patch. Just wanted to note what the existing code did. I also trust timings but recognize that they reflect a particular build configuration (compiler/processor/o.s)and the usage pattern for a particular benchmark.

[issue9915] speeding up sorting with a key

Antoine Pitrou added the comment: > Just wanted to post this so there weren't any illusions about the > patch being a big win. Daniel has already posted benchmark numbers, I would trust them rather than any theoretical speculation about whether the patch is interesting or not. --

[issue9915] speeding up sorting with a key

Daniel Stutzbach added the comment: > Just wanted to post this so there weren't any illusions about the > patch being a big win. > When a key function is defined, this is all you can possibly shave > off the time for a comparison. I don't want to argue whether the patch is a big win or not (I

[issue9915] speeding up sorting with a key

Raymond Hettinger added the comment: Just for the record, I wanted to highlight how little room there is for optimization here. The sort wrapper is *very* thin: sortwrapper_richcompare(sortwrapperobject *a, sortwrapperobject *b, int op) { if (!PyObject_TypeCheck(b, &PySortWrapper_Type)) {

[issue9915] speeding up sorting with a key

Daniel Stutzbach added the comment: > The use of Py_LOCAL_INLINE is new to me since we usually use #define > instead, but this has a cleaner look to it. I am unclear on whether > all the our target compilers support an inline keyword. If you're > sure it works everywhere, that's great. I fi

[issue9915] speeding up sorting with a key

Raymond Hettinger added the comment: Thanks. This nice, clean diff is much more reviewable and it looks like what I expected. The use of Py_LOCAL_INLINE is new to me since we usually use #define instead, but this has a cleaner look to it. I am unclear on whether all the our target comp

[issue9915] speeding up sorting with a key

Daniel Stutzbach added the comment: Antoine and Raymond, thank you for the valuable feedback. Attached is a revised version of the patch, which restricts changes to those directly related to moving elements in the keys and values arrays at the same time. I apologize for having gotten a littl

[issue9915] speeding up sorting with a key

Raymond Hettinger added the comment: +1 on the basic idea of moving elements in the keys and values arrays at the same time thereby eliminating the fragmented memory overhead of the sortwrapper indirection. I would like the patch to be restricted to just that change. The other tweaks are no

[issue9915] speeding up sorting with a key

Changes by Mark Dickinson : -- nosy: +mark.dickinson ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail

[issue9915] speeding up sorting with a key

Antoine Pitrou added the comment: > My original patch was much more focused, but had a slightly larger > performance penalty for sorting random keys (see > http://bugs.python.org/msg122178). Do you think the performance > tradeoff there was still worthwhile? I am not objecting against the perf

[issue9915] speeding up sorting with a key

Daniel Stutzbach added the comment: Antoine, My original patch was much more focused, but had a slightly larger performance penalty for sorting random keys (see http://bugs.python.org/msg122178). Do you think the performance tradeoff there was still worthwhile? Ihave uploaded my original pa

[issue9915] speeding up sorting with a key

Daniel Stutzbach added the comment: Antoine Pitrou wrote: > Next time, please upload a single patch. Really. I haven't used Rietveld that much yet, and I'm still learning best-practices. I apologize for the painful experience. For anyone else planning to take a look at this, here it is as on

[issue9915] speeding up sorting with a key

Antoine Pitrou added the comment: > > I ended up loading my incremental patches in, but it's easy enough to > > diff the base with the last patch. If for some reasons it doesn't > > work as conveniently as I expect, let me know and I will upload it to > > Rietveld again as one big patch. > > I

[issue9915] speeding up sorting with a key

Antoine Pitrou added the comment: > The Rietveld issue is here: > http://codereview.appspot.com/3269041 > > I ended up loading my incremental patches in, but it's easy enough to > diff the base with the last patch. If for some reasons it doesn't > work as conveniently as I expect, let me know

[issue9915] speeding up sorting with a key

Daniel Stutzbach added the comment: > How did it get *faster* than the original (in the case with no > key-function)? I was able to shave off some instructions in countrun(), binarysort(), and the setup and cleanup code in listsort() proper. For small n, these made a difference. > Is there

[issue9915] speeding up sorting with a key

Raymond Hettinger added the comment: > If the "key" parameter was not used, then the values pointer > is a null pointer. . . . > Since the branch will always be the same throughout any given > call to sort(), CPU branch prediction is effective making the > branches fairly inexpensive. I se

[issue9915] speeding up sorting with a key

Daniel Stutzbach added the comment: Raymond Hettinger added the comment: > That result is surprising though -- I thought the concept was > manipulate the key and value arrays at the same time instead of just > the keys If the "key" parameter was not used, then the values pointer is a null poin

[issue9915] speeding up sorting with a key

Raymond Hettinger added the comment: Thanks for the revisions and timing updates. I'm heartened that the common-case of sorting without a key function isn't negatively impacted. That result is surprising though -- I thought the concept was manipulate the key and value arrays at the same tim

[issue9915] speeding up sorting with a key

Daniel Stutzbach added the comment: Antoine Pitrou wrote: > Right, that wouldn't suit your present purposes. But apparently you > are proposing to add a list sorting benchmark to the Tools directory, > with lots of duplicated code from that repo... Oh, I just stuck that under Tools because it

[issue9915] speeding up sorting with a key

Antoine Pitrou added the comment: Le mardi 23 novembre 2010 à 00:10 +, Daniel Stutzbach a écrit : > Daniel Stutzbach added the comment: > > Antoine Pitrou wrote: > > Why don't you contribute a list sorting benchmark to the suite in > > http://hg.python.org/benchmarks/? > > I considered

[issue9915] speeding up sorting with a key

Daniel Stutzbach added the comment: Antoine Pitrou wrote: > Why don't you contribute a list sorting benchmark to the suite in > http://hg.python.org/benchmarks/? I considered that, but I want to separately benchmark sorting different kinds and quantities of data. AFAIK, there isn't an easy

[issue9915] speeding up sorting with a key

Antoine Pitrou added the comment: > Worthwhile trade? +1 obviously. Why don't you contribute a list sorting benchmark to the suite in http://hg.python.org/benchmarks/? -- ___ Python tracker _

[issue9915] speeding up sorting with a key

Changes by Daniel Stutzbach : Added file: http://bugs.python.org/file19781/detailed-speed-results.txt ___ Python tracker ___ ___ Python-bugs-li

[issue9915] speeding up sorting with a key

Changes by Daniel Stutzbach : Added file: http://bugs.python.org/file19780/sort-faster.patch ___ Python tracker ___ ___ Python-bugs-list mailin

[issue9915] speeding up sorting with a key

Daniel Stutzbach added the comment: I'm starting to get settled in here at Google and finding time to follow up on everything that got put on hold while moving. Based on the feedback everyone gave me (thanks!), I greatly revised my script for comparing the speed of sort(). It's now compares

[issue9915] speeding up sorting with a key

Daniel Stutzbach added the comment: > what about adding a simple "random.seed(12345)" That's an excellent suggestion! In fact, I'm embarrassed that it never occurred to me (especially since I have used it in other projects). I will have a revised speed_test along with more extensive measurem

[issue9915] speeding up sorting with a key

Amaury Forgeot d'Arc added the comment: > the random data you run in interpreter 1 won't be the same data > you run in interpreter 2 what about adding a simple "random.seed(12345)" -- nosy: +amaury.forgeotdarc ___ Python tracker

[issue9915] speeding up sorting with a key

Daniel Stutzbach added the comment: > Does this help any? No :-) The problem is that the random data you run in interpreter 1 won't be the same data you run in interpreter 2, so the results are not directly comparable. One of the sets of random data may be more easily sortable than the othe

[issue9915] speeding up sorting with a key

Terry J. Reedy added the comment: Does this help any? >>> import random >>> from timeit import timeit >>> testlist = list(range(10)) >>> random.shuffle(testlist) >>> timeit('t=list(testlist); t.sort()', 'from __main__ import testlist', number=1) 0.1467957519740679 I just learned the imp

[issue9915] speeding up sorting with a key

Daniel Stutzbach added the comment: > Since the patch is intended to speed up 3.2 and your posted > experiments were run on that, I am puzzled that you would post a > test script to run under late 2.x instead of 3.1+. I had originally written the test script was originally written for somethin

[issue9915] speeding up sorting with a key

Terry J. Reedy added the comment: The posted experiments on sorted data do not do any sorting. They only test the difference in setup and comparison speed and not sorting/swapping speed. Please post something with large arrays of random data. Since the patch is intended to speed up 3.2 and yo

[issue9915] speeding up sorting with a key

Daniel Stutzbach added the comment: Attached is my script for running a more comprehensive battery of speed tests. The script itself requires Python 2.6 with argparse installed or Python 2.7 (which includes argparse). For obvious reasons, please make sure that your unpatched and patched vers

[issue9915] speeding up sorting with a key

Changes by Eric Smith : -- nosy: +eric.smith ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.

[issue9915] speeding up sorting with a key

Daniel Stutzbach added the comment: Antoine said: > I don't think there's any point in micro-optimizations such as > stack_keys. Good point. I'll try taking that out and see how it impacts the timing. Raymond said: > The memmove, memcpy functions are tricky to time because of varying > perfor

[issue9915] speeding up sorting with a key

Raymond Hettinger added the comment: Conceptually, this is a reasonable approach. I originally put in the sortwrapper as a straight-forward technique of tackling the 2.x API which allowed a key-function, or a cmp-function, or both, or neither. IOW, the original motivation is now gone. Th

[issue9915] speeding up sorting with a key

Antoine Pitrou added the comment: Looks rather nice. I don't think there's any point in micro-optimizations such as stack_keys. -- nosy: +pitrou ___ Python tracker ___ _

[issue9915] speeding up sorting with a key

New submission from Daniel Stutzbach : (I've made an educated guess about who to add to the Nosy list) The attached patch substantially speeds up sorting using the "key" parameter. It is purely a performance patch; the language and libraries are not changed in any other way from the users poi