[issue2690] Precompute range length and enhance range subscript support
Daniel Stutzbach stutzb...@google.com added the comment: Doc change committed to py3k in r87346. Thanks, SilentGhost! I also committed r87349 to reverse r87162 (which was in the wrong branch). -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue2690 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2690] Precompute range length and enhance range subscript support
SilentGhost michael.mischurow+...@gmail.com added the comment: here is the patch for the py3k docs. -- Added file: http://bugs.python.org/file20021/stdtypes.rst.diff ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue2690 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2690] Precompute range length and enhance range subscript support
SilentGhost michael.mischurow+...@gmail.com added the comment: Not sure this worth a patch, to me it looks like a removal of a single word. But here it goes anyway. -- nosy: +SilentGhost Added file: http://bugs.python.org/file20003/stdtypes.rst.diff ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue2690 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2690] Precompute range length and enhance range subscript support
Raymond Hettinger rhettin...@users.sourceforge.net added the comment: Applied in r87162 -- status: open - closed ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue2690 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2690] Precompute range length and enhance range subscript support
Nick Coghlan ncogh...@gmail.com added the comment: The other major change for ranges is that in and not in are no longer inefficient for actual instances of int (it does an arithmetic calculation instead of a linear search). -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue2690 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2690] Precompute range length and enhance range subscript support
Raymond Hettinger rhettin...@users.sourceforge.net added the comment: Is the in/not-in fast path in 2.7? -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue2690 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2690] Precompute range length and enhance range subscript support
Nick Coghlan ncogh...@gmail.com added the comment: No, I believe it was added as part of the .index() and .count() implementation. Checking the source, there's definitely no sq_contains implementation in 3.1 or 2.7. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue2690 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2690] Precompute range length and enhance range subscript support
Nick Coghlan ncogh...@gmail.com added the comment: I brought the patch up to date for the Py3k branch, but realised just before checking it in that it may run afoul of the language moratorium (since it alters the behaviour of builtin range objects). However, the .count() and .index() methods (along with the Sequence ABC registration) as well as the O(1) containment testing for integers were already put in place. (I also noticed that the new methods from issue #9213 are not mentioned in the range() docs, unlike the O(1) optimisation) I've gone ahead and checked it in as r86970, as I see this patch as filling out the promise of the Sequence ABC registration by adding support for slicing and negative indices (with the length caching as more of an implementation detail). However, I'm also leaving the tracker issue open and assigning to Georg in case he wants to revert it before the beta goes out. Note that I also fixed the patch so that OverflowError occurs only when encountering an affected operation (primarily indexing and retrieval of the length). If you don't do any of those things, you can make your ranges as large as you like. (The indexing could fairly easily be fixed to eliminate the overflow errors - I just didn't do it in this patch, since it is a separate problem). -- assignee: - georg.brandl nosy: +georg.brandl resolution: - accepted stage: patch review - committed/rejected title: Precompute range length - Precompute range length and enhance range subscript support Added file: http://bugs.python.org/file19926/issue2690_lazy_overflow_check.diff ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue2690 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2690] Precompute range length and enhance range subscript support
Daniel Stutzbach stutzb...@google.com added the comment: (I also noticed that the new methods from issue #9213 are not mentioned in the range() docs Wasn't that fixed in Issue9746? -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue2690 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2690] Precompute range length and enhance range subscript support
Nick Coghlan ncogh...@gmail.com added the comment: On Sat, Dec 4, 2010 at 2:26 AM, Daniel Stutzbach rep...@bugs.python.org wrote: Daniel Stutzbach stutzb...@google.com added the comment: (I also noticed that the new methods from issue #9213 are not mentioned in the range() docs Wasn't that fixed in Issue9746? Ah, I see what you mean. I was more referring to the lack of a versionchanged note on the range() documentation itself, rather than the mentioning of range() under the sequence types documentation. Some of my new additions to the range documentation could probably be deleted and replaced with a reference to that part of the docs. Cheers, Nick. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue2690 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2690] Precompute range length and enhance range subscript support
Nick Coghlan ncogh...@gmail.com added the comment: Daniel Stutzbach pointed out that range() is also mentioned under: http://docs.python.org/dev/library/stdtypes.html#sequence-types-str-bytes-bytearray-list-tuple-range The descriptions of range's limitations there is no longer accurate (slicing is supported following this patch and containment testing is now efficient) -- assignee: georg.brandl - status: open - closed ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue2690 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2690] Precompute range length and enhance range subscript support
Daniel Stutzbach stutzb...@google.com added the comment: The descriptions of range's limitations there is no longer accurate (slicing is supported following this patch and containment testing is now efficient) Want to open a new issue for that? (or is there one already?) -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue2690 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2690] Precompute range length and enhance range subscript support
Nick Coghlan ncogh...@gmail.com added the comment: (Oops, didn't mean to reclose this yet) I want to wait for Georg's verdict on including the functionality in 3.2 before stressing too much about correct documentation of it :) -- assignee: - georg.brandl status: closed - open ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue2690 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2690] Precompute range length and enhance range subscript support
Georg Brandl ge...@python.org added the comment: I'm fine with it: as with the other changes for .count and .index, consistency with the protocols/ABCs the types are members of is not exclusively a new feature. -- status: open - closed ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue2690 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2690] Precompute range length and enhance range subscript support
Daniel Stutzbach stutzb...@google.com added the comment: The descriptions of range's limitations in the docs still needs an update. -- assignee: georg.brandl - ncoghlan status: closed - open ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue2690 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2690] Precompute range length
Nick Coghlan ncogh...@gmail.com added the comment: I'd still like to have another look at this before beta 1, but can't promise I'll get to it. Unassigning in case someone else has some roundtuits to spare over the next few weeks. -- assignee: ncoghlan - ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue2690 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2690] Precompute range length
Changes by Daniel Stutzbach dan...@stutzbachenterprises.com: -- nosy: +stutzbach ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue2690 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2690] Precompute range length
Changes by Guido van Rossum gu...@python.org: -- nosy: -gvanrossum ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue2690 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2690] Precompute range length
Changes by Nick Coghlan ncogh...@gmail.com: -- assignee: - ncoghlan ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue2690 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2690] Precompute range length
Mark Lawrence breamore...@yahoo.co.uk added the comment: @Nick, would you have time to work on this for 3.2, or should we target 3.3, or could somebody else take this over? -- nosy: +BreamoreBoy ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue2690 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2690] Precompute range length
Changes by Raymond Hettinger rhettin...@users.sourceforge.net: -- assignee: rhettinger - ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue2690 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2690] Precompute range length
Changes by Daniel Diniz aja...@gmail.com: -- stage: - patch review versions: +Python 3.2 -Python 3.1 ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue2690 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2690] Precompute range length
Changes by Raymond Hettinger rhettin...@users.sourceforge.net: -- assignee: - rhettinger nosy: +rhettinger ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue2690 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2690] Precompute range length
Nick Coghlan [EMAIL PROTECTED] added the comment: This issue was missing a priority setting. Alexander's range-sequence patch still applies cleanly to the Py3k branch, and make test still runs correctly after applying it. As Alexander notes above, range_contains does still need slightly better handling of non-integer numbers - I suggest doing a numeric conversion via PyNumber_Index(el) at the beginning of range_contains, and if that conversion fails, do a conversion via PyNumber_Long(el) and immediately return False if the result is not equal to el itself (i.e. only integer values of non-integer types will be found in the range. Since that explanation got kind of complicated, I've added a modified patch that includes the above change, and adds a couple of additional tests to ensure a non-integer floating point value won't be found in the sequence. -- keywords: +needs review priority: - release blocker Added file: http://bugs.python.org/file11345/issue2690-range-sequence-ncoghlan.diff ___ Python tracker [EMAIL PROTECTED] http://bugs.python.org/issue2690 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2690] Precompute range length
Antoine Pitrou [EMAIL PROTECTED] added the comment: It looks like your range_subscript() forgets to compute the length field... ___ Python tracker [EMAIL PROTECTED] http://bugs.python.org/issue2690 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2690] Precompute range length
Changes by Nick Coghlan [EMAIL PROTECTED]: Removed file: http://bugs.python.org/file11345/issue2690-range-sequence-ncoghlan.diff ___ Python tracker [EMAIL PROTECTED] http://bugs.python.org/issue2690 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2690] Precompute range length
Nick Coghlan [EMAIL PROTECTED] added the comment: My initial patch had a few problems - I removed it and uploaded a corrected version. Added file: http://bugs.python.org/file11346/issue2690-range-sequence-ncoghlan.diff ___ Python tracker [EMAIL PROTECTED] http://bugs.python.org/issue2690 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2690] Precompute range length
Nick Coghlan [EMAIL PROTECTED] added the comment: Good catch Antoine (I missed that in Alexander's patch) - working on that now. ___ Python tracker [EMAIL PROTECTED] http://bugs.python.org/issue2690 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2690] Precompute range length
Nick Coghlan [EMAIL PROTECTED] added the comment: v2 of my updated patch attached to fix the issue Antoine noted. Also gets rid of some tab-instead-of-spaces indenting issues in the file, and avoids hardcoding PyRange_Type when creating new instances. However, the patch still has issues, as can be seen with the new tests I added to test_range to actually exercise some of the functionality beyond the sys.maxsize limit. Added file: http://bugs.python.org/file11348/issue2690-range-sequence-ncoghlan-v2.diff ___ Python tracker [EMAIL PROTECTED] http://bugs.python.org/issue2690 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2690] Precompute range length
Antoine Pitrou [EMAIL PROTECTED] added the comment: By the way, why is this release blocker? do we have performance numbers? ___ Python tracker [EMAIL PROTECTED] http://bugs.python.org/issue2690 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2690] Precompute range length
Guido van Rossum [EMAIL PROTECTED] added the comment: I wonder if we shouldn't hold off on this. It's a substantial amount of new code. I'd be fine with it going into 3.0.1 since it's pure optimization (IIUC!). But right now we want burn-in, not new features. ___ Python tracker [EMAIL PROTECTED] http://bugs.python.org/issue2690 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2690] Precompute range length
Nick Coghlan [EMAIL PROTECTED] added the comment: Given the problems with it, I'm dropping this to normal priority and punting to 3.1. (the release blocker status was just temporary to ensure we got a decision on it before rc1 - it previously didn't have a priority set) -- keywords: -needs review priority: release blocker - normal versions: +Python 3.1 -Python 3.0 ___ Python tracker [EMAIL PROTECTED] http://bugs.python.org/issue2690 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2690] Precompute range length
Nick Coghlan [EMAIL PROTECTED] added the comment: Guido, does that mean we can apply this patch to get the cleaner list-like behaviour for 3.0, and then work on the sq_item/sq_len fixes for 3.1 as a separate issue? ___ Python tracker [EMAIL PROTECTED] http://bugs.python.org/issue2690 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2690] Precompute range length
Guido van Rossum [EMAIL PROTECTED] added the comment: On the issue of whether len(range()) should be allowed to be sys.maxsize, I think this should be allowed. I think in the future we should change the __len__ protocol to allow unbounded lengths. Even today, I think range(10**100).__len__() should return 10**100 rather than raising an OverflowError, even if len(range(10**100)) raises OverflowError. I also think ranges should be introspectable, exposing their start, stop and step values just like slice objects. Probably all those changes are for post 3.0. -- nosy: +gvanrossum ___ Python tracker [EMAIL PROTECTED] http://bugs.python.org/issue2690 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2690] Precompute range length
Antoine Pitrou [EMAIL PROTECTED] added the comment: Has a resolution been made on this? -- nosy: +pitrou ___ Python tracker [EMAIL PROTECTED] http://bugs.python.org/issue2690 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2690] Precompute range length
Nick Coghlan [EMAIL PROTECTED] added the comment: It also isn't what range() and xrange() are used for now in 2.x. range() returns an actual list, hence is limited to sequences that fit in a reasonable amount of memory, and xrange() doesn't support values greater than sys.maxint at all (as it uses C ints for its internal storage of the start, stop and step values). With itertools.count() available for the unbounded iterator case, I think making range() mimic its 2.x counterpart as closely as possible (without the memory inefficiency) will be quite valuable. __ Tracker [EMAIL PROTECTED] http://bugs.python.org/issue2690 __ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2690] Precompute range length
Facundo Batista [EMAIL PROTECTED] added the comment: Fair enough, specially if in the documentation of range() we put if you want a unbound, no limit, number generator, use itertools.count() (or something well written in english ;) ). Thanks! __ Tracker [EMAIL PROTECTED] http://bugs.python.org/issue2690 __ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2690] Precompute range length
Alexander Belopolsky [EMAIL PROTECTED] added the comment: I've implemented range slicing and x in range(..) in range-sequence.diff and registered range with the Sequence ABC. Added file: http://bugs.python.org/file10131/range-sequence.diff __ Tracker [EMAIL PROTECTED] http://bugs.python.org/issue2690 __ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2690] Precompute range length
Alexander Belopolsky [EMAIL PROTECTED] added the comment: 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. __ Tracker [EMAIL PROTECTED] http://bugs.python.org/issue2690 __ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2690] Precompute range length
Facundo Batista [EMAIL PROTECTED] added the comment: 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. -- nosy: +facundobatista __ Tracker [EMAIL PROTECTED] http://bugs.python.org/issue2690 __ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2690] Precompute range length
Alexander Belopolsky [EMAIL PROTECTED] added the comment: For me, range() should mimic a number generator: no limit, no length. That's itertools.count() __ Tracker [EMAIL PROTECTED] http://bugs.python.org/issue2690 __ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2690] Precompute range length
Nick Coghlan [EMAIL PROTECTED] added the comment: 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 -- nosy: +ncoghlan __ Tracker [EMAIL PROTECTED] http://bugs.python.org/issue2690 __ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2690] Precompute range length
New submission from Alexander Belopolsky [EMAIL PROTECTED]: 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 . -- components: Interpreter Core files: range-length.diff keywords: patch messages: 65786 nosy: belopolsky severity: normal status: open title: Precompute range length type: performance versions: Python 3.0 Added file: http://bugs.python.org/file10107/range-length.diff __ Tracker [EMAIL PROTECTED] http://bugs.python.org/issue2690 __ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2690] Precompute range length
Mark Dickinson [EMAIL PROTECTED] added the comment: 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 -- nosy: +marketdickinson __ Tracker [EMAIL PROTECTED] http://bugs.python.org/issue2690 __ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2690] Precompute range length
Alexander Belopolsky [EMAIL PROTECTED] added the comment: On Fri, Apr 25, 2008 at 12:55 PM, Mark Dickinson [EMAIL PROTECTED] 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(). __ Tracker [EMAIL PROTECTED] http://bugs.python.org/issue2690 __ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2690] Precompute range length
Mark Dickinson [EMAIL PROTECTED] added the comment: 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. __ Tracker [EMAIL PROTECTED] http://bugs.python.org/issue2690 __ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2690] Precompute range length
Alexander Belopolsky [EMAIL PROTECTED] added the comment: 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. __ Tracker [EMAIL PROTECTED] http://bugs.python.org/issue2690 __ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2690] Precompute range length
Amaury Forgeot d'Arc [EMAIL PROTECTED] added the comment: 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. -- nosy: +amaury.forgeotdarc Added file: http://bugs.python.org/file10109/anyrange.patch __ Tracker [EMAIL PROTECTED] http://bugs.python.org/issue2690 __ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2690] Precompute range length
Mark Dickinson [EMAIL PROTECTED] added the comment: 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. __ Tracker [EMAIL PROTECTED] http://bugs.python.org/issue2690 __ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2690] Precompute range length
Alexander Belopolsky [EMAIL PROTECTED] added the comment: On Fri, Apr 25, 2008 at 4:37 PM, Mark Dickinson [EMAIL PROTECTED] 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. __ Tracker [EMAIL PROTECTED] http://bugs.python.org/issue2690 __ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue2690] Precompute range length
Mark Dickinson [EMAIL PROTECTED] added the comment: 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 :) __ Tracker [EMAIL PROTECTED] http://bugs.python.org/issue2690 __ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
