Return-Path: <i@introo.me>
X-Original-To: python-list@python.org
Delivered-To: python-list@mail.python.org
X-Spam-Status: OK 0.019
X-Spam-Evidence: '*H*': 0.96; '*S*': 0.00; 'output': 0.05; '"""': 0.07; 'nested': 0.07; 'derived': 0.09; 'happen?': 0.09; 'slow.': 0.09; 'advance!': 0.16; 'constructs': 0.16; 'innermost': 0.16; 'internals,': 0.16; 'iteration': 0.16; 'itertools': 0.16; 'slow,': 0.16; 'subject:slow': 0.16; 'example': 0.22; 'import': 0.22; 'header:User-Agent:1': 0.23; 'example.': 0.24; 'script.': 0.24; 'pass': 0.26; 'code': 0.31; 'evil': 0.31; 'quite': 0.32; 'actual': 0.34; 'received:209.85': 0.35; 'received:209.85.220': 0.35; 'test': 0.35; 'received:google.com': 0.35; 'curious': 0.36; 'done': 0.36; 'doing': 0.36; 'thanks': 0.36; 'seconds': 0.37; 'received:209': 0.37; 'ends': 0.38; 'to:addr:python-list': 0.38; 'rather': 0.38; 'skip:8 10': 0.39; 'to:addr:python.org': 0.39; 'skip:p 20': 0.39; 'space': 0.40; 'skip:x 10': 0.40; 'skip:2 20': 0.60; 'first': 0.61; 'here:': 0.62; 'content-disposition:inline': 0.62; 'more': 0.64; 'finish': 0.65; 'skip:1 20': 0.65; 'url:me': 0.69; 'hood': 0.84; 'why?': 0.91
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:date:from:to:subject:message-id:mime-version :content-type:content-disposition:user-agent; bh=BZSq5x1KD4seKqAz/zYUg6kA4aEF80MPxbuWQfbcrz0=; b=ALFWfQqfLEAEX4jxzHrt3iMR24Rx4KM0DN+donIBIpICszhBmkIA39T7ehvCxAnpc/ TahxZEySwK2urhxBaSI2NOj0ex/VybRPBfOvew7yAiVYQHNeLMoDnD8F4YELRm7TdOTm qt2GzLSWyuDA7QrMomKrf9zP+tyFbaUSIuKLgLr0LZh4AUydvCUE8mR1vmmCxGnY0j9Z 9aenIZCxIrN9WmqzYTtT2gmipgXZ5xbFBNsQdiYGSP69H3JToo35RSYW5BA3VuVgL1UD GEzJPLTz4pxV9q3wFipbE6CfUUl1i5CNWyhezeahaOFgh1s7buaW8w+pjByRScmI0nfR obxg==
X-Gm-Message-State: ALoCoQlUayCkjFuL8dLXYQZzXjmDUhKkS+WDz3Yf1nAoJIRbe0JCGbLKF7cZRjeXarZfbjEvh0GL
X-Received: by 10.70.35.227 with SMTP id l3mr3653461pdj.33.1418188830043; Tue, 09 Dec 2014 21:20:30 -0800 (PST)
Date: Wed, 10 Dec 2014 13:20:25 +0800
From: Shiyao Ma <i@introo.me>
To: Python <python-list@python.org>
Subject: Nested loops is strangely slow, totally at a loss.
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Disposition: inline
User-Agent: All mail clients suck. This one just sucks way more.
X-Info: Find me @introom on Freenode. Have beers! :)
X-BeenThere: python-list@python.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: General discussion list for the Python programming language <python-list.python.org>
List-Unsubscribe: <https://mail.python.org/mailman/options/python-list>, <mailto:python-list-request@python.org?subject=unsubscribe>
List-Archive: <http://mail.python.org/pipermail/python-list/>
List-Post: <mailto:python-list@python.org>
List-Help: <mailto:python-list-request@python.org?subject=help>
List-Subscribe: <https://mail.python.org/mailman/listinfo/python-list>, <mailto:python-list-request@python.org?subject=subscribe>
Newsgroups: comp.lang.python
Message-ID: <mailman.16794.1418188833.18130.python-list@python.org>
Lines: 59
NNTP-Posting-Host: 2001:888:2000:d::a6
X-Trace: 1418188833 news.xs4all.nl 2890 [2001:888:2000:d::a6]:34403
X-Complaints-To: abuse@xs4all.nl
Path: csiph.com!usenet.pasdenom.info!bete-des-vosges.org!feed.ac-versailles.fr!nerim.net!novso.com!newsfeed.xs4all.nl!newsfeed2a.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Xref: csiph.com comp.lang.python:82261

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))


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

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")


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")


# example output
"""
('A, finish a loop with ', 2.1457672119140625e-06)
Done Test A
('B, finish a loop with ', 8.736134052276611)
('B, finish a loop with ', 1.9073486328125e-06)
('B, finish a loop with ', 0.0)
('B, finish a loop with ', 0.0)
('B, finish a loop with ', 1.1920928955078125e-06)
('B, finish a loop with ', 9.5367431640625e-07)
('B, finish a loop with ', 9.5367431640625e-07)
...
"""

We can see that the first iteration of B ends rather slow, 8.7 seconds here.

Why? I am curious about the internals, what's happening under the hood that makes this happen?

Thanks in advance!


-- 
Shiyao Ma
http://introo.me