trace-tree torture

Edwin Smith edwsmith at adobe.com
Tue Jan 29 14:48:35 PST 2008


Here's an example of a trace-tree torture test, taken from a
game-of-life test (see below).  the inner loop has 8 consequtive if's,
and 8 calls to a function with 4 array bounds checks for the grid
border.  so all 12 tests are relatively equally weighted.  Although the
decision tree has theoretically 2^12 leaves, some get pruned due to
common subexpression elimination.   but it's still a lot of branches. 

The money question is, do you just let the tree get that branchy? it's a
lot of very short traces.  or extend trace-trees conceptually to
trace-dags?  or prune the trees?  careful pruning should allow a couple
of subtrees within the loop body, that could potentially still be
optimized somewhat, albeit less agressively than with full tail
splitting.

see also the trace stats, tree 11 is the inner loop and has ~750 leaves,
all but four of which do indeed loop back to the top of the loop.  

Ed

                private function cell (row:int, col:int):Boolean {
67:                return (row >= 0 && row < rows && col >= 0 && col <
cols
68:                     && cells[row * cols + col]);
69:                }
       
               // Advances the simulation by a discrete time step. This
is a very
               // straightforward, 'naive' implementation of the Game of
Life.
73:                private function step():Boolean {
74:                    var next:Array = new Array(rows * cols);
75:                    var changed:Boolean = false;
                    
77:                    for (var row:int = rows - 1; row >= 0; row--) {
78:                        var row_offset:int = row * cols;
79:                        for (var col:int = cols - 1; col >= 0; col--)
{
80:                            var count:int= 0;
81:                            if (cell(row - 1, col - 1)) count++;
82:                            if (cell(row - 1, col)) count++;
83:                            if (cell(row - 1, col + 1)) count++;
84:                            if (cell(row, col - 1)) count++;
85:                            if (cell(row, col + 1)) count++;
86:                            if (cell(row + 1, col - 1)) count++;
87:                            if (cell(row + 1, col)) count++;
88:                            if (cell(row + 1, col + 1)) count++;
89:                            var old_state:Boolean = cells[row_offset
+ col];
90:                            var new_state:Boolean = (!old_state &&
count == 3)
91:                                || (old_state && (count == 2 || count
== 3));
92:                            if (!changed && new_state != old_state)
93:                                changed = true;
94:                                next[row_offset + col] = new_state;
95:                        }
96:                    }
97:                    cells = next;
98:                    return changed; // indicates if simulation is
still active
99:                 }




-------------- next part --------------
A non-text attachment was scrubbed...
Name: t2.log
Type: application/octet-stream
Size: 90063 bytes
Desc: t2.log
Url : http://mail.mozilla.org/pipermail/tamarin-devel/attachments/20080129/a9a989cc/attachment-0001.obj 


More information about the Tamarin-devel mailing list