[Python-Dev] Sorting

[Scott Gilbert]

--- Tim Peters <tim.one@comcast.net> wrote:
> 
>     "A Meticulous Analysis of Mergesort Programs"
>     Jyrki Katajainen, Jesper Larsson Traff
> 

Thanks for the cool reference.  I read a bit of it last night.  I ought to
know by now that there really isn't much new under the sun...

> 
> The real reason it's uninteresting to me is that it has no clear
> applicability to the cases this sort aims at:  exploiting significant
> pre-existing order of various kinds.
> [...]
> (unless you can speed a single left-to-right scan!  that would be way 
> cool).
> 

Do a few well placed prefetch instructions buy you anything?  The MMU could
be grabbing your next pointer while you're doing your current comparison. 
And of course you could implement it as a macro that evaporates for
whatever platforms you didn't care to implement it on.  (I need to look it
up, but I'm pretty sure you could do this for both VC++ and gcc on recent
x86s.)

>
> If you think you can write a sort for random Python arrays faster than
> the
> samplesort hybrid, be my guest:  I'd love to see it!  You should be aware
> that I've been making this challenge for years <wink>.
>

You're remarkably good at taunting me.  :-)  I've spent a little time on a
few of these optimization challenges that get posted.  One of these days
I'll best you...  (not this day though)


> 
> Something to note:  I think you have an overly simple view of Python's
> lists in mind.
>

No, I think I understand the model.  I just assumed the objects pointed to
would be scattered pretty randomly through memory.  So statistically
they'll step on the same cache lines as your list once in a while, but that
it would average out to being less interesting than the adjacent slots in
the list.  I'm frequently wrong about stuff like this though...


Cheers,
    -Scott


__________________________________________________
Do You Yahoo!?
Yahoo! Health - Feel better, live better
http://health.yahoo.com