[Aahz]

Any reason the list object can't grow a .stablesort() method?

I'm not sure. Python's samplesort implementation is right up there among the most complicated (by any measure) algorithms in the code base, and the mergesort isn't any simpler anymore. Yet another large mass of difficult code can make for a real maintenance burden after I'm dead. Here, guess what this does: static int gallop_left(PyObject *pivot, PyObject** p, int n, PyObject *compare) { int k; int lo, hi; PyObject **pend; assert(pivot && p && n); pend = p+(n-1); lo = 0; hi = -1; for (;;) { IFLT(*(pend - lo), pivot) break; hi = lo; lo = (lo << 1) + 1; if (lo >= n) { lo = n; break; } } lo = n - lo; hi = n-1 - hi; while (lo < hi) { int m = (lo + hi) >> 1; IFLT(p[m], pivot) lo = m+1; else hi = m; } return lo; fail: return -1; } There are 12 other functions that go into this, some less obscure, some more. Change "hi = -1" to "hi = 0" and you'll get a core dump, etc; it's exceedingly delicate, and because truly understanding it essentially requires doing a formal correctness proof, it's difficult to maintain; fight your way to that understanding, and you'll know why it sorts, but still won't have a clue about why it's so fast. I'm disinclined to add more code of this nature unless I can use it to replace code at least as difficult (which samplesort is). An irony is that stable sorts are, by definition, pointless unless you *do* have equal elements, and the many-equal-elements case is the one known case where the new algorithm is much slower than the current one (indeed, I have good reason to suspect it's the only such case, and reasons beyond just that God loves a good joke <wink>). It's OK by me if this were to become Python's only sort. Short of that, I'd be happier contributing the code to a sorting extension module. There are other reasons the latter may be a good idea; e.g., if you know you're sorting C longs, it's not particularly difficult to do that 10x faster than Python's generic list.sort() can do it; ditto if you know you're comparing strings; etc. Exposing the binary insertion sort (which both samplesort and mergesort use) would also be useful to some people (it's a richer variant of bisect.insort_right). I'd prefer that Python-the-language have just one "really good general sort" built in.

--- "Barry A. Warsaw" wrote:

Because when a user looks at the methods of a list object and sees both .sort() and .stablesort() you now need to explain the difference, and perhaps give some hint as to why you'd want to choose one over the other.

Or you could have an optional parameter that defaults to whatever the more sane value should be (probably stable), and when the user stumbles across this parameter they stumble across the docs too. I think Tim's codebloat argument is more compelling. __________________________________________________ Do You Yahoo!? Yahoo! Health - Feel better, live better http://health.yahoo.com

[Barry Warsaw]

Except that in

http://mail.python.org/pipermail/python-dev/2002-July/026837.html

Tim says:

"Back on Earth, among Python users the most frequent complaint I've heard is that list.sort() isn't stable."

Yes, and because the current samplesort falls back to a stable sort when lists are small, almost everyone who cares about this and tries to guess about stability via trying small examples comes to a wrong conclusion.

and here

http://mail.python.org/pipermail/python-dev/2002-July/026854.html

Tim seems <wink> to be arguing against stable sort as being the default due to code bloat.

