Version 12 of quadratic time

Updated 2004-02-25 22:09:05

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

  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

---

Category Performance