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:

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 so 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.

DGP 2004-Mar-06 UPDATE The dgp-refactor branch of development is adapted so that the partial results are not thrown away. Consequently it does not suffer from quadratic complexity when parsing deeply nested command substitutions. Give it a try.

TFW 24 Feb 2004 Looking at the expr subexpression 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]"

DGP See Tcl Feature Request 903765 [L1 ]

Category Performance | Category GUI