Version 2 of Tcl Static Prime

Updated 2015-07-28 08:12:11 by aspect

Tcl Static Prime (TSP) is an experimental compiler for the Tcl language that produces C or Java code, which is then compiled on-the-fly during execution of a Tcl program. TSP is a currently a work-in-progress; it's performance varies greatly depending the Tcl commands that are currently compiled.

TSP compiles a typed subset of Tcl. Proc definitions and variables are typed by comment-based annotations. Native types supported are boolean, int (64-bit integers), double, string, and var (TclObjects for lists, dicts, etc.)

TSP language restrictions include restricting all arithmetic expressions (expr, if, while, etc) to using boolean, int, double, and string data types. Additionally, expressions may not include array references or nested commands. TSP also assumes that builtin Tcl commands are not re-defined, as builtin commands are compiled to C or Java, or the native command implementation is invoked directly, bypassing the Tcl interpreter.

TSP is written entirely in Tcl, with support libraries written in C and Java.

TSP is written by Tom Poindexter (TP).

TSP development is hosted at Github: https://github.com/tpoindex/tsp


Very, very, very preliminary results (July, 2015) Timing on my local machine, 3.0ghz i7.

md5 - This is a slightly modified version of the md5 function included in Tcllib, version 1.4.4. Various size message are tested. Times are in seconds. Timings for both C/Tcl and JTcl.

msg size: ---32 bytes--- ---4k bytes--- --64k bytes--- --256k bytes--
tcl 8.6.3 0.0003683 0.0239789 0.3650953 1.4585577
jtcl 2.8.0 0.0008000 0.0339000 0.5122000 2.0477000
tcl + tsp 0.0000532 0.0001546 0.0020362 0.0072202
jtcl + tsp 0.0000000 0.0004000 0.0058000 0.0128000

langbench - Larry McVoy's langbench, using slightly modified versions of the Tcl programs found in the benchmark. Several other notable changes to how the benchmark was prepared and run should be reviewed . Times are in seconds.

lang cat grep hash loop proc fib sort wc
tcl 8.6.3 1.34 2.77 1.25 0.03 0.36 3.73 2.44 20.03
tcl + tsp 0.80 2.63 0.94 0.00 0.13 0.57 2.00 28.25

Notes - I've been working on this off and on for over two years, and thought it was about time TSP escaped out of the lab. TSP currently has about 9,700 lines of Tcl, 2,400 lines of C, and 750 lines of Java. All of my development has been on Linux, but since it's nearly all written in Tcl, there should be some degree of portability to OSX & Windows.

I haven't been able to find much time lately to work on it, so I'm hoping posting it now will spur some interest in others who might like to help out, test new ideas, work on code generation, etc. Interested in contributing? Start by forking the Github repository. I'm often logged into the Tcl Chatroom most weekdays for quick questions, or feel free to email.


aspect: this is fantastic! I made a little chart with ukaz using the test_fib example to get my feet wet. I stopped benchmarking each when a computation took more than 1s: interpreted got fib(31) = 1346269, compiled to fib(36) = 14930352.

tsp-fib-benchmark.png

Reading the implementation is going to be a lot of fun!

The benchmark script is hidden below this discussion tag, in the unlikely case it's useful to derive more:

package require tsp
package require ukaz

tsp::proc tsp_fib {n} {
    #tsp::procdef int -args int
    if {$n < 2} {
        return $n
    }
    #tsp::int n1 n2
    incr n -1
    set n1 [tsp_fib $n]
    incr n -1
    set n2 [tsp_fib $n]
    set n [expr {$n1 + $n2}]
    return $n
}

proc fib {n} {
    if {$n < 2} {
        return $n
    }
    incr n -1
    set n1 [fib $n]
    incr n -1
    set n2 [fib $n]
    set n [expr {$n1 + $n2}]
    return $n
}

proc elapsed {cmd} {
    set s -[clock microseconds]
    uplevel 1 $cmd
    incr s [clock microseconds]
    set s [expr {$s / 1e6}]
    return $s
}


set ctimes {0 0}
set itimes {0 0}

set maxtime 1   ;# stop measuring once an iteration takes this long
set cok 1
set iok 1

pack [ukaz::graph .l] -expand yes -fill both
set cg [.l plot $ctimes with lines color red title "Compiled fib"]
set ig [.l plot $itimes with lines color blue title "Interpreted fib"]
.l set xlabel "N"
.l set ylabel "Seconds"

for {set i 1} {$i < Inf} {incr i} {
    if {$cok} {
        set ctime [elapsed {set cr [tsp_fib $i]}]
        .l update $cg data [lappend ctimes $i $ctime]
        set cok [expr {$ctime < $maxtime}]
        update
    }
    if {$iok} {
        set itime [elapsed {set ir [fib $i]}]
        .l update $ig data [lappend itimes $i $itime]
        set iok [expr {$itime < $maxtime}]
        update
    }
    if {!($cok || $iok)} {break}
    if {($cok && $iok)} {
        if {$cr ne $ir} {
            puts "ERROR: results differ for $i ($cr vs $ir)"
            break
        }
    }
}