A simple question

While I was teaching a class about iterators and generators, a student asked me a question that didn't seem so interesting at first. "What is faster - xrange or range?". I tried to explain to him that in many cases it's better to use xrange instead of range - but because of the lower memory usage, and not because of run time. He continued: "Yes, I get it. But which one is faster?".
Well, it's pretty obvious that building a list with range takes more time than calling xrange - since when calling xrange, no real list is built. So to phrase it more precisely, the question is:
What is faster - calling next of an iterator over a list object, or calling next of an iterator of an xrange object?

A simple answer?

I had to think about it for a bit. Before looking at the documentation or source code, I tried to think what is my intuition about it.
Both operations suppose to be pretty fast, compared to other basic operations (like building a list with range).

• Getting the next object in a list is basically accessing an array in some specific index (and increasing that index)
• Getting the next object of a xrange object is basically increasing some number, and returning it. Again, a very simple operation.

So what is faster? Direct memory access or a simple addition?
I thought that maybe the addition (xrange) would be a bit faster, but not by much.

RTFM

What does the documentation of xrange have to say about it?
Well, according to Docstring of xrange, it is slightly faster than range:

In [1]: xrange?
Docstring:
xrange(stop) -> xrange object
xrange(start, stop[, step]) -> xrange object


Like range(), but instead of returning a list, returns an object that
generates the numbers in the range on demand.  For looping, this is
slightly faster than range() and more memory efficient.

But the Docstring doesn't say exactly what is faster about range. So we have to guess that they are addressing calling the next method (iterating over the xrange)

But, the "formal" documentation of python, doesn't say anything explicitly about the speed of xrange:

xrange(stop)
xrange(start, stop[, step])
This function is very similar to range(), but returns an xrange object instead of a list. This is an opaque sequence type which yields the same values as the corresponding list, without actually storing them all simultaneously. The advantage of xrange() over range() is minimal (since xrange() still has to create the values when asked for them) except when a very large range is used on a memory-starved machine or when all of the range’s elements are never used (such as when the loop is usually terminated with break). For more information on xrange objects, see XRange Type and Sequence Types — str, unicode, list, tuple, bytearray, buffer, xrange.

You can see that documentation here - https://docs.python.org/2/library/functions.html#xrange

Run it!

One of the many things I like about Python is that it is really easy to try things out. If you want to know what is faster, just run the code, and see what is faster!
We want to eliminate the time building the list with range and focus just on the iteration itself.
ipython has a very nice feature for checking the run time of methods - %timeit. We can use it with next of list iterator / xrange iterator and see which one is faster.
We will use a list /xrange of size 10,000,000 for the test. We will also need to limit the number of tests that %timeit performs, so we won't hit StopIteration exception (the end of the list / xrange).
Here are the results:

In [4]: list_iterator = iter(range(10 ** 7))

In [5]: %timeit -n 1000000 list_iterator.next()
1000000 loops, best of 3: 68.7 ns per loop

In [6]: xrange_iterator = iter(xrange(10 ** 7))

In [7]: %timeit -n 1000000 xrange_iterator.next()
1000000 loops, best of 3: 65.9 ns per loop

Seems a bit faster, right? By about 5%
But the results are not so consistent:

In [8]: xrange_iterator = iter(xrange(10 ** 7))

In [9]: %timeit -n 1000000 xrange_iterator.next()
1000000 loops, best of 3: 71.6 ns per loop

Sometimes the xrange is slower!
The source of differences is probably my running environment (a pretty old Ubuntu 14.04 VM, with just 1GB of memory and a single CPU).
The important part is that it doesn't seem like there is a big different between the speed of xrange and range in Python 2.7.

What about Python 3?

Well, in Python 3 xranges were removed completely from the language. Now range objects behave like the old and beloved xranges, and they return an object which you can iterate on - but which is not a list.
So you would think that the new range objects will be faster than the old xrange objects, right?
Let's check it out.
Remember that .next was also removed from Python 3, and now we need to call next(iterator) instead of iterator.next().

In [1]: range_iterator = iter(range(10 ** 7))

In [2]: %timeit -n 1000000 next(range_iterator)
111 ns ± 7.63 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

That's above 110 ns for an operation, instead of ~70 ns in Python 2!
And as with Python 2, it seems that iterating over lists takes similar time:

In [3]: list_iterator = iter(list(range(10 ** 7)))

In [4]: %timeit -n 1000000 next(list_iterator)
95.7 ns ± 7.13 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

It's even a bit faster then xrange, but still - it's 50% slower than iteration in Python 2.

This is actually a known phenomenon with Python 3.
You can read some possible explanation for it here - https://stackoverflow.com/questions/23453133/is-there-a-reason-python-3-enumerates-slower-than-python-2
(though, In my opinion, this answer doesn't seem correct - since we use only small numbers - lower than sys.maxint)

High numbers

The answer in the above stack overflow link made me wonder - what will happen with very high numbers? Would range and list(range) still have similar speeds?
My intuition said that the results will be similar to the results we saw before - around 100 ns for each call to next.
But again - the best way to find things out is to try!
So let's check it:

In [2]: list_iterator_high_numbers = iter(list(range(2 ** 64, 2 ** 64 + 10 ** 7)))

In [3]: %timeit -n 1000000 next(list_iterator_high_numbers)
97 ns ± 12.1 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)