Version 16 of quadratic time

In Elegance vs. performance RS et al. bring up some interesting results, and a nice graph widget to visualise them.

(DKF elides stuff in favour of a much more compacted and effective version; see the end of this page)

Here are some interesting and counter-intuitive results:

First we time compilation of trivial procs of increasing length

  proc sum1 list {
    foreach i $list {append body "set v$i $i" \n}
    proc x1 {} $body
  }
  proc sum2 list {
    foreach i $list {append body "set v$i $i" \n}
    proc x2 {} $body
    x2
  }

Now for the surprise - we generate a series of procs with increasingly nested command substitutions.

  proc sum1 list {
    set body 0
    foreach i $list {set body "\[set v$i $body]"}
    proc x1 {} "set N $body"
  }
  proc sum2 list {
    set body 0
    foreach i $list {set body "\[set v$i $body]"}
    proc x2 {} "set N $body"
    x2
  }

Turns out that it's the parser that's the problem, after discussion with dkf.

Here's some code that demonstrates it; the green line is running a pre-compiled proc.

 proc sum1 list {
    set body 0
    foreach i $list {set body "\[set v $body]"}
    proc x1 {} "set N $body"
 }
 proc sum2 list {
    set body 0
    foreach i $list {set body "\[set v $body]"}
    proc x2_[llength $list] {} "set N $body"
    x2_[llength $list]
 }
 proc sum3 list {
    x2_[llength $list]
 }

and here's the resulting plot:

TFW 24 Feb 2004 Looking at the parser, tokens are built up in reverse order (primarily in PrependSubExprTokens), which uses a memmove to shift the existing tokens to the right and inserts the new tokens. When parsing a short line, there isn't much of a penalty; however as expressions grow larger this could be the root cause of the quadratic performance penalty.

Another releated issue is CompileSubExpr can recursively call itself during the parse, which can cause a stack overflow.

 expr "[string repeat +1 10000]"

DKF: Let's regularize and standardize this. It's getting too hard to track what is going on.

 package require Tk
 proc plotGraph {conversionExpr args} {
    wm title . "Plotting using $conversionExpr"
    pack [canvas .c -bg white -width 500 -height 500] -expand 1
    array set color {
       1 red 2 blue 3 green 4 black
    }
    set i 0
    foreach tag $args {
       .c create line 0 500 0 500 -fill $color([incr i]) -tag $tag
    }
    set list {}
    for {set i 1} {$i<450} {incr i} {
       lappend list 1 1
       foreach func $args {
          set t [lindex [time {$func $list}] 0]
          .c coords $func [concat [.c coords $func] $i [expr {500-[expr $conversionExpr]}]]
       }
       update
    }
 }

 proc sum1 list {
    # Script construction
    set n [llength $list]
    proc x2_$n {} "set N [string repeat {[set v } $n]0[string repeat {]} $n]"
 }
 proc sum2 list {
    # Compilation and execution
    x2_[llength $list]
 }
 proc sum3 list {
    # Just execution
    x2_[llength $list]
 }

 plotGraph {$t} sum1 sum2 sum3        ;# Plots things normally
 #plotGraph {sqrt($t)} sum1 sum2 sum3 ;# Plots so straight-line = quadratic function
 #plotGraph {log($t)} sum1 sum2 sum3  ;# Plots si straight-line = exponential function

DGP 2004-Feb-26 The quadratic parsing of deeply nested command substitutions is due to the Tcl_Parse struct being specifically tuned for parsing a single Tcl command. One of these Tcl_Parse structs can be passed among all the parsing routines, so the Tcl_Tokens corresponding to the parse of a single command can be built up all in one place.

When parsing a command substitution, Tcl's parser parses all the commands between the [ and the ] with recursive calls to Tcl_ParseCommand, then throws away the results. When the nested command substitution is actually evaluated, the nested command is parsed all over again. N parses of strings of length N down to 0 is a quadratic number of characters parsed.

The dgp-refactor branch of development is adapted so that the partial results are not thrown away. However, because the Tcl_Parse struct only holds the Tcl_Tokens from a single command parse, the dgp-refactor branch is stuck copying those Tcl_Tokens from the Tcl_Parse into a larger Tcl_Token array holding all the tokens for a whole script. In the nested scenario, this implies a quadratic number of copies.

It should be possible to further develop the dgp-refactor branch so that TclParseScript accepts an (optional) argument of an existing token array to extend, rather than having TclParseScript always generate a new one that will have to be copied into and out of.

Category Performance