On Mon, Oct 10, 2016 at 1:42 PM, Elliot Gorokhovsky wrote:

*** 10 strings *** F.fastsort(): 1.6689300537109375e-06 F.sort(): 1.6689300537109375e-06

I think something has gone wrong with your timing harness... For accurately timing microbenchmarks, you should use timeit, or better yet Victor Stinner's perf package: https://perf.readthedocs.io/ -n -- Nathaniel J. Smith -- https://vorpus.org

On Mon, Oct 10, 2016 at 2:16 PM, Elliot Gorokhovsky wrote:

Hm... that is strange, but I don't think there's anything wrong with the way I'm timing, though I agree perf/timeit would be better. I ran the benchmark a couple of times and the numbers seem to exactly line up something like one in five times; perhaps not that crazy considering they're executing nearly the same code?

No, computer clocks are precise enough, and CPUs are wonky enough (cache effects, etc.), that it should be effectively impossible to get the same timing result twice in row, even for running exactly the same code. I'm not sure what's going on, but it's weird. Making these kinds of measurements is much more complicated than it looks and you really need to use something like timeit or perf if you want trustworthy results. Fortunately, they're easy to use :-) -n -- Nathaniel J. Smith -- https://vorpus.org

So maybe someone should explain to Elliott *why* his own benchmarks are not trustworthy, rather than just repeat "use perf or timeit". Actually, there are two things: (a) when something new comes along it *always* needs to prove beyond a shadow of a doubt that it is actually an improvement and not a timing artifact or a trick; (b) you can't time sorting 10 values *once* and get a useful result. You have to do it many times. And you have to make sure that creating a list of 10 random values isn't taken as part of your test -- that's tricky since random() isn't all that fast; but it has to be done. Although Elliott had it coming when he used needlessly offensive language in his first post. On Mon, Oct 10, 2016 at 5:09 PM, Steven D'Aprano wrote:

On Mon, Oct 10, 2016 at 09:16:32PM +0000, Elliot Gorokhovsky wrote:

...

