python3 performance: loop using range() Vs plain old while()

Question

In Python3, I find that if I replace a

for i in range(n):

statement with

while i < n:

I get significant runtime gains. My loop itself is not meaty where it does couple of basic arithmetic operations.

Any pointers to why I am seeing this behavior?

Edit: n is ranging in 10s of K, 10K, 12K etc Timing I observe is .19s for 12K, .12s for 10K with while loop. Whereas with 'while' loop, i see .11s for 12K, .08s for 10K. Here is my program:

target = 0
i = 1
#for i in range(1, n+1):
while i < n+1:
    target += i * (2 ** (i - 1)) + (i * (i + 1))//2
    i += 1

return target % (10 ** 9 + 7)

How big is n? range has some fixed overhead to create, and might lose if n is small. — ShadowRanger
– ShadowRanger, Commented Dec 24, 2018 at 21:59
please provide a minimal reproducible example. Generally, looping directly over a range iterable will be faster than manually += some i. Depends on the scope of your problem, and what exactly you are doing with i I suppose — juanpa.arrivillaga
– juanpa.arrivillaga, Commented Dec 24, 2018 at 22:02

ShadowRanger · Accepted Answer · 2018-12-24 22:03:52Z

4

range involves a small amount of fixed overhead (to look up range, first in the globals, then in the built-ins, then the cost of generic function call dispatch, and allocating/initializing the object); if n is sufficiently small, it won't be made up on the reduced per loop cost:

In [1]: %%timeit -r5 n = 3
   ...: for i in range(n):
   ...:     pass
   ...:
365 ns ± 15.1 ns per loop (mean ± std. dev. of 5 runs, 1000000 loops each)

In [2]: %%timeit -r5 n = 3
   ...: i = 0
   ...: while i < n:
   ...:     i += 1
   ...:
252 ns ± 16.9 ns per loop (mean ± std. dev. of 5 runs, 1000000 loops each)

But when n gets to even moderate size, the reduced overhead per item pays off:

In [3]: %%timeit -r5 n = 10
   ...: for i in range(n):
   ...:     pass
   ...:
461 ns ± 18.1 ns per loop (mean ± std. dev. of 5 runs, 1000000 loops each)

In [4]: %%timeit -r5 n = 10
   ...: i = 0
   ...: while i < n:
   ...:     i += 1
   ...:
788 ns ± 73.6 ns per loop (mean ± std. dev. of 5 runs, 1000000 loops each)

range involves higher fixed costs, but lower per-item costs, that's all.

answered Dec 24, 2018 at 22:03

ShadowRanger

158k12 gold badges221 silver badges315 bronze badges

Sign up to request clarification or add additional context in comments.

14 Comments

DeepSpace Over a year ago

itertools.repeat(None, n) may beat both range and while. See stackoverflow.com/a/9059268/1453822

ShadowRanger Over a year ago

@DeepSpace: Yup. range (after it passes the small int cache boundaries) has to make actual objects, and has to look them up in the cache even before then; repeat doesn't, which saves a little time. The savings aren't completely trivial (for the n = 10 case, the timing measurement for me is 319 ns ± 39.6 ns), but they're not as extreme as in range vs. manual while loops, and the need for an import (which itself costs over a microsecond, and therefore eats the savings from the first few uses at least) makes it less of an automatic choice (especially if i might be used for something).

DeepSpace Over a year ago

premature optimization at its best :)

ShadowRanger Over a year ago

@DeepSpace: I can't fault you; it may be the root of all evil, but it's also the root of all fun, at least for folks with my mentality. :-)

ShadowRanger Over a year ago

@badmad: Did you leave in the i = 1 and i += 1 with the for loop version? Because then you'd be paying most of the cost of the while and the cost of the for which is clearly going to be worse than just one or the other.

|

Collectives™ on Stack Overflow

python3 performance: loop using range() Vs plain old while()

1 Answer 1

14 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

14 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related