I'm arguing there against having two highly complex and long-winded sorting algorithms in the core. Pick one. In favor of samplesort: + It can be much faster in very-many-equal-elements cases (note that ~sort lists have only 4 distinct values, each repeated N/4 times and spread uniformaly across the whole list). + While it requires some extra memory, that lives on the stack and is O(log N). As a result, it can never raise MemoryError unless a comparison function does. + It's never had a bug reported against it (so is stable in a different sense <wink>). In favor of timsort: + It's stable. + The code is more uniform and so potentially easier to grok, and because it has no random component is easier to predict (e.g., it's certain that it has no quadratic-time cases). + It's incredibly faster in the face of many more kinds of mild disorder, which I believe are very common in the real world. As obvious examples, you add an increment of new data to an already- sorted file, or paste together several sorted files. timsort screams in those cases, but they may as well be random to samplesort, and the difference in runtime can easily exceed a factor of 10. A factor of 10 is a rare and wonderful thing in algorithm development. Against timsort: + It can require O(N) temp storage, although the constant is small compared to object sizes. That means it can raise MemoryError even if a comparison function never does. + Very-many-equal-elements cases can be much slower, but that's partly because it *is* stable, and preserving the order of equal elements is exactly what makes stability hard to achieve in a fast sort (samplesort can't be made stable efficiently).

As Tim's Official Sysadmin, I'm only good at channeling him on one subject, albeit probably one he'd deem most important to his life: lunch. So I'm not sure if he's arguing for or against stable sort being the default. ;)

All else being equal, a stable sort is a better choice. Alas, all else isn't equal. If Python had no sort method now, I'd pick timsort with scant hesitation. Speaking of which, is it time for lunch yet <wink>?

If you have access to a good library, you'll enjoy reading the original paper on samplesort; or a scan can be purchased from the ACM: Samplesort: A Sampling Approach to Minimal Storage Tree Sorting W. D. Frazer, A. C. McKellar JACM, Vol. 17, No. 3, July 1970 As in many papers of its time, the algorithm description is English prose and raises more questions than it answers, but the mathematical analysis is extensive. Two things made me laugh out loud: 1. The largest array they tested had 50,000 elements, because that was the practical upper limit given storage sizes at the time. Now that's such a tiny case that even in Python it's hard to time it accurately. 2. They thought about using a different sort method for small buckets, However, the additional storage required for the program would reduce the size of the input sequence which could be accommodated, and hence it is an open question as to whether or not the efficiency of the total sorting process could be improved in this way. In some ways, life was simpler then <wink>. for-example-i-had-more-hair-ly y'rs - tim

--- Tim Peters wrote:

In an effort to save time on email (ya, right ...), I wrote up a pretty detailed overview of the "timsort" algorithm. It's attached.

all-will-be-revealed-ly y'rs - tim

[Interesting stuff deleted.]

I'm curious if there is any literature that you've come across, or if you've done any experiments with merging more than two parts at a time. So instead of merging like such: A B C D E F G H I J K L AB CD EF GH IJ KL ABCD EFGH IJKL ABCDEFGH IJKL ABCDEFGHIJKL You were to merge A B C D E F G H I J K L ABC DEF GHI JKL ABCDEF GHIJKL ABCDEFGHIJKL (I realize that your merges are based on the lengths of the subsequences, but you get the point.) My thinking is that many machines (probably yours for instance) have a cache that is 4-way associative, so merging only 2 blocks at a time might not be using the cache as well as it could. Also, changing from merging 2 blocks to 3 or 4 blocks at a time would change the number of passes you have to make (the log part of N*log(N)). It's quite possible that this isn't worth the trade off in complexity and space (or your time :-). Keeping track of comparisons that you've already made could get ugly, and your temp space requirement would go from N/2 to possibly 3N/4... But since you're diving so deeply into this problem, I figured I'd throw it out there. OTOH, this could be close to the speedup that heavily optimized FFT algs get when they go from radix-2 to radix-4. Just thinking out loud... __________________________________________________ Do You Yahoo!? Yahoo! Health - Feel better, live better http://health.yahoo.com

--- Tim Peters 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

[Aahz]

... It seems pretty clear by now that the new mergesort is going to replace samplesort, but since nobody else has said this, I figured I'd add one more comment:

I actually understood your description of the new mergesort algorithm. Unless you can come up with similar docs for samplesort, the Beer Truck scenario dictates that mergesort be the new gold standard.

Or to quote Tim Peters, "Complex is better than complicated."

Good observation! I wish I'd thought of that <wink>. The mergesort is more complex, but it doesn't have so many fiddly little complications obscuring it. There were was an extensive description of the samplesort hybrid in listobject.c's comments, but you know you're in Complication Heaven when you've got to document half a dozen distinct "tuning macros" in hand-wavy terms. The only tuning parameter in the meregesort is MIN_GALLOP, and the tradeoff it makes is explainable.

Just FYI. I ripped out the complications I added to the mergesort variant that tried to speed many-equal-keys cases, and worked on its core competency (intelligent merging) instead. There's a reason <wink>: this kick started while investigating ways to speed Zope B-Tree operations when they're used as sets, equal keys are impossible in that context, but intelligent merging can really help. So whatever the fate of this sort, some of the code will live on in Zope's B-Tree routines. The result is that non-trivial cases of near-order got a nice boost, while ~sort got even slower again. I added a new test +sort, which replaces the last 10 values of a sorted array with random values. samplesort has a special case for this, limited to a maximum of 15 trailing out-of-order entries. timsort has no special case for this but does it significantly faster than the samplesort hack anyway, has no limit on how many such trailing entries it can exploit, and couldn't care less whether such entries are at the front or the end of the array; I expect it would be (just) a little slower if they were in the middle. As shown below, timsort does a +sort almost as fast as for a wholly-sorted array. Ditto now for 3sort too, which perturbs order by doing 3 random exchanges in a sorted array. It's become a very interesting sort implementation, handling more kinds of near-order at demonstrably supernatural speed than anything else I'm aware of. ~sort isn't an example of near-order. Quite the contrary, it has a number of inversions quadratic in N, and N/4 runs; the only reason ~sort goes faster than *sort now is-- believe it or not --a surprising benefit from a memory optimization. Key: *sort: random data \sort: descending data /sort: ascending data 3sort: ascending, then 3 random exchanges +sort: ascending, then 10 random at the end ~sort: many duplicates =sort: all equal !sort: worst case scenario C:\Code\python\PCbuild>python -O sortperf.py 15 20 1 samplesort i 2**i *sort \sort /sort 3sort +sort ~sort =sort !sort 15 32768 0.18 0.02 0.01 0.14 0.01 0.07 0.01 0.17 16 65536 0.24 0.02 0.02 0.22 0.02 0.08 0.02 0.24 17 131072 0.53 0.05 0.04 0.49 0.05 0.18 0.04 0.52 18 262144 1.16 0.09 0.09 1.06 0.12 0.37 0.09 1.13 19 524288 2.53 0.18 0.17 2.30 0.24 0.74 0.17 2.47 20 1048576 5.47 0.37 0.35 5.17 0.45 1.51 0.35 5.34 timsort i 2**i *sort \sort /sort 3sort +sort ~sort =sort !sort 15 32768 0.17 0.01 0.01 0.01 0.01 0.14 0.01 0.02 16 65536 0.23 0.02 0.02 0.03 0.02 0.21 0.03 0.04 17 131072 0.53 0.04 0.04 0.05 0.04 0.46 0.04 0.09 18 262144 1.16 0.09 0.09 0.12 0.09 1.01 0.08 0.18 19 524288 2.53 0.18 0.17 0.18 0.18 2.20 0.17 0.36 20 1048576 5.48 0.36 0.35 0.36 0.37 4.78 0.35 0.73

FYI, I've been poking at this in the background. The ~sort regression is vastly reduced, via removing special-casing and adding more general adaptivity (if you read the timsort.txt file, the special case for run lengths within a factor of 2 of each other went away, replaced by a more intelligent mix of one-pair-at-a-time versus galloping modes). *sort lost about 1% as a result (one-pair-at-a-time is maximally effective for *sort, but in a random mix every now again the "switch to the less efficient (for it) galloping mode" heuristic triggers by blind luck). There's also a significant systematic regression in timsort's +sort case, although it remains faster (and much more general) than samplesort's special-casing of it; also a mix of small regressions and speedups in 3sort. These are because, to simplify experimenting, I threw out the "copy only the shorter run" gimmick, always copying the left run instead. That hurts +sort systematically, as instead of copying just the 10 oddball elements at the end, it copies the very long run of N-10 elements instead (and as many as N-1 temp pointers can be needed, up from N/2). That's all repairable, it's just a PITA to do it. C:\Code\python\PCbuild>python -O sortperf.py 15 20 1 samplesort i 2**i *sort \sort /sort 3sort +sort ~sort =sort !sort 15 32768 0.18 0.01 0.02 0.11 0.01 0.04 0.01 0.11 16 65536 0.24 0.02 0.02 0.25 0.02 0.08 0.02 0.24 17 131072 0.53 0.05 0.04 0.49 0.05 0.18 0.04 0.52 18 262144 1.16 0.09 0.09 1.06 0.12 0.37 0.09 1.14 19 524288 2.53 0.18 0.17 2.30 0.24 0.75 0.17 2.47 20 1048576 5.48 0.37 0.35 5.18 0.45 1.52 0.35 5.35 timsort i 2**i *sort \sort /sort 3sort +sort ~sort =sort !sort 15 32768 0.17 0.01 0.02 0.01 0.01 0.05 0.01 0.02 16 65536 0.24 0.02 0.02 0.02 0.02 0.09 0.02 0.04 17 131072 0.54 0.05 0.04 0.05 0.05 0.19 0.04 0.09 18 262144 1.17 0.09 0.09 0.10 0.10 0.38 0.09 0.18 19 524288 2.56 0.18 0.17 0.20 0.20 0.79 0.17 0.36 20 1048576 5.54 0.37 0.35 0.37 0.41 1.62 0.35 0.73 In short, there's no real "speed argument" against this anymore (as I said in the first msg of this thread, the ~sort regression was serious -- it's an important case; turns out galloping is very effective at speeding it too, provided that dumbass premature special-casing doesn't stop galloping from trying <wink>).

[Tim]

... There's also a significant systematic regression in timsort's +sort case, ... also a mix of small regressions and speedups in 3sort. These are because, to simplify experimenting, ...(and as many as N-1 temp pointers can be needed, up from N/2). That's all repairable, it's just a PITA to do it.

It's repaired, and those glitches went away:

timsort i 2**i *sort \sort /sort 3sort +sort ~sort =sort !sort 15 32768 0.17 0.01 0.02 0.01 0.01 0.05 0.01 0.02 16 65536 0.24 0.02 0.02 0.02 0.02 0.09 0.02 0.04 17 131072 0.54 0.05 0.04 0.05 0.05 0.19 0.04 0.09 18 262144 1.17 0.09 0.09 0.10 0.10 0.38 0.09 0.18 19 524288 2.56 0.18 0.17 0.20 0.20 0.79 0.17 0.36 20 1048576 5.54 0.37 0.35 0.37 0.41 1.62 0.35 0.73

Now at 15 32768 0.17 0.01 0.01 0.01 0.02 0.09 0.01 0.03 16 65536 0.24 0.02 0.02 0.02 0.02 0.09 0.02 0.04 17 131072 0.53 0.05 0.04 0.05 0.05 0.18 0.04 0.09 18 262144 1.17 0.09 0.09 0.10 0.09 0.38 0.09 0.18 19 524288 2.56 0.18 0.18 0.19 0.19 0.78 0.17 0.36 20 1048576 5.53 0.37 0.35 0.36 0.37 1.60 0.35 0.74 In other news, an elf revealed that Perl is moving to an adaptive stable mergesort(!!!harmonic convergence!!!), and sent some cleaned-up source code. The comments reference a non-existent paper, but if I change the title and the year I find it here: Optimistic sorting and information theoretic complexity. Peter McIlroy. SODA (Fourth Annual ACM-SIAM Symposium on Discrete Algorithms), pp 467-474, Austin, Texas, 25-27 January 1993. Jeremy got that for me, and it's an extremely relevant paper. What I've been calling galloping he called "exponential search", and the paper has some great analysis, pretty much thoroughly characterizing the set of permutations for which this kind approach is helpful, and even optimal. It's a large set <wink>. Amazingly, citeseer finds only one reference to this paper, also from 1993, and despite all the work done on adaptive sorting since then. So it's either essentially unknown in the research community, was shot full of holes (but then people would have delighted in citing it just to rub that in <0.5 wink>), or was quickly superceded by a better result (but then ditto!). I'll leave that a mystery. I haven't had time yet to study the Perl code. The timsort algorithm is clearly more frugal with memory: worst-case N/2 temp pointers needed, and, e.g., in +sort it only needs (at most) 10 temp pointers (independent of N). That may or may not be good, though, depending on whether the Perl algorithm makes more effective use of the memory hierarchy; offhand I don't think it does. OTOH, timsort has 4 flavors of galloping and 2 flavors of binary search and 2 merge routines, because the memory-saving gimmick can require merging "from the left" or "from the right", depending on which run is smaller. Doubling the number of helper routines is what "PITA" meant in the quote at the start <wink>. One more bit of news: cross-box performance of this stuff is baffling. Nobody else has tried timsort yet (unless someone who asked for the code tried an earlier version), but there are Many Mysteries just looking at the numbers for /sort under current CVS Python. Recall that /sort is the case where the data is already sorted: it does N-1 compares in one scan, and that's all. For an array with 2**20 distinct floats that takes 0.35 seconds on my Win98SE 866MHz Pentium box, compiled w/ MSVC6. On my Win2K 866MHz Pentium box, compiled w/ MSVC6, it takes 0.58(!) seconds, and indeed all the sort tests take incredibly much longer on the Win2K box. On Fred's faster Pentium box (I forget exactly how fast, >900MHz and <1GHz), using gcc, the sort tests take a lot less time than on my Win2K box, but my Win98SE box is still faster. Another Mystery (still with the current samplesort): on Win98SE, !sort is always a bit faster than *sort. On Win2K and on Fred's box, it's always a bit slower. I'm leaving that a mystery too. I haven't tried timsort on another box yet, and given that my home machine may be supernaturally fast, I'm never going to <wink>.

On Thu, 25 Jul 2002, Tim Peters wrote:

One more bit of news: cross-box performance of this stuff is baffling.

I'll run tests on the P4 Xeon, Alpha (21164A, 21264), AMD Elan 520, and maybe a few Sparcs, and whatever else I can get my hands on. Just let me know where I can snag the code + test script. -Kevin -- Kevin Jacobs The OPAL Group - Enterprise Systems Architect Voice: (216) 986-0710 x 19 E-mail: jacobs@theopalgroup.com Fax: (216) 986-0714 WWW: http://www.theopalgroup.com

Tim Peters wrote:

Apart from fine-tuning and rewriting the doc file, I think the mergesort is done. I'm confident that if any bugs remain, I haven't seen them <wink>. A patch against current CVS listobject.c is here:

http://www.python.org/sf/587076

Simple instructions for timing exactly the same data I've posted times against are in the patch description (you already have sortperf.py -- it's in Lib/test). This patch doesn't replace samplesort, it adds a new .msort() method, to make comparative timings easier. It also adds an .hsort() method for weak heapsort, because I forgot to delete that code after I gave up on it <wink>.

