New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
speeding up sorting with a key #54124
Comments
(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 point of view. I measured a reduction in execution time of at least 15% in many cases and more than 40% for large n. I performed measurements on an Intel 64-bit Linux system using gcc 4.3.2 and on an Intel 32-bit Windows XP system using Visual C Express Edition 2009. Previously, "key" was implemented by a creating a sortwrapperobject, which is a PyObject storing a key and a value and using only the key for comparison. With the patch, sortwrapperobject is removed entirely. Instead, the sort uses two arrays: one for keys and one for values. Comparisons use the keys array. Whenever a swap is performed, the swap is performed on both arrays. If the "keys" parameter is not provided to the sort, the second swap is skipped (since the keys are also the values). Compared to the sortwrapperobject approach, speed is improved by:
When the "key" parameter is not used, the code still needs to check to see if it should be performing a second swap. However, the additional instructions are cache and branch-prediction friendly and do not have a noticeable impact on performance. I conducted enough experiments to establish a 95% confidence interval that excluded a slowdown of more than 1% (but did not exclude a slowdown of 0% - which is good). A handful of results: # No key, same speed # With a key, patched version is faster # Results are more dramatic with large n I have been using a script for running a large battery of experiments with different values of n and different conditions (random data, sorted data, reverse-sorted data, key, no key, etc.). The script works, but it's clunky to use. I'm working on cleaning that up and hope to attach it to this issue within the next few days. |
Looks rather nice. I don't think there's any point in micro-optimizations such as stack_keys. |
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. The only remaining advantage of the sortwrapper is that it is independent of the main code for the timsort, so both are more readable and maintainable in their current form. I've only had a cursory look at the patch. A couple of thoughts:
|
Antoine said:
Good point. I'll try taking that out and see how it impacts the timing. Raymond said:
Anything that was a memmove or memcpy remains a memmove or memcpy. Anything that was equivalent but implemented "by hand" remains that way. (Although in either case the details have been moved into a sortslice_* static inline function.) I have avoided changing any memcpy/memmove to "by hand" (or vise versa), because I know that it might be faster on my system but slower on someone else's.
The short answer is "no". The long answer is that I conducted enough experiments for the 95% confidence interval of the ratio of execution times (patched/trunk) to be 0.994735131656 +/- 0.00540792612332, for the case where no key function is provided.
The compiler can exactly compute the stack offset of "lo.values", so it should require the same number and type of instructions to access as just "lo".
I have one, but it's clunky and requires modifying the script to change important parameters. I'm refactoring it to use argparse and will attach it to this issue when it's ready. |
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 versions of python are otherwise identical (same source, same compiler, same configure and compiler settings, etc.). The script will create subdirectories to store data, so please run it in the speed_test directory. Example usage: otto:~/speed_test$ ./speed_test.py ../py3k-unpatched/ ../py3k-patched/ 'sort random' otto:~/speed_test$ ./speed_test.py --help Compare the speed of two list implementations positional arguments: optional arguments: Available experiments: |
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 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 something else and repurposed it. Actually, it's been repurposed at least twice so it has a long history and an unfortunate amount of cruft. I will work on porting it to run on py3k. My original examples did not use random data because timeit is challenging to use to time sorting of random data and I wanted to post something relatively concise. Sometime next week I plan to post extensive timing results on random data. I have been working on some fine-tuning of my patch as well as to my timing script. |
Does this help any?
>>> import random
>>> from timeit import timeit
>>> testlist = list(range(100000))
>>> random.shuffle(testlist)
>>> timeit('t=list(testlist); t.sort()',
'from __main__ import testlist', number=1)
0.1467957519740679 I just learned the import trick from the tracker issue suggesting that it be made more prominent. |
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 other. That leaves two options:
I have been using approach #2. |
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 measurement results sometime next week. |
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 speeds more quickly and more accurately. I discovered a few things along the way:
On Linux systems, the new version of my script will check to see if CPU frequency scaling is turned on and provide suggestions on how to turn it off. On other operating systems, you are on your own. ;) Usage: Using my new-and-improved timing script and running on real hardware with CPU frequency scaling turned off, I was able to detect a slight slowdown on sorting random integers. Here's a summary for sorting random integers: Original patch (increasing execution time is bad): I went back to the code and managed to squeeze out a bit more performance. Here's a summary of the new patch: New patch (increasing execution time is bad): All of the above results are for sorting without a key. For sorting *with* a key, there's a big performance boost across the board (15% to 45% decrease in execution time, when the key function is simply "int"). Overall, the patch shrinks Objects/listobject.c by 10 lines. Executive Summary Good:
Bad:
Worthwhile trade? |
+1 obviously. Why don't you contribute a list sorting benchmark to the suite in http://hg.python.org/benchmarks/? |
Antoine Pitrou <report@bugs.python.org> wrote:
I considered that, but I want to separately benchmark sorting different kinds and quantities of data. AFAIK, there isn't an easy way to do that with perf.py. |
Le mardi 23 novembre 2010 à 00:10 +0000, Daniel Stutzbach a écrit :
Right, that wouldn't suit your present purposes. But apparently you are |
Antoine Pitrou <report@bugs.python.org> wrote:
Oh, I just stuck that under Tools because it was convenient for testing. The timing script is in a separate patch because I'm -0 on committing the timing script itself. The perf.py that my timing script uses is based on the one from benchmarks/, but with 90% of the code removed, so the amount of duplicated code is less than it may at first appear. My script could go in benchmarks/ if there was a convenient way for it to import perf.py. I wouldn't want to clutter the top-level directory with my script though. Any suggestions? |
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 time instead of just the keys -- did you do more than this, perhaps changing the logic or pattern of comparisons? If so, I would be *much* more comfortable if Tim reviewed this. The one part of the current code that would be missed is that it cleanly separates/decouples the key-function logic from the Timsort logic. Now those are heavily intertwined -- I find the code harder to follow. Why did the variable names change, pa/pb to ssa/ssb, etc.? I'm hoping that I'll have a chance to go through the details of the patch in the next couple of weeks. Unfortunately, the patch is huge and it looks like it mixes in a number of optimizations beyond just moving keys and values in parallel, variable names are changing, comment lines are rewrapped, etc. |
Raymond Hettinger <rhettinger@users.sourceforge.net> added the comment:
If the "key" parameter was not used, then the values pointer is a null pointer. Each time elements must be moved, the code needs to check if the values pointer is NULL. In other words, the overhead is one conditional branch per move or group of moves (we only have to check once for memmove()). Since the branch will always be the same throughout any given call to sort(), CPU branch prediction is effective making the branches fairly inexpensive.
In the original version of the patch, I tried hard to avoid unrelated changes. In the new version, I made many small not-strictly-related optimizations. However, I have not changed the order in which comparisons occur.
I took "pa" to mean "pointer to array A", but it's now a sortslice structure instead of a pointer.
The comment rewrapping aren't completely spurious. The comments really have changed and in some cases the constraints on the inputs to a function have changed slightly. For what it's worth, my methodology when working on this patch went like this:
I can upload the patch to Rietveld to facilitate review. If I can get Rietveld to show each of my local commits, would it be helpful to see the patch in incremental pieces? |
I see how the branch can be optimized away but not how it gets cheaper than when there was no branch at all (and no lo.keys and lo.values extra layer of direction). How did it get *faster* than the original (in the case with no key-function)?
That makes sense.
At this point, it may be best for me to read the patch as-is. Unfortunately, it's a big patch and will likely take a lot of time to read in detail. Is there any chance you can persuade Uncle Timmy to review this? This is all his code and he's likely to have some good insights. Also, is there anyone else who is knowledgeable about Python on less common platforms? ISTM part of the optimization is dependent on the branch-prediction and other nuances that vary from environment to environment. That being said, doing fewer memory allocations is always a win. |
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.
Any suggestions on how he might be persuaded? ;-)
I do have a Windows machine I can test on. It's not exactly a "less common" platform, but at least it's a completely different compiler. I'll post the results once I have them. The Rietveld issue is here: 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. If there's anything else I can do to make reviewing easier, please let me know. For that matter, if there's other code you'd like me to review in exchange or straightforward bugs you'd like to pawn off, I would be happy to help out. |
I've started reviewing, and I must say that incremental patches would |
Ok, things are even worse: comments I've made to intermediate patches Bottom line is that you're making too many gratuitous changes, including Next time, please upload a single patch. Really. |
Antoine Pitrou wrote:
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 one big patch: |
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 patch (as one patch :) ) here: If you think the original performance looks like a worthwhile tradeoff, could you spend about 1 minute looking over that version of patch and give your general impression? |
I am not objecting against the performance tweaks but the other more or You can still try to salvage my comments from the review I've posted, |
+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 not convincing (relying on compiler and processor specific optimizations that vary across platforms). Instead, try to minimize the patch, making as few changes as possible to manipulation both arrays. Also, try to follow the C style of the other code in the standard library -- the current patch has a different flavor to say the least ;-) Ideally, the code will have the same look and feel as it does now (so that the Timsort remains recognizable to Tim ;-). This code doesn't just need to run fast, it needs to serve as a readable model for anyone else trying to implement the algorithm. If you still want the other tweaks, I recommend putting them in a separate patch afterwards and consider deferring them to 3.3. It's a little late in the dev cycle to make lots of microscopic changes that may introduce a bug or unexpected behavior or perform weirdly on one of the less used platforms. |
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 little carried away with optimizing. I think I eliminated all of the significant style differences as well. If you still see glaring style mismatches, please let me know. It's possible that the differences aren't visible to my eyes. ;-) http://codereview.appspot.com/3369042/diff/1/Objects/listobject.c Please let me know what you think of the revised version. |
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 compilers support an inline keyword. If you're sure it works everywhere, that's great. If not, consider going back to ugly defines -- those reliably work everywhere. Also note that this patch puts a lot of faith in branch prediction. If some target processor doesn't support it, or has limited ability to remember predictions, or mispredicts, then the code will be slower. That being said, I'm happy with the patch. You have a +1 from me. |
I fixed ./configure to properly set up Py_LOCAL_INLINE in bpo-5553. :-) It will expand to "static inline" under both MSVC and gcc. On older compilers, it may expand to "static __inline__", "static __inline", or whatever else is needed to get the job done. As a last resort, it will expand to simply "static", but I don't know of any 32-bit (or 64-bit) compilers where that would actually happen.
I think even a limited amount of memory dedicated to branch prediction should be sufficient. There are two cases:
Thanks for taking the time to review this. |
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)) {
PyErr_SetString(PyExc_TypeError,
"expected a sortwrapperobject");
return NULL;
}
return PyObject_RichCompare(a->key, b->key, op);
} When a key function is defined, this is all you can possibly shave off the time for a comparison. When a key function is not defined, there was no overhead at all. With the patch, we're relying on branch prediction to minimize the cost to the regular case and adding a little indirection in the form of lo variables becoming lo.keys, etc. And the number of memmoves is doubled. To me, the main advantage of the patch is that it saves a little memory for each key: typedef struct {
PyObject_HEAD
PyObject *key;
PyObject *value;
} sortwrapperobject; Just wanted to post this so there weren't any illusions about the patch being a big win. |
I don't want to argue whether the patch is a big win or not (I recognize that it is a tradeoff), but when using a key it does shave off more than the call to sortwrapper_richcompare. Stack with sortwrapper: long_richcompare Stack without: long_richcompare |
Daniel has already posted benchmark numbers, I would trust them rather |
AP: I've already given my blessing to the patch. |
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. |
Thank you! |
Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.
Show more details
GitHub fields:
bugs.python.org fields:
The text was updated successfully, but these errors were encountered: