Version 10 of quadratic time

Updated 2004-02-25 20:34:44

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

Here's the widget:

 pack [canvas .c -bg white -width 600 -height 500] -expand 1

 array set color {
    1 red
    2 blue
    3 green
    4 yellow
 }
 foreach idx {1 2 3} {
    .c create line 0 500 0 500 -fill $color($idx)  -tag sum$idx
 }

 for {set i 1} {$i<600} {incr i} {
    set list [lrange [string repeat "1 " [expr {$i*2}]] 0 end]
    foreach idx {1 2 3} {
        set t [lindex [time {sum$idx $list}] 0]
        .c coords sum$idx [concat [.c coords sum$idx] $i [expr {500-$t/40}]]
    }
    update
 }

Which will graph the time performance of two procs names sum1 and sum2.

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]"

---

Here's another test script for people to try:

 package require Tk
 proc sum1 list {
     set body 0
     foreach i $list {
        set body "\[set v $body]"
     }
     proc x2_[llength $list] {} "set N $body"
 }

 proc sum2 list {
 if 0 {
     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]
 }

  pack [canvas .c -bg white -width 600 -height 500] -expand 1

  array set color {
     1 red
     2 blue
     3 green
     4 black
  }
  foreach idx {1 2 3} {
     .c create line 0 500 0 500 -fill $color($idx)  -tag sum$idx
  }

  for {set i 1} {$i<450} {incr i} {
      set list [lrange [string repeat "1 " [expr {$i*2}]] 0 end]
      foreach idx {1 2 3} {
         set t [lindex [time {sum$idx $list}] 0]
 #       .c coords sum$idx [concat [.c coords sum$idx] $i [expr {500-sqrt($t/40)}]]
         .c coords sum$idx [concat [.c coords sum$idx] $i [expr {500-sqrt($t)}]]
 #       .c coords sum$idx [concat [.c coords sum$idx] $i [expr {500-$t/20}]]
      }
      update
  }

---

Category Performance