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

[Alexey Kardashevskiy]

On 17/07/2020 07:21, Segher Boessenkool wrote:
> 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)


for O(1) we need to keep a parent in the current node (which we do). I
wonder now if SLOF does O(1) walks anywhere.


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



-- 
Alexey