Re: [Python-Dev] Optimizing list.sort() by checking type in advance
[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. ___ 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/archive%40mail-archive.com
Re: [Python-Dev] Optimizing list.sort() by checking type in advance
On 10/11/2016 10:26 AM, Chris Angelico wrote: After the first call, the list will be sorted. Any subsequent attempts will use the sorted list. This seems like a generic issue with timing mutation methods. Is the mutated output suitable input for another mutation. With list.reverse, the output is suitable. Ditto for other permutations that are independent of the data, including random.shuffle. With list.pop, the number of mutations has to be limited to the length of the list. With list.sort, the list needs to be 'restored' -- either copied or shuffled each time. So it seems that one is stuck with timing 'restore', restore + sort_a, restore + sort_b, subtracting the timing for restore, and comparing. 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. -- Terry Jan Reedy ___ 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/archive%40mail-archive.com
Re: [Python-Dev] Optimizing list.sort() by checking type in advance
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=;F=FastList(L)" "F.fastsort()" # Core sort routine python -m perf timeit -s "L=" "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=;F=FastList(L)" "F.sort()" Paul. ___ 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/archive%40mail-archive.com
Re: [Python-Dev] Optimizing list.sort() by checking type in advance
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. On Tue, Oct 11, 2016, 7: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. > > Paul > ___ 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/archive%40mail-archive.com
Re: [Python-Dev] Optimizing list.sort() by checking type in advance
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 > ___ 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/archive%40mail-archive.com
Re: [Python-Dev] Optimizing list.sort() by checking type in advance
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 ___ 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/archive%40mail-archive.com
Re: [Python-Dev] Optimizing list.sort() by checking type in advance
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. Paul ___ 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/archive%40mail-archive.com
Re: [Python-Dev] Optimizing list.sort() by checking type in advance
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 ___ 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/archive%40mail-archive.com
Re: [Python-Dev] Optimizing list.sort() by checking type in advance
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. Paul ___ 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/archive%40mail-archive.com
Re: [Python-Dev] Optimizing list.sort() by checking type in advance
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 ___ 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/archive%40mail-archive.com
Re: [Python-Dev] Optimizing list.sort() by checking type in advance
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 ___ 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/archive%40mail-archive.com
Re: [Python-Dev] Optimizing list.sort() by checking type in advance
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 +, 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) > ___ 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/archive%40mail-archive.com
Re: [Python-Dev] Optimizing list.sort() by checking type in advance
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 1000 1-fastsort()/sort(): 0.14896401672523163
5 200 1-fastsort()/sort(): 0.2915859704616376
10 100 1-fastsort()/sort(): 0.3576859149132914
1000 1 1-fastsort()/sort(): 0.3230363920681264
100 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(100, 1e7/1e6)
Is that a valid way to benchmark the implementation?
On Mon, Oct 10, 2016 at 8:15 PM Elliot Gorokhovsky <
elliot.gorokhov...@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 +, 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)
>
>
___
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/archive%40mail-archive.com
Re: [Python-Dev] Optimizing list.sort() by checking type in advance
[please restrict follow-ups to python-ideas] Let's not get hung up on meta-discussion here - I always thought "massive clusterf**k" was a precise technical term anyway ;-) While timing certainly needs to be done more carefully, it's obvious to me that this approach _should_ pay off significantly when it applies. Comparisons are extraordinarily expensive in Python, precisely because of the maze of test-and-branch code it requires just to figure out which bottom-level comparison function to invoke each time. That's why I spent months of my life (overall) devising a sequence of sorting algorithms for Python that reduced the number of comparisons needed. Note that when Python's current sort was adopted in Java, they still kept a quicksort variant for "unboxed" builtin types. The adaptive merge sort incurs many overheads that often cost more than they save unless comparisons are in fact very expensive compared to the cost of pointer copying (and in Java comparison of unboxed types is cheap). Indeed, for native numeric types, where comparison is dirt cheap, quicksort generally runs faster than mergesort despite that the former does _more_ comparisons (because mergesort does so much more pointer-copying). I had considered something "like this" for Python 2, but didn't pursue it because comparison was defined between virtually any two types (34 < [1], etc), and people were careless about that (both by design and by accident). In Python 3, comparison "blows up" for absurdly mixed types, so specializing for homogeneously-typed lists is a more promising idea on the face of it. The comparisons needed to determine _whether_ a list's objects have a common type is just len(list)-1 C-level pointer comparisons, and so goes fast. So I expect that, when it applies, this would speed even sorting an already-ordered list with at least 2 elements. For a mixed-type list with at least 2 elements, it will always be pure loss. But (a) I expect such lists are uncommon (and especially uncommon in Python 3); and (b) a one-time scan doing C-level pointer comparisons until finding a mismatched type is bound to be a relatively tiny cost compared to the expense of all the "rich comparisons" that follow. So +1 from me on pursuing this. Elliot, please: - Keep this on python-ideas. python-dev is for current issues in Python development, not for speculating about changes. - Open an issue on the tracker: https://bugs.python.org/ - At least browse the info for developers: https://docs.python.org/devguide/ - Don't overlook Lib/test/sortperf.py. As is, it should be a good test of what your approach so far _doesn't_ help, since it sorts only lists of floats (& I don't think you're special-casing them). If the timing results it reports aren't significantly hurt (and I expect they won't be), then add specialization for floats too and gloat about the speedup :-) - I expect tuples will also be worth specializing (complex sort keys are often implemented as tuples). Nice start! :-) ___ 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/archive%40mail-archive.com
Re: [Python-Dev] Optimizing list.sort() by checking type in advance
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 +, 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) ___ 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/archive%40mail-archive.com
Re: [Python-Dev] Optimizing list.sort() by checking type in advance
On Mon, Oct 10, 2016 at 09:16:32PM +, 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/archive%40mail-archive.com
Re: [Python-Dev] Optimizing list.sort() by checking type in advance
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 ___ 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/archive%40mail-archive.com
Re: [Python-Dev] Optimizing list.sort() by checking type in advance
On Tue, Oct 11, 2016 at 7:42 AM, Elliot Gorokhovsky wrote: > ChrisA suggested I also try "make test" or something to get a more realistic > benchmark. I will do that once I implement this as a patch, right now it's > an extension module that subclasses list, so I can't just drop it into > existing code without modification. Oh, okay. If it's done that way, there's (in a way) a guarantee that it won't worsen anything, because you have to explicitly request the new behaviour. So if you KNOW that you're going to be doing a ton of string-only sorting, you can call on this new list subclass, and if you're not, you simply don't. ChrisA ___ 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/archive%40mail-archive.com
Re: [Python-Dev] Optimizing list.sort() by checking type in advance
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? Anyway, benchmarking technique aside, the point is that it it works well for small lists (i.e. doesn't affect performance). On Mon, Oct 10, 2016 at 2:53 PM Nathaniel Smith wrote: > 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 > ___ 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/archive%40mail-archive.com
Re: [Python-Dev] Optimizing list.sort() by checking type in advance
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 ___ 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/archive%40mail-archive.com
Re: [Python-Dev] Optimizing list.sort() by checking type in advance
I'd like to reply to both questions with one email, if that's all right. Bernardo Sulzbach asked, "How does this interfere with sorting very small lists?", and ChrisA asked, "How much slower are sorts of heterogeneous lists?". I modified the benchmark to answer both questions, the former at the top, and the latter at the bottom (see the git repo): *** 10 ints *** F.fastsort(): 2.86102294921875e-06 F.sort(): 3.337860107421875e-06 *** 10 strings *** F.fastsort(): 1.6689300537109375e-06 F.sort(): 1.6689300537109375e-06 *** 1e3 ints *** F.fastsort(): 0.00013589859008789062 F.sort(): 0.00018906593322753906 *** 1e3 strings *** F.fastsort(): 0.0002529621124267578 F.sort(): 0.0002772808074951172 *** 1e7 ints *** F.fastsort(): 5.472854375839233 F.sort(): 7.8826072216033936 *** 1e7 strings *** F.fastsort(): 10.104042053222656 F.sort(): 13.139304876327515 *** 1e7 ints + 1 float (to disable the optimization while keeping the precheck)*** F.fastsort(): 7.57237982749939 F.sort(): 7.666172504425049 ChrisA suggested I also try "make test" or something to get a more realistic benchmark. I will do that once I implement this as a patch, right now it's an extension module that subclasses list, so I can't just drop it into existing code without modification. Let me know if you have any other questions/suggestions! On Mon, Oct 10, 2016 at 12:18 AM Elliot Gorokhovsky < elliot.gorokhov...@gmail.com> wrote: > Hi, > > I posted here a while back asking what you guys thought about implementing > radix sort for strings in list.sort(). You gave me a lot of reasons why > that would be a bad idea. However, it got me thinking, and I came up with > something that you may find interesting. > > First, some simple benchmark results (numbers are seconds, check out the > extension module at https://github.com/embg/python-fast-listsort.git): > > *** 1e3 ints *** > F.fastsort(): 0.00018930435180664062 > F.sort(): 0.0002830028533935547 > *** 1e3 strings *** > F.fastsort(): 0.0003533363342285156 > F.sort(): 0.00044846534729003906 > *** 1e7 ints *** > F.fastsort(): 5.479267358779907 > F.sort(): 8.063318014144897 > *** 1e7 strings *** > F.fastsort(): 9.992833137512207 > F.sort(): 13.730914115905762 > > The optimization uses the fact that, in practice, we are almost always > sorting keys of the same type (note: not objects of the same type, *keys* > of the same type; we could have a complex key function like str that takes > many different types, but the keys are still all the same type). So we can > just do one typecheck up front and then do unsafe comparisons during the > sort (if our initial check passes). Specifically, we check that for all the > PyObject* in saved_ob_item, the ob->ob_type are the same. Then we replace > PyObject_RichCompare with ob_type->tp_richcompare. Additionally, we can > check for the very common cases of ints and strings and give optimized > comparison functions for those cases. It might not seem like this would > save a lot of time, but it turns out that PyObject_RichCompare is a massive > clusterf**k that has to test tons of type stuff before it can actually > compare. Cutting that out ends up saving a *lot* of time, as the benchmark > demonstrates. > > What do you think? I'm planning on writing this up into a patch, but > wanted to get some feedback on the implementation and ideas for improvement > first. > > Thanks, > Elliot > > ___ 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/archive%40mail-archive.com
Re: [Python-Dev] Optimizing list.sort() by checking type in advance
On Mon, Oct 10, 2016 at 5:18 PM, Elliot Gorokhovsky
wrote:
> First, some simple benchmark results (numbers are seconds, check out the
> extension module at https://github.com/embg/python-fast-listsort.git):
>
> *** 1e3 ints ***
> F.fastsort(): 0.00018930435180664062
> F.sort(): 0.0002830028533935547
> *** 1e3 strings ***
> F.fastsort(): 0.0003533363342285156
> F.sort(): 0.00044846534729003906
> *** 1e7 ints ***
> F.fastsort(): 5.479267358779907
> F.sort(): 8.063318014144897
> *** 1e7 strings ***
> F.fastsort(): 9.992833137512207
> F.sort(): 13.730914115905762
>
> The optimization uses the fact that, in practice, we are almost always
> sorting keys of the same type
(Might be a topic for python-ideas rather than python-dev.)
Can you pick up a standard benchmark suite and use that instead of
these simplistic operations? How much slower are sorts of
heterogeneous lists - what's the impact/cost on those? If a large test
suite ("make test" if you don't have a nice benchmark handy - the
CPython test suite is a solid mass of code) shows an overall slowdown,
this probably isn't worth pursuing; if it shows a minor but
insignificant increase, there might be something worth looking into;
and if it shows a huge increase... well, to be honest, if it shows a
huge increase, I'd suspect a fault in the measurements, because
sorting isn't a significant part of most test suites :)
ChrisA
___
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/archive%40mail-archive.com
Re: [Python-Dev] Optimizing list.sort() by checking type in advance
On 10/10/2016 03:18 AM, Elliot Gorokhovsky wrote: Hi, I posted here a while back asking what you guys thought about implementing radix sort for strings in list.sort(). You gave me a lot of reasons why that would be a bad idea. However, it got me thinking, and I came up with something that you may find interesting. First, some simple benchmark results (numbers are seconds, check out the extension module at https://github.com/embg/python-fast-listsort.git): *** 1e3 ints *** F.fastsort(): 0.00018930435180664062 F.sort(): 0.0002830028533935547 *** 1e3 strings *** F.fastsort(): 0.0003533363342285156 F.sort(): 0.00044846534729003906 *** 1e7 ints *** F.fastsort(): 5.479267358779907 F.sort(): 8.063318014144897 *** 1e7 strings *** F.fastsort(): 9.992833137512207 F.sort(): 13.730914115905762 The numbers are good. How does this interfere with sorting very small lists? Obviously, even if it does not help with very small lists, we can always put a threshold on the size and take this path or not. -- Bernardo Sulzbach http://www.mafagafogigante.org/ mafagafogiga...@mafagafogigante.org ___ 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/archive%40mail-archive.com
