--- 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
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4