Tcl Source Code

The following type introduces a new objtype 'cons', which is simply a two-element list (named by analogy with Lisp's fundamental data structures). The advantage over plain lists is the absence of heap-allocated space for the internal rep, since twoPtrValue is enough to hold the two pointers.

The script-visible part is as follows:

 - [cons $a $b] creates a Cons of elements $a and $b
 - the string repr of [cons $a $b] is the same as [list $a $b]'s

Important details behind the scenes:

 - [lindex] and [lsort -index] access Conses transparently *without shimmering*

 - all other list ops do shimmer as they should, giving them the intuitively expected semantics (By going through the string rep for now. A shortcut is imagineable).

Timing results below.

Summary: 

- Cons is nearly 2x faster and 1.7x smaller-memory than List for building a large (10 million) list of pairs.

- This list is typical of an [lsort -index] task

- The [lsort -index] speed is then exactly the same

Perspective:

The cons can be a useful replacement for lists everywhere a small structure is needed. That is notably the case of the Maybe monad proposed by Neil Madden to solve the NULL issue:

    [cons 0 ""] -> Nothing
    [cons 1 $x] -> Some $x



***CONS***

Alex@DELLALEX /src/cvs/tcl/win
$ ./tclsh86.exe
% proc g n {set l {};for {set i 0} {$i<$n} {incr i} {lappend l [cons $i $i]};return $l}
% time {set big [g 10000000];set x 1}
4288955 microseconds per iteration
% time {set big [g 10000000];set x 1}
3746134 microseconds per iteration
% time {set big [g 10000000];set x 1}
3697388 microseconds per iteration

% time {set srt [lsort -index 0 -integer -decreasing $big];set x 1}
2301849 microseconds per iteration
% time {set srt [lsort -index 0 -integer -decreasing $big];set x 1}
2683979 microseconds per iteration
% exit
(process VM ~474M)


***LIST***

Alex@DELLALEX /src/cvs/tcl/win
$ ./tclsh86.exe
% proc f n {set l {};for {set i 0} {$i<$n} {incr i} {lappend l [list $i $i]};return $l}
% time {set big [f 10000000];set x 1}
7609976 microseconds per iteration
% time {set big [f 10000000];set x 1}
6912197 microseconds per iteration
% time {set big [f 10000000];set x 1}
7021424 microseconds per iteration

% time {set srt [lsort -index 0 -integer -decreasing $big];set x 1}
2304322 microseconds per iteration
% time {set srt [lsort -index 0 -integer -decreasing $big];set x 1}
2703814 microseconds per iteration
% exit
(process VM ~796M)

Logged In: YES 
user_id=496139
Originator: YES

Yes, that was an option I proposed during the discussion of the Cons.
However, it needs pondering yet, because there are two options:

(a) either keep it as a separate Cons type. In that case, [list $a $b] will violate an "intuitive" contract, saying that an object just created with Tcl_NewListObj() *is* of type tclListType. Maybe this is mild, maybe not, dunno yet. Also, absolutely all list operations must be adapted to handle Cons without shimmering back to List. Some work.

(b) or do all this within the List type. The problem here is that the access to the list's intrep is not abstracted; hence there are dozens of places with hard-coded (List *)xxx->twoPtrValue.Ptr1, and even ->elements and ->elemCount despite the access macros.
Yet more work :-}

Now if you see an alternative, I'm open (but please identify yourself next time ;-)

Logged In: NO 

It looks like [cons $a $b] is exactly equivalent to [list $a $b] from
the script level, and cons is just an optimisation.

I would guess most code that today uses two-arg [list] would benefit
from this optimisation, so why not just make this new internal rep
an optimisation in the [list] command, instead of making a new api?

Could then be done without any TIP.

File Added - 281358: cons.patch