Updated 2004-10-18 07:01:22 by AM

Arjen Markus (18 october 2004) I intend this page for recording various ways to implement algorithms to solve PDEs and their relative performance.

The first set of implementations concerns the creation and updating of a "matrix" (as a list of lists).
 # testmatrix.tcl
 #     Test a variety of ways to create and update a matrix
 #     (implemented as a list of lists) and find out which is
 #     the fastest
 #

 proc buildup { norows nocols } {
    #
    # Use a nested for-loop to create and expand the lists
    #
    set newmat {}
    for { set j 0 } { $j < $norows } { incr j } {
       set newrow {}
       for { set i 0 } { $i < $nocols } { incr i } {
          lappend newrow [expr {rand()}]
       }
       lappend newmat $newrow
    }
    return $newmat
 }

 proc copy_and_update { matrix } {
    #
    # Use an existing matrix as a template, copy this and
    # update the entries
    #
    set newmat $matrix
    set r 0
    foreach row $newmat {
       set c 0
       foreach col $row {
          lset newmat $r $c [expr {rand()}]
          incr c
       }
       incr r
    }
    return $newmat
 }

 proc template_and_buildup { matrix } {
    #
    # Use an existing matrix as a template and
    # construct a new matrix via foreach-loops
    #
    set newmat {}
    foreach row $matrix {
       set newrow {}
       foreach col $row {
          lappend newrow [expr {rand()}]
       }
       lappend newmat $newrow
    }
    return $newmat
 }

 foreach size {10 20 50 100} times {10000 3000 1000 1000} {
    puts "Size: $size"
    puts "Build up: [time {buildup $size $size} $times]"

    set matrix [buildup $size $size]
    puts "Copy and update: [time {copy_and_update $matrix} $times]"
    puts "Template and build up: [time {template_and_buildup $matrix} $times]"
 }

Here is the result with Tcl 8.4.5, on Windows XP, fairly fast hardware (but the relative speeds are more important):
 Size: 10
 Build up: 81 microseconds per iteration
 Copy and update: 103 microseconds per iteration
 Template and build up: 78 microseconds per iteration
 Size: 20
 Build up: 273 microseconds per iteration
 Copy and update: 368 microseconds per iteration
 Template and build up: 260 microseconds per iteration
 Size: 50
 Build up: 1534 microseconds per iteration
 Copy and update: 2279 microseconds per iteration
 Template and build up: 1499 microseconds per iteration
 Size: 100
 Build up: 5936 microseconds per iteration
 Copy and update: 9262 microseconds per iteration
 Template and build up: 5781 microseconds per iteration

Conclusion from this (and another test, Tcl 8.4.1 on WIndows 98):

  • Rebuilding a list of lists is definitely faster than updating the entries
  • Using [foreach] seems slightly faster than [for] loops

[ Category Numerical Analysis ]