## Changing a Recursive Algorithm into a Linear Algorithm

George Peter Staplin - 2007, Dec 9 - I had a basic rendering algorithm used in Whim2 that I was trying to improve without turning to C, and I came upon an interesting solution, that I thought others might benefit from.

This is the recursive algorithm I started out with. I was getting a peak of about 35 FPS with a 1024x768 display, and much less when there were more windows, or the tree was deeper.

```proc render-tree {baseobj win x y} {
global bserver_windows

foreach child [\$win _children] {
set scale 1000

set destx [expr {\$x + [\$child x]}]
set desty [expr {\$y + [\$child y]}]

if {[info exists bserver_windows(\$child.window)]} {
set scale [\$child.window scale]
}

if {1000 != \$scale} {
set b [\$child _render_tree_data]
if {"" eq \$b} {
\$child _render_tree_data [set b [megaimage-blank]]
}
\$b setdata [[\$child obj] getdata]
render-tree \$b \$child 0 0
\$b scale \$scale \$scale
lassign [\$b getsize] bwidth bheight
\$child width \$bwidth height \$bheight
\$baseobj blendobj \$destx \$desty \$b
} else {
\$baseobj blendobj \$destx \$desty [\$child obj]
render-tree \$baseobj \$child \$destx \$desty
}
}
}```

Now how do we go about turning it into a linear algorithm you may ask, we generate code recursively, that is linear. I found that Tcl is so fast at compiling a proc that it's not a big deal to regenerate it when the tree changes. I also took the time to eliminate as many variable lookups as possible. Improving performance is about removing indirection.

```proc generate-render-tree {} {
set v 0
set body [generate-render-windows [. obj] . [list] v]
proc render-tree {} [subst {set offx0 0; set offy0 0; \$body}]
}

proc generate-render-windows {baseobj win parentlist v_var} {
global bserver_windows
upvar \$v_var v

set code ""

foreach child [\$win _children] {
set scale 1000
set oldv \$v
incr v
append code [subst -nocommands -nobackslashes {
set offx\$v [expr {[set offx\$oldv] + [\$child x]}]
set offy\$v [expr {[set offy\$oldv] + [\$child y]}]
}]

if {[info exists bserver_windows(\$child.window)]} {
set scale [\$child.window scale]
}

if {1000 == \$scale} {
append code [subst -nocommands -nobackslashes {
\$baseobj blendobj [set offx\$v] [set offy\$v] [\$child obj]
}]
append code [generate-render-windows \$baseobj \$child \
[concat \$parentlist [list \$child]] v]
} else {
set b [\$child _render_tree_data]
if {\$b eq ""} {
\$child _render_tree_data [set b [megaimage-blank]]
}

incr v
append code [subst -nocommands -nobackslashes {
\$b setdata [[\$child obj] getdata]
set offx\$v 0
set offy\$v 0
}]

append code [generate-render-windows \$b \$child [list] v]
incr v -1
append code [subst -nocommands -nobackslashes {
\$b scale \$scale \$scale
lassign [\$b getsize] bwidth bheight
\$child width [set bwidth] height [set bheight]
\$baseobj blendobj [set offx\$v] [set offy\$v] \$b
}]
}
incr v -1
}
return \$code
}```

So how much did that change my frame rate you may ask? I get a peak of about 74-75 FPS for the same test case as the recursive algorithm. That's more than double the speed. :-) The extra cost of regenerating the proc is minimal. I call generate-render-tree in several key places that alter the tree in Whim2. I have a feeling I wouldn't have been able to get the same performance with a C solution as easily. Tcl has a unique advantage in some respects :-)

Wow, this is really an interesting approach! Redefining a proc being called repeatedly ... hm ... perhaps this can be used to avoid some global variables in e.g. binding scripts, that need some state information ... I have to think about this one. Thanks for sharing!

escargo 10 Dec 2007 - I was thinking of downloading Whim again; is the code going to be updated with this new feature soon?

 Category Algorithm Category Performance