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 avaoid some global variables in e.g. binding scripts, that need some state information ... I have to think about this one. Thanks for sharing!