X-platform samplesort timings are interesting as well as samplesort versus mergesort timings. Timings against "real life" sort jobs are especially interesting. Attaching results to the bug report sounds like a good idea to me, so we get a coherent record in one place.

Thanks in advance!

Here's the result for AMD Athlon 1.2GHz/Linux/gcc: Python/Tim-Python> ./python -O Lib/test/sortperf.py 15 20 1 i 2**i *sort \sort /sort 3sort +sort ~sort =sort !sort 15 32768 0.07 0.00 0.01 0.09 0.01 0.03 0.01 0.08 16 65536 0.18 0.02 0.02 0.19 0.03 0.07 0.02 0.20 17 131072 0.43 0.05 0.04 0.46 0.05 0.18 0.05 0.48 18 262144 0.99 0.09 0.10 1.04 0.13 0.40 0.09 1.11 19 524288 2.23 0.19 0.21 2.32 0.24 0.83 0.20 2.46 20 1048576 4.96 0.40 0.40 5.41 0.47 1.72 0.40 5.46 without patch: Python/Tim-Python> ./python -O Lib/test/sortperf.py 15 20 1 i 2**i *sort \sort /sort 3sort +sort ~sort =sort !sort 15 32768 0.08 0.01 0.01 0.09 0.01 0.03 0.00 0.09 16 65536 0.20 0.02 0.01 0.20 0.03 0.07 0.02 0.20 17 131072 0.46 0.06 0.02 0.45 0.05 0.20 0.04 0.49 18 262144 0.99 0.09 0.10 1.09 0.11 0.40 0.12 1.12 19 524288 2.33 0.20 0.20 2.30 0.24 0.83 0.19 2.47 20 1048576 4.89 0.40 0.41 5.37 0.48 1.71 0.38 6.22 -- Marc-Andre Lemburg CEO eGenix.com Software GmbH _______________________________________________________________________ eGenix.com -- Makers of the Python mx Extensions: mxDateTime,mxODBC,... Python Consulting: http://www.egenix.com/ Python Software: http://www.egenix.com/files/python/

