Hacker News Reader

Comment by kgm | Hacker News Reader

To be pedantic (which I think is warranted here), range does not return a generator, it returns a sequence called a range object. This object can be indexed, sliced, and (relevant to this discussion) supports the 'in' operator.

"x in range(10)" will operate in constant time and memory in Python 3. Whether it is actually more efficient than "0 <= x < 10" is another matter, of course. I would expect the call to range() to dominate here, and indeed, it is much slower in this microbenchmark:

  $ python3 -m timeit -s 'x = 8' 'x in range(10)'
  1000000 loops, best of 3: 0.351 usec per loop
  $ python3 -m timeit -s 'x = 8' '0 <= x < 10'
  10000000 loops, best of 3: 0.0732 usec per loop

Even aside from this, I find the "0 <= x < 10" syntax to be clearer.

View on HN

I'm certain that the call to range is significant there, but if you think of how this actually plays out, it may be doing a naive list compare. if a compare operation is your limiting operation, then the former has to do nine operations (Is x == 0? Is x == 1? ... Is x == 8?) vs precisely two in the latter (is x >= 0? Is x < 10?). The math on that is pretty close - 2/9ths of 0.351 is 0.078, quite close to your result.

From a formal CS perspective, that's why this is wrong; It's because 'in' is an o(n) operation, while the two comparisons are constant time. It may be abstracted away by the range object overloading, but that's a fairly narrow optimization it's able to pull off.

On modern CPUS, branching operations like compare usually are your problem; An unconditional function call is easy to optimize, but a branch in a looping construct is guaranteed to lead to one or more mispredictions. Trying to minimize the surface area of comparisons is an important part of performant code.

Mainly, the call to range() has to construct something that it returns, that means allocating memory, which is probably going to dwarf any other code involved in this. (In case of range(1,5) I tend to assume that constructing [1,2,3,4] is probably marginally faster than constructing rangeobject)

Also, as noted in other comments, range object has special cased O(1) implementation of in for integers (range_contains_long() in Objects/rangeobject.c)

CPython bytecode interpreter tries to minimize amount of branching it causes by using some non-obvious tricks, but still by definition it is going to cause at least one essentially unpredictable branch per interpreted instruction, so optimizing for number of branches in user python code is mostly pointless endeavor.

To question your assessment I tested it on my own machine:

  python3 -m timeit -s 'x = 8' 'x in range(1000)'
  1000000 loops, best of 3: 0.405 usec per loop
  python3 -m timeit -s 'x = 8' '0 <= x < 1000'
  10000000 loops, best of 3: 0.0742 usec per loop
  python3 -m timeit -s 'x = 8' 'x in range(100000)'
  1000000 loops, best of 3: 0.405 usec per loop
  python3 -m timeit -s 'x = 1123' 'x in range(100000)'
  1000000 loops, best of 3: 0.415 usec per loop
  python3 -m timeit -s 'x = 1123' '0 <= x < 100000'
  10000000 loops, best of 3: 0.0745 usec per loop

While 0<=x<10 seems to be 5 times faster, both seem to be independent of the actual chosen values.

Reply on news.ycombinator.com