Anyway, benchmarking technique aside, the point is that it it works well for small lists (i.e. doesn't affect performance).

You've been shown that there is something suspicious about your benchmarking technique, something that suggests that the timing results aren't trustworthy. Until you convince us that your timing results are reliable and trustworthy, you shouldn't be drawing *any* conclusions about your fastsort versus the standard sort.

-- Steve _______________________________________________ Python-Dev mailing list Python-Dev@python.org https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/guido%40python.org

-- --Guido van Rossum (python.org/~guido)

So here's a simple attempt at taking lots of measurements just using time.time() with lists of ints. The results are great, if they are valid (which I leave to you to judge); even for lists with just one element, it's 16% faster! The columns are length, number of trials, and percent improvement: Integer benchmarks 1 10000000 1-fastsort()/sort(): 0.14896401672523163 5 2000000 1-fastsort()/sort(): 0.2915859704616376 10 1000000 1-fastsort()/sort(): 0.3576859149132914 1000 10000 1-fastsort()/sort(): 0.3230363920681264 1000000 10 1-fastsort()/sort(): 0.292595011903772 And here's the benchmark script: from fastlist import FastList import random; random.seed(42) from time import time def bench_list(size, trials): L = [random.randrange(size) for _ in range(size)] trials = int(trials); size = int(size) fastlist_time = 0 for _ in range(trials): F = FastList(L) start = time() F.fastsort() fastlist_time += time() - start defaultlist_time = 0 for _ in range(trials): F = FastList(L) start = time() F.sort() defaultlist_time += time() - start print(size, trials, "1-fastsort()/sort():", 1-fastlist_time/defaultlist_time) print("Integer benchmarks") bench_list(1, 1e7) bench_list(5, 1e7/5) bench_list(10, 1e7/10) bench_list(1000, 1e7/1000) bench_list(1000000, 1e7/1e6) Is that a valid way to benchmark the implementation? On Mon, Oct 10, 2016 at 8:15 PM Elliot Gorokhovsky < elliot.gorokhovsky@gmail.com> wrote:

Right - sorry about that last bit!

I couldn't figure out how to use timeit/perf for this because the list has to be reinitialized each time it gets sorted. So with time.time() I can just wrap the sorting and cut the initialization out (and I could always throw it in a for loop to do it as many times as necessary). But with timeit/perf, as I understand, you just give it a number of iterations and a code snippet and it loops for you. So I don't see how I could get it to cut out the initialization. There's an option to provide setup code, of course, but I need to set up before each trial, not just before the loop.

Regardless, one could always wrap the whole contribution with a length test and disable for lists with less than, say, 1000 elements. And though for the above reason I couldn't figure out how to benchmark properly for small lists, it's clear that for large lists this gives a real improvement with very little change in the code: the fact is that it really doesn't make sense to do all this typechecking nlogn times when we can just get it over with once at the beginning. The cost is very, very small, as demonstrated by the last benchmark (which is for a 1e7 list, so it is probably more valid with my crude technique), so heterogeneous lists don't get slowed down perceptibly.

On Mon, Oct 10, 2016 at 8:06 PM Guido van Rossum wrote:

So maybe someone should explain to Elliott *why* his own benchmarks

are not trustworthy, rather than just repeat "use perf or timeit".

Actually, there are two things: (a) when something new comes along it

*always* needs to prove beyond a shadow of a doubt that it is actually

an improvement and not a timing artifact or a trick; (b) you can't

time sorting 10 values *once* and get a useful result. You have to do

it many times. And you have to make sure that creating a list of 10

random values isn't taken as part of your test -- that's tricky since

random() isn't all that fast; but it has to be done.

Although Elliott had it coming when he used needlessly offensive

language in his first post.

On Mon, Oct 10, 2016 at 5:09 PM, Steven D'Aprano wrote:

...

On Mon, Oct 10, 2016 at 09:16:32PM +0000, Elliot Gorokhovsky wrote:

...

...

...

Anyway, benchmarking technique aside, the point is that it it works well

...

...

for small lists (i.e. doesn't affect performance).

...

...

You've been shown that there is something suspicious about your

...

benchmarking technique, something that suggests that the timing results

...

aren't trustworthy. Until you convince us that your timing results are

...

reliable and trustworthy, you shouldn't be drawing *any* conclusions

...

about your fastsort versus the standard sort.

...

...

...

--

...

Steve

...

_______________________________________________

...

Python-Dev mailing list

...

Python-Dev@python.org

...

https://mail.python.org/mailman/listinfo/python-dev

...

Unsubscribe: https://mail.python.org/mailman/options/python-dev/guido%40python.org

--

--Guido van Rossum (python.org/~guido)

Right, that sounds good, but there's just one thing I don't understand that's keeping me from using it. Namely, I would define a benchmark list L in my setup, and then I would have code="F=FastList(L);F.fastsort()". The problem here is I'm measuring the constructor time along with the sort time, right, so wouldn't that mess up the benchmark? Or does timeit separate the times? On Tue, Oct 11, 2016, 2:22 AM Paul Moore wrote:

On 11 October 2016 at 03:15, Elliot Gorokhovsky wrote:

...

There's an option to provide setup code, of course, but I need to set up before each trial, not just before the loop.

Typically, I would just run the benchmark separately for each case, and then you'd do

# Case 1 python -m perf timeit -s 'setup; code; here' 'code; to; be; timed; here' [Results 1] # Case 2 python -m perf timeit -s 'setup; code; here' 'code; to; be; timed; here' [Results 2]

The other advantage of doing it this way is that you can post your benchmark command lines, which will allow people to see what you're timing, and if there *are* any problems (such as a method lookup that skews the results) people can point them out.

Paul

On Wed, Oct 12, 2016 at 12:51 AM, Paul Moore wrote:

On 11 October 2016 at 14:04, Elliot Gorokhovsky wrote:

...

Right, that sounds good, but there's just one thing I don't understand that's keeping me from using it. Namely, I would define a benchmark list L in my setup, and then I would have code="F=FastList(L);F.fastsort()". The problem here is I'm measuring the constructor time along with the sort time, right, so wouldn't that mess up the benchmark? Or does timeit separate the times?

That would mess up your times. Put F=FastList(L) in your setup.

But then you're resorting an already-sorted list, which may well have different timings (it certainly does in timsort). ChrisA

On Wed, Oct 12, 2016 at 1:24 AM, Paul Moore wrote:

On 11 October 2016 at 15:00, Chris Angelico wrote:

...

On Wed, Oct 12, 2016 at 12:51 AM, Paul Moore wrote:

...

On 11 October 2016 at 14:04, Elliot Gorokhovsky wrote:

...

Right, that sounds good, but there's just one thing I don't understand that's keeping me from using it. Namely, I would define a benchmark list L in my setup, and then I would have code="F=FastList(L);F.fastsort()". The problem here is I'm measuring the constructor time along with the sort time, right, so wouldn't that mess up the benchmark? Or does timeit separate the times?

That would mess up your times. Put F=FastList(L) in your setup.

But then you're resorting an already-sorted list, which may well have different timings (it certainly does in timsort).

Why would it be already sorted? I assume FastList(L) is simply a wrapper round a normal list that has a modified sort method with the optimisation included.

Of course, that's essentially the point here - without seeing the code, we're (to an extent) guessing.

After the first call, the list will be sorted. Any subsequent attempts will use the sorted list. ChrisA

[Terry Reedy]

This seems like a generic issue with timing mutation methods ... But I am sure Tim worked this out in his test code, which should be reused, perhaps updated with Viktor's perf module to get the most stable timings possible.

sortperf.py is older than me ;-) It's not at all intended to give fine-grained timings: it's a sledgehammer than runs each case _only once_, to confirm/refute _big_ changes. So it's useful qualitatively when a "big claimed change" is at issue, but useless for quantifying beyond "wow!" or "ouch!" or "meh". Since this is a "big claimed change", a "wow!" outcome is good-enough confirmation. And a "meh" outcome would be almost good enough for cases where the new specializations don't apply - although I haven't seen any numbers from sortperf.py for those cases yet. I expect a "meh" outcome for those, based on reasoning - but may be surprised by reality.

On 11 October 2016 at 15:32, Elliot Gorokhovsky wrote:

But the sort mutates F...does the setup get executed each time? I thought it's just at the beginning. So then F gets mutated (sorted) and subsequent sorts time wrong.

Did I not say earlier - sorry. I'm suggesting that you put each timing run into a separate Python process. # Optimised code python -m perf timeit -s "from mymod import FastList; L=<whatever you do to create the list>;F=FastList(L)" "F.fastsort()" # Core sort routine python -m perf timeit -s "L=<whatever you do to create the list>" "L.sort()" # Or maybe, if FastList exposes the existing sort function as well # Non-optimised code python -m perf timeit -s "from mymod import FastList; L=<whatever you do to create the list>;F=FastList(L)" "F.sort()" Paul.

Elliot Gorokhovsky wrote:

I ran the benchmark a couple of times and the numbers seem to exactly line up something like one in five times; perhaps not that crazy considering they're executing nearly the same code?

Could this be a result of a time being measured in seconds somewhere and then divided down?

*** 1e7 ints + 1 float (to disable the optimization while keeping the precheck)*** F.fastsort(): 7.57237982749939 F.sort(): 7.666172504425049

This result looks a bit suspicious too -- it's hard to see how fastsort could be faster even when the optimisation is not being used. -- Greg