classification
Title: Cache constant "slice" instances
Type: performance Stage: needs patch
Components: Interpreter Core Versions: Python 3.8
process
Status: open Resolution:
Dependencies: Superseder:
Assigned To: Nosy List: belopolsky, josh.r, meador.inge, pitrou, remi.lapeyre, scoder, serhiy.storchaka, yselivanov
Priority: normal Keywords:

Created on 2011-02-03 19:25 by scoder, last changed 2019-05-07 14:19 by josh.r.

Messages (9)
msg127804 - (view) Author: Stefan Behnel (scoder) * (Python committer) 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) * (Python committer) Date: 2011-02-03 19:27
Erm, issue 10227.
msg127808 - (view) Author: Alexander Belopolsky (belopolsky) * (Python committer) 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) * (Python committer) 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) * (Python committer) 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) * (Python triager) 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) * (Python committer) 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) * (Python triager) 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. :-)
History
Date User Action Args
2019-05-07 14:19:27josh.rsetmessages: + msg341733
2019-05-07 09:20:11serhiy.storchakasetnosy: + serhiy.storchaka
messages: + msg341702
2019-05-07 08:57:12remi.lapeyresetnosy: + remi.lapeyre
messages: + msg341700
2019-05-06 18:56:58josh.rsetmessages: + msg341602
2018-12-04 02:39:34josh.rsetversions: + Python 3.8, - Python 3.5
2014-03-06 22:40:28josh.rsetnosy: + josh.r
2014-01-31 21:58:35yselivanovsetnosy: + yselivanov
2014-01-31 21:57:44yselivanovsetversions: + Python 3.5, - Python 3.3
2011-11-28 01:34:57meador.ingesetnosy: + meador.inge
2011-11-18 16:39:24ezio.melottisetstage: needs patch
2011-02-03 20:20:16pitrousetmessages: + msg127818
2011-02-03 19:48:57scodersetmessages: + msg127810
2011-02-03 19:47:03pitrousetnosy: + pitrou
2011-02-03 19:35:38belopolskysetnosy: + belopolsky
messages: + msg127808
2011-02-03 19:27:21scodersetmessages: + msg127806
2011-02-03 19:25:20scodercreate