Dear PyPy developers! In CPython, a common idiom to copy a list is to use slice, as in: copy = original[:] I noticed that under PyPy 2.6.0 it seems quite a bit slower than using `list` constructor: from timeit import timeit print timeit('b = a[:]', 'a = list(range(100))') # 0.0732719898224 print timeit('b = list(a)', 'a = list(range(100))') # 0.00285792350769 Please, could some comment on what is the preferred way to copy a list under PyPy? Should I try to avoid the "slice way"? Thanks!
Hello, is your code actually such a heavy list-copy-through-slicing user ? This question is independent from pypy's eventual desire to speed this python "idiom", though. I myself was using it, but went to use list(), as that look more natural, to my eyes, but that's a matter of taste anyways, I think... On Mon, Sep 28, 2015 at 3:57 PM, Tuom Larsen <tuom.larsen@gmail.com> wrote:
Dear PyPy developers!
In CPython, a common idiom to copy a list is to use slice, as in:
copy = original[:]
I noticed that under PyPy 2.6.0 it seems quite a bit slower than using `list` constructor:
from timeit import timeit print timeit('b = a[:]', 'a = list(range(100))') # 0.0732719898224 print timeit('b = list(a)', 'a = list(range(100))') # 0.00285792350769
Please, could some comment on what is the preferred way to copy a list under PyPy? Should I try to avoid the "slice way"?
Thanks! _______________________________________________ pypy-dev mailing list pypy-dev@python.org https://mail.python.org/mailman/listinfo/pypy-dev
-- Vincent Legoll
On Mon, 28 Sep 2015 at 14:57 Tuom Larsen <tuom.larsen@gmail.com> wrote:
Dear PyPy developers!
In CPython, a common idiom to copy a list is to use slice, as in:
copy = original[:]
I noticed that under PyPy 2.6.0 it seems quite a bit slower than using `list` constructor:
from timeit import timeit print timeit('b = a[:]', 'a = list(range(100))') # 0.0732719898224 print timeit('b = list(a)', 'a = list(range(100))') # 0.00285792350769
Please, could some comment on what is the preferred way to copy a list under PyPy? Should I try to avoid the "slice way"?
I don't get the same timings here: enojb@it054759:~$ pypy -m timeit -s 'a = list(range(100))' 'b = a[:]' 1000000000 loops, best of 3: 0.00142 usec per loop enojb@it054759:~$ pypy -m timeit -s 'a = list(range(100))' 'b = list(a)' 1000000000 loops, best of 3: 0.00109 usec per loop So for me it's about the same. However if you look closer you'll see that it's about 1 nanosecond in either case. That's really a very short time. Why is so short? I guess because it's not really copying the lists. If I try with a much bigger list it takes the same time: enojb@it054759:~$ pypy -m timeit -s 'a = list(range(1000000))' 'b = a[:]' 1000000000 loops, best of 3: 0.00142 usec per loop enojb@it054759:~$ pypy -m timeit -s 'a = list(range(1000000))' 'b = list(a)' 1000000000 loops, best of 3: 0.00105 usec per loop I would guess that the actual copy has somehow been optimised away. If I make the expression do some actual work instead of just copying a list then the differences are insignificant: enojb@it054759:~$ pypy -m timeit -s 'a = list(range(100))' 'b = sum(a[:])' 1000000 loops, best of 3: 0.212 usec per loop enojb@it054759:~$ pypy -m timeit -s 'a = list(range(100))' 'b = sum(list(a))' 1000000 loops, best of 3: 0.205 usec per loop So I wouldn't worry about how many nanoseconds the copy takes. Finish your application and then if the difference between slice/list copy actually affects whole application performance in a significant way then this question may be worth considering. Until then just code it whichever way seems clearest to you. Bear in mind that the two are not equivalent since b[:] will return a tuple if b is a tuple, or a range if b is a range etc. -- Oscar
Hi Tuom, On Mon, Sep 28, 2015 at 3:57 PM, Tuom Larsen <tuom.larsen@gmail.com> wrote:
from timeit import timeit print timeit('b = a[:]', 'a = list(range(100))') # 0.0732719898224 print timeit('b = list(a)', 'a = list(range(100))') # 0.00285792350769
In addition to the other comments, this is not testing what you think it is: 'range(100)' returns a list optimized for being a range, and 'list(range(100))' does it too. You can see it like this:
import __pypy__ __pypy__.strategy([]) 'EmptyListStrategy' __pypy__.strategy(range(100)) 'SimpleRangeListStrategy' __pypy__.strategy(list(range(100))) 'SimpleRangeListStrategy'
The SimpleRangeListStrategy means that the list is implemented as just a number, here 100.
__pypy__.strategy(range(100)[:]) 'IntegerListStrategy'
So we discover here that slicing a range-list is not as optimized as it could be. It expands it to an array containing all the integers. That's the reason for why the slicing version seems slower in your tests. But optimizing that would of course be pointless in almost any real program. A bientôt, Armin.
Hello Armin, Thanks for the answer! On Mon, Sep 28, 2015 at 8:17 PM, Armin Rigo <arigo@tunes.org> wrote:
In addition to the other comments, this is not testing what you think it is: 'range(100)' returns a list optimized for being a range, and 'list(range(100))' does it too. You can see it like this:
import __pypy__ __pypy__.strategy([]) 'EmptyListStrategy' __pypy__.strategy(range(100)) 'SimpleRangeListStrategy' __pypy__.strategy(list(range(100))) 'SimpleRangeListStrategy'
The SimpleRangeListStrategy means that the list is implemented as just a number, here 100.
__pypy__.strategy(range(100)[:]) 'IntegerListStrategy'
So we discover here that slicing a range-list is not as optimized as it could be. It expands it to an array containing all the integers. That's the reason for why the slicing version seems slower in your tests. But optimizing that would of course be pointless in almost any real program.
However, I still get "slice-way" twice as slow as "constructor-way" when I use normal lists: from timeit import timeit print timeit('b = a[:]', 'a = [1,2,3,4,5,6,7,8,9,0]') # 0.0329349040985 print timeit('b = list(a)', 'a = [1,2,3,4,5,6,7,8,9,0]') # 0.0171940326691 or: pypy -m timeit -s 'a = [1,2,3,4,5,6,7,8,9,0]' 'b = a[:]' # 0.0306 usec per loop pypy -m timeit -s 'a = [1,2,3,4,5,6,7,8,9,0]' 'b = list(a)' # 0.0149 usec per loop Please, let me rephrase my question: currently I use `[:]` because it is faster in CPython (0.131 usec vs 0.269 usec per loop). I almost don't mind changing it to `list()` because of PyPy but I was wondering what do PyPy developers recommend. I don't understand why is `[:]` twice as slow as `list()` as it seems it should do the same thing (create a list and copy the content). So my question is, is there a reason why `list()` is fundamentally faster, and then I would switch to it, or maybe/perhaps/somewhere-in-the-future PyPy would make it as fast as `[:]`, as it does the same amount of work, and then I could leave it as it is (`[:]`)?
Hi Tuom, On Tue, Sep 29, 2015 at 7:31 AM, Tuom Larsen <tuom.larsen@gmail.com> wrote:
Please, let me rephrase my question: currently I use `[:]` because it is faster in CPython (0.131 usec vs 0.269 usec per loop). I almost don't mind changing it to `list()` because of PyPy but I was wondering what do PyPy developers recommend. I don't understand why is `[:]` twice as slow as `list()` as it seems it should do the same thing (create a list and copy the content).
Looking at the jit logs, it is tripped by a RPython function with a loop in its slow-path. Fixed in 4e688540cfe9. There is still a bit of overhead. For example, lst[:] is equivalent to lst[0:9223372036854775807]. The general logic looks like this: when doing lst[a:b], if b > len(lst) then replace b with len(lst). This means here a check if 9223372036854775807 > len(lst)... It is not possible that the length of a list be that huge, but this knowledge is not codified explicitly. Yes, we could improve that in the future. But this is really advanced details. You should write 'list()' or '[:]' as you feel more natural, or maybe as benefits the speed of CPython if it makes an important difference there. Using 'timeit' to measure microbenchmarks in PyPy may or may not give a useful result. In this case it did only after you stopped using range() and only because we don't have more advanced optimizations that realize that the resulting list is not needed at all. In general, you should not rely on it. What you should do instead is measure how much time is spent in some real loop of your algorithm, and compare it with variants. (Make sure every variant is run in its own process, otherwise the JITting of similar pieces of code might interfere in unexpected ways.) If you're lucky you may be able to find a variant that is overall much faster. If you're not, it means that what you're changing is not relevant for performance. A bientôt, Armin.
Hi Armin, thanks a lot, both for the explanation and the fix! I will try it soon. Have a nice day! Tuom PS: The speed difference came from larger piece of code, which I tried to reproduce in "minimal viable test case". Hence that `timeit`, where it showed up as well. But in any case, thanks a lot once more! On Tue, Sep 29, 2015 at 9:25 AM, Armin Rigo <arigo@tunes.org> wrote:
Hi Tuom,
On Tue, Sep 29, 2015 at 7:31 AM, Tuom Larsen <tuom.larsen@gmail.com> wrote:
Please, let me rephrase my question: currently I use `[:]` because it is faster in CPython (0.131 usec vs 0.269 usec per loop). I almost don't mind changing it to `list()` because of PyPy but I was wondering what do PyPy developers recommend. I don't understand why is `[:]` twice as slow as `list()` as it seems it should do the same thing (create a list and copy the content).
Looking at the jit logs, it is tripped by a RPython function with a loop in its slow-path. Fixed in 4e688540cfe9.
There is still a bit of overhead. For example, lst[:] is equivalent to lst[0:9223372036854775807]. The general logic looks like this: when doing lst[a:b], if b > len(lst) then replace b with len(lst). This means here a check if 9223372036854775807 > len(lst)... It is not possible that the length of a list be that huge, but this knowledge is not codified explicitly.
Yes, we could improve that in the future. But this is really advanced details. You should write 'list()' or '[:]' as you feel more natural, or maybe as benefits the speed of CPython if it makes an important difference there. Using 'timeit' to measure microbenchmarks in PyPy may or may not give a useful result. In this case it did only after you stopped using range() and only because we don't have more advanced optimizations that realize that the resulting list is not needed at all. In general, you should not rely on it.
What you should do instead is measure how much time is spent in some real loop of your algorithm, and compare it with variants. (Make sure every variant is run in its own process, otherwise the JITting of similar pieces of code might interfere in unexpected ways.) If you're lucky you may be able to find a variant that is overall much faster. If you're not, it means that what you're changing is not relevant for performance.
A bientôt,
Armin.
So I just tried it with the latest nightly build and `[:]` is now even a bit faster than `list()`! Thank you once more! On Tue, Sep 29, 2015 at 12:27 PM, Tuom Larsen <tuom.larsen@gmail.com> wrote:
Hi Armin,
thanks a lot, both for the explanation and the fix! I will try it soon.
Have a nice day!
Tuom
PS: The speed difference came from larger piece of code, which I tried to reproduce in "minimal viable test case". Hence that `timeit`, where it showed up as well. But in any case, thanks a lot once more!
On Tue, Sep 29, 2015 at 9:25 AM, Armin Rigo <arigo@tunes.org> wrote:
Hi Tuom,
On Tue, Sep 29, 2015 at 7:31 AM, Tuom Larsen <tuom.larsen@gmail.com> wrote:
Please, let me rephrase my question: currently I use `[:]` because it is faster in CPython (0.131 usec vs 0.269 usec per loop). I almost don't mind changing it to `list()` because of PyPy but I was wondering what do PyPy developers recommend. I don't understand why is `[:]` twice as slow as `list()` as it seems it should do the same thing (create a list and copy the content).
Looking at the jit logs, it is tripped by a RPython function with a loop in its slow-path. Fixed in 4e688540cfe9.
There is still a bit of overhead. For example, lst[:] is equivalent to lst[0:9223372036854775807]. The general logic looks like this: when doing lst[a:b], if b > len(lst) then replace b with len(lst). This means here a check if 9223372036854775807 > len(lst)... It is not possible that the length of a list be that huge, but this knowledge is not codified explicitly.
Yes, we could improve that in the future. But this is really advanced details. You should write 'list()' or '[:]' as you feel more natural, or maybe as benefits the speed of CPython if it makes an important difference there. Using 'timeit' to measure microbenchmarks in PyPy may or may not give a useful result. In this case it did only after you stopped using range() and only because we don't have more advanced optimizations that realize that the resulting list is not needed at all. In general, you should not rely on it.
What you should do instead is measure how much time is spent in some real loop of your algorithm, and compare it with variants. (Make sure every variant is run in its own process, otherwise the JITting of similar pieces of code might interfere in unexpected ways.) If you're lucky you may be able to find a variant that is overall much faster. If you're not, it means that what you're changing is not relevant for performance.
A bientôt,
Armin.
participants (4)
-
Armin Rigo -
Oscar Benjamin -
Tuom Larsen -
Vincent Legoll