Precompute range length and enhance range subscript support

[abalkin]

BPO	2690
Nosy	@birkenfeld, @rhettinger, @facundobatista, @amauryfa, @mdickinson, @ncoghlan, @abalkin, @pitrou
Files	range-length.diff anyrange.patch range-sequence.diff: patch against revision 62564 issue2690-range-sequence-ncoghlan.diff: Modified patch against rev 66147 issue2690-range-sequence-ncoghlan-v2.diff: Fix issue noted by Antoine (also adds new unit tests) issue2690_lazy_overflow_check.diff: Complete with docs and lazy overflow semantics stdtypes.rst.diff stdtypes.rst.diff

^{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:

assignee = 'https://github.com/ncoghlan'
closed_at = <Date 2010-12-11.00:43:24.715>
created_at = <Date 2008-04-25.15:32:00.391>
labels = ['interpreter-core', 'performance']
title = 'Precompute range length and enhance range subscript support'
updated_at = <Date 2010-12-17.21:29:31.330>
user = 'https://github.com/abalkin'

bugs.python.org fields:

activity = <Date 2010-12-17.21:29:31.330>
actor = 'stutzbach'
assignee = 'ncoghlan'
closed = True
closed_date = <Date 2010-12-11.00:43:24.715>
closer = 'rhettinger'
components = ['Interpreter Core']
creation = <Date 2008-04-25.15:32:00.391>
creator = 'belopolsky'
dependencies = []
files = ['10107', '10109', '10131', '11346', '11348', '19926', '20003', '20021']
hgrepos = []
issue_num = 2690
keywords = ['patch']
message_count = 44.0
messages = ['65786', '65793', '65798', '65802', '65803', '65807', '65810', '65812', '65825', '65835', '65926', '65937', '65942', '65956', '65963', '65981', '69884', '70525', '70548', '72344', '72345', '72346', '72348', '72352', '72354', '72355', '72357', '110812', '119515', '123250', '123257', '123259', '123261', '123267', '123268', '123273', '123278', '123755', '123760', '123762', '123765', '123779', '123819', '124258']
nosy_count = 11.0
nosy_names = ['georg.brandl', 'rhettinger', 'facundobatista', 'amaury.forgeotdarc', 'mark.dickinson', 'ncoghlan', 'belopolsky', 'pitrou', 'stutzbach', 'SilentGhost', 'BreamoreBoy']
pr_nums = []
priority = 'normal'
resolution = 'accepted'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue2690'
versions = ['Python 3.2']

[abalkin]

Attached patch makes range objects precompute their length on creation.
This speeds up indexing and len at the expense of a small increase in
range object size. The main benefit, however is that unsupported length >
sys.maxsize is detected early and confusing OverflowError from len(r) or
r[i] is avoided.

See discussion starting at http://mail.python.org/pipermail/python-
3000/2008-April/013225.html .

[mdickinson]

So with this patch, range(10**100) produces an OverflowError: is that
right?

I don't much like this aspect of the change: there are uses for

for i in range(ridiculously_large_number):
   ...
   if condition_that_occurs_early_in_practice:
       break

[abalkin]

On Fri, Apr 25, 2008 at 12:55 PM, Mark Dickinson <report@bugs.python.org> wrote:
..

I don't much like this aspect of the change: there are uses for

for i in range(ridiculously_large_number):

For this application, I would use "for i in itertools.count():"
instead. The only caveat is that while count() lets you specify the
start, it does not provide for a step. If that is a problem, I would
rather add step to count().

[mdickinson]

I guess there needs to be a decision on whether to make range objects of
length >= PY_SSIZE_T_MAX illegal; perhaps more discussion on python-dev
would be worthwhile?

I can see three options, besides leaving things as they are:

(1) make large ranges illegal, as with this patch
(2) make large ranges legal, but don't allow indexing with indices
larger than PY_SSIZE_T_MAX.
(3) allow large ranges *and* large indices.

Option 3 seems to me like the ideal from the users' point of view, but I'm
not sure whether it's easy/possible to implement it given that sq_item
receives a Py_ssize_t for the index.

Option 2 seems messy: half of one thing and half of the other, but I
think it would be easy to implement. This is what I'd personally prefer
if Option 3 isn't feasible.

If Option 1 is indeed the preferred option, then the patch looks good to
me, and works for me on OS X 10.5. (Minor nitpick: it introduces some
extra tab characters.)

Whatever happens, we probably also need a documentation update explaining
the limitations on range.

[abalkin]

Option (3) would require changing both sq_item and sq_length signatures,
which is likely to have a large negative impact on performance.

Option (2) would either require a change for the sq_length signature, or
leave the problem of having valid range objects for which applying len()
would produce an OverflowError.

What are the use cases for ranges with length greater than maxsize? Note
that in 2.x all arguments to length are limited to 32 bit integers (even
on 64-bit platforms) and the main reason to support long start/stop/step
in 3.0 is because 2.x range() supports them. On the other hand, since
2.x range() produces lists, it is limited in length to a fraction of
sys.maxsize. Therefore none of the current uses of either range or
xrange require support of long length.

[amauryfa]

I am currently working on a patch that allows large ranges and large
indices. The trick is to define tp_as_mapping->mp_subscript.
Then range_item() is rarely used, only by functions calling directly the
PySequence_* functions, instead of the abstract PyObject_*.

There is still a limit with len(), which seems bound by the size_t limit.
Most of the tests in test_builtin were re-enabled.

I join the current version of the patch.
I'm still working on further simplifications, and maybe supporting
slices on ranges...

Note: I found more useful to store a "range->end" member, which is the
multiple of "step" just beyond the "stop" limit.

[mdickinson]

What are the use cases for ranges with length greater than maxsize?

Yeah---I'm a bit short on use cases. The one that originally bit me with
Python 2.x was when I was doing a search for a quadratic non-residue
modulo a largeish prime;

for i in range(1, p):
    if (i_is_a_nonresidue_modulo_p):
        break

Here p might be a 200-digit prime number, and the situation is that half
the integers between 1 and p-1 are 'quadratic residues', while the other
half are 'quadratic nonresidues'; in practice the residues and
nonresidues are mixed up fairly well, so the first nonresidue shows up
pretty quickly, but there's no known small upper bound on when the first
nonresidue appears.

Of course, it's not hard to rewrite this with a while loop instead; it
would just be a bit annoying if that were necessary, when the code above
is so clear and direct, and the one obvious way to do it (TM).

I'd also note that it's not completely out of the question that something
like range(10**10) would be useful on a 32-bit machine: a long-running
process might easily go through 10**10 iterations of something.

I agree it's a bit strange to have a semi-functional range object, that
you can iterate over but not take the length of.

[abalkin]

On Fri, Apr 25, 2008 at 4:37 PM, Mark Dickinson <report@bugs.python.org> wrote:
..

for i in range(1, p):
if (i_is_a_nonresidue_modulo_p):
break

Here p might be a 200-digit prime number, and the situation is that half
the integers between 1 and p-1 are 'quadratic residues', while the other
half are 'quadratic nonresidues'; in practice the residues and
nonresidues are mixed up fairly well, so the first nonresidue shows up
pretty quickly, but there's no known small upper bound on when the first
nonresidue appears.

Hmm, AFAIKT there is always at least one non-residue between 1 and p
and therefore you can just write

for i in itertools.count(1):
    if (i_is_a_nonresidue_modulo_p):
         break

maybe with an additional check for p > 1.

[mdickinson]

Hmm, AFAIKT there is always at least one non-residue between 1 and p
and therefore you can just write

for i in itertools.count(1):
if (i_is_a_nonresidue_modulo_p):
break

maybe with an additional check for p > 1.

Sure. It's just uglier that way. :-) And I feel it would be mildly
annoying not to be able to use the obvious tool for the job, for subtle
reasons. It's also a potential source of bugs: one might write such code
using range and only discover later that it fails unexpectedly for large
inputs.

These really aren't serious objections---just mild preferences. I'll stop
being disruptive now :)

[ncoghlan]

Given that range() produced a list in the 2.x series (hence limited to
available memory), and xrange() uses int internally for its values (and
hence couldn't even cope with short ranges with values greater than
sys.maxint).

So my preference is to mimic the 2.x range's behaviour in this case by
raising an overflow error if the sequence is too long.

(From Python 2.5.1)

>>> range(2**99, 2**100)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
OverflowError: range() result has too many items
>>> range(2**99, 2**99+5)
[633825300114114700748351602688L, 633825300114114700748351602689L,
633825300114114700748351602690L, 633825300114114700748351602691L,
633825300114114700748351602692L]
>>> xrange(2**99, 2**99+5)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
OverflowError: long int too large to convert to int

[abalkin]

I've implemented range slicing and x in range(..) in range-sequence.diff
and registered range with the Sequence ABC.

[abalkin]

Reviewing my own patch (range-sequence.diff), I've realized that it is
being a bit too clever in handling x in range(..) where x is not an
integer. It seems that upon a failed PyLong_Check, range_contains should
just do a linear search. This is easy to implement, but I will wait for
more feedback before posting further changes.

[facundobatista]

My 2 cents: for me is more useful to have a unbound range() than to be
able to do a len() on it.

For me, range() should mimic a number generator: no limit, no length.