[SLOF] [PATCH slof] fdt: Avoid recursion when traversing tree

[Segher Boessenkool]

Hi!

On Thu, Jul 16, 2020 at 05:54:30PM +0200, Greg Kurz wrote:
> On Thu, 16 Jul 2020 14:55:42 +1000
> Alexey Kardashevskiy <aik at ozlabs.ru> wrote:
> > A loop over peers does not need recursion which becomes a problem with
> > hundreds devices.
> 
> You're likely right but, per curiosity, do you have some numbers to
> share ?

It's two items on the data stack per recursion (and one on the return
stack).  This would probably not take too much stack (just a lot, not
*too* much though), except that to do "peer" we also recurse, so if
there are a lot of entries in any of your parent nodes, you lose.  And
most trees have some nodes with many children.

You can code any of the tree walks without any recursion, using just
O(1) extra memory (just keep track of the previous node visited, for
example), but in this case, it is probably fine to just do a loop to
handle the nodes on one level.

> > -: (fdt-cas-search-obsolete-nodes) ( start node -- )
> > -    dup IF
> > -	dup child 2 pick swap recurse
> > -	dup peer 2 pick swap recurse
> > -
> > -	dup fdt-cas-node-obsolete? IF
> > -	    fdt-debug IF dup ." Deleting obsolete node: " dup .node ." = " . cr THEN
> > -	    dup delete-node
> > -	THEN
> > +: (fdt-cas-search-obsolete-nodes) ( node -- )
> > +    dup child
> > +    BEGIN
> > +	dup
> > +    WHILE
> > +	dup recurse
> > +	peer
> > +    REPEAT
> > +    drop
> > +    dup fdt-cas-node-obsolete? IF
> > +        fdt-debug IF dup ." Deleting obsolete node: " dup .node ." = " . cr THEN
> > +        dup delete-node
> >      THEN
> > -    2drop
> > +    drop
> >  ;

... which is what this does :-)

The patch looks fine to me.


Segher