dictionary tree traversal with path keeping

1. Execution results CPython 3.4.2

inline: 0.388133 seconds
iterate_tree: 0.772798
iterate_tree2: 0.707333
iterate_tree3: 0.564626
iterate_tree3_noyield: 0.498388
iterate_tree3_nofeedback: 0.353944
iterate_tree5: 0.650102
iterate_tree5_noyield: 0.566557
iterate_tree5_nofeedback: 0.435601
iterate_tree6: 0.562908
iterate_tree6_noyield: 0.657400
iterate_tree6_nofeedback: 0.495867
===================
inline: 0.373992 seconds
iterate_tree: 0.785275
iterate_tree2: 0.733026
iterate_tree3: 0.568669
iterate_tree3_noyield: 0.478942
iterate_tree3_nofeedback: 0.349861
iterate_tree5: 0.666957
iterate_tree5_noyield: 0.561710
iterate_tree5_nofeedback: 0.436763
iterate_tree6: 0.556949
iterate_tree6_noyield: 0.661005
iterate_tree6_nofeedback: 0.505315
===================
inline: 0.371376 seconds
iterate_tree: 0.774100
iterate_tree2: 0.792793
iterate_tree3: 0.576650
iterate_tree3_noyield: 0.479125
iterate_tree3_nofeedback: 0.344007
iterate_tree5: 0.663087
iterate_tree5_noyield: 0.582382
iterate_tree5_nofeedback: 0.438463
iterate_tree6: 0.643334
iterate_tree6_noyield: 0.702786
iterate_tree6_nofeedback: 0.542529
===================
inline: 0.375493 seconds
iterate_tree: 0.775765
iterate_tree2: 0.699562
iterate_tree3: 0.559925
iterate_tree3_noyield: 0.529699
iterate_tree3_nofeedback: 0.343166
iterate_tree5: 0.639239
iterate_tree5_noyield: 0.549155
iterate_tree5_nofeedback: 0.461195
iterate_tree6: 0.543466
iterate_tree6_noyield: 0.620466
iterate_tree6_nofeedback: 0.494854
===================
inline: 0.360489 seconds
iterate_tree: 0.781050
iterate_tree2: 0.714968
iterate_tree3: 0.568337
iterate_tree3_noyield: 0.474860
iterate_tree3_nofeedback: 0.364178
iterate_tree5: 0.658812
iterate_tree5_noyield: 0.554898
iterate_tree5_nofeedback: 0.433046
iterate_tree6: 0.560966
iterate_tree6_noyield: 0.649476
iterate_tree6_nofeedback: 0.497308
===================

2. Execution results CPython 2.7.8

inline: 0.418819 seconds
iterate_tree: 0.782076
iterate_tree2: 0.994035
iterate_tree3: 0.672291
iterate_tree3_noyield: 0.602802
iterate_tree3_nofeedback: 0.438645
iterate_tree5: 0.811397
iterate_tree5_noyield: 0.704024
iterate_tree5_nofeedback: 0.555990
iterate_tree6: 0.634752
iterate_tree6_noyield: 0.708318
iterate_tree6_nofeedback: 0.548175
===================
inline: 0.431803 seconds
iterate_tree: 0.797864
iterate_tree2: 0.962760
iterate_tree3: 0.676052
iterate_tree3_noyield: 0.627296
iterate_tree3_nofeedback: 0.432995
iterate_tree5: 0.801945
iterate_tree5_noyield: 0.760071
iterate_tree5_nofeedback: 0.557158
iterate_tree6: 0.618978
iterate_tree6_noyield: 0.715398
iterate_tree6_nofeedback: 0.564163
===================
inline: 0.430824 seconds
iterate_tree: 0.790162
iterate_tree2: 0.961879
iterate_tree3: 0.685668
iterate_tree3_noyield: 0.603360
iterate_tree3_nofeedback: 0.426412
iterate_tree5: 0.801495
iterate_tree5_noyield: 0.717511
iterate_tree5_nofeedback: 0.550656
iterate_tree6: 0.615157
iterate_tree6_noyield: 0.724978
iterate_tree6_nofeedback: 0.552988
===================
inline: 0.428661 seconds
iterate_tree: 0.789669
iterate_tree2: 1.007039
iterate_tree3: 0.675401
iterate_tree3_noyield: 0.600943
iterate_tree3_nofeedback: 0.440957
iterate_tree5: 0.808624
iterate_tree5_noyield: 0.720491
iterate_tree5_nofeedback: 0.563287
iterate_tree6: 0.655150
iterate_tree6_noyield: 0.774540
iterate_tree6_nofeedback: 0.583963
===================
inline: 0.415149 seconds
iterate_tree: 0.788343
iterate_tree2: 0.962036
iterate_tree3: 0.690689
iterate_tree3_noyield: 0.592946
iterate_tree3_nofeedback: 0.468659
iterate_tree5: 0.804124
iterate_tree5_noyield: 0.709770
iterate_tree5_nofeedback: 0.601748
iterate_tree6: 0.623776
iterate_tree6_noyield: 0.714162
iterate_tree6_nofeedback: 0.562679
===================

3. Execution results PyPy 2.5.0

inline: 0.271403 seconds
iterate_tree: 0.843282
iterate_tree2: 0.216329
iterate_tree3: 0.413761
iterate_tree3_noyield: 0.227204
iterate_tree3_nofeedback: 0.161373
iterate_tree5: 0.439838
iterate_tree5_noyield: 0.221589
iterate_tree5_nofeedback: 0.179010
iterate_tree6: 0.230437
iterate_tree6_noyield: 0.140812
iterate_tree6_nofeedback: 0.119887
===================
inline: 0.278680 seconds
iterate_tree: 0.803759
iterate_tree2: 0.231160
iterate_tree3: 0.398721
iterate_tree3_noyield: 0.212599
iterate_tree3_nofeedback: 0.158962
iterate_tree5: 0.439686
iterate_tree5_noyield: 0.221264
iterate_tree5_nofeedback: 0.191299
iterate_tree6: 0.215052
iterate_tree6_noyield: 0.136341
iterate_tree6_nofeedback: 0.118227
===================
inline: 0.278797 seconds
iterate_tree: 0.859108
iterate_tree2: 0.220438
iterate_tree3: 0.417627
iterate_tree3_noyield: 0.232952
iterate_tree3_nofeedback: 0.158761
iterate_tree5: 0.467679
iterate_tree5_noyield: 0.221373
iterate_tree5_nofeedback: 0.182964
iterate_tree6: 0.229962
iterate_tree6_noyield: 0.136830
iterate_tree6_nofeedback: 0.134050
===================
inline: 0.272146 seconds
iterate_tree: 0.846570
iterate_tree2: 0.216674
iterate_tree3: 0.402913
iterate_tree3_noyield: 0.208778
iterate_tree3_nofeedback: 0.173020
iterate_tree5: 0.451698
iterate_tree5_noyield: 0.242138
iterate_tree5_nofeedback: 0.192739
iterate_tree6: 0.229692
iterate_tree6_noyield: 0.135935
iterate_tree6_nofeedback: 0.123902
===================
inline: 0.271496 seconds
iterate_tree: 0.835806
iterate_tree2: 0.236507
iterate_tree3: 0.483542
iterate_tree3_noyield: 0.209482
iterate_tree3_nofeedback: 0.156664
iterate_tree5: 0.423417
iterate_tree5_noyield: 0.222805
iterate_tree5_nofeedback: 0.202381
iterate_tree6: 0.214501
iterate_tree6_noyield: 0.140129
iterate_tree6_nofeedback: 0.119652
===================

perf-p2k.py

def iterate_tree(tree, depth, callback):
    if depth:
        for k, subtree in tree.items():
            cb = partial(callback, k)
            for i in iterate_tree(subtree, depth-1, cb):
                yield i
    else:
        for k, v in tree.items():
            rv = callback(k, v)
            yield rv


def iterate_tree2(tree, depth, callback):
    iterators = [iter(tree.items())]
    args = []
    while iterators:
        try:
            k, v = next(iterators[-1])
        except StopIteration:
            depth += 1
            iterators.pop()
            if args:
                args.pop()
            continue

        if depth:
            args.append(k)
            iterators.append(iter(v.items()))
            depth -= 1
        else:
            yield callback(*(args + [k, v]))


def iterate_tree3(tree, depth, callback, args=()):
    if depth:
        for k, subtree in tree.items():
            for i in iterate_tree3(subtree, depth-1, callback, args+(k,)):
                yield i
    else:
        for k, v in tree.items():
            rv = callback(*(args + (k, v)))
            yield rv

def iterate_tree3_noyield(tree, depth, callback, args=()):
    if depth:
        for k, subtree in tree.items():
            iterate_tree3_noyield(subtree, depth-1, callback, args+(k,))
    else:
        for k, v in tree.items():
            callback(*(args + (k, v)))