Tim Peters wrote:

[MAL]

...

Here's the result for AMD Athlon 1.2GHz/Linux/gcc:

without patch:

Python/Tim-Python> ./python -O Lib/test/sortperf.py 15 20 1 i 2**i *sort \sort /sort 3sort +sort ~sort =sort !sort 15 32768 0.08 0.01 0.01 0.09 0.01 0.03 0.00 0.09 16 65536 0.20 0.02 0.01 0.20 0.03 0.07 0.02 0.20 17 131072 0.46 0.06 0.02 0.45 0.05 0.20 0.04 0.49 18 262144 0.99 0.09 0.10 1.09 0.11 0.40 0.12 1.12 19 524288 2.33 0.20 0.20 2.30 0.24 0.83 0.19 2.47 20 1048576 4.89 0.40 0.41 5.37 0.48 1.71 0.38 6.22

I assume you didn't read the instructions in the patch description:

http://www.python.org/sf/587076

The patch doesn't change anything about how list.sort() works, so what you've shown us is the timing variance on your box across two identical runs. To time the new routine, you need to (temporarily) change L.sort() to L.msort() in sortperf.py's doit() function. It's a one-character change, but an important one <wink>.

Dang. Why don't you distribute a ZIP file which can be dumped onto the standard Python installation ? Here's the .msort() version: Python/Tim-Python> ./python -O sortperf.py 15 20 1 i 2**i *sort \sort /sort 3sort +sort ~sort =sort !sort 15 32768 0.08 0.01 0.01 0.01 0.01 0.03 0.00 0.02 16 65536 0.17 0.02 0.02 0.02 0.02 0.07 0.02 0.06 17 131072 0.41 0.05 0.04 0.05 0.04 0.16 0.04 0.09 18 262144 0.95 0.10 0.10 0.10 0.10 0.33 0.10 0.20 19 524288 2.17 0.20 0.21 0.20 0.21 0.66 0.20 0.44 20 1048576 4.85 0.42 0.40 0.41 0.41 1.37 0.41 0.84 -- Marc-Andre Lemburg CEO eGenix.com Software GmbH _______________________________________________________________________ eGenix.com -- Makers of the Python mx Extensions: mxDateTime,mxODBC,... Python Consulting: http://www.egenix.com/ Python Software: http://www.egenix.com/files/python/

