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

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

Category Performance