[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?

<<categories>> Algorithm | Performance