Tim Peters wrote:

[MAL]

...

Dang. Why don't you distribute a ZIP file which can be dumped onto the standard Python installation ?

A zip file containing what? And which "standard Python installation"? If someone is on Python-Dev but can't deal with a one-file patch against CVS, I'm not sure what to conclude, except that I don't want to deal with them at this point <wink>.

Point taken ;-) I meant something like this: Here's a ZIP file. To install take your standard Python CVS download, unzip it on top of it, then run echo "With .sort()" ./python -O sortperf.py 15 20 1 echo "With .msort()" ./python -O timsortperf.py 15 20 1 -- Marc-Andre Lemburg CEO eGenix.com Software GmbH _______________________________________________________________________ eGenix.com -- Makers of the Python mx Extensions: mxDateTime,mxODBC,... Python Consulting: http://www.egenix.com/ Python Software: http://www.egenix.com/files/python/

Tim> Skip's Pentium III acts most like my Pentium III, which shouldn't Tim> be surprising. ... Tim> sf userid ~sort speedup under timsort (negative means slower) Tim> --------- --------------------------------------------------- Tim> montanaro -23% Tim> tim_one - 6% Tim> jacobs99 +18% Tim> lemburg +25% Tim> nascheme +30% I should point out that my PIII is in a laptop. I don't know if it's a so-called mobile Pentium or not. /proc/cpuinfo reports: processor : 0 vendor_id : GenuineIntel cpu family : 6 model : 8 model name : Pentium III (Coppermine) stepping : 1 cpu MHz : 451.030 cache size : 256 KB fdiv_bug : no hlt_bug : no f00f_bug : no coma_bug : no fpu : yes fpu_exception : yes cpuid level : 2 wp : yes flags : fpu vme de pse tsc msr pae mce cx8 sep mtrr pge mca cmov pat pse36 mmx fxsr sse bogomips : 897.84 It also has separate 16KB L1 I and D caches. From what I was able to glean from a quick glance at a Katmai vs. Coppermine article, the Coppermine's L2 cache is full-speed, on-chip, with a 256-bit wide connection and 8-way set associative cache. Does any of that help explain why my results are similar to Tim's? Skip