Concatenating lists

From a recent query on comp.lang.tcl on combining 2 list into a single list:

Here is the test code used:

proc SET         {l1 l2} { set l1 "$l1 $l2" }
proc APPEND      {l1 l2} { append l1 " $l2" }
proc APPEND2     {l1 l2} { append l1 " " $l2 } ; # LH, 2008-06-12: Should be better than APPEND, since it avoids copying the $l2 data twice!
proc CONCAT      {l1 l2} { set l1 [concat $l1 $l2] }
proc EVAL/LAPPEND {l1 l2} { eval [list lappend l1] $l2 }
proc FOREACH/LAPPEND {l1 l2} {foreach i $l2 {lappend l1 $i} ; set l1}
proc EXPAND      {l1 l2} { lappend l1 {*}$l2 } ; # requires Tcl 8.5
set cases "SET APPEND APPEND2 CONCAT EVAL/LAPPEND FOREACH/LAPPEND"
if {![catch {package require Tcl 8.5}]} then {lappend cases EXPAND}

proc makeList {len item} {
    for {set i 0} {$i< $len} {incr i} {
        lappend res $item
    }
    return $res
}

proc testem {len} {
    global cases
    set res {}
    foreach p $cases {
        catch {unset l1}
        catch {unset l2}
        set l1 [makeList $len a]
        set l2 [makeList $len b]
        puts -nonewline stderr "$p..." ; flush stderr
        lappend res $p,$len [lindex [time {llength [$p $l1 $l2]} 1000] 0]
    }
    return $res
}


foreach l {10 100 1000 10000} {
    puts -nonewline stderr "testing size $l..." ; flush stderr
    array set data [testem $l]
    puts stderr done ; flush stderr
}

puts "Tcl Version - [info patchlevel]\n"

set fmtstr "| %15s | %7.1f | %7.1f | %7.1f | %7.1f |"
set divid  "|-----------------|---------|---------|---------|---------|"
set ends   "|---------------------------------------------------------|"

puts $ends
puts [format $fmtstr Method 10 100 1000 10000]
puts $divid

foreach p $cases {
    puts [format $fmtstr $p \
                $data($p,10) $data($p,100) \
                $data($p,1000) $data($p,10000)]
}

puts $ends

And here are the results on an oLder alPha box running Tru64 UNIX

 Tcl Version - 7.4p3
Method 10 100 1000 10000
SET 14 45 1298 12978
APPEND 13 43 1474 12787
CONCAT 17 57 1639 15712
EVAL/LAPPEND 29 104 3494 34986
FOREACH/LAPPEND 42 796 10501 105971
 Tcl Version - 7.5  
Method 10 100 1000 10000
SET 15 45 1334 13277
APPEND 14 45 1396 12904
CONCAT 18 54 1632 16561
EVAL/LAPPEND 26 108 3635 36794
FOREACH/LAPPEND 44 832 11428 114468
 Tcl Version - 7.6
Method 10 100 1000 10000
SET 21 64 1592 17324
APPEND 21 62 1801 15949
CONCAT 28 72 2237 19821
EVAL/LAPPEND 43 719 6153 66896
FOREACH/LAPPEND 80 2261 22370 232325
 Tcl Version - 8.0
Method 10 100 1000 10000
SET 20 146 6727 61365
APPEND 27 215 7527 72501
CONCAT 21 661 6224 63780
EVAL/LAPPEND 34 344 3140 24726
FOREACH/LAPPEND 37 1018 10688 107653
 Tcl Version - 8.2.0
Method 10 100 1000 10000
SET 20 145 6611 67115
APPEND 28 176 7485 78008
CONCAT 21 598 6069 67277
EVAL/LAPPEND 31 172 2805 26525
FOREACH/LAPPEND 36 925 10676 108879
 Tcl Version - 8.4a4
Method10100100010000
SET 21150655569080
APPEND28391817282023
CONCAT9143385830
EVAL/LAPPEND15287955956
FOREACH/LAPPEND19530425945044

Here are results for the 2008 version of the test, on a different machine. Tcl Version is 8.4.10

Method 10.0 100.0 1000.0 10000.0
SET 25.3 203.7 2164.9 25546.0
APPEND 31.5 227.8 2422.6 28924.0
APPEND2 31.6 227.1 2418.7 28432.2
CONCAT 6.9 10.1 44.8 746.8
EVAL/LAPPEND 13.1 19.4 84.8 1937.0
FOREACH/LAPPEND 10.9 51.3 459.9 5326.5

Results for Tcl 8.6a0 on a 2GHz Dual-core MacBook (including the EXPAND variant):

Method 10.0 100.0 1000.0 10000.0
SET 6.1 32.9 337.6 3586.4
APPEND 7.7 37.9 381.0 4139.5
APPEND2 8.2 37.7 381.7 4080.2
CONCAT 2.1 2.7 13.4 241.9
EVAL/LAPPEND 4.5 8.7 64.6 882.5
FOREACH/LAPPEND 5.3 26.2 260.8 2741.6
EXPAND 2.4 3.6 20.1 304.9

Results for Tcl 8.6.0 on a 2GHz Windows Vista 32 bit:

Method 10.0 100.0 1000.0 10000.0
SET 13.4 93.7 812.5 8197.3
APPEND 18.2 89.6 905.6 9144.4
APPEND2 19.6 90.0 891.7 9128.2
CONCAT 5.5 6.8 38.5 350.2
EVAL/LAPPEND 9.4 10.8 57.5 527.5
FOREACH/LAPPEND 12.2 50.1 458.3 4570.7
EXPAND 6.3 9.2 55.2 515.6

How do I interpret these results?

The entries in the tables are the times (in microseconds) it takes to concatenate two lists of length equal to the column heading, using the method in the row heading. The smaller the number, the faster the method.

Experienced Tclers may find it strange that concat should be faster than eval+lappend or lappend+{*}, but this is because the test considers a functional operation; there is no unshared base list that can be modified in place. As given, concat should win this, since the test is exactly to do a concat of lists! The strange thing is rather that concat loses to eval+lappend in 8.0 and 8.2, but maybe it didn't make use of the internal representation of lists before 8.4?


AMG, 25 Nov 2006: While writing Directory recursion, I verified that [list] + {*} is faster than [concat].

AMG, 20 Feb 2013: Not so much anymore. Now [concat] is faster.

set list [lrepeat 100 asdf]; list
proc a {} {list {*}$::list {*}$::list}
proc b {} {concat $::list $::list}
a; list
b; list
time a 1000000; # 2.332994 microseconds per iteration
time b 1000000; # 1.583927 microseconds per iteration