a more efficient loopForestSteensgaard

Stephen Weeks MLton@sourcelight.com
Wed, 19 Dec 2001 14:05:57 -0800


> No.  The space required for my proposed representation of inLoop is
> linear in the size of the program graph.  I don't do any concats, I
> just keep a list of vectors (of notInLoop's).  The post-processing is
> linear time.  The space usage is linear because of the sharing of
> vectors amongst multiple loops.

Darn.  I'm wrong -- you are right about the concats.  You can't do it
with a node vector list, you need a node vector append list, at which
point you've basically represented the tree in the append list.

Hmmm ...

Here's another way to look at it.  The tree with just notInLoops
is a perfectly fine representation of inLoop.  Whenever you want to
do something over all the nodes in a loop, you do a Tree.foreach
over all of the notInLoops instead of a List.foreach.  The time
complexity is still linear in the number of nodes in the loop.