New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Improve pickling efficiency of itertools.cycle #69062
Comments
When a cycle object has fully consumed its input iterable, __reduce__ method uses the returns a space-inefficient result when space-efficient alternative is available. # Current way of restoring a cycle object with excess info in setstate:
>>> c = cycle(iter('de'))
>>> c.__setstate__((['a', 'b', 'c', 'd', 'e'], 1))
>>> ''.join(next(c) for i in range(20)) # next 20 values
'deabcdeabcdeabcdeabc'
# The same result can be achieved with less information:
>>> c = cycle(iter('de'))
>>> c.__setstate__((['a', 'b', 'c'], 0))
>>> ''.join(next(c) for i in range(20)) # next 20 values
'deabcdeabcdeabcdeabc' |
Also, looking at the source for itertools.cycle(), it looks like the overall speed could be boosted considerably by looping over the saved list directly rather than allocating a new list iterator every time the cycle loops around. |
Attaching a partial patch:
|
Current cycle implementation is simple and clever, but can be optimized. The part about iterating LGTM (but looks the firstpass field can be eliminated at all). But __reduce__ doesn't look so optimal. It makes a copy of a list and makes iterating an unpickled cycle object slow. It would be more optimal if create new list with rotated content or even rotate original list inplace. |
Added an updated patch that passes all tests. |
Original Raymonds reason in msg248662 is not valid. Pickling a cycle object that fully consumed its input iterable is already space-inefficient. >>> import itertools, pickle, pickletools
>>> c = itertools.cycle(iter('abcde'))
>>> [next(c) for i in range(8)]
['a', 'b', 'c', 'd', 'e', 'a', 'b', 'c']
>>> pickle.dumps(c)
b'\x80\x03citertools\ncycle\nq\x00cbuiltins\niter\nq\x01]q\x02(X\x01\x00\x00\x00aq\x03X\x01\x00\x00\x00bq\x04X\x01\x00\x00\x00cq\x05X\x01\x00\x00\x00dq\x06X\x01\x00\x00\x00eq\x07e\x85q\x08Rq\tK\x03b\x85q\nRq\x0bh\x02K\x01\x86q\x0cb.'
>>> pickletools.dis(pickle.dumps(c))
0: \x80 PROTO 3
2: c GLOBAL 'itertools cycle'
19: q BINPUT 0
21: c GLOBAL 'builtins iter'
36: q BINPUT 1
38: ] EMPTY_LIST
39: q BINPUT 2
41: ( MARK
42: X BINUNICODE 'a'
48: q BINPUT 3
50: X BINUNICODE 'b'
56: q BINPUT 4
58: X BINUNICODE 'c'
64: q BINPUT 5
66: X BINUNICODE 'd'
72: q BINPUT 6
74: X BINUNICODE 'e'
80: q BINPUT 7
82: e APPENDS (MARK at 41)
83: \x85 TUPLE1
84: q BINPUT 8
86: R REDUCE
87: q BINPUT 9
89: K BININT1 3
91: b BUILD
92: \x85 TUPLE1
93: q BINPUT 10
95: R REDUCE
96: q BINPUT 11
98: h BINGET 2
100: K BININT1 1
102: \x86 TUPLE2
103: q BINPUT 12
105: b BUILD
106: . STOP
highest protocol among opcodes = 2 An internal iterator is not pickled as iter("de"), but as an iterator of the list ["a", "b", "c", "d", "e"] with 3 items consumed. This list also saved as a part of a cycle object state, but not as a copy, but as a reference. There are two alternative patches. Both keep Raymonds optimization of cycle iterating, but have advantages. cycle_reduce_2.patch makes __reduce__ faster and more memory efficient than Raymonds variant. cycle_reduce_3.patch makes unpickled cycle object so optimized as original. |
New changeset 17b5c8ba6875 by Raymond Hettinger in branch 'default': |
Applied the cycle2 patch but kept the signature the same as the original reduce (using a number instead of a boolean). |
Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.
Show more details
GitHub fields:
bugs.python.org fields:
The text was updated successfully, but these errors were encountered: