bad generator performance

[Johannes Ahl mann]

hi,

i am in the process of profiling an application and noticed how much
time my depth first generator for walking a tree data structure took.

i wrote the same thing as a recursive function producing an array, and
this non-generator version is nearly 10 times faster!

any ideas why this is, what i did wrong...
for some reason the generator version appears as being called much more
often than the recursive one. no idea why that is, but the data is
definitely identical!

here the output from the python profiler and the respective code:

### snip ###

ncalls tottime percall cumtime percall filename:lineno(function)
94209/8191 0.560 0.000 0.590 0.000 :71(depthFirstIterator2)
4095/1 0.060 0.000 0.080 0.080 :62(depthFirstIterator1)

### snip ###

def depthFirstIterator1(self, depth = 0):
ret = [[self, True, depth]]

if self.isFolder():
for c in self.children:
ret = ret + c.depthFirstIterator(depth = depth + 1)

return ret + [[self, False, depth]]

def depthFirstIterator2(self, depth = 0):
yield [self, True, depth]

if self.isFolder():
for c in self.children:
for y in c.depthFirstIterator(depth = depth + 1):
yield y

yield [self, False, depth]

### snip ###

i'd appreciate any comments or explanations why the generator might be
so much slower, as i had just decided to use generators more frequently
and in the respective PEP they are praised as generally fast.

thx,

Johannes

 

[Johannes Ahl mann]

sorry, forgot to post the profiling info for the recursive helper
function.
but generator is still FAR slower...

4095/1 0.050 0.000 0.120 0.120 file.py:135(rek)

Johannes

 

[Alex Martelli]

a non-recursive solution to traversing a recursive data type is bound to
get ugly, isn't it?

Not necessarily: sometimes using an explicit stack can be quite pretty,
depending. E.g.:

def all_leaves(root):
stack = [root]
while stack:
rightmost = stack.pop()
if is_leaf(rightmost):
yield rightmost
else:
stack.extend(rightmost.all_children())

This isn't the traversing you're looking for, but it is _a_ traversing
of a recursive data type, non-recursive, and IMHO quite pretty.


Alex