Nested loops is strangely slow, totally at a loss.

[Steven D'Aprano]

On Wed, 10 Dec 2014 13:20:25 +0800, Shiyao Ma wrote:

> When doing nested loop, the very first iteration of the innermost loop
> ends ultimately slow.
> 
> Let's the code speak.
> 
> The following code is quite contrived. Actually it's derived from my
> 3d-dct script. The actual difference is way more significant than this
> example.
> 
> In case of any evil of gmail, bpaste here:
> https://bpaste.net/show/edfef62edb17
> 
> # this constructs a space_len x space_len x space_len 3D coordinate
> import timeit
> from itertools import product
> space_len = 580
> space = product(xrange(space_len), xrange(space_len), xrange(space_len))

space will contain 580**3 == 195112000 items, but they are lazily 
generated. Once you access an item, it is gone, never to be seen again 
(until you recreate the product iterator object).


> sparse_cloud = product(xrange(1), xrange(1), xrange(1))

This, on the other hand, only has a single item, (0,0,0). When you run 
this:


> for i, j, k in sparse_cloud:
>     ts = timeit.default_timer()
>     if (i, j, k) in space: pass
>     te = timeit.default_timer()
>     print("A, finish a loop with ", te-ts)
> print("Done Test A")

it tests:

    (0,0,0) in space


which matches the very first item of space, which takes hardly any time 
at all. But having done this, you have consumed that first value.


> sparse_cloud = product(xrange(1000), xrange(1000), xrange(1000)) for i,
> j, k in sparse_cloud:
>     ts = timeit.default_timer()
>     if (i, j, k) in space: pass
>     te = timeit.default_timer()
>     print("B, finish a loop with ", te-ts)
> print("Done Test B")

Now you create a new sparse_cloud iterator, and iterate over it. The 
first loop gets

    i, j, k = 0, 0, 0

and then tried to check:

    (0,0,0) in space

*but* that item from has already been consumed. So it now runs through 
the rest of the iterator:

    (0,0,0) == (0,0,1)  # False
    (0,0,0) == (0,0,2)  # False
    (0,0,0) == (0,0,3)  # False
    ...
    (0,0,0) == (0,0,579)  # False
    (0,0,0) == (0,1,0)  # False
    (0,0,0) == (0,1,1)  # False
    ...
    (0,0,0) == (579,579,579)  # False

which takes a long time.

Now the next loop gets the values:

    i, j, k = 0, 0, 1

and then tried to check:

    (0,0,1) in space

but space is now exhausted, and it returns False immediately. And so on 
for the rest of the sparse_cloud iterator.




It would be nice if product iterators behaved like xrange() objects and 
could perform "in" tests without exhausting the iterator, but they don't. 
That's sad.



-- 
Steven