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(depthFirstI terator2)
4095/1 0.060 0.000 0.080 0.080 :62(depthFirstI terator1)

### snip ###

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

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

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

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

if self.isFolder() :
for c in self.children:
for y in c.depthFirstIte rator(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]

Re: bad generator performance

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]

Re: bad generator performance

Johannes Ahl-mann <softpro@gmx.ne t> wrote:
[color=blue]
> a non-recursive solution to traversing a recursive data type is bound to
> get ugly, isn't it?[/color]

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(rightmo st):
yield rightmost
else:
stack.extend(ri ghtmost.all_chi ldren())

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