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
Method | 10 | 100 | 1000 | 10000 |
---|---|---|---|---|
SET | 21 | 150 | 6555 | 69080 |
APPEND | 28 | 391 | 8172 | 82023 |
CONCAT | 9 | 14 | 338 | 5830 |
EVAL/LAPPEND | 15 | 28 | 795 | 5956 |
FOREACH/LAPPEND | 19 | 530 | 4259 | 45044 |
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