Re: Tcl/Lisp/Python: A "User" point of view

John Ousterhout (ouster@tcl.eng.sun.com)
29 Sep 1994 16:11:33 GMT

In article <36cafa$5ue@btree.brooktree.com>, mdimeo@brooktree.com (Matt DiMeo) writes:
|>
|> The users will care about O(1) vs. O(n) as soon as they notice how long it
|> takes for tcl to build up a ten thousand element list.
|>
|> tst.tcl------------------
|> set l ""
|> for { set i 0 } { $i < 10000 } { incr i } {
|> lvarpush l $i
|> }
|> -------------------------
|>
|> tst.perl-----------------
|> for ($i = 0 ; $i < 10000 ; $i++) {
|> unshift(@f, $i) ;
|> }
|> -------------------------
|>
|> {/home/mdimeo}% /bin/time /cad/bin/perl tst.perl
|> 4.8 real 4.6 user 0.0 sys
|> {/home/mdimeo}% /bin/time tcl tst.tcl
|> ^CCommand terminated abnormally.
|> 334.2 real 326.7 user 0.2 sys
|>
|> I control-C'd the tcl one, 'cause I got tired of waiting. You get the idea.
|> Lisp would have been fast, probably faster than perl.
|>

I'm getting a little weary of the discussion of O(1) vs. O(n). There are
many things in Tcl worthy of criticism, I'm sure, but please don't criticize
list append time until you've tried the "lappend" command. It is specially
designed to append elements to a list in constant time regardless of
the list's length. For example, consider the following file "foo":

for {set i 0} {$i < 10000} {incr i} {
lappend x $i
}

Now look at the following sequence of commands run under Tcl:

% set x {}
% time {source foo}
2018672 microseconds
% time {source foo}
1984031 microseconds
% time {source foo}
1982729 microseconds
% time {source foo}
1985394 microseconds
% llength $x
40000

Each execution of the program (10000 appends) took about 2 seconds;
for comparison, the Perl example from Matt DiMeo's message took about
4 seconds on my machine, or twice as long as Tcl. Note also that
each run adds on to the previous result, so the list gets longer and
longer through the four runs, yet the execution time does not increase.

There are many other ways of using lists in Tcl that have longer
running times, but the common operation of appending does not. The
other operations won't speed up until the Tcl compiler gets built.