xrange vs. range vs. range

Guy Goldberg — Fri, 19 Jan 2018 13:01:21 +0000

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)

As we can see, the result for lists is very similar to the results before. No surprise here.

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

In [5]: %timeit -n 1000000 next(range_iterator_high_numbers)
204 ns ± 9.15 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

Now, this is a surprise! Iterating on high numbers with range is much slower than iterating over low numbers. Calling next takes on average 100% more time!

Why does that happen?
I couldn't find any hint in the documentation, so I had to take the next step and

Read the source code

Another great thing about Python is that you can just simply read its source code. If you want to understand something more thoroughly, or if you are just a bit curious, you can read the code itself!
The relevant module we want to look at is Objects/rangeobject.c, which contains the implementation of range objects in Python 3.
You can find it here - https://github.com/python/cpython/blob/master/Objects/rangeobject.c
It's pretty easy to find the code of the "next" method, which is the method we are interested in:

The code is pretty straight-forward. If the range didn't reach its end yet, increase the index by one, multiply it by "step", add to "start" and return the value as a Python long object. (The casting issue is not relevant to us now).
It seems like an efficient code. Why is it less efficient for high numbers?
But wait a second. It doesn't work for numbers which are "longer" than long at all!
We just saw that range does support very high numbers, with more than 64 bits. long variables in C can only store numbers with up to 32 (or 64) bits. There must be some other code that handles the higher numbers.
Well, in my first look I missed the comment just above that method:

it clearly says that there's one implementation for C longs (the one that we just saw) and another implementation for Python ints.
That method appears ~250 lines later:

Look at all that code.
Instead of 3-4 basic arithmetic operations that we saw in rangeiter_next, here at longrangeiter_next there are much more complicated operations. You can't simply use "+" to add Python ints - you have to use PyNumber_Add. You can't use "*" to multiply the "index" and "step" - you have to use PyNumber_Multiple.
No wonder that calling next takes more time for "longer than long" numbers - much more things are happening under the hood.
But for the next method of regular lists, it doesn't matter what the values inside the list are - you don't need to do any "complicated" arithmetic operations like multiplying Python ints to get an item from a list.

Final words

So, what did we see here?
We started with a simple question - what is faster, xrange or range? and we saw that the answer is not so obvious.
We continued by comparing the speed of Python 2 and Python 3, and we were surprised to see that Python 3 is a bit slower in that area.
Then we looked at ranges with high numbers and saw that they are much slower than "lower" ranges. We had to explore the Python source code to find out the reason for that.

That's all for this post, I hope you enjoyed it.

5 Tips for interviewers

Guy Goldberg — Fri, 17 Nov 2017 12:50:00 +0000

Interviewing someone for your company is not an easy job. Sometimes you have to do it without any training. If you're lucky, in the first few interviews you will join someone experienced who will lead the interview. If you take your job seriously, you might want to read some tips and guidelines on how to conduct a great interview.
After conducting hundreds of interviews, for various positions (Researchers, Developers, Team leaders and QA engineers), I collected the 5 most important tips, in my opinion, which might help you for any kind of interview.

1. Ask "Can you give me an example?"

When the interviewee is saying something like "I was in charge of testing feature X", or "I developed many features", always ask him to give concrete examples. You will be amazed how people can talk with extreme confidence about things they did in a very general way, but once you ask them to give examples - you'll find out they don't really understand what they did.

2. Ask "What was your role in that project"?

This is quite similar to the previous tip. Candidates sometimes describe really big projects, which seem impressive. In those cases, it's important to check what they actually did on that project. More often than not, you'll find out that the role the candidate had in the project is smaller than it seemed at first.

3. Try to make the candidate talk while he is thinking

The number 1 tip that I give to candidates is to always talk while you think. In this way, the interviewer can understand better your thinking processes and might help you if you are not in the correct direction. From the interviewer perspective, many candidates don't follow that tip, and it is hard to know what they think. Simply ask them to talk and explain what they are thinking about. Even if they have ideas that they think are "bad", ask them to explain them. Sometimes they hit the correct solution to the question, but just don't say it to you since they think that there's some mistake in it. As an interviewer, you want to know that they found the solution, even if they didn't think it is correct.

4. Ask "Can you explain me an interesting bug that you encountered?"

This is my favorite interview question. It gives you an opportunity to see how good the candidate can explain something technical, and how deep he understands technical issues. It also helps you to see if the candidate can identify what was important and what wasn't.

5. Don't have small-talks with your co-interviewer

The interviewee is under a lot of stress and is trying to think. Yes, you might be bored, and yes, it is much more interesting to talk about what to eat for lunch than look at someone you don't know trying to solve a question you know. But you should respect the candidate, and you shouldn't disturb him

What do you think about the tips in this article? Do you have any other tips for someone who begins to interview? Let me know if the article was useful to someone.

DEV Community: Guy Goldberg