range() vs xrange() Python2|3 issues for performance

[Steven D'Aprano]

harrismh777 wrote:

> The following is intended as a helpful small extension to the xrange()
> range() discussion brought up this past weekend by Billy Mays...
> 
> With Python2 you basically have two ways to get a range of numbers:
>     range() , which returns a list,  and
>    xrange() , which returns an iterator.


xrange does not return an iterator. It returns a lazy iterable object, which
is not the same thing.

In Python, "iterator" is not merely a generic term for something which can
be iterated over. An iterator is an object which obeys the iterator
protocol, which depends on at least two properties:

* the object must have a next() method, which returns values until the
iterator is exhausted, and then raises StopIteration;

(In Python 3, the method is __next__.)

* and the object must have an __iter__() method which returns itself.

(Also, "non-broken" iterators will continue to raise StopIteration once they
do so once. That is, they can't be reset or repeated.)

xrange objects fail on both accounts. (Likewise for range objects in Python
3.)


[...]
>     These are coded with range().  The interesting thing to note is that
> xrange() on Python2 runs "considerably" faster than the same code using
> range() on Python3. For large perfect numbers (above 8128) the
> performance difference for perf() is orders of magnitude. Actually,
> range() on Python2 runs somewhat slower than xrange() on Python2, but
> things are much worse on Python3.

I find these results surprising, at least for numbers as small as 8128, and
suspect your timing code is inaccurate.

(But don't make the mistake of doing what I did, which was to attempt to
produce range(290000000) in Python 2. After multiple *hours* of swapping, I
was finally able to kill the Python process and get control of my PC again.
Sigh.)

I would expect that, in general, Python 3.1 or 3.2 is slightly slower than
Python 2.6 or 2.7. (If you're using Python 3.0, stop now!) But in Python 2,
I wouldn't expect orders of magnitude difference in range and xrange. Using
the function perf(N) you gave, and a modified copy perfx(N) which simply
replaces xrange for range, I get these timings in Python2.6:

>>> from timeit import Timer
>>> t1 = Timer('perf(10000)', 'from __main__ import perf')
>>> t2 = Timer('perfx(10000)', 'from __main__ import perfx')
>>> min(t1.repeat(number=1000, repeat=5))
3.0614659786224365
>>> min(t2.repeat(number=1000, repeat=5))
2.8787298202514648

A small difference, but not an order of magnitude. In Python 3.1, I get
this:

>>> min(t1.repeat(number=1000, repeat=5))
3.4577009677886963


>     This is something I never thought to test before Billy's question,
> because I had already decided to work in C for most of my integer
> stuff... like perfects. But now that it sparked my interest, I'm
> wondering if there might be some focus placed on range() performance in
> Python3 for the future, PEP?

Oh indubitably. I doubt it will need a PEP. Python 3.x is still quite young,
and the focus is on improving unicode support, but performance improvements
will usually be welcome.

However, at some point I would expect adding hand-crafted optimizations to
CPython will cease to be worthwhile. Guido is already talking about CPython
becoming the reference implementation, and PyPy the production
implementation because it's faster. PyPy's optimizing compiler is already
about twice as fast as CPython, and for at least one specially crafted
example, faster than C:

http://morepypy.blogspot.com/2011/02/pypy-faster-than-c-on-carefully-crafted.html



-- 
Steven