def iterate_tree5(node, depth, callback, path=()):
    for (k, v) in node.items():
        kpath = path + (k,)
        if depth:
            for i in iterate_tree5(v, depth-1, callback, kpath):
                                yield i
        else:
            yield callback(*(kpath + (v,)))

def iterate_tree5_noyield(node, depth, callback, path=()):
    for (k, v) in node.items():
        kpath = path + (k,)
        if depth:
            iterate_tree5_noyield(v, depth-1, callback, kpath)
        else:
            callback(*(kpath + (v,)))

def iterate_tree6(tree, depth, callback):
    iterators = [iter(tree.items())]
    args = [] 
    while iterators:
        while depth:
            for k, v in iterators[-1]:
                args.append(k)
                iterators.append(iter(v.items()))
                depth -= 1
                break
            else:
                break
        else:
            for k, v in iterators[-1]:
                yield callback(*(args + [k, v]))
        depth += 1
        del iterators[-1]
        del args[-1:]

def iterate_tree6_noyield(tree, depth, callback):
    iterators = [iter(tree.items())]
    args = [] 
    while iterators:
        while depth:
            for k, v in iterators[-1]:
                args.append(k)
                iterators.append(iter(v.items()))
                depth -= 1
                break
            else:
                break
        else:
            for k, v in iterators[-1]:
                callback(*(args + [k, v]))
        depth += 1
        del iterators[-1]
        del args[-1:]

tree = dict()
for i in range(10):
    tree[i] = dict()
    for j in range(10):
        tree[i][j] = dict()
        for k in range(10):
            tree[i][j][k] = dict()
            for l in range(10):
                tree[i][j][k][l] = dict()
                for m in range(10):
                    tree[i][j][k][l][m] = dict()
                    for n in range(10):
                        tree[i][j][k][l][m][n] = ["a", "b", "c", "d", "e", "f", "g"]

import time
from functools import partial

def callback(*args):
    assert isinstance(args[-1], list)

def callback2(*args):
        callback(*args)

start = time.time()
for k1, leafs1 in tree.items():
    for k2, leafs2 in leafs1.items():
        for k3, leafs3 in leafs2.items():
            for k4, leafs4 in leafs3.items():
                for k5, leafs5 in leafs4.items():
                    for k6, val in leafs5.items():
                        callback(k1, k2, k3, k4, k5, k6, val)
print("inline: %f seconds" % (time.time() - start))

        

start = time.time()
for i in iterate_tree(tree, 5, callback):
    pass
print("iterate_tree: %f" % (time.time() - start))

start = time.time()
for i in iterate_tree2(tree, 5, callback):
    pass
print("iterate_tree2: %f" % (time.time() - start))

start = time.time()
for i in iterate_tree3(tree, 5, callback):
    pass
print("iterate_tree3: %f" % (time.time() - start))

start = time.time()
iterate_tree3_noyield(tree, 5, callback2)
print("iterate_tree3_noyield: %f" % (time.time() - start))

start = time.time()
iterate_tree3_noyield(tree, 5, callback)
print("iterate_tree3_nofeedback: %f" % (time.time() - start))

start = time.time()
for i in iterate_tree5(tree, 5, callback):
    pass
print("iterate_tree5: %f" % (time.time() - start))

start = time.time()
iterate_tree5_noyield(tree, 5, callback2)
print("iterate_tree5_noyield: %f" % (time.time() - start))

start = time.time()
iterate_tree5_noyield(tree, 5, callback)
print("iterate_tree5_nofeedback: %f" % (time.time() - start))

start = time.time()
for i in iterate_tree6(tree, 5, callback):
    pass
print("iterate_tree6: %f" % (time.time() - start))

start = time.time()
iterate_tree6_noyield(tree, 5, callback2)
print("iterate_tree6_noyield: %f" % (time.time() - start))

start = time.time()
iterate_tree6_noyield(tree, 5, callback)
print("iterate_tree6_nofeedback: %f" % (time.time() - start))

perf-p3k.py

def iterate_tree(tree, depth, callback):
    if depth:
        for k, subtree in tree.items():
            cb = partial(callback, k)
            yield from iterate_tree(subtree, depth-1, cb)
    else:
        for k, v in tree.items():
            rv = callback(k, v)
            yield rv


def iterate_tree2(tree, depth, callback):
    iterators = [iter(tree.items())]
    args = []
    while iterators:
        try:
            k, v = next(iterators[-1])
        except StopIteration:
            depth += 1
            iterators.pop()
            if args:
                args.pop()
            continue

        if depth:
            args.append(k)
            iterators.append(iter(v.items()))
            depth -= 1
        else:
            yield callback(*(args + [k, v]))


