[issue9915] speeding up sorting with a key

Daniel Stutzbach report at bugs.python.org
Tue Sep 21 23:40:36 CEST 2010


Daniel Stutzbach <daniel at stutzbachenterprises.com> 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
> performance across various architectures and libraries.  Code like
> "*dest++ = *pb++;" is hard to beat, especially for short runs.

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.

> Is the code slower for the common case where a key function is not
> provided?  

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 patch seems to add a level of indirection throughout the code
> (lots of "lo.values" instead of just "lo").

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".

> A more extensive timing suite would be helpful; the ones listed in 
> the first post are simplistic.

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.

----------

_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue9915>
_______________________________________


More information about the Python-bugs-list mailing list