On 12 October 2016 at 02:16, Elliot Gorokhovsky wrote:

So I thought, wow, this will give some nice numbers! But I underestimated the power of this optimization. You have no idea. It's crazy. This is just insane. This is crazy.

Not to take away from the potential for speed improvements (which do indeed seem interesting), but I'd ask that folks avoid using mental health terms to describe test results that we find unbelievable. There are plenty of other adjectives we can use, and a text-based medium like email gives us a chance to proofread our posts before we send them. Regards, Nick. -- Nick Coghlan | ncoghlan@gmail.com | Brisbane, Australia

On 10/11/2016 2:30 PM, Paul Moore wrote:

On 11 October 2016 at 17:49, Nick Coghlan wrote:

...

On 12 October 2016 at 02:16, Elliot Gorokhovsky wrote:

...

So I thought, wow, this will give some nice numbers! But I underestimated the power of this optimization. You have no idea. It's crazy. This is just insane. This is crazy.

Not to take away from the potential for speed improvements (which do indeed seem interesting), but I'd ask that folks avoid using mental health terms to describe test results that we find unbelievable. There are plenty of other adjectives we can use, and a text-based medium like email gives us a chance to proofread our posts before we send them.

I'd also suggest toning down the rhetoric a bit (all-caps title, "the contents of this message may be dangerous for readers with heart conditions" etc.

I triple the motion. In general, all caps = spam or worse and I usually don't even open such posts. Elliot, to me, all caps means IGNORE ME. I suspect this is not what you want.

Your results do seem good, but it's a little hard to work out what you actually did, and how your results were produced, through the hype. It'll be much better when someone else has a means to reproduce your results to confirm them. In all honestly, people have been working on Python's performance for a long time now, and I'm more inclined to think that a 50% speedup is a mistake rather than an opportunity that's been missed for all that time. I'd be happy to be proved wrong, but for now I'm skeptical.

I'm not, in the same sense, even though Elliot suggested that we should be ;-). His key insight is that if all members of a list have the same type (which is a common 'special case'), then we can replace the general, somewhat convoluted, rich-comparison function, containing at least two type checks, with a faster special-case comparison function without any type checks. Since Python floats wrap machine doubles, I expect that float may have the greatest speedup.

Please continue working on this - I'd love my skepticism to be proved wrong!

It may be the case now that sorting a list of all floats is faster than a mixed list of ints and floats. I expect that it definitely will be with a float comparison function. -- Terry Jan Reedy

So I got excited here. And the reason why is that I got those numbers *on Tim's benchmark*. When I got these kinds of numbers on my benchmarks, I figured there was probably a problem with they way I was timing, and certainly the gains couldn't be as extreme as they suggested. But this is on a benchmark that's already in the codebase! Here is a detailed explanation of how to reproduce my results, and the circumstances that would lead them to be invalid: ****************************************** To reproduce, just activate a virtualenv, and then clone https://github.com/embg/python-fast-listsort.git. Then python setup.py install and python sortperf.py. Now let's look at what sortperf.py does and how it relates to Tim's benchmark at Lib/test/sortperf.py. If you diff the two, you'll find I made three changes: 1. I added an import, "import fastlist". This obviously would not make sorting twice faster. 2. I changed the way it formats the output: I changed "fmt = ("%2s %7s" + " %7s"*len(cases))" to "fmt = ("%2s %7s" + " %6s"*len(cases))". Again irrelevant. 3. I changed the timing function #from this def doit_fast(L): t0 = time.perf_counter() L.fastsort() t1 = time.perf_counter() print("%6.2f" % (t1-t0), end=' ') flush() #to this def doit(L): F = FastList(L) f0 = time.perf_counter() F.fastsort() f1 = time.perf_counter() F = FastList(L) t0 = time.perf_counter() F.sort() t1 = time.perf_counter() print("%6.2f%%" % (100*(1-(f1-f0)/(t1-t0))), end=' ') flush() ******************************************* So what we've shown is that (1) if you trust the existing sorting benchmark and (2) if my modification to doit() doesn't mess anything up (I leave this up to you to judge), then the measurements are as valid. Which is a pretty big deal (50% !!!!!!!), hence my overexcitement. **************************************** Now I'd like to respond to responses (the one I'm thinking of was off-list so I don't want to quote it) I've gotten questioning how it could be possible for such a small optimization, bypassing the typechecks, to possibly have such a large effect, even in theory. Here's my answer: Let's ignore branch prediction and cache for now and just look at a high level. The cost of sorting is related to the cost of a single comparison, because the vast majority of our time (let's say certainly at least 90%, depending on the list) is spent in comparisons. So let's look at the cost of a comparison. Without my optimization, comparisons for floats (that's what this benchmark looks at) go roughly like this: 1. Test type of left and right for PyObject_RichCompare (which costs two pointer dereferences) and compare them. "3 ops" (quotes because counting ops like this is pretty hand-wavy). "2 memory accesses". 2. Get the address of the float compare method from PyFloat_Type->tp_richcompare. "1 op". "1 memory access". 3. Call the function whose address we just got. "1 op". "Basically 0 memory accesses because we count the stack stuff in that 1 op". 4. Test type of left and right again in PyFloat_RichCompare and compare both of them to PyFloat_Type. "4 ops". "2 memory accesses". 5. Get floats from the PyObject* by calling PyFloat_AS_DOUBLE or whatever. "2 ops". "2 memory accesses". 6. Compare the floats and return. "2 ops". Now let's tally the "cost" (sorry for use of quotes here, just trying to emphasize this is an intuitive, theoretical explanation for the numbers which doesn't take into account the hardware): "13 ops, 7 memory accesses". Here's what it looks like in my code: 1. Call PyFloat_AS_DOUBLE on left and right. "2 ops". "2 memory acceses". 2. Compare the floats and return. "2 ops". Tally: "4 ops, 2 memory accesses". Now you can argue branch prediction alleviates a lot of this cost, since we're taking the same branches every time. But note that, branch prediction or not, we still have to do all of those memory acceses, and since they're pointers to places all over memory, they miss the cache basically every time (correct me if I'm wrong). So memory-wise, we really are doing something like a 7:2 ratio, and op-wise, perhaps not as bad because of branch prediction, but still, 13:4 is probably bad no matter what's going on in the hardware. Now consider that something like 90% of our time is spent in those steps. Are my numbers really that unbelievable? Thanks for everything, looking forward to writing this up as a nice latex doc with graphs and perf benchmarks and all the other rigorous goodies, as well as a special case cmp func for homogeneous tuples and a simple patch file, Elliot

On Tue, Oct 11, 2016 at 9:56 PM Nick Coghlan wrote:

Once you get to the point of being able to do performance mentions on a CPython build with a modified list.sort() implementation, you'll want to take a look at the modern benchmark suite in https://github.com/python/performance

Yup, that's the plan. I'm going to implement optimized compares for tuples, then implement this as a CPython build, and then run benchmark suites and write some rigorous benchmarks using perf/timeit.