def iterate_tree3(tree, depth, callback, args=()):
    if depth:
        for k, subtree in tree.items():
            yield from iterate_tree3(subtree, depth-1, callback, args+(k,))
    else:
        for k, v in tree.items():
            rv = callback(*(args + (k, v)))
            yield rv

def iterate_tree3_noyield(tree, depth, callback, args=()):
    if depth:
        for k, subtree in tree.items():
            iterate_tree3_noyield(subtree, depth-1, callback, args+(k,))
    else:
        for k, v in tree.items():
            callback(*(args + (k, v)))

def iterate_tree5(node, depth, callback, path=()):
    for (k, v) in node.items():
        kpath = path + (k,)
        if depth:
            yield from iterate_tree5(v, depth-1, callback, kpath)
        else:
            yield callback(*(kpath + (v,)))

def iterate_tree5_noyield(node, depth, callback, path=()):
    for (k, v) in node.items():
        kpath = path + (k,)
        if depth:
            iterate_tree5_noyield(v, depth-1, callback, kpath)
        else:
            callback(*(kpath + (v,)))

def iterate_tree6(tree, depth, callback):
    iterators = [iter(tree.items())]
    args = [] 
    while iterators:
        while depth:
            for k, v in iterators[-1]:
                args.append(k)
                iterators.append(iter(v.items()))
                depth -= 1
                break
            else:
                break
        else:
            for k, v in iterators[-1]:
                yield callback(*(args + [k, v]))
        depth += 1
        del iterators[-1]
        del args[-1:]

def iterate_tree6_noyield(tree, depth, callback):
    iterators = [iter(tree.items())]
    args = [] 
    while iterators:
        while depth:
            for k, v in iterators[-1]:
                args.append(k)
                iterators.append(iter(v.items()))
                depth -= 1
                break
            else:
                break
        else:
            for k, v in iterators[-1]:
                callback(*(args + [k, v]))
        depth += 1
        del iterators[-1]
        del args[-1:]

tree = dict()
for i in range(10):
    tree[i] = dict()
    for j in range(10):
        tree[i][j] = dict()
        for k in range(10):
            tree[i][j][k] = dict()
            for l in range(10):
                tree[i][j][k][l] = dict()
                for m in range(10):
                    tree[i][j][k][l][m] = dict()
                    for n in range(10):
                        tree[i][j][k][l][m][n] = ["a", "b", "c", "d", "e", "f", "g"]

import time
from functools import partial

def callback(*args):
    assert isinstance(args[-1], list)

def callback2(*args):
        callback(*args)

start = time.time()
for k1, leafs1 in tree.items():
    for k2, leafs2 in leafs1.items():
        for k3, leafs3 in leafs2.items():
            for k4, leafs4 in leafs3.items():
                for k5, leafs5 in leafs4.items():
                    for k6, val in leafs5.items():
                        callback(k1, k2, k3, k4, k5, k6, val)
print("inline: %f seconds" % (time.time() - start))

        

start = time.time()
for i in iterate_tree(tree, 5, callback):
    pass
print("iterate_tree: %f" % (time.time() - start))

start = time.time()
for i in iterate_tree2(tree, 5, callback):
    pass
print("iterate_tree2: %f" % (time.time() - start))

start = time.time()
for i in iterate_tree3(tree, 5, callback):
    pass
print("iterate_tree3: %f" % (time.time() - start))

start = time.time()
iterate_tree3_noyield(tree, 5, callback2)
print("iterate_tree3_noyield: %f" % (time.time() - start))

start = time.time()
iterate_tree3_noyield(tree, 5, callback)
print("iterate_tree3_nofeedback: %f" % (time.time() - start))

start = time.time()
for i in iterate_tree5(tree, 5, callback):
    pass
print("iterate_tree5: %f" % (time.time() - start))

start = time.time()
iterate_tree5_noyield(tree, 5, callback2)
print("iterate_tree5_noyield: %f" % (time.time() - start))

start = time.time()
iterate_tree5_noyield(tree, 5, callback)
print("iterate_tree5_nofeedback: %f" % (time.time() - start))

start = time.time()
for i in iterate_tree6(tree, 5, callback):
    pass
print("iterate_tree6: %f" % (time.time() - start))

start = time.time()
iterate_tree6_noyield(tree, 5, callback2)
print("iterate_tree6_noyield: %f" % (time.time() - start))

start = time.time()
iterate_tree6_noyield(tree, 5, callback)
print("iterate_tree6_nofeedback: %f" % (time.time() - start))