Version 1 of quadratic time

Updated 2004-02-24 15:18:09

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
  }

---

Category Performance