msg127804 - (view) |
Author: Stefan Behnel (scoder) *  |
Date: 2011-02-03 19:25 |
Follow-up to ticket 10227. The following facts seem to indicate that it would be worth caching constant instances of the slice type, such as in [:] or [:-1].
with cached slice instance:
$ ./python -m timeit -s 'l = list(range(100)); s=slice(None)' 'l[s]'
1000000 loops, best of 3: 0.464 usec per loop
$ ./python -m timeit -s 'l = list(range(10)); s=slice(None)' 'l[s]'
10000000 loops, best of 3: 0.149 usec per loop
$ ./python -m timeit -s 'l = list(range(10)); s=slice(None,1)' 'l[s]'
10000000 loops, best of 3: 0.135 usec per loop
uncached normal usage:
$ ./python -m timeit -s 'l = list(range(100))' 'l[:]'
1000000 loops, best of 3: 0.499 usec per loop
$ ./python -m timeit -s 'l = list(range(100))' 'l[:1]'
10000000 loops, best of 3: 0.171 usec per loop
Timings based on Python 3.2 rc2.
A quick grep against the py3k stdlib finds 2096 lines in 393 files that use constant slices.
|
msg127806 - (view) |
Author: Stefan Behnel (scoder) *  |
Date: 2011-02-03 19:27 |
Erm, issue 10227.
|
msg127808 - (view) |
Author: Alexander Belopolsky (belopolsky) *  |
Date: 2011-02-03 19:35 |
Similar idea has been rejected in issue2268 because the win was too small to justify the number of changes that had to be made.
|
msg127810 - (view) |
Author: Stefan Behnel (scoder) *  |
Date: 2011-02-03 19:48 |
Hmm, ok, but AFAICT, your patch was rejected rather because of the way it approached the problem, not so much because of the issue itself.
Plus, the fact that Python 3 requires slices in more places than Python 2 (which had the lower level getslice protocol) makes this a bigger issue now than it was three years ago.
|
msg127818 - (view) |
Author: Antoine Pitrou (pitrou) *  |
Date: 2011-02-03 20:20 |
> Hmm, ok, but AFAICT, your patch was rejected rather because of the way
> it approached the problem, not so much because of the issue itself.
I would be rather for the patch myself. The bytecode currently generated
for sliced indexing is awfully suboptimal.
> Plus, the fact that Python 3 requires slices in more places than
> Python 2 (which had the lower level getslice protocol) makes this a
> bigger issue now than it was three years ago.
True.
|
msg341602 - (view) |
Author: Josh Rosenberg (josh.r) *  |
Date: 2019-05-06 18:56 |
I'm trying to sprint on this this week. I already had a PoC put together, but it has some significant issues caused by one major quirk with slices:
1. They're immutable, but
2. They're not hashable
In various places, it is (reasonably) assumed that constants can be hashed (so as to coalesce identical constants), and since slice objects can't be, this causes problems.
In my proof of concept, I cheated, and added a field to the slice object, hashable, that was only set to true when the slice was a result of:
1. ast_opt.c's constant coalescence
2. marshal.c's r_object reading in a slice from the bytecode
Obviously this isn't practical for an actual patch, and I'm trying to figure out if there is a way around it.
Right now, it seems like ast_opt.c's approach may not be necessary (even if I don't set hashable, it still works, and seems to coalesce, which seems odd; pretty sure when I first started the slices tried to get stored as dict keys at some point).
I'm still having issues figuring out to handle marshaling; my code currently works, but where the first load of a module (from .py) performs constant coalescence, my attempts to make slices use w_ref/R_REF appropriately have been unsuccessful. I'd greatly appreciate any help/tips from anyone who knows enough about:
1. The constant coalescence code for ast/compile steps (for first load)
2. The rules for w_ref/R_REF in the marshal code (for writing out and loading from compiled bytecode files)
3. Working around the (possible) need for hashable objects in the constant coalescent/marshal-ing code
If you're at the sprints, I'm sitting in the CPython room directly in front of the entrance.
|
msg341700 - (view) |
Author: Rémi Lapeyre (remi.lapeyre) * |
Date: 2019-05-07 08:57 |
Hi josh.r, this may be dump but is there a reason not to make slices hashable? Couldn't they hash like a tuple (start, stop, step)?
I looked around in the code, bpo and the mailing lists but could not find a reason why not, maybe it was just not useful at the time but could be implemented now?
|
msg341702 - (view) |
Author: Serhiy Storchaka (serhiy.storchaka) *  |
Date: 2019-05-07 09:20 |
To support slice constants we need to change the marshal format and introduce new version (current version is 4 and it was stable for several releases). If my memory do not betray me we already discussed this on other issue and the conclusion was that the benefit of this is too small for such large change.
But if we will need to add new marshal version for other reasons, supporting slices will be a nice addition. We just do not have enough reasons for this now.
|
msg341733 - (view) |
Author: Josh Rosenberg (josh.r) *  |
Date: 2019-05-07 14:19 |
Remi: The reason they're not hashable is presumably because it would make them valid dictionary keys, further confusing the difference between sequences and mappings. x[::-1] would, for a sequence, return a reversed sequence, but for a mapping, would end up using the slice as a key (not actually slicing) to obtain a single value. Confusing at best.
Serhiy: It was discussed on the other issue, but the rationale there was, to quote Raymond:
* too many other things need to be changed to support it
* the measured win is somewhat small
* we have a negative bias towards expanding the peephole optimizer
* the AST may be a better place to do these kind of optimizations
Of those, only the first bullet is (essentially) unchanged. Addressing the following points in order:
* The win will likely be higher given that the __getslice__ protocol no longer exists; where slice objects need not be constructed in many cases in Python 2 (which had the SLICE+N bytecodes to perform subscripting directly, without a separate code to build a slice), leaving only slices with a step dependent on actually building slices. Nowadays, x[:-1] requires building a slice object, as does x[1:] and the like, where previously they did not
* The approach I'm taking does not use the peephole optimizer in any way
* I'm making the changes in the AST optimizer
Perhaps the issues with "too many other things need to be changed" remain, but I'd like to at least have a PR in place so that, should the marshalling format change be accepted, we'd be able to take advantage of it.
Side-note: The marshal code for marshalling slices that I chose was ':'; seemed rather appropriate for slices, and conveniently, it was not already in use. :-)
|
msg381996 - (view) |
Author: Terry J. Reedy (terry.reedy) *  |
Date: 2020-11-28 12:29 |
Batuhan Taskaya opened a duplicate issue #42454. Since it includes PR-23496, with some review, and at least as much discussion, I am closing this issue, contrary to normal policy.
Worthwhile? Batuhan found about 100000 constant slices in 3200 PyPI packages, and 3-50% speedup.
Rémi asked "Couldn't [slices] hash like a tuple (start, stop, step)?"
Batuhad used the tuple analogy - hashability and hash depends on components. See PR for details.
Josh: the PR defines TYPE_SLICE as ':'.
|
|
Date |
User |
Action |
Args |
2022-04-11 14:57:12 | admin | set | github: 55316 |
2020-11-28 12:29:53 | terry.reedy | set | status: open -> closed
superseder: Move slice creation to the compiler for constants
nosy:
+ terry.reedy messages:
+ msg381996 resolution: duplicate stage: needs patch -> resolved |
2019-05-07 14:19:27 | josh.r | set | messages:
+ msg341733 |
2019-05-07 09:20:11 | serhiy.storchaka | set | nosy:
+ serhiy.storchaka messages:
+ msg341702
|
2019-05-07 08:57:12 | remi.lapeyre | set | nosy:
+ remi.lapeyre messages:
+ msg341700
|
2019-05-06 18:56:58 | josh.r | set | messages:
+ msg341602 |
2018-12-04 02:39:34 | josh.r | set | versions:
+ Python 3.8, - Python 3.5 |
2014-03-06 22:40:28 | josh.r | set | nosy:
+ josh.r
|
2014-01-31 21:58:35 | yselivanov | set | nosy:
+ yselivanov
|
2014-01-31 21:57:44 | yselivanov | set | versions:
+ Python 3.5, - Python 3.3 |
2011-11-28 01:34:57 | meador.inge | set | nosy:
+ meador.inge
|
2011-11-18 16:39:24 | ezio.melotti | set | stage: needs patch |
2011-02-03 20:20:16 | pitrou | set | messages:
+ msg127818 |
2011-02-03 19:48:57 | scoder | set | messages:
+ msg127810 |
2011-02-03 19:47:03 | pitrou | set | nosy:
+ pitrou
|
2011-02-03 19:35:38 | belopolsky | set | nosy:
+ belopolsky messages:
+ msg127808
|
2011-02-03 19:27:21 | scoder | set | messages:
+ msg127806 |
2011-02-03 19:25:20 | scoder | create | |