foreach, an analogy

Bill Baxter wbaxter at gmail.com
Fri Oct 20 09:27:04 PDT 2006


Karen Lanrap wrote:
> Bill Baxter wrote:
> 
> 
>>>>The call stack stores our stack implicitly.
>>>
>>>Would this be true in any case of enumeration of the tree,
>>>asuming that the stored structure has indeed the property of a
>>>tree? 
>>
>>I don't understand your question.
> 
> 
> I know of at least one algorithm where it was necessary to peek down 
> into the stack. This is not possible, if the stack is stored 
> implicitely. Therefore the assumed benefit may turn out as a waste of 
> space.

Ah, I see.  Yeh, I suppose a traversal algorithm with that sort of 
property would be trickier.

Also I seem to recall reading advice somewhere to the effect of, "if you 
need the best speed, turn your recursive tree algorithm into a 
non-recursive one."  -- basically by managing the stack of nodes 
yourself in a list or something.  Then you save function call overhead. 
  You're not storing the extra frame pointers, extra copies of local 
variables etc, that go with pushing and popping stack frames.  You just 
push and pop the node values in your data structure.

And then there's the issue with stack depths often being limited (don't 
know if this is an issue with D or not, but if so...).  If 
foreach/delegate/opApply is D's primary iterator strategy, then to write 
a serious tree library for big data on 64-bit architectures, does that 
mean I'll need to avoid opApply as a means of traversing?

I guess it's still possible to write the opApply tree traverser 
non-recursively if you need to.

--bb



More information about the Digitalmars-d-announce mailing list