    Author:        Ashok P. Nadkarni <[email protected]>
    State:         Final
    Type:          Project
    Vote:          Done
    Created:       17-05-2022
    Tcl-Version:   8.7
    Keywords:      Tcl
    Tcl-Branch:    tip-625
    Vote-Summary   Accepted 3/0/0
    Votes-For:     BG, JN, KW
    Votes-Against: none
    Votes-Present: none

Abstract
Rationale
Specification
- Internal representation
Performance
- Performance testing scripts
- Performance measurements
  - list and list expansion
  - lappend
  - linsert
  - lrange
  - lassign
  - lpop
  - lset
  - lremove
  - lreplace
  - lreverse
  - lsort
  - lsearch
  - concat
  - lindex
  - join
  - split
  - llength
  - lrepeat
  - lmap
  - foreach
- Memory statistics
  - Memory leaks
  - Memory usage
Tests
Implementation
Copyright

Abstract

The current implementation of lists in Tcl is efficient for operations on the tail but can be slow in many other cases. This TIP proposes an alternate implementation to improve performance while maintaining full compatibility at both the script and public C API levels. No new functionality is proposed. Performance measurements are included for all list commands to support the case for the new implementation.

Although the TIP targets 8.7, there is nothing in the implementation that would prevent integration with 8.6.

Rationale

The current list implementation is based on an internal representation that stores elements in a reference counted structure with a dynamically sized array field at the end. Allocations after the initial creation include extra trailing space so that new elements can be quickly appended without reallocation. Deletion from the back is also quick as it only requires updating a count. Both these optimizations however require the list Tcl_Obj as well as the internal representation to be unshared, which although not infrequent, limits their applicability even accounting for the K operator idiom.

The proposed implementation is also based on a variable size struct used to store the list elements. As before, the initial allocation of list structures is of the exact required size. However, reallocations caused by list operations leave optional additional space in the front as well as the back. The same efficiencies that apply to list tails in the current implementation can thus also be applied to the list head. In addition, a list Tcl_Obj internal representation includes an optional span structure that delineates a subrange of elements in the master structure.

The changes have the following benefits in performance for some frequently used operations:

Range operations are very fast, even for shared objects.
Deletions from the head and tail are very fast since these boil down to range operations. Again, this applies to shared objects as well.
Insertions at head of unshared objects are as fast as appending. Under some circumstances, this is possible even when the object is shared.

The measured performance of all commands for a number of conditions is given in Performance. Aside from obvious issues of correctness, the content of that section should determine acceptance or rejection of the TIP.

The following sample sequences illustrate some of the more substantial improvements for value based list commands.

** 8.7 **

% timerate -calibrate {}
0.03367925540411432 µs/#-overhead 0.033679 µs/# 57958526 # 29691867 #/sec
% set L [lrepeat 1001 x] ; set idx 0
0
% timerate {lrange $L 1 end-1}
4.904651 µs/# 202498 # 203888 #/sec 993.182 net-ms
% timerate {set L [linsert $L $idx x]} 1000 1000
6.572000 µs/# 1000 # 152160 #/sec 6.572 net-ms
% timerate {set L [lremove $L end]} 1000 1000
6.004000 µs/# 1000 # 166555 #/sec 6.004 net-ms
% timerate {set L [lassign $L x]} 1000 1000
2.305000 µs/# 1000 # 433839 #/sec 2.305 net-ms

** TIP 625 **

% timerate -calibrate {}
0.03181002427730623 µs/#-overhead 0.031810 µs/# 61364304 # 31436631 #/sec
% set L [lrepeat 1001 x] ; set idx 0
0
% timerate {lrange $L 1 end-1}
0.125190 µs/# 6369421 # 7987846 #/sec 797.389 net-ms
% timerate {set L [linsert $L $idx x]} 1000 1000
0.499000 µs/# 1000 # 2004008 #/sec 0.499 net-ms
% timerate {set L [lremove $L end]} 1000 1000
0.503000 µs/# 1000 # 1988071 #/sec 0.503 net-ms
% timerate {set L [lassign $L x]} 1000 1000
0.286000 µs/# 1000 # 3496503 #/sec 0.286 net-ms

The improvement is even more pronounced with larger lists.

Commands that operate on list variables show similar improvements when operating on shared values. Benefits on unshared values are less pronounced but still present in many cases.

Commands that show significant improvement (multiples) in specific cases include linsert, lrange, lassign, lreplace, lpop and lremove. The Performance section has the details.

In addition to execution time, memory usage is also a consideration when it comes to performance. Sharing of storage as above raises issues with regard to when unreachable memory is actually freed. This is discussed in Memory usage.

Specification

Internal representation

The internal representation of a list is implemented through three structs.

The ListStore struct is a structure that includes a variable size array that serves as storage for a Tcl list. A contiguous sequence of slots in the array, the in-use area, holds valid pointers to Tcl_Obj values that belong to one or more Tcl lists. The unused slots before and after these are free slots that may be used to prepend and append to the list without having to reallocate the struct. The ListStore may be shared amongst multiple lists and is reference counted.

typedef struct ListStore {
    int refCount;      /* Count of references to this span record */
    int firstUsed;     /* Index of first slot in use within the slots[] array */
    int numUsed;       /* Number of slots in use (starting at index firstUsed) */
    int numAllocated;  /* Total number of slots[] array slots. */
    int flags;         /* LISTSTORE_* flags */
    Tcl_Obj *slots[1]; /* Variable size array to be grown as needed */
} ListStore;

A ListSpan struct defines a sequence of slots within a ListStore. This sequence always lies within the in-use area of the ListStore. Like ListStore, the structure may be shared among multiple lists and is reference counted.

typedef struct ListSpan {
    int refCount;     /* Count of references to this span record */
    int spanStart;    /* Starting index within parentList where the span */
    int spanLength;   /* Number of elements in the span */
} ListSpan;

A ListRep struct holds the internal representation of a Tcl list as stored in a Tcl_Obj. It is composed of a ListStore and a ListSpan that together define the content of the list. The ListSpan specifies the range of slots within the ListStore that hold elements for this list. The ListSpan is optional in which case the list includes all the in-use slots of the ListStore.

typedef struct ListRep {
    ListStore *storePtr;/* Storage area shared amongst different lists */
    ListSpan *spanPtr;  /* If not NULL, the span holds the range of slots 
                           within *storePtr that contain this list elements. */
} ListRep;

Invariants

In addition to the obvious invariants related to correctness, such as relations between indices and lengths, the implementation maintains the following invariants as a design choice.

If a ListStore is referenced from any ListRep/Tcl_Obj whose spanPtr field is NULL, the firstUsed field of the ListStore must be 0, i.e. the in-use area begins right at the front. To put it another way, if a ListRep does not have a span, its ListStore has no free space in the front. This invariant is not mandated for correctness, but maintaining it permits prepending to even shared ListStore instances under certain conditions as described in Insertion.
List objects created from other types (via the string representation) always have NULL spans. This means a list object created with a span will always start without a string representation and thus have a canonical string representation when it is generated. This is used in determining Canonical lists.

ListStore space allocation

When a ListRep list internal representation is created through Tcl_NewListObj or through conversion from another internal type, a ListStore is created with the slots[] array of size exactly that requested. As in the pre-TIP 625 implementation, no extra space is allocated. The rationale for this is that lists are often created and never modified thereafter so the extra space is wasted.

On the other hand, when a command such as lappend requires reallocation, a ListStore is allocated with twice the space required by the current request. This is based on the assumption that once an operation is executed it is likely that further operations will be also be invoked. Allocating additional space up front makes these much more efficient.

The above allocation strategy applies to the pre-TIP 625 list implementation as well as the proposed one. The differences are

While all extra space in the pre-TIP 625 implementation is trailing, the proposed implementation apportions it between the leading and trailing areas as described below.
When a list operation results in a smaller list, if the space in-use has shrunk to less than a quarter of the allocated space, the ListStore is reallocated. This memory usage optimization is orthogonal to the rest of this TIP and may be removed without affecting anything else.

Apportioning of additional space

When reallocation is triggered by an operation that increases the list size, the additional allocated space is apportioned between the front and the back in the following manner.

For operations that append elements, if it is likely that the list has only had append opertions invoked (can be determined through the absence of a span), all extra space is allocated to the back. Otherwise, three fourth of the extra space is allocated to the back and a fourth to the front.
For operations that prepend elements, three fourth of the extra space is allocated to the front and a fourth to the back.
For operations that insert in the middle, the additional space is equally allocated to the front and the back.

The above heuristic is plucked out of thin air, so to speak, but does not seem entirely unreasonable based on benchmarks. It is completely subject to change.

Space management in unshared representation

When both the Tcl_Obj and its ListRep are unshared, the in-use area within the ListStore may be moved to make room for new elements assuming the total allocated space is large enough. In the pre-TIP 625 implementation, elements can only be shifted upward (to higher index slots) since any allocated space is always at the back. The availability of leading space in the proposed implementation enables additional optimization. Assuming the availability of both leading and trailing free space, the implementation chooses to move the smaller segment. For example, inserting at index 1 in a list will cause the single element at index 0 to be moved down to make room. Inserting at index end-1 on the other hand will cause the single element at the end to be moved up.

Span management

The introduction of spans into the internal representation of lists is the primary design change proposed by this TIP. The use of spans offers some significant advantages

A basic range operation implemented using spans is very fast. Since deletions from the front and back can be thought of as range operations, those benefit from the same speed-up.
A list with a spanned internal representation offers the same O(1) efficiency (instead of O(n)) for prepending as was previously available only for appending.

The speed up for even moderately sized (few thousand elements) lists can be orders of magnitude faster for some operations as presented in the Performance section.

However, use of spans also has some drawbacks.

There is a execution cost associated with allocating an additional block of memory to hold the ListSpan struct if not already existing.
There is a potential memory cost in holding on to more memory than necessary. For example, consider a lrange command that extracts 5 elements from a list of a thousand elements. If the source list object is released after use, a span based implementation would hold on to the 1000-element ListStore even though only five elements were actually being referenced.

The code implements certain allocation policies to tackle the above issues. See Memory usage for a further discussion.

Performance

The whole motivation for this TIP is performance so this section provides supporting data in the form of benchmark results for all the list commands.

Needless to say, all the standard cautions regarding interpretation of benchmarks apply.

Performance testing scripts

The numbers in this section are generated with the listPerf.tcl and comparePerf.tcl scripts in the tests-perf directory. The former generates test data for a Tcl implementation while the latter is used to compare multiple test runs. For example, the tables for the lappend command can be generated by

d:\tcl\core-8-branch\x64\bin\tclsh87.exe listPerf.tcl --label core-8-branch lappend > core-8-branch.perf 
d:\tcl\tip-625\bin\tclsh87.exe listPerf.tcl --label tip-625 lappend > tip-625.perf
tclsh comparePerf.tcl --print-test-number core-8-branch tip-625

Not specifying the command (lappend above) will measure all list commands. Both scripts have various options to control list lengths, run iterations and so on. See the script source for details.

Some caveats to keep in mind when interpreting results.

There is a fair amount of relative variance in results for smaller list sizes. When running these scripts on Windows, it is very important to turn off all unnecessary services and background shell processes. This greatly reduces variance from run to run. The same is likely true on other platforms. To account for other applications interfering, the test results are based on running each test multiple times and averaging after discarding outliers (depending on total iterations).
There is some difficulty in devising tests for unshared values. The overhead for generating unshared values overshadows the actual test despite the use of timerate calibration and -overhead options.
Currently there is a minimum list size threshold of 100 ( arbitrary and subject to change after further measurements) for generating span based lists. Thus the rows for lists of 100 items or fewer should show little difference.

Performance measurements

Note: These are preliminary figures. Both the implementation and tests need tuning.

All tests run on 64-bit Windows 10.

In the tables below, the first column [1] is the baseline 8.7 time in usecs. Column [2] is the TIP 625 time in usecs and ratio of baseline time to TIP 625 time (so 2.0 means TIP 625 is twice as fast).

list and list expansion

List creation from string

List creation is unaffected by TIP 625. The span in the Tcl_Obj is simply set to NULL.

           [1]           [2]
1.     0.24900|   0.24350|1.02  |list L[10] from a string
2.     0.24410|   0.25000|0.98  |list L[100] from a string
3.     0.24200|   0.26010|0.93  |list L[1000] from a string
4.     0.24360|   0.24190|1.01  |list L[10000] from a string

List creation from expanded lists

List expansion using the {*} operator is unchanged. The performance improvements in rows 9 and 12 should be ignored as creating a list from a single list degenerates into a range operation which is optimized in TIP 625. It is not generally applicable to the expansion operator.

5.     0.26960|   0.28310|0.95  |list L[10] from a {*}list
6.     0.43100|   0.42870|1.01  |list L[10] from a {*}list {*}list
7.     0.55480|   0.54280|1.02  |list L[100] from a {*}list
8.     0.73070|   0.67800|1.08  |list L[100] from a {*}list {*}list
9.     3.17630|   0.26440|12.01 |list L[1000] from a {*}list
10.    3.51040|   3.14870|1.11  |list L[1000] from a {*}list {*}list
11.   29.95070|   0.25500|117.45|list L[10000] from a {*}list
12.   31.90530|  28.23100|1.13  |list L[10000] from a {*}list {*}list

lappend

As seen from the table below, there is no real discernable difference between the pre-TIP 625 implementation and TIP 625. This is to be expected as both optimize list appends in almost identical fashion.

           [1]           [2]
1.     0.43330|   0.50000|0.87  |lappend L[5] shared 1 elems 10 times
2.     0.63000|   0.56670|1.11  |lappend L[50] shared 1 elems 100 times
3.     2.72930|   2.71200|1.01  |lappend L[500] shared 1 elems 1000 times
4.    26.32310|  24.00330|1.10  |lappend L[5000] shared 1 elems 10000 times
5.     0.20000|   0.20000|1.00  |lappend L[5] unshared 1 elems 10 times
6.     0.23000|   0.23000|1.00  |lappend L[50] unshared 1 elems 100 times
7.     0.22730|   0.22900|0.99  |lappend L[500] unshared 1 elems 1000 times
8.     0.22930|   0.22840|1.00  |lappend L[5000] unshared 1 elems 10000 times
9.     0.33330|   0.36670|0.91  |lappend L[5] unshared-span 1 elems 10 times
10.    0.25000|   0.26000|0.96  |lappend L[50] unshared-span 1 elems 100 times
11.    0.23930|   0.24170|0.99  |lappend L[500] unshared-span 1 elems 1000 times
12.    0.23750|   0.23980|0.99  |lappend L[5000] unshared-span 1 elems 10000 times
13.   32.06250|  29.77750|1.08  |lappend total run time
14.   32.06250|  29.77750|1.08  |Total run time

linsert

The linsert code pre-TIP 625 takes a different path when the index is a constant from when it is a variable. In the former case the command is executed entirely in byte code and is unchanged in TIP 625. The latter case is implemented as a C function and has a new implementation in TIP 625.

The tables below are split based on the above in addition to the usual distinction between shared and unshared values.

Insertion into an shared list at a variable index

As expected, the greatest improvement in performance with TIP 625 for insert operations is for repeated insertions at index 0 (rows 6, 7, 9, 10, 12, 13). The improvement comes from the free leading space in a ListStore that allows constant time insertion. Note this is true even when the value is shared provided certain conditions are met. The magnitude of the improvement depends on the list size and number of insertions ranging from 6x to 30x in the test cases.

The initial insert at index 0 (rows 5, 8, 11) shows no improvement. This is because the initial list allocation is always an exact size as in the pre-TIP 625 implementation, with extra space only allocated on the first insertion.

Insertions at other indices has no change in performance as the list storage must always be reallocated when shared.

Insertions at the end also do not exhibit any change in performance for the same reason. However, if the implementation was modified to always allocate a span for every list, it would see similar gains as insertions at index 0. This is currently not done to avoid allocating spans on initial allocation.

           [1]           [2]
1.     0.24750|   0.24850|1.00  |linsert L[0] shared 1 elems 1 times at 0 (var)
2.     0.49820|   0.50050|1.00  |linsert L[10] shared 1 elems 1 times at 0 (var)
3.     2.06970|   0.42600|4.86  |linsert L[10] shared 1 elems 1000 times at 0 (var)
4.     8.91400|   0.59570|14.96 |linsert L[10] shared 5 elems 1000 times at 0 (var)
5.     0.78810|   0.71840|1.10  |linsert L[100] shared 1 elems 1 times at 0 (var)
6.     2.33900|   0.44600|5.24  |linsert L[100] shared 1 elems 1000 times at 0 (var)
7.     9.21300|   0.46500|19.81 |linsert L[100] shared 5 elems 1000 times at 0 (var)
8.     3.79430|   3.21220|1.18  |linsert L[1000] shared 1 elems 1 times at 0 (var)
9.     5.31230|   0.43000|12.35 |linsert L[1000] shared 1 elems 1000 times at 0 (var)
10.   12.25630|   0.47670|25.71 |linsert L[1000] shared 5 elems 1000 times at 0 (var)
11.   35.11010|  30.28560|1.16  |linsert L[10000] shared 1 elems 1 times at 0 (var)
12.   36.58100|   0.46070|79.40 |linsert L[10000] shared 1 elems 1000 times at 0 (var)
13.   43.44170|   0.45030|96.47 |linsert L[10000] shared 5 elems 1000 times at 0 (var)
14.    0.56020|   0.52930|1.06  |linsert L[10] shared 1 elems 1 times at 1 (var)
15.    2.25070|   1.82030|1.24  |linsert L[10] shared 1 elems 1000 times at 1 (var)
16.    8.92330|   7.68870|1.16  |linsert L[10] shared 5 elems 1000 times at 1 (var)
17.    0.77570|   0.72540|1.07  |linsert L[100] shared 1 elems 1 times at 1 (var)
18.    2.34870|   2.09230|1.12  |linsert L[100] shared 1 elems 1000 times at 1 (var)
19.    9.16830|   7.92000|1.16  |linsert L[100] shared 5 elems 1000 times at 1 (var)
20.    3.81680|   3.20380|1.19  |linsert L[1000] shared 1 elems 1 times at 1 (var)
21.    5.28400|   4.88830|1.08  |linsert L[1000] shared 1 elems 1000 times at 1 (var)
22.   12.31270|  10.48970|1.17  |linsert L[1000] shared 5 elems 1000 times at 1 (var)
23.   34.92510|  30.19400|1.16  |linsert L[10000] shared 1 elems 1 times at 1 (var)
24.   36.73070|  31.81330|1.15  |linsert L[10000] shared 1 elems 1000 times at 1 (var)
25.   43.21970|  38.56530|1.12  |linsert L[10000] shared 5 elems 1000 times at 1 (var)
26.    0.47370|   0.46620|1.02  |linsert L[10] shared 1 elems 1 times at 5 (var)
27.    2.07530|   1.79370|1.16  |linsert L[10] shared 1 elems 1000 times at 5 (var)
28.    8.96530|   7.67570|1.17  |linsert L[10] shared 5 elems 1000 times at 5 (var)
29.    0.77590|   0.70820|1.10  |linsert L[100] shared 1 elems 1 times at 50 (var)
30.    2.32600|   2.04500|1.14  |linsert L[100] shared 1 elems 1000 times at 50 (var)
31.    9.35530|   7.75070|1.21  |linsert L[100] shared 5 elems 1000 times at 50 (var)
32.    3.75230|   3.40850|1.10  |linsert L[1000] shared 1 elems 1 times at 500 (var)
33.    5.26800|   4.70970|1.12  |linsert L[1000] shared 1 elems 1000 times at 500 (var)
34.   12.28930|  10.39000|1.18  |linsert L[1000] shared 5 elems 1000 times at 500 (var)
35.   35.06610|  30.19210|1.16  |linsert L[10000] shared 1 elems 1 times at 5000 (var)
36.   36.68430|  31.26800|1.17  |linsert L[10000] shared 1 elems 1000 times at 5000 (var)
37.   43.36100|  38.76800|1.12  |linsert L[10000] shared 5 elems 1000 times at 5000 (var)
38.    0.57700|   0.57900|1.00  |linsert L[10] shared 1 elems 1 times at end-1 (var)
39.    2.09770|   1.89870|1.10  |linsert L[10] shared 1 elems 1000 times at end-1 (var)
40.    9.05570|   7.55030|1.20  |linsert L[10] shared 5 elems 1000 times at end-1 (var)
41.    0.80080|   0.76280|1.05  |linsert L[100] shared 1 elems 1 times at end-1 (var)
42.    2.41200|   2.12630|1.13  |linsert L[100] shared 1 elems 1000 times at end-1 (var)
43.    9.32400|   7.77270|1.20  |linsert L[100] shared 5 elems 1000 times at end-1 (var)
44.    3.84790|   3.32180|1.16  |linsert L[1000] shared 1 elems 1 times at end-1 (var)
45.    5.35570|   4.80630|1.11  |linsert L[1000] shared 1 elems 1000 times at end-1 (var)
46.   12.37500|  10.41570|1.19  |linsert L[1000] shared 5 elems 1000 times at end-1 (var)
47.   35.28820|  30.29200|1.16  |linsert L[10000] shared 1 elems 1 times at end-1 (var)
48.   36.78430|  31.61500|1.16  |linsert L[10000] shared 1 elems 1000 times at end-1 (var)
49.   44.48700|  39.07300|1.14  |linsert L[10000] shared 5 elems 1000 times at end-1 (var)
50.    0.64420|   0.55340|1.16  |linsert L[10] shared 1 elems 1 times at end (var)
51.    2.11600|   1.85770|1.14  |linsert L[10] shared 1 elems 1000 times at end (var)
52.    9.00430|   7.62200|1.18  |linsert L[10] shared 5 elems 1000 times at end (var)
53.    0.79890|   0.74750|1.07  |linsert L[100] shared 1 elems 1 times at end (var)
54.    2.42330|   2.05930|1.18  |linsert L[100] shared 1 elems 1000 times at end (var)
55.    9.48700|   7.78170|1.22  |linsert L[100] shared 5 elems 1000 times at end (var)
56.    3.80500|   3.30070|1.15  |linsert L[1000] shared 1 elems 1 times at end (var)
57.    5.61330|   4.72230|1.19  |linsert L[1000] shared 1 elems 1000 times at end (var)
58.   12.48070|  10.33970|1.21  |linsert L[1000] shared 5 elems 1000 times at end (var)
59.   35.22460|  29.26230|1.20  |linsert L[10000] shared 1 elems 1 times at end (var)
60.   37.17000|  31.39700|1.18  |linsert L[10000] shared 1 elems 1000 times at end (var)
61.   43.76670|  38.58900|1.13  |linsert L[10000] shared 5 elems 1000 times at end (var)

Insertion into an unshared list at a variable index

The pre-TIP 625 implementation moves the contents of the list storage "in-place" when it is unshared and thus is fairly efficient as it is. As with the shared case, there is an measurable improvement with TIP 625 when repeated prepending but is much less pronounced since moving memory is fairly fast to begin with. The difference will however become more pronounced for larger lists.

Moreover, this improvement also carries over to the case where the insertion is at an index where the prefix is significantly shorter than the suffix around the insertion point (77, 78). This is because with spans, there is both free leading and trailing space permitting the shorter segment to be moved to make room for insertions.

           [1]           [2]
62.    0.18780|   0.20680|0.91  |linsert L[0] unshared 1 elems 1 times at 0 (var)
63.    1.10530|   0.55870|1.98  |linsert L[10] unshared 1 elems 1000 times at 0 (var)
64.    1.00530|   0.57400|1.75  |linsert L[10] unshared 5 elems 1000 times at 0 (var)
65.    0.67730|   0.55030|1.23  |linsert L[100] unshared 1 elems 1000 times at 0 (var)
66.    0.98700|   0.57030|1.73  |linsert L[100] unshared 5 elems 1000 times at 0 (var)
67.    0.78970|   0.52500|1.50  |linsert L[1000] unshared 1 elems 1000 times at 0 (var)
68.    1.21670|   0.56600|2.15  |linsert L[1000] unshared 5 elems 1000 times at 0 (var)
69.    2.55330|   0.54470|4.69  |linsert L[10000] unshared 1 elems 1000 times at 0 (var)
70.    2.89630|   0.56370|5.14  |linsert L[10000] unshared 5 elems 1000 times at 0 (var)
71.    0.63900|   0.71400|0.89  |linsert L[10] unshared 1 elems 1000 times at 1 (var)
72.    1.03970|   1.27100|0.82  |linsert L[10] unshared 5 elems 1000 times at 1 (var)
73.    0.68130|   1.00930|0.68  |linsert L[100] unshared 1 elems 1000 times at 1 (var)
74.    1.04000|   0.68200|1.52  |linsert L[100] unshared 5 elems 1000 times at 1 (var)
75.    1.53330|   1.02900|1.49  |linsert L[1000] unshared 1 elems 1000 times at 1 (var)
76.    1.61600|   1.21000|1.34  |linsert L[1000] unshared 5 elems 1000 times at 1 (var)
77.    2.74670|   0.59370|4.63  |linsert L[10000] unshared 1 elems 1000 times at 1 (var)
78.    3.16400|   0.56770|5.57  |linsert L[10000] unshared 5 elems 1000 times at 1 (var)
79.    1.09870|   0.99970|1.10  |linsert L[10] unshared 1 elems 1000 times at 5 (var)
80.    1.00570|   1.28030|0.79  |linsert L[10] unshared 5 elems 1000 times at 5 (var)
81.    1.15530|   0.54670|2.11  |linsert L[100] unshared 1 elems 1000 times at 50 (var)
82.    1.00000|   0.88270|1.13  |linsert L[100] unshared 5 elems 1000 times at 50 (var)
83.    0.72100|   0.59070|1.22  |linsert L[1000] unshared 1 elems 1000 times at 500 (var)
84.    1.11730|   1.06100|1.05  |linsert L[1000] unshared 5 elems 1000 times at 500 (var)
85.    1.66330|   1.24730|1.33  |linsert L[10000] unshared 1 elems 1000 times at 5000 (var)
86.    2.07230|   1.27530|1.62  |linsert L[10000] unshared 5 elems 1000 times at 5000 (var)
87.    1.07970|   0.60230|1.79  |linsert L[10] unshared 1 elems 1000 times at end-1 (var)
88.    0.60630|   0.78870|0.77  |linsert L[10] unshared 5 elems 1000 times at end-1 (var)
89.    0.90630|   1.05270|0.86  |linsert L[100] unshared 1 elems 1000 times at end-1 (var)
90.    0.64300|   0.69070|0.93  |linsert L[100] unshared 5 elems 1000 times at end-1 (var)
91.    0.63330|   1.04100|0.61  |linsert L[1000] unshared 1 elems 1000 times at end-1 (var)
92.    0.62530|   1.13900|0.55  |linsert L[1000] unshared 5 elems 1000 times at end-1 (var)
93.    0.59200|   0.58500|1.01  |linsert L[10000] unshared 1 elems 1000 times at end-1 (var)
94.    0.61400|   0.61170|1.00  |linsert L[10000] unshared 5 elems 1000 times at end-1 (var)
95.    0.62470|   0.55700|1.12  |linsert L[10] unshared 1 elems 1000 times at end (var)
96.    0.65270|   0.62330|1.05  |linsert L[10] unshared 5 elems 1000 times at end (var)
97.    1.02030|   1.00730|1.01  |linsert L[100] unshared 1 elems 1000 times at end (var)
98.    0.62070|   0.57630|1.08  |linsert L[100] unshared 5 elems 1000 times at end (var)
99.    0.62030|   0.56030|1.11  |linsert L[1000] unshared 1 elems 1000 times at end (var)
100.   0.64170|   0.89930|0.71  |linsert L[1000] unshared 5 elems 1000 times at end (var)
101.   0.57830|   0.57030|1.01  |linsert L[10000] unshared 1 elems 1000 times at end (var)
102.   0.64330|   0.62070|1.04  |linsert L[10000] unshared 5 elems 1000 times at end (var)

Insertion into an shared list at a constant index

While the variable index argument to linsert generates a callout to the Tcl_ListObjReplace C function, when an constant index is supplied for the linsert command, the generated byte code implements the command as a sequence of range and concat operations. It thus does not profit from the same efficiencies as the variable case. Nevertheless, at larger list sizes, there is a benefit as a consequence of the faster range operations implemented in TIP 625. This benefit is however mitigated by the fact that a new list object always has to be created which is always an expensive operation. The net improvement is therefore minor.

There is currently no plan to modify the compiler generated bytecode to take advantage of spans or any free space at the front of the list.

           [1]           [2]
103.   0.18540|   0.18130|1.02  |linsert L[0] shared 1 elems 1 times at 0 (const)
104.   0.25880|   0.26330|0.98  |linsert L[10] shared 1 elems 1 times at 0 (const)
105.   0.44330|   0.38000|1.17  |linsert L[10] shared 1 elems 100 times at 0 (const)
106.   1.22000|   0.96670|1.26  |linsert L[10] shared 5 elems 100 times at 0 (const)
107.   0.60530|   0.51480|1.18  |linsert L[100] shared 1 elems 1 times at 0 (const)
108.   0.73670|   0.62000|1.19  |linsert L[100] shared 1 elems 100 times at 0 (const)
109.   1.49330|   1.21330|1.23  |linsert L[100] shared 5 elems 100 times at 0 (const)
110.   3.95110|   2.93190|1.35  |linsert L[1000] shared 1 elems 1 times at 0 (const)
111.   4.13000|   3.28330|1.26  |linsert L[1000] shared 1 elems 100 times at 0 (const)
112.   4.97000|   3.83670|1.30  |linsert L[1000] shared 5 elems 100 times at 0 (const)
113.  38.36360|  28.76360|1.33  |linsert L[10000] shared 1 elems 1 times at 0 (const)
114.  37.51330|  29.32670|1.28  |linsert L[10000] shared 1 elems 100 times at 0 (const)
115.  39.89000|  30.17000|1.32  |linsert L[10000] shared 5 elems 100 times at 0 (const)
116.   0.47830|   0.51190|0.93  |linsert L[10] shared 1 elems 1 times at 1 (const)
117.   1.08000|   0.87330|1.24  |linsert L[10] shared 1 elems 100 times at 1 (const)
118.   3.25330|   1.90670|1.71  |linsert L[10] shared 5 elems 100 times at 1 (const)
119.   1.46070|   1.25230|1.17  |linsert L[100] shared 1 elems 1 times at 1 (const)
120.   1.89670|   1.64330|1.15  |linsert L[100] shared 1 elems 100 times at 1 (const)
121.   4.14000|   2.50000|1.66  |linsert L[100] shared 5 elems 100 times at 1 (const)
122.  11.23310|   5.98890|1.88  |linsert L[1000] shared 1 elems 1 times at 1 (const)
123.  11.66670|   6.32670|1.84  |linsert L[1000] shared 1 elems 100 times at 1 (const)
124.  14.07330|   7.62670|1.85  |linsert L[1000] shared 5 elems 100 times at 1 (const)
125. 112.16530|  58.52860|1.92  |linsert L[10000] shared 1 elems 1 times at 1 (const)
126. 113.97000|  60.19330|1.89  |linsert L[10000] shared 1 elems 100 times at 1 (const)
127. 115.52670|  62.52670|1.85  |linsert L[10000] shared 5 elems 100 times at 1 (const)
128.   0.50360|   0.50910|0.99  |linsert L[10] shared 1 elems 1 times at 5 (const)
129.   1.07000|   1.31000|0.82  |linsert L[10] shared 1 elems 100 times at 5 (const)
130.   3.20330|   1.90330|1.68  |linsert L[10] shared 5 elems 100 times at 5 (const)
131.   1.12490|   0.98450|1.14  |linsert L[100] shared 1 elems 1 times at 50 (const)
132.   1.61000|   1.35330|1.19  |linsert L[100] shared 1 elems 100 times at 50 (const)
133.   3.76000|   2.35330|1.60  |linsert L[100] shared 5 elems 100 times at 50 (const)
134.   7.66140|   4.52380|1.69  |linsert L[1000] shared 1 elems 1 times at 500 (const)
135.   8.06330|   6.87330|1.17  |linsert L[1000] shared 1 elems 100 times at 500 (const)
136.  10.31000|   8.18670|1.26  |linsert L[1000] shared 5 elems 100 times at 500 (const)
137.  75.09560|  43.91060|1.71  |linsert L[10000] shared 1 elems 1 times at 5000 (const)
138.  74.12000|  61.13670|1.21  |linsert L[10000] shared 1 elems 100 times at 5000 (const)
139.  77.89670|  63.89670|1.22  |linsert L[10000] shared 5 elems 100 times at 5000 (const)
140.   0.44220|   0.48840|0.91  |linsert L[10] shared 1 elems 1 times at 9 (const)
141.   1.07000|   0.89330|1.20  |linsert L[10] shared 1 elems 100 times at 9 (const)
142.   3.19670|   1.88670|1.69  |linsert L[10] shared 5 elems 100 times at 9 (const)
143.   0.73510|   0.73570|1.00  |linsert L[100] shared 1 elems 1 times at 99 (const)
144.   1.29330|   1.13000|1.14  |linsert L[100] shared 1 elems 100 times at 99 (const)
145.   3.45330|   2.33670|1.48  |linsert L[100] shared 5 elems 100 times at 99 (const)
146.   3.94120|   3.12830|1.26  |linsert L[1000] shared 1 elems 1 times at 999 (const)
147.   5.15670|   3.70000|1.39  |linsert L[1000] shared 1 elems 100 times at 999 (const)
148.   6.80330|   5.69000|1.20  |linsert L[1000] shared 5 elems 100 times at 999 (const)
149.  37.68500|  28.63000|1.32  |linsert L[10000] shared 1 elems 1 times at 9999 (const)
150.  37.92000|  30.65330|1.24  |linsert L[10000] shared 1 elems 100 times at 9999 (const)
151.  41.80330|  31.68000|1.32  |linsert L[10000] shared 5 elems 100 times at 9999 (const)
152.   0.45730|   0.48470|0.94  |linsert L[10] shared 1 elems 1 times at 8 (const)
153.   1.05330|   2.13330|0.49  |linsert L[10] shared 1 elems 100 times at 8 (const)
154.   3.14000|   2.29670|1.37  |linsert L[10] shared 5 elems 100 times at 8 (const)
155.   0.76410|   0.71740|1.07  |linsert L[100] shared 1 elems 1 times at 98 (const)
156.   1.30670|   1.12330|1.16  |linsert L[100] shared 1 elems 100 times at 98 (const)
157.   3.47330|   2.30330|1.51  |linsert L[100] shared 5 elems 100 times at 98 (const)
158.   3.91820|   3.14420|1.25  |linsert L[1000] shared 1 elems 1 times at 998 (const)
159.   4.62670|   3.68330|1.26  |linsert L[1000] shared 1 elems 100 times at 998 (const)
160.   6.83330|   5.57000|1.23  |linsert L[1000] shared 5 elems 100 times at 998 (const)
161.  37.70950|  29.19590|1.29  |linsert L[10000] shared 1 elems 1 times at 9998 (const)
162.  38.74670|  29.55670|1.31  |linsert L[10000] shared 1 elems 100 times at 9998 (const)
163.  40.15670|  31.91330|1.26  |linsert L[10000] shared 5 elems 100 times at 9998 (const)

Insertion into an unshared list at a constant index

In the case of an unshared list the performance benefit can be significantly greater (15-35x) than the shared case (195, 196, 203, 204). This is because of the sequence of byte code operations generated which dups the operand list object, extracts the prefix and suffix ranges and concatenates them with the insertion objects in the middle. The prefix is extracted as a range from the dup'ed object which can be expensive in the pre-TIP 625 implementation when the prefix is long. In TIP 625 range operations on shared objects are still very efficient and hence the improvement in performance.

           [1]           [2]
164.   0.13330|   0.12820|1.04  |linsert L[0] unshared 1 elems 1 times at 0 (const)
165.   0.70330|   0.56330|1.25  |linsert L[10] unshared 1 elems 100 times at 0 (const)
166.   1.34670|   1.13000|1.19  |linsert L[10] unshared 5 elems 100 times at 0 (const)
167.   0.97330|   1.16000|0.84  |linsert L[100] unshared 1 elems 100 times at 0 (const)
168.   1.69000|   1.53000|1.10  |linsert L[100] unshared 5 elems 100 times at 0 (const)
169.   4.27000|   3.34330|1.28  |linsert L[1000] unshared 1 elems 100 times at 0 (const)
170.   5.30670|   4.06670|1.30  |linsert L[1000] unshared 5 elems 100 times at 0 (const)
171.  38.51330|  29.28330|1.32  |linsert L[10000] unshared 1 elems 100 times at 0 (const)
172.  39.07000|  30.26330|1.29  |linsert L[10000] unshared 5 elems 100 times at 0 (const)
173.   0.99670|   1.01330|0.98  |linsert L[10] unshared 1 elems 100 times at 1 (const)
174.   2.42670|   2.01330|1.21  |linsert L[10] unshared 5 elems 100 times at 1 (const)
175.   1.68670|   1.57670|1.07  |linsert L[100] unshared 1 elems 100 times at 1 (const)
176.   3.07000|   2.53330|1.21  |linsert L[100] unshared 5 elems 100 times at 1 (const)
177.   8.40670|   6.45000|1.30  |linsert L[1000] unshared 1 elems 100 times at 1 (const)
178.  10.08000|   7.74670|1.30  |linsert L[1000] unshared 5 elems 100 times at 1 (const)
179.  78.64330|  57.81670|1.36  |linsert L[10000] unshared 1 elems 100 times at 1 (const)
180.  79.64000|  59.39670|1.34  |linsert L[10000] unshared 5 elems 100 times at 1 (const)
181.   0.97000|   0.85000|1.14  |linsert L[10] unshared 1 elems 100 times at 5 (const)
182.   2.81670|   1.98330|1.42  |linsert L[10] unshared 5 elems 100 times at 5 (const)
183.   1.45000|   1.18670|1.22  |linsert L[100] unshared 1 elems 100 times at 50 (const)
184.   2.87670|   2.30000|1.25  |linsert L[100] unshared 5 elems 100 times at 50 (const)
185.   6.32000|   5.09000|1.24  |linsert L[1000] unshared 1 elems 100 times at 500 (const)
186.   7.62330|   6.20670|1.23  |linsert L[1000] unshared 5 elems 100 times at 500 (const)
187.  57.87330|  44.85670|1.29  |linsert L[10000] unshared 1 elems 100 times at 5000 (const)
188.  59.49000|  46.44330|1.28  |linsert L[10000] unshared 5 elems 100 times at 5000 (const)
189.   1.10670|   0.84670|1.31  |linsert L[10] unshared 1 elems 100 times at 9 (const)
190.   2.42670|   1.97670|1.23  |linsert L[10] unshared 5 elems 100 times at 9 (const)
191.   1.28000|   1.09330|1.17  |linsert L[100] unshared 1 elems 100 times at 99 (const)
192.   2.74330|   2.21670|1.24  |linsert L[100] unshared 5 elems 100 times at 99 (const)
193.   4.36000|   0.93000|4.69  |linsert L[1000] unshared 1 elems 100 times at 999 (const)
194.   5.99670|   2.57670|2.33  |linsert L[1000] unshared 5 elems 100 times at 999 (const)
195.  37.42000|   0.99670|37.54 |linsert L[10000] unshared 1 elems 100 times at 9999 (const)
196.  39.17670|   2.60330|15.05 |linsert L[10000] unshared 5 elems 100 times at 9999 (const)
197.   0.97330|   0.85000|1.15  |linsert L[10] unshared 1 elems 100 times at 8 (const)
198.   2.44000|   1.98000|1.23  |linsert L[10] unshared 5 elems 100 times at 8 (const)
199.   1.19000|   1.30670|0.91  |linsert L[100] unshared 1 elems 100 times at 98 (const)
200.   2.74670|   2.22000|1.24  |linsert L[100] unshared 5 elems 100 times at 98 (const)
201.   4.37000|   0.95000|4.60  |linsert L[1000] unshared 1 elems 100 times at 998 (const)
202.   6.00000|   2.57000|2.33  |linsert L[1000] unshared 5 elems 100 times at 998 (const)
203.  37.51000|   1.09330|34.31 |linsert L[10000] unshared 1 elems 100 times at 9998 (const)
204.  38.61330|   2.60670|14.81 |linsert L[10000] unshared 5 elems 100 times at 9998 (const)

Total run time

           [1]           [2]
205. 2530.56730|1705.90700|1.48  |linsert total run time

lrange

Extracting ranges from shared lists

Prior to TIP 625 range operations on shared lists involved allocating new list storage, copying the elements (pointers) within the range and incrementing all their reference counts. With the introduction of spans in TIP 625, this is reduced to allocating a ListSpan and storing the range endpoint indices. The improvement in performance is therefore considerable for even moderately sized ranges (20, 23, 24) and even more for larger ranges (32, 34, 35).

For smaller ranges spans are not used. See Memory usage.

           [1]           [2]
1.     0.21440|   0.25370|0.85  |lrange L[10] shared range 0 0
2.     0.25440|   0.25410|1.00  |lrange L[10] shared range 0 end-1
3.     0.24980|   0.24210|1.03  |lrange L[10] shared range 1 3
4.     0.21510|   0.22770|0.94  |lrange L[10] shared range 1 7
5.     0.23670|   0.23180|1.02  |lrange L[10] shared range 1 end
6.     0.20950|   0.26910|0.78  |lrange L[10] shared range end-1 end
7.     0.20490|   0.23460|0.87  |lrange L[100] shared range 0 0
8.     0.52390|   0.48350|1.08  |lrange L[100] shared range 0 end-1
9.     0.26780|   0.29530|0.91  |lrange L[100] shared range 12 36
10.    0.44480|   0.41870|1.06  |lrange L[100] shared range 12 84
11.    0.52210|   0.48630|1.07  |lrange L[100] shared range 1 end
12.    0.21310|   0.23690|0.90  |lrange L[100] shared range end-1 end
13.    0.25190|   0.22590|1.12  |lrange L[100] shared-span range 0 0
14.    0.53790|   0.48840|1.10  |lrange L[100] shared-span range 0 end-1
15.    0.28620|   0.29560|0.97  |lrange L[100] shared-span range 12 36
16.    0.45080|   0.41780|1.08  |lrange L[100] shared-span range 12 84
17.    0.53400|   0.50430|1.06  |lrange L[100] shared-span range 1 end
18.    0.25040|   0.26950|0.93  |lrange L[100] shared-span range end-1 end
19.    0.24860|   0.21460|1.16  |lrange L[1000] shared range 0 0
20.    3.52010|   0.24920|14.13 |lrange L[1000] shared range 0 end-1
21.    1.02110|   0.89190|1.14  |lrange L[1000] shared range 125 375
22.    2.70940|   0.23740|11.41 |lrange L[1000] shared range 125 875
23.    3.51850|   0.20270|17.36 |lrange L[1000] shared range 1 end
24.    0.22500|   0.22570|1.00  |lrange L[1000] shared range end-1 end
25.    0.21470|   0.27290|0.79  |lrange L[1000] shared-span range 0 0
26.    3.52640|   0.26750|13.18 |lrange L[1000] shared-span range 0 end-1
27.    1.03050|   0.91470|1.13  |lrange L[1000] shared-span range 125 375
28.    2.74930|   0.21490|12.79 |lrange L[1000] shared-span range 125 875
29.    3.54340|   0.25600|13.84 |lrange L[1000] shared-span range 1 end
30.    0.23830|   0.25140|0.95  |lrange L[1000] shared-span range end-1 end
31.    0.20370|   0.25660|0.79  |lrange L[10000] shared range 0 0
32.   34.71510|   0.20390|170.26|lrange L[10000] shared range 0 end-1
33.    8.84370|   7.63740|1.16  |lrange L[10000] shared range 1250 3750
34.   26.02270|   0.20440|127.31|lrange L[10000] shared range 1250 8750
35.   34.68470|   0.20520|169.03|lrange L[10000] shared range 1 end
36.    0.23660|   0.21570|1.10  |lrange L[10000] shared range end-1 end
37.    0.23460|   0.25280|0.93  |lrange L[10000] shared-span range 0 0
38.   34.67930|   0.25190|137.67|lrange L[10000] shared-span range 0 end-1
39.    8.83120|   7.80600|1.13  |lrange L[10000] shared-span range 1250 3750
40.   26.00760|   0.28250|92.06 |lrange L[10000] shared-span range 1250 8750
41.   34.69180|   0.21290|162.95|lrange L[10000] shared-span range 1 end
42.    0.23830|   0.24700|0.96  |lrange L[10000] shared-span range end-1 end

Extracting ranges from unshared lists

When lists are unshared, the overhead of unshared list creation for performance tests seems to make measurement difficult while the actual range operation is very fast. This is reflected by the 0 values in the table below.

43.    0.05100|   0.00470|10.85 |lrange L[10] unshared range 0 0
44.    0.04680|   0.00770|6.08  |lrange L[10] unshared range 0 end-1
45.    0.09790|   0.04960|1.97  |lrange L[10] unshared range 1 3
46.    0.05050|   0.05060|1.00  |lrange L[10] unshared range 1 7
47.    0.07620|   0.04910|1.55  |lrange L[10] unshared range 1 end
48.    0.07200|   0.02710|2.66  |lrange L[10] unshared range end-1 end
49.    0.03360|   0.10320|0.33  |lrange L[100] unshared range 0 0
50.    0.06580|   0.00000|Inf   |lrange L[100] unshared range 0 end-1
51.    0.04010|   0.06420|0.62  |lrange L[100] unshared range 12 36
52.    0.04080|   0.06420|0.64  |lrange L[100] unshared range 12 84
53.    0.07140|   0.06390|1.12  |lrange L[100] unshared range 1 end
54.    0.03600|   0.11250|0.32  |lrange L[100] unshared range end-1 end
55.    0.05800|   0.09130|0.64  |lrange L[100] unshared-span range 0 0
56.    0.03770|   0.03110|1.21  |lrange L[100] unshared-span range 0 end-1
57.    0.04950|   0.00000|Inf   |lrange L[100] unshared-span range 12 36
58.    0.03120|   0.01390|2.24  |lrange L[100] unshared-span range 12 84
59.    0.05440|   0.00520|10.46 |lrange L[100] unshared-span range 1 end
60.    0.02480|   0.05610|0.44  |lrange L[100] unshared-span range end-1 end
61.    0.00000|   0.00220|0.00  |lrange L[1000] unshared range 0 0
62.    0.06130|   0.00740|8.28  |lrange L[1000] unshared range 0 end-1
63.    0.03550|   0.04470|0.79  |lrange L[1000] unshared range 125 375
64.    0.09490|   0.04210|2.25  |lrange L[1000] unshared range 125 875
65.    0.14050|   0.01310|10.73 |lrange L[1000] unshared range 1 end
66.    0.00000|   0.23580|0.00  |lrange L[1000] unshared range end-1 end
67.    0.05750|   0.10460|0.55  |lrange L[1000] unshared-span range 0 0
68.    0.04160|   0.08040|0.52  |lrange L[1000] unshared-span range 0 end-1
69.    0.01420|   0.08840|0.16  |lrange L[1000] unshared-span range 125 375
70.    0.01840|   0.00000|Inf   |lrange L[1000] unshared-span range 125 875
71.    0.14030|   0.08980|1.56  |lrange L[1000] unshared-span range 1 end
72.    0.00000|   0.05250|0.00  |lrange L[1000] unshared-span range end-1 end
73.    0.35680|   0.00000|Inf   |lrange L[10000] unshared range 0 0
74.    0.00000|   0.29400|0.00  |lrange L[10000] unshared range 0 end-1
75.    0.32920|   0.00000|Inf   |lrange L[10000] unshared range 1250 3750
76.    1.08890|   0.00000|Inf   |lrange L[10000] unshared range 1250 8750
77.    1.34590|   0.00000|Inf   |lrange L[10000] unshared range 1 end
78.    0.00000|   0.00000|NaN   |lrange L[10000] unshared range end-1 end
79.    0.71840|   0.00000|Inf   |lrange L[10000] unshared-span range 0 0
80.    0.85540|   0.07690|11.12 |lrange L[10000] unshared-span range 0 end-1
81.    1.09630|   0.00000|Inf   |lrange L[10000] unshared-span range 1250 3750
82.    1.56450|   0.00000|Inf   |lrange L[10000] unshared-span range 1250 8750
83.    2.23600|   0.00000|Inf   |lrange L[10000] unshared-span range 1 end
84.    0.47300|   0.00000|Inf   |lrange L[10000] unshared-span range end-1 end
85.  249.40840|  29.73670|8.39  |lrange total run time

lassign

A lassign is essentially one or more lindex-like operations combined with a range operation. TIP 625 optimizes the latter and thus shows similar benefits (5-8, 11-12) for the same reasons as lrange.

           [1]           [2]
1.     0.96470|   0.51570|1.87  |lassign L[10] shared 1 elems 1000 times
2.     1.89870|   1.16070|1.64  |lassign L[10] shared 5 elems 1000 times
3.     1.19530|   1.21800|0.98  |lassign L[100] shared 1 elems 1000 times
4.     1.24400|   2.17270|0.57  |lassign L[100] shared 5 elems 1000 times
5.     3.81000|   0.43970|8.66  |lassign L[1000] shared 1 elems 1000 times
6.     3.82770|   1.00600|3.80  |lassign L[1000] shared 5 elems 1000 times
7.    30.35730|   0.42370|71.65 |lassign L[10000] shared 1 elems 1000 times
8.    34.00100|   0.97600|34.84 |lassign L[10000] shared 5 elems 1000 times
9.     0.50000|   0.87500|0.57  |lassign L[10] unshared 1 elems 8 times
10.    0.64970|   0.63950|1.02  |lassign L[100] unshared 1 elems 98 times
11.    2.64930|   0.49930|5.31  |lassign L[1000] unshared 1 elems 498 times
12.   23.00290|   0.49100|46.85 |lassign L[10000] unshared 1 elems 4998 times
13.  104.10050|  10.41710|9.99  |lassign total run time

lpop

Popping an element from a shared list variable

A lpop in the general case is has the same performance with the exception of popping elements in the front or end (13, 16) which benefit from being able to use a span.

           [1]           [2]
1.     0.62500|   0.66670|0.94  |lpop L[10] shared at 0 8 times
2.     0.66670|   0.66670|1.00  |lpop L[10] shared at 1 8 times
3.     0.75000|   0.79170|0.95  |lpop L[10] shared at end-1 8 times
4.     0.75000|   0.75000|1.00  |lpop L[10] shared at end 8 times
5.     0.77210|   0.71770|1.08  |lpop L[100] shared at 0 98 times
6.     0.74150|   0.71770|1.03  |lpop L[100] shared at 1 98 times
7.     0.84010|   0.78910|1.06  |lpop L[100] shared at end-1 98 times
8.     0.80610|   0.84350|0.96  |lpop L[100] shared at end 98 times
9.     3.00070|   0.57430|5.22  |lpop L[1000] shared at 0 498 times
10.    3.01610|   2.60440|1.16  |lpop L[1000] shared at 1 498 times
11.    3.07430|   2.70820|1.14  |lpop L[1000] shared at end-1 498 times
12.    3.08300|   0.60310|5.11  |lpop L[1000] shared at end 498 times
13.   26.51510|   0.57460|46.15 |lpop L[10000] shared at 0 4998 times
14.   26.54970|  23.53140|1.13  |lpop L[10000] shared at 1 4998 times
15.   26.71740|  23.13300|1.15  |lpop L[10000] shared at end-1 4998 times
16.   26.75190|   0.65620|40.77 |lpop L[10000] shared at end 4998 times

Popping an element from an unshared list variable

Again, unshared list storage is manipulated in both implementations by fast memory movement operations. There is 3x benefit from TIP 625 being able to move the smaller segment in the split (29, 30) but memory operations being fast, this is not as pronounced as the shared case.

17.    1.00000|   0.54170|1.85  |lpop L[10] unshared at 0 8 times
18.    0.50000|   0.58330|0.86  |lpop L[10] unshared at 1 8 times
19.    0.62500|   0.62500|1.00  |lpop L[10] unshared at end-1 8 times
20.    0.62500|   0.62500|1.00  |lpop L[10] unshared at end 8 times
21.    0.56460|   0.57480|0.98  |lpop L[100] unshared at 0 98 times
22.    0.57140|   0.57480|0.99  |lpop L[100] unshared at 1 98 times
23.    0.62930|   0.63270|0.99  |lpop L[100] unshared at end-1 98 times
24.    0.61220|   0.63950|0.96  |lpop L[100] unshared at end 98 times
25.    0.63720|   0.61310|1.04  |lpop L[1000] unshared at 0 498 times
26.    0.62520|   0.57630|1.08  |lpop L[1000] unshared at 1 498 times
27.    0.62180|   0.62450|1.00  |lpop L[1000] unshared at end-1 498 times
28.    0.61310|   0.63450|0.97  |lpop L[1000] unshared at end 498 times
29.    1.63330|   0.56870|2.87  |lpop L[10000] unshared at 0 4998 times
30.    1.79790|   0.57550|3.12  |lpop L[10000] unshared at 1 4998 times
31.    0.61620|   0.63030|0.98  |lpop L[10000] unshared at end-1 4998 times
32.    0.61040|   0.63150|0.97  |lpop L[10000] unshared at end 4998 times

Popping a nested element

There is no benefit popping a nested element because the outer list size is not affected and the inner list in the test scripts is only a pair. There would be a benefit if the inner list was large but benefits with large lists is already illustrated above.

33.    1.87500|   0.95830|1.96  |lpop L[10] shared at {0 0} 8 times
34.    1.00000|   1.79170|0.56  |lpop L[10] shared at {1 0} 8 times
35.    1.00000|   1.87500|0.53  |lpop L[10] shared at {end-1 0} 8 times
36.    1.91670|   1.75000|1.10  |lpop L[10] shared at {end 0} 8 times
37.    1.13610|   1.90140|0.60  |lpop L[100] shared at {0 0} 98 times
38.    1.15310|   1.03400|1.12  |lpop L[100] shared at {1 0} 98 times
39.    1.19730|   1.94560|0.62  |lpop L[100] shared at {end-1 0} 98 times
40.    1.16330|   1.98300|0.59  |lpop L[100] shared at {end 0} 98 times
41.    3.92770|   3.52340|1.11  |lpop L[1000] shared at {0 0} 498 times
42.    3.99930|   3.52880|1.13  |lpop L[1000] shared at {1 0} 498 times
43.    4.14660|   3.55560|1.17  |lpop L[1000] shared at {end-1 0} 498 times
44.    4.13520|   3.78110|1.09  |lpop L[1000] shared at {end 0} 498 times
45.   35.43270|  29.50360|1.20  |lpop L[10000] shared at {0 0} 4998 times
46.   35.42940|  29.55170|1.20  |lpop L[10000] shared at {1 0} 4998 times
47.   35.69910|  29.65230|1.20  |lpop L[10000] shared at {end-1 0} 4998 times
48.   35.72930|  29.53960|1.21  |lpop L[10000] shared at {end 0} 4998 times
49.  305.88310| 215.85440|1.42  |lpop total run time

lset

The lset command always modifies existing elements except when it is appending elements at the end in unshared objects. Thus the optimizations enabled by spans have no relevance and there is no fundamental difference in performance with TIP 625.

           [1]           [2]
1.     0.66100|   0.52020|1.27  |lset L[10] shared at 0
2.     0.58350|   0.50630|1.15  |lset L[10] shared at 1
3.     0.74100|   0.56530|1.31  |lset L[10] shared at end-1
4.     0.53390|   0.56890|0.94  |lset L[10] shared at end
5.    18.29250|  14.80990|1.24  |lset L[10] shared at end+1
6.     0.77470|   0.76170|1.02  |lset L[100] shared at 0
7.     0.77850|   0.73750|1.06  |lset L[100] shared at 1
8.     0.78550|   0.86950|0.90  |lset L[100] shared at end-1
9.     0.82000|   0.82230|1.00  |lset L[100] shared at end
10.   18.29150|  15.01350|1.22  |lset L[100] shared at end+1
11.    3.77540|   3.24230|1.16  |lset L[1000] shared at 0
12.    3.77920|   3.21060|1.18  |lset L[1000] shared at 1
13.    3.85980|   3.34070|1.16  |lset L[1000] shared at end-1
14.    3.78070|   3.78780|1.00  |lset L[1000] shared at end
15.   21.49420|  17.83840|1.20  |lset L[1000] shared at end+1
16.   35.05950|  28.91080|1.21  |lset L[10000] shared at 0
17.   35.02110|  28.86800|1.21  |lset L[10000] shared at 1
18.   35.35520|  29.16350|1.21  |lset L[10000] shared at end-1
19.   35.36760|  29.61640|1.19  |lset L[10000] shared at end
20.   53.12720|  46.70010|1.14  |lset L[10000] shared at end+1
21.    0.46900|   0.58610|0.80  |lset L[10] unshared at 0
22.    0.54760|   0.42710|1.28  |lset L[10] unshared at 1
23.    0.63430|   0.48870|1.30  |lset L[10] unshared at end-1
24.    0.70830|   0.48200|1.47  |lset L[10] unshared at end
25.    0.48820|   0.49160|0.99  |lset L[10] unshared at end+1
26.    0.43980|   0.45920|0.96  |lset L[100] unshared at 0
27.    0.47010|   0.43100|1.09  |lset L[100] unshared at 1
28.    0.50790|   0.51480|0.99  |lset L[100] unshared at end-1
29.    0.51490|   0.48460|1.06  |lset L[100] unshared at end
30.    0.48470|   0.48910|0.99  |lset L[100] unshared at end+1
31.    0.54990|   0.43500|1.26  |lset L[1000] unshared at 0
32.    0.66490|   0.42830|1.55  |lset L[1000] unshared at 1
33.    0.48850|   0.48410|1.01  |lset L[1000] unshared at end-1
34.    0.48220|   0.48240|1.00  |lset L[1000] unshared at end
35.    0.48480|   0.49340|0.98  |lset L[1000] unshared at end+1
36.    0.42830|   0.42870|1.00  |lset L[10000] unshared at 0
37.    0.43210|   0.42910|1.01  |lset L[10000] unshared at 1
38.    0.48240|   0.48850|0.99  |lset L[10000] unshared at end-1
39.    0.47850|   0.48820|0.98  |lset L[10000] unshared at end
40.    0.47870|   0.49310|0.97  |lset L[10000] unshared at end+1
41.    0.80710|   0.83320|0.97  |lset L[10] shared at {0 0}
42.    0.81530|   0.84830|0.96  |lset L[10] shared at {1 0}
43.    0.86030|   0.85740|1.00  |lset L[10] shared at {end-1 0}
44.    0.86040|   0.84410|1.02  |lset L[10] shared at {end 0}
45.    0.89310|   0.86580|1.03  |lset L[100] shared at {0 0}
46.    0.88720|   0.88110|1.01  |lset L[100] shared at {1 0}
47.    0.92060|   0.92840|0.99  |lset L[100] shared at {end-1 0}
48.    0.90130|   0.93150|0.97  |lset L[100] shared at {end 0}
49.    3.84860|   3.30240|1.17  |lset L[1000] shared at {0 0}
50.    3.87790|   3.27960|1.18  |lset L[1000] shared at {1 0}
51.    3.90020|   3.38740|1.15  |lset L[1000] shared at {end-1 0}
52.    3.92310|   3.33990|1.17  |lset L[1000] shared at {end 0}
53.   35.12130|  28.95020|1.21  |lset L[10000] shared at {0 0}
54.   35.13800|  29.34310|1.20  |lset L[10000] shared at {1 0}
55.   35.29860|  28.99230|1.22  |lset L[10000] shared at {end-1 0}
56.   35.25650|  29.49380|1.20  |lset L[10000] shared at {end 0}
57.    0.58430|   0.57820|1.01  |lset L[10] unshared at {0 0}
58.    0.57740|   0.56700|1.02  |lset L[10] unshared at {1 0}
59.    0.61630|   0.61840|1.00  |lset L[10] unshared at {end-1 0}
60.    0.60040|   0.61650|0.97  |lset L[10] unshared at {end 0}
61.    0.58370|   0.57960|1.01  |lset L[100] unshared at {0 0}
62.    0.57160|   0.58160|0.98  |lset L[100] unshared at {1 0}
63.    0.61570|   0.61860|1.00  |lset L[100] unshared at {end-1 0}
64.    0.60550|   0.60200|1.01  |lset L[100] unshared at {end 0}
65.    0.58340|   0.58690|0.99  |lset L[1000] unshared at {0 0}
66.    0.56380|   0.58650|0.96  |lset L[1000] unshared at {1 0}
67.    0.62190|   0.61750|1.01  |lset L[1000] unshared at {end-1 0}
68.    0.60010|   0.61210|0.98  |lset L[1000] unshared at {end 0}
69.    0.55840|   0.57300|0.97  |lset L[10000] unshared at {0 0}
70.    0.57610|   0.56020|1.03  |lset L[10000] unshared at {1 0}
71.    0.61370|   0.60830|1.01  |lset L[10000] unshared at {end-1 0}
72.    0.62110|   0.61860|1.00  |lset L[10000] unshared at {end 0}
73.  455.91970| 385.96240|1.18  |lset total run time

lremove

Removal of elements from a shared list

Removal of leading or trailing elements is essentially a range operation and thus sees order of magnitude improvements in performance when operating on shared lists (13, 17, 19, 23, 37, 41, 43, 47).

Removal at other indices from shared lists requires new list creation and this does not show any benefits.

           [1]           [2]
1.     0.61560|   0.69080|0.89  |lremove L[10] shared 1 elements at 0
2.     0.46840|   0.50220|0.93  |lremove L[10] shared 1 elements at 1
3.     0.60580|   0.44440|1.36  |lremove L[10] shared 1 elements at 5
4.     0.50520|   0.48700|1.04  |lremove L[10] shared 1 elements at end-1
5.     0.47830|   0.57630|0.83  |lremove L[10] shared 1 elements at end
6.     0.64130|   0.79860|0.80  |lremove L[10] shared 5 elements at 0 1 5 end-1 end
7.     0.84040|   0.68670|1.22  |lremove L[100] shared 1 elements at 0
8.     0.76790|   0.80940|0.95  |lremove L[100] shared 1 elements at 1
9.     0.82900|   0.67930|1.22  |lremove L[100] shared 1 elements at 50
10.    0.77090|   0.75290|1.02  |lremove L[100] shared 1 elements at end-1
11.    0.95350|   0.72420|1.32  |lremove L[100] shared 1 elements at end
12.    1.15080|   1.04890|1.10  |lremove L[100] shared 5 elements at 0 1 50 end-1 end
13.    3.51060|   0.43450|8.08  |lremove L[1000] shared 1 elements at 0
14.    3.52400|   3.22860|1.09  |lremove L[1000] shared 1 elements at 1
15.    3.52350|   3.14890|1.12  |lremove L[1000] shared 1 elements at 500
16.    3.52310|   3.25950|1.08  |lremove L[1000] shared 1 elements at end-1
17.    3.74320|   0.47500|7.88  |lremove L[1000] shared 1 elements at end
18.    3.83280|   3.48050|1.10  |lremove L[1000] shared 5 elements at 0 1 500 end-1 end
19.   30.39120|   0.42240|71.95 |lremove L[10000] shared 1 elements at 0
20.   30.27250|  28.59490|1.06  |lremove L[10000] shared 1 elements at 1
21.   30.34820|  28.50400|1.06  |lremove L[10000] shared 1 elements at 5000
22.   30.42090|  28.71930|1.06  |lremove L[10000] shared 1 elements at end-1
23.   30.53150|   0.45170|67.59 |lremove L[10000] shared 1 elements at end
24.   32.39280|  28.88290|1.12  |lremove L[10000] shared 5 elements at 0 1 5000 end-1 end
25.    0.71680|   0.47780|1.50  |lremove L[10] shared-span 1 elements at 0
26.    0.45080|   0.48900|0.92  |lremove L[10] shared-span 1 elements at 1
27.    0.66590|   0.48710|1.37  |lremove L[10] shared-span 1 elements at 5
28.    0.87990|   0.52540|1.67  |lremove L[10] shared-span 1 elements at end-1
29.    0.56630|   0.54030|1.05  |lremove L[10] shared-span 1 elements at end
30.    0.97410|   0.70920|1.37  |lremove L[10] shared-span 5 elements at 0 1 5 end-1 end
31.    0.73820|   0.72490|1.02  |lremove L[100] shared-span 1 elements at 0
32.    0.73480|   0.75080|0.98  |lremove L[100] shared-span 1 elements at 1
33.    0.79750|   0.72650|1.10  |lremove L[100] shared-span 1 elements at 50
34.    0.77370|   0.88570|0.87  |lremove L[100] shared-span 1 elements at end-1
35.    0.77440|   0.75230|1.03  |lremove L[100] shared-span 1 elements at end
36.    0.99760|   0.98270|1.02  |lremove L[100] shared-span 5 elements at 0 1 50 end-1 end
37.    3.51090|   0.52070|6.74  |lremove L[1000] shared-span 1 elements at 0
38.    3.54570|   3.29990|1.07  |lremove L[1000] shared-span 1 elements at 1
39.    3.99660|   3.31420|1.21  |lremove L[1000] shared-span 1 elements at 500
40.    3.67910|   3.25230|1.13  |lremove L[1000] shared-span 1 elements at end-1
41.    3.75820|   0.52310|7.18  |lremove L[1000] shared-span 1 elements at end
42.    4.44580|   3.57670|1.24  |lremove L[1000] shared-span 5 elements at 0 1 500 end-1 end
43.   32.86260|   0.44870|73.24 |lremove L[10000] shared-span 1 elements at 0
44.   33.38560|  28.51260|1.17  |lremove L[10000] shared-span 1 elements at 1
45.   30.40200|  28.58650|1.06  |lremove L[10000] shared-span 1 elements at 5000
46.   30.58530|  28.65760|1.07  |lremove L[10000] shared-span 1 elements at end-1
47.   30.42020|   0.48410|62.84 |lremove L[10000] shared-span 1 elements at end
48.   32.47680|  28.85620|1.13  |lremove L[10000] shared-span 5 elements at 0 1 5000 end-1 end

Removal of elements from a unshared list

Removal of elements from an unshared list object is done in both implementations by moving elements within the existing list storage array. The difference is that with TIP 625, the shorter segment can be moved in the common case where a single element is being removed. This is reflected in the 7x-8x speed removing elements towards the front of the list (64, 65).

49.    0.37500|   0.62500|0.60  |lremove L[10] unshared 1 elements at 0
50.    0.33330|   0.37500|0.89  |lremove L[10] unshared 1 elements at 1
51.    0.33330|   0.75000|0.44  |lremove L[10] unshared 1 elements at 5
52.    0.87500|   0.87500|1.00  |lremove L[10] unshared 1 elements at end-1
53.    0.87500|   0.37500|2.33  |lremove L[10] unshared 1 elements at end
54.    0.73810|   0.24150|3.06  |lremove L[100] unshared 1 elements at 0
55.    0.29590|   0.74490|0.40  |lremove L[100] unshared 1 elements at 1
56.    0.24490|   0.25850|0.95  |lremove L[100] unshared 1 elements at 50
57.    0.31630|   0.78910|0.40  |lremove L[100] unshared 1 elements at end-1
58.    0.28570|   0.58500|0.49  |lremove L[100] unshared 1 elements at end
59.    0.38400|   0.23470|1.64  |lremove L[1000] unshared 1 elements at 0
60.    0.82930|   0.71470|1.16  |lremove L[1000] unshared 1 elements at 1
61.    0.34930|   0.30400|1.15  |lremove L[1000] unshared 1 elements at 500
62.    0.77600|   0.29600|2.62  |lremove L[1000] unshared 1 elements at end-1
63.    0.78670|   0.28530|2.76  |lremove L[1000] unshared 1 elements at end
64.    1.67200|   0.20080|8.33  |lremove L[10000] unshared 1 elements at 0
65.    1.65570|   0.21680|7.64  |lremove L[10000] unshared 1 elements at 1
66.    0.92130|   0.87950|1.05  |lremove L[10000] unshared 1 elements at 5000
67.    0.32290|   0.27950|1.16  |lremove L[10000] unshared 1 elements at end-1
68.    0.30750|   0.27250|1.13  |lremove L[10000] unshared 1 elements at end
69.    0.29170|   0.70830|0.41  |lremove L[10] unshared-span 1 elements at 0
70.    0.75000|   0.25000|3.00  |lremove L[10] unshared-span 1 elements at 1
71.    0.25000|   0.25000|1.00  |lremove L[10] unshared-span 1 elements at 5
72.    0.87500|   0.87500|1.00  |lremove L[10] unshared-span 1 elements at end-1
73.    0.25000|   0.25000|1.00  |lremove L[10] unshared-span 1 elements at end
74.    0.26870|   0.27890|0.96  |lremove L[100] unshared-span 1 elements at 0
75.    0.72790|   0.69050|1.05  |lremove L[100] unshared-span 1 elements at 1
76.    0.24830|   0.68370|0.36  |lremove L[100] unshared-span 1 elements at 50
77.    0.76870|   0.32650|2.35  |lremove L[100] unshared-span 1 elements at end-1
78.    0.74150|   0.30270|2.45  |lremove L[100] unshared-span 1 elements at end
79.    0.77070|   0.70670|1.09  |lremove L[1000] unshared-span 1 elements at 0
80.    0.30130|   0.26400|1.14  |lremove L[1000] unshared-span 1 elements at 1
81.    0.73600|   0.75200|0.98  |lremove L[1000] unshared-span 1 elements at 500
82.    0.76800|   0.29070|2.64  |lremove L[1000] unshared-span 1 elements at end-1
83.    0.28270|   0.34130|0.83  |lremove L[1000] unshared-span 1 elements at end
84.    1.29200|   0.25410|5.08  |lremove L[10000] unshared-span 1 elements at 0
85.    1.63650|   0.26850|6.09  |lremove L[10000] unshared-span 1 elements at 1
86.    0.76990|   0.90030|0.86  |lremove L[10000] unshared-span 1 elements at 5000
87.    0.28720|   0.23410|1.23  |lremove L[10000] unshared-span 1 elements at end-1
88.    0.26990|   0.29040|0.93  |lremove L[10000] unshared-span 1 elements at end

Total run time

89.  461.74330| 294.10770|1.57  |lremove total run time

lreplace

Pure inserts in a shared list

Pure inserts that are repeated prepends to a list are much faster (43, 44, 63, 64). lreplace unsurprisingly show the same characteristics as the linsert command. See there for more details.

           [1]           [2]
1.     0.47940|   0.47790|1.00  |lreplace L[10] shared 0 (0:-1) elems at 0 with 1 elems 1 times.
2.     0.50010|   0.51730|0.97  |lreplace L[10] shared 0 (0:-1) elems at 0 with 10 elems 1 times.
3.     0.62500|   0.62500|1.00  |lreplace L[10] shared 0 (0:-1) elems at 0 with 1 elems 8 times.
4.     0.75000|   0.62500|1.20  |lreplace L[10] shared 0 (0:-1) elems at 0 with 10 elems 8 times.
5.     0.48000|   0.48200|1.00  |lreplace L[10] shared 0 (1:-1) elems at 1 with 1 elems 1 times.
6.     0.49280|   0.53140|0.93  |lreplace L[10] shared 0 (1:-1) elems at 1 with 10 elems 1 times.
7.     0.62500|   0.62500|1.00  |lreplace L[10] shared 0 (1:-1) elems at 1 with 1 elems 8 times.
8.     0.75000|   0.75000|1.00  |lreplace L[10] shared 0 (1:-1) elems at 1 with 10 elems 8 times.
9.     0.48990|   0.68220|0.72  |lreplace L[10] shared 0 (5:-1) elems at 5 with 1 elems 1 times.
10.    0.65100|   0.52350|1.24  |lreplace L[10] shared 0 (5:-1) elems at 5 with 10 elems 1 times.
11.    0.62500|   0.62500|1.00  |lreplace L[10] shared 0 (5:-1) elems at 5 with 1 elems 8 times.
12.    0.75000|   0.75000|1.00  |lreplace L[10] shared 0 (5:-1) elems at 5 with 10 elems 8 times.
13.    0.48510|   0.52490|0.92  |lreplace L[10] shared 0 (end-1:-1) elems at end-1 with 1 elems 1 times.
14.    0.51940|   0.53900|0.96  |lreplace L[10] shared 0 (end-1:-1) elems at end-1 with 10 elems 1 times.
15.    0.66670|   0.70830|0.94  |lreplace L[10] shared 0 (end-1:-1) elems at end-1 with 1 elems 8 times.
16.    0.75000|   0.75000|1.00  |lreplace L[10] shared 0 (end-1:-1) elems at end-1 with 10 elems 8 times.
17.    0.49670|   0.65090|0.76  |lreplace L[10] shared 0 (end:-1) elems at end with 1 elems 1 times.
18.    0.52690|   0.75680|0.70  |lreplace L[10] shared 0 (end:-1) elems at end with 10 elems 1 times.
19.    0.66670|   0.70830|0.94  |lreplace L[10] shared 0 (end:-1) elems at end with 1 elems 8 times.
20.    0.75000|   0.75000|1.00  |lreplace L[10] shared 0 (end:-1) elems at end with 10 elems 8 times.
21.    0.86160|   0.72000|1.20  |lreplace L[100] shared 0 (0:-1) elems at 0 with 1 elems 1 times.
22.    0.98610|   0.82330|1.20  |lreplace L[100] shared 0 (0:-1) elems at 0 with 10 elems 1 times.
23.    1.03060|   0.61560|1.67  |lreplace L[100] shared 0 (0:-1) elems at 0 with 1 elems 98 times.
24.    2.35710|   0.71430|3.30  |lreplace L[100] shared 0 (0:-1) elems at 0 with 10 elems 98 times.
25.    0.82810|   0.73730|1.12  |lreplace L[100] shared 0 (1:-1) elems at 1 with 1 elems 1 times.
26.    0.74340|   0.75490|0.98  |lreplace L[100] shared 0 (1:-1) elems at 1 with 10 elems 1 times.
27.    1.01020|   1.01360|1.00  |lreplace L[100] shared 0 (1:-1) elems at 1 with 1 elems 98 times.
28.    2.30950|   2.24490|1.03  |lreplace L[100] shared 0 (1:-1) elems at 1 with 10 elems 98 times.
29.    0.91550|   0.72490|1.26  |lreplace L[100] shared 0 (50:-1) elems at 50 with 1 elems 1 times.
30.    0.78790|   0.75560|1.04  |lreplace L[100] shared 0 (50:-1) elems at 50 with 10 elems 1 times.
31.    0.98300|   0.99660|0.99  |lreplace L[100] shared 0 (50:-1) elems at 50 with 1 elems 98 times.
32.    2.28230|   2.21430|1.03  |lreplace L[100] shared 0 (50:-1) elems at 50 with 10 elems 98 times.
33.    0.95890|   0.75470|1.27  |lreplace L[100] shared 0 (end-1:-1) elems at end-1 with 1 elems 1 times.
34.    0.79480|   0.87110|0.91  |lreplace L[100] shared 0 (end-1:-1) elems at end-1 with 10 elems 1 times.
35.    1.03400|   1.03060|1.00  |lreplace L[100] shared 0 (end-1:-1) elems at end-1 with 1 elems 98 times.
36.    2.32990|   2.26530|1.03  |lreplace L[100] shared 0 (end-1:-1) elems at end-1 with 10 elems 98 times.
37.    0.81070|   0.77270|1.05  |lreplace L[100] shared 0 (end:-1) elems at end with 1 elems 1 times.
38.    0.88110|   0.82370|1.07  |lreplace L[100] shared 0 (end:-1) elems at end with 10 elems 1 times.
39.    1.04080|   1.03060|1.01  |lreplace L[100] shared 0 (end:-1) elems at end with 1 elems 98 times.
40.    2.32990|   2.25850|1.03  |lreplace L[100] shared 0 (end:-1) elems at end with 10 elems 98 times.
41.    3.47370|   3.27660|1.06  |lreplace L[1000] shared 0 (0:-1) elems at 0 with 1 elems 1 times.
42.    3.42180|   3.28980|1.04  |lreplace L[1000] shared 0 (0:-1) elems at 0 with 10 elems 1 times.
43.    3.61600|   0.65870|5.49  |lreplace L[1000] shared 0 (0:-1) elems at 0 with 1 elems 125 times.
44.    5.33330|   0.74130|7.19  |lreplace L[1000] shared 0 (0:-1) elems at 0 with 10 elems 125 times.
45.    3.44310|   3.21840|1.07  |lreplace L[1000] shared 0 (1:-1) elems at 1 with 1 elems 1 times.
46.    3.48970|   3.29960|1.06  |lreplace L[1000] shared 0 (1:-1) elems at 1 with 10 elems 1 times.
47.    3.61870|   3.86930|0.94  |lreplace L[1000] shared 0 (1:-1) elems at 1 with 1 elems 125 times.
48.    5.32000|   5.61600|0.95  |lreplace L[1000] shared 0 (1:-1) elems at 1 with 10 elems 125 times.
49.    3.47820|   3.21690|1.08  |lreplace L[1000] shared 0 (500:-1) elems at 500 with 1 elems 1 times.
50.    3.51640|   3.34630|1.05  |lreplace L[1000] shared 0 (500:-1) elems at 500 with 10 elems 1 times.
51.    3.59470|   3.66130|0.98  |lreplace L[1000] shared 0 (500:-1) elems at 500 with 1 elems 125 times.
52.    5.30930|   5.32270|1.00  |lreplace L[1000] shared 0 (500:-1) elems at 500 with 10 elems 125 times.
53.    3.37250|   3.31760|1.02  |lreplace L[1000] shared 0 (end-1:-1) elems at end-1 with 1 elems 1 times.
54.    3.47360|   3.22670|1.08  |lreplace L[1000] shared 0 (end-1:-1) elems at end-1 with 10 elems 1 times.
55.    3.67730|   3.74930|0.98  |lreplace L[1000] shared 0 (end-1:-1) elems at end-1 with 1 elems 125 times.
56.    5.36000|   5.43730|0.99  |lreplace L[1000] shared 0 (end-1:-1) elems at end-1 with 10 elems 125 times.
57.    3.47170|   3.26540|1.06  |lreplace L[1000] shared 0 (end:-1) elems at end with 1 elems 1 times.
58.    3.54830|   3.42090|1.04  |lreplace L[1000] shared 0 (end:-1) elems at end with 10 elems 1 times.
59.    3.66130|   3.71200|0.99  |lreplace L[1000] shared 0 (end:-1) elems at end with 1 elems 125 times.
60.    5.35470|   5.40270|0.99  |lreplace L[1000] shared 0 (end:-1) elems at end with 10 elems 125 times.
61.   30.27910|  30.01480|1.01  |lreplace L[10000] shared 0 (0:-1) elems at 0 with 1 elems 1 times.
62.   30.36400|  31.46430|0.97  |lreplace L[10000] shared 0 (0:-1) elems at 0 with 10 elems 1 times.
63.   32.08320|   0.68590|46.78 |lreplace L[10000] shared 0 (0:-1) elems at 0 with 1 elems 1250 times.
64.   48.88990|   0.84270|58.02 |lreplace L[10000] shared 0 (0:-1) elems at 0 with 10 elems 1250 times.
65.   30.27520|  30.60110|0.99  |lreplace L[10000] shared 0 (1:-1) elems at 1 with 1 elems 1 times.
66.   30.42620|  29.92770|1.02  |lreplace L[10000] shared 0 (1:-1) elems at 1 with 10 elems 1 times.
67.   32.10670|  32.28190|0.99  |lreplace L[10000] shared 0 (1:-1) elems at 1 with 1 elems 1250 times.
68.   48.80400|  51.68190|0.94  |lreplace L[10000] shared 0 (1:-1) elems at 1 with 10 elems 1250 times.
69.   30.26310|  29.98060|1.01  |lreplace L[10000] shared 0 (5000:-1) elems at 5000 with 1 elems 1 times.
70.   30.35280|  29.73200|1.02  |lreplace L[10000] shared 0 (5000:-1) elems at 5000 with 10 elems 1 times.
71.   32.14530|  32.12450|1.00  |lreplace L[10000] shared 0 (5000:-1) elems at 5000 with 1 elems 1250 times.
72.   49.19330|  50.84690|0.97  |lreplace L[10000] shared 0 (5000:-1) elems at 5000 with 10 elems 1250 times.
73.   30.36830|  29.65420|1.02  |lreplace L[10000] shared 0 (end-1:-1) elems at end-1 with 1 elems 1 times.
74.   30.38940|  30.02930|1.01  |lreplace L[10000] shared 0 (end-1:-1) elems at end-1 with 10 elems 1 times.
75.   32.29440|  32.24910|1.00  |lreplace L[10000] shared 0 (end-1:-1) elems at end-1 with 1 elems 1250 times.
76.   49.03310|  51.02960|0.96  |lreplace L[10000] shared 0 (end-1:-1) elems at end-1 with 10 elems 1250 times.
77.   30.43670|  29.91730|1.02  |lreplace L[10000] shared 0 (end:-1) elems at end with 1 elems 1 times.
78.   30.47630|  29.89420|1.02  |lreplace L[10000] shared 0 (end:-1) elems at end with 10 elems 1 times.
79.   32.31550|  32.84430|0.98  |lreplace L[10000] shared 0 (end:-1) elems at end with 1 elems 1250 times.
80.   48.94850|  50.78560|0.96  |lreplace L[10000] shared 0 (end:-1) elems at end with 10 elems 1250 times.

Pure deletes from a shared list

Pure deletions from the front or the back translate to a range operation and show order of magnitude increases (91, 95, 96, 100) as TIP 625 makes use of spans in these cases.

Deletions from the middle show no difference as a new list object has to be created when the operand list is shared.

81.    0.56120|   0.65720|0.85  |lreplace L[10] shared 0:0 with 0 elems 1 times.
82.    0.61420|   0.61920|0.99  |lreplace L[10] shared 1:1 with 0 elems 1 times.
83.    0.57910|   0.63710|0.91  |lreplace L[10] shared 5:5 with 0 elems 1 times.
84.    0.64440|   0.70020|0.92  |lreplace L[10] shared end-1:end-1 with 0 elems 1 times.
85.    0.64570|   0.66650|0.97  |lreplace L[10] shared end:end with 0 elems 1 times.
86.    0.85890|   0.88870|0.97  |lreplace L[100] shared 0:0 with 0 elems 1 times.
87.    0.87410|   0.87850|0.99  |lreplace L[100] shared 1:1 with 0 elems 1 times.
88.    0.84450|   0.88400|0.96  |lreplace L[100] shared 50:50 with 0 elems 1 times.
89.    0.92150|   0.95340|0.97  |lreplace L[100] shared end-1:end-1 with 0 elems 1 times.
90.    1.05190|   0.93860|1.12  |lreplace L[100] shared end:end with 0 elems 1 times.
91.    3.62780|   0.58330|6.22  |lreplace L[1000] shared 0:0 with 0 elems 1 times.
92.    3.78750|   3.27940|1.15  |lreplace L[1000] shared 1:1 with 0 elems 1 times.
93.    3.64500|   3.36440|1.08  |lreplace L[1000] shared 500:500 with 0 elems 1 times.
94.    3.57190|   3.34580|1.07  |lreplace L[1000] shared end-1:end-1 with 0 elems 1 times.
95.    3.80310|   0.65340|5.82  |lreplace L[1000] shared end:end with 0 elems 1 times.
96.   32.88180|   0.57780|56.91 |lreplace L[10000] shared 0:0 with 0 elems 1 times.
97.   34.93830|  29.90320|1.17  |lreplace L[10000] shared 1:1 with 0 elems 1 times.
98.   35.16850|  29.76260|1.18  |lreplace L[10000] shared 5000:5000 with 0 elems 1 times.
99.   35.48920|  30.26280|1.17  |lreplace L[10000] shared end-1:end-1 with 0 elems 1 times.
100.  35.31320|   0.64430|54.81 |lreplace L[10000] shared end:end with 0 elems 1 times.

Replacing elements in a shared list

The table below covers cases where the number of elements deleted is less, equal and greater than the number inserted. Replacement (where elements are deleted and inserted) of elements in shared lists always require a new list object to be created. Thus there is no difference in performance in any of the cases.

101.   0.65750|   0.61980|1.06  |lreplace L[10] shared 0:1 with 3 elems 1 times.
102.   0.70640|   0.62930|1.12  |lreplace L[10] shared 0:1 with 2 elems 1 times.
103.   0.61070|   0.69230|0.88  |lreplace L[10] shared 0:1 with 1 elems 1 times.
104.   0.61710|   0.80190|0.77  |lreplace L[10] shared 1:2 with 3 elems 1 times.
105.   0.82560|   0.60530|1.36  |lreplace L[10] shared 1:2 with 2 elems 1 times.
106.   0.64700|   0.63040|1.03  |lreplace L[10] shared 1:2 with 1 elems 1 times.
107.   0.73040|   0.69910|1.04  |lreplace L[10] shared 0 (end-2:end-1) elems at end-2 with 3 elems 1 times.
108.   0.66290|   0.76100|0.87  |lreplace L[10] shared 0 (end-2:end-1) elems at end-2 with 2 elems 1 times.
109.   0.98590|   0.72480|1.36  |lreplace L[10] shared 0 (end-2:end-1) elems at end-2 with 1 elems 1 times.
110.   0.78410|   0.86180|0.91  |lreplace L[10] shared 0 (end-1:end) elems at end-1 with 3 elems 1 times.
111.   0.64710|   0.87300|0.74  |lreplace L[10] shared 0 (end-1:end) elems at end-1 with 2 elems 1 times.
112.   0.81320|   0.67810|1.20  |lreplace L[10] shared 0 (end-1:end) elems at end-1 with 1 elems 1 times.
113.   0.90510|   0.89730|1.01  |lreplace L[100] shared 0:1 with 3 elems 1 times.
114.   0.88180|   0.87050|1.01  |lreplace L[100] shared 0:1 with 2 elems 1 times.
115.   0.90480|   1.09520|0.83  |lreplace L[100] shared 0:1 with 1 elems 1 times.
116.   0.88150|   0.95750|0.92  |lreplace L[100] shared 1:2 with 3 elems 1 times.
117.   0.89530|   0.88120|1.02  |lreplace L[100] shared 1:2 with 2 elems 1 times.
118.   0.90940|   0.87730|1.04  |lreplace L[100] shared 1:2 with 1 elems 1 times.
119.   0.95880|   0.92530|1.04  |lreplace L[100] shared 0 (end-2:end-1) elems at end-2 with 3 elems 1 times.
120.   0.97030|   0.94920|1.02  |lreplace L[100] shared 0 (end-2:end-1) elems at end-2 with 2 elems 1 times.
121.   0.96520|   0.99490|0.97  |lreplace L[100] shared 0 (end-2:end-1) elems at end-2 with 1 elems 1 times.
122.   0.96970|   0.94620|1.02  |lreplace L[100] shared 0 (end-1:end) elems at end-1 with 3 elems 1 times.
123.   0.95190|   0.97260|0.98  |lreplace L[100] shared 0 (end-1:end) elems at end-1 with 2 elems 1 times.
124.   0.96100|   0.94280|1.02  |lreplace L[100] shared 0 (end-1:end) elems at end-1 with 1 elems 1 times.
125.   3.88890|   3.31820|1.17  |lreplace L[1000] shared 0:1 with 3 elems 1 times.
126.   3.88640|   3.36360|1.16  |lreplace L[1000] shared 0:1 with 2 elems 1 times.
127.   3.93460|   3.32050|1.18  |lreplace L[1000] shared 0:1 with 1 elems 1 times.
128.   3.83000|   3.33620|1.15  |lreplace L[1000] shared 1:2 with 3 elems 1 times.
129.   3.90790|   3.28990|1.19  |lreplace L[1000] shared 1:2 with 2 elems 1 times.
130.   3.96350|   3.37550|1.17  |lreplace L[1000] shared 1:2 with 1 elems 1 times.
131.   4.01580|   3.44970|1.16  |lreplace L[1000] shared 0 (end-2:end-1) elems at end-2 with 3 elems 1 times.
132.   4.00600|   3.46050|1.16  |lreplace L[1000] shared 0 (end-2:end-1) elems at end-2 with 2 elems 1 times.
133.   4.04070|   3.39300|1.19  |lreplace L[1000] shared 0 (end-2:end-1) elems at end-2 with 1 elems 1 times.
134.   3.96110|   3.45400|1.15  |lreplace L[1000] shared 0 (end-1:end) elems at end-1 with 3 elems 1 times.
135.   3.99370|   3.41680|1.17  |lreplace L[1000] shared 0 (end-1:end) elems at end-1 with 2 elems 1 times.
136.   4.03230|   3.47010|1.16  |lreplace L[1000] shared 0 (end-1:end) elems at end-1 with 1 elems 1 times.
137.  34.93770|  29.83270|1.17  |lreplace L[10000] shared 0:1 with 3 elems 1 times.
138.  34.98580|  30.19310|1.16  |lreplace L[10000] shared 0:1 with 2 elems 1 times.
139.  35.05860|  30.02560|1.17  |lreplace L[10000] shared 0:1 with 1 elems 1 times.
140.  35.10190|  29.87490|1.17  |lreplace L[10000] shared 1:2 with 3 elems 1 times.
141.  35.09290|  30.15570|1.16  |lreplace L[10000] shared 1:2 with 2 elems 1 times.
142.  35.15620|  30.31950|1.16  |lreplace L[10000] shared 1:2 with 1 elems 1 times.
143.  35.45930|  30.32200|1.17  |lreplace L[10000] shared 0 (end-2:end-1) elems at end-2 with 3 elems 1 times.
144.  35.39280|  29.78930|1.19  |lreplace L[10000] shared 0 (end-2:end-1) elems at end-2 with 2 elems 1 times.
145.  35.34340|  29.96270|1.18  |lreplace L[10000] shared 0 (end-2:end-1) elems at end-2 with 1 elems 1 times.
146.  35.38980|  30.14600|1.17  |lreplace L[10000] shared 0 (end-1:end) elems at end-1 with 3 elems 1 times.
147.  35.38750|  29.86510|1.18  |lreplace L[10000] shared 0 (end-1:end) elems at end-1 with 2 elems 1 times.
148.  35.28000|  30.06530|1.17  |lreplace L[10000] shared 0 (end-1:end) elems at end-1 with 1 elems 1 times.
149.   0.60670|   0.62750|0.97  |lreplace L[10] shared-span 0:1 with 3 elems 1 times.
150.   0.61480|   0.62680|0.98  |lreplace L[10] shared-span 0:1 with 2 elems 1 times.
151.   0.62980|   0.65230|0.97  |lreplace L[10] shared-span 0:1 with 1 elems 1 times.
152.   0.64620|   0.61170|1.06  |lreplace L[10] shared-span 1:2 with 3 elems 1 times.
153.   0.60560|   0.63060|0.96  |lreplace L[10] shared-span 1:2 with 2 elems 1 times.
154.   0.61010|   0.63700|0.96  |lreplace L[10] shared-span 1:2 with 1 elems 1 times.
155.   0.76760|   0.77940|0.98  |lreplace L[10] shared-span 0 (end-2:end-1) elems at end-2 with 3 elems 1 times.
156.   0.66550|   0.97870|0.68  |lreplace L[10] shared-span 0 (end-2:end-1) elems at end-2 with 2 elems 1 times.
157.   0.68190|   0.81500|0.84  |lreplace L[10] shared-span 0 (end-2:end-1) elems at end-2 with 1 elems 1 times.
158.   0.70920|   0.77750|0.91  |lreplace L[10] shared-span 0 (end-1:end) elems at end-1 with 3 elems 1 times.
159.   0.69400|   0.79640|0.87  |lreplace L[10] shared-span 0 (end-1:end) elems at end-1 with 2 elems 1 times.
160.   0.79150|   0.68680|1.15  |lreplace L[10] shared-span 0 (end-1:end) elems at end-1 with 1 elems 1 times.
161.   0.89000|   0.85330|1.04  |lreplace L[100] shared-span 0:1 with 3 elems 1 times.
162.   0.91340|   0.87790|1.04  |lreplace L[100] shared-span 0:1 with 2 elems 1 times.
163.   0.91230|   0.89800|1.02  |lreplace L[100] shared-span 0:1 with 1 elems 1 times.
164.   0.91210|   0.87770|1.04  |lreplace L[100] shared-span 1:2 with 3 elems 1 times.
165.   0.90490|   0.87460|1.03  |lreplace L[100] shared-span 1:2 with 2 elems 1 times.
166.   0.89170|   0.89650|0.99  |lreplace L[100] shared-span 1:2 with 1 elems 1 times.
167.   0.96910|   0.92580|1.05  |lreplace L[100] shared-span 0 (end-2:end-1) elems at end-2 with 3 elems 1 times.
168.   0.96320|   0.95080|1.01  |lreplace L[100] shared-span 0 (end-2:end-1) elems at end-2 with 2 elems 1 times.
169.   0.98120|   0.99000|0.99  |lreplace L[100] shared-span 0 (end-2:end-1) elems at end-2 with 1 elems 1 times.
170.   0.98520|   0.95170|1.04  |lreplace L[100] shared-span 0 (end-1:end) elems at end-1 with 3 elems 1 times.
171.   0.96350|   0.93680|1.03  |lreplace L[100] shared-span 0 (end-1:end) elems at end-1 with 2 elems 1 times.
172.   0.95590|   0.97240|0.98  |lreplace L[100] shared-span 0 (end-1:end) elems at end-1 with 1 elems 1 times.
173.   3.93890|   3.33180|1.18  |lreplace L[1000] shared-span 0:1 with 3 elems 1 times.
174.   3.90450|   3.34690|1.17  |lreplace L[1000] shared-span 0:1 with 2 elems 1 times.
175.   3.90990|   3.35300|1.17  |lreplace L[1000] shared-span 0:1 with 1 elems 1 times.
176.   3.87520|   3.32150|1.17  |lreplace L[1000] shared-span 1:2 with 3 elems 1 times.
177.   3.86850|   3.30460|1.17  |lreplace L[1000] shared-span 1:2 with 2 elems 1 times.
178.   3.93850|   3.44900|1.14  |lreplace L[1000] shared-span 1:2 with 1 elems 1 times.
179.   3.98380|   3.41950|1.17  |lreplace L[1000] shared-span 0 (end-2:end-1) elems at end-2 with 3 elems 1 times.
180.   3.95630|   3.43710|1.15  |lreplace L[1000] shared-span 0 (end-2:end-1) elems at end-2 with 2 elems 1 times.
181.   3.91830|   3.39130|1.16  |lreplace L[1000] shared-span 0 (end-2:end-1) elems at end-2 with 1 elems 1 times.
182.   3.99120|   3.46460|1.15  |lreplace L[1000] shared-span 0 (end-1:end) elems at end-1 with 3 elems 1 times.
183.   3.99690|   3.37240|1.19  |lreplace L[1000] shared-span 0 (end-1:end) elems at end-1 with 2 elems 1 times.
184.   3.96020|   3.48160|1.14  |lreplace L[1000] shared-span 0 (end-1:end) elems at end-1 with 1 elems 1 times.
185.  35.03300|  29.85710|1.17  |lreplace L[10000] shared-span 0:1 with 3 elems 1 times.
186.  35.08120|  30.09080|1.17  |lreplace L[10000] shared-span 0:1 with 2 elems 1 times.
187.  35.07970|  29.82660|1.18  |lreplace L[10000] shared-span 0:1 with 1 elems 1 times.
188.  35.08990|  29.80730|1.18  |lreplace L[10000] shared-span 1:2 with 3 elems 1 times.
189.  34.97130|  29.80890|1.17  |lreplace L[10000] shared-span 1:2 with 2 elems 1 times.
190.  35.24050|  29.76600|1.18  |lreplace L[10000] shared-span 1:2 with 1 elems 1 times.
191.  35.47870|  30.21850|1.17  |lreplace L[10000] shared-span 0 (end-2:end-1) elems at end-2 with 3 elems 1 times.
192.  35.41750|  30.18880|1.17  |lreplace L[10000] shared-span 0 (end-2:end-1) elems at end-2 with 2 elems 1 times.
193.  35.59270|  30.04520|1.18  |lreplace L[10000] shared-span 0 (end-2:end-1) elems at end-2 with 1 elems 1 times.
194.  35.46990|  29.97180|1.18  |lreplace L[10000] shared-span 0 (end-1:end) elems at end-1 with 3 elems 1 times.
195.  35.47750|  30.15570|1.18  |lreplace L[10000] shared-span 0 (end-1:end) elems at end-1 with 2 elems 1 times.
196.  35.50200|  30.01660|1.18  |lreplace L[10000] shared-span 0 (end-1:end) elems at end-1 with 1 elems 1 times.

Pure inserts into an unshared list

There is significant improvement when the number of elements before the insertion point is much smaller than the number after (227-229).

197.   0.87500|   0.79170|1.11  |lreplace L[10] unshared 0 (0:-1) elems at 0 with 1 elems 1 times.
198.   0.91670|   0.41670|2.20  |lreplace L[10] unshared 0 (0:-1) elems at 0 with 10 elems 1 times.
199.   0.83330|   0.37500|2.22  |lreplace L[10] unshared 0 (1:-1) elems at 1 with 1 elems 1 times.
200.   0.87500|   0.87500|1.00  |lreplace L[10] unshared 0 (1:-1) elems at 1 with 10 elems 1 times.
201.   0.83330|   0.87500|0.95  |lreplace L[10] unshared 0 (5:-1) elems at 5 with 1 elems 1 times.
202.   0.37500|   0.75000|0.50  |lreplace L[10] unshared 0 (5:-1) elems at 5 with 10 elems 1 times.
203.   0.37500|   0.87500|0.43  |lreplace L[10] unshared 0 (end-1:-1) elems at end-1 with 1 elems 1 times.
204.   0.41670|   0.41670|1.00  |lreplace L[10] unshared 0 (end-1:-1) elems at end-1 with 10 elems 1 times.
205.   0.75000|   0.87500|0.86  |lreplace L[10] unshared 0 (end:-1) elems at end with 1 elems 1 times.
206.   0.37500|   0.95830|0.39  |lreplace L[10] unshared 0 (end:-1) elems at end with 10 elems 1 times.
207.   0.70410|   0.70410|1.00  |lreplace L[100] unshared 0 (0:-1) elems at 0 with 1 elems 1 times.
208.   0.42860|   0.30610|1.40  |lreplace L[100] unshared 0 (0:-1) elems at 0 with 10 elems 1 times.
209.   0.34010|   0.28910|1.18  |lreplace L[100] unshared 0 (1:-1) elems at 1 with 1 elems 1 times.
210.   0.83330|   0.80270|1.04  |lreplace L[100] unshared 0 (1:-1) elems at 1 with 10 elems 1 times.
211.   0.30950|   1.49660|0.21  |lreplace L[100] unshared 0 (50:-1) elems at 50 with 1 elems 1 times.
212.   0.82650|   0.80950|1.02  |lreplace L[100] unshared 0 (50:-1) elems at 50 with 10 elems 1 times.
213.   0.28570|   0.29250|0.98  |lreplace L[100] unshared 0 (end-1:-1) elems at end-1 with 1 elems 1 times.
214.   0.31290|   0.35030|0.89  |lreplace L[100] unshared 0 (end-1:-1) elems at end-1 with 10 elems 1 times.
215.   0.76190|   0.74490|1.02  |lreplace L[100] unshared 0 (end:-1) elems at end with 1 elems 1 times.
216.   0.38100|   0.77550|0.49  |lreplace L[100] unshared 0 (end:-1) elems at end with 10 elems 1 times.
217.   0.86670|   0.24000|3.61  |lreplace L[1000] unshared 0 (0:-1) elems at 0 with 1 elems 1 times.
218.   0.54400|   0.32530|1.67  |lreplace L[1000] unshared 0 (0:-1) elems at 0 with 10 elems 1 times.
219.   0.45870|   0.25600|1.79  |lreplace L[1000] unshared 0 (1:-1) elems at 1 with 1 elems 1 times.
220.   0.57330|   0.73600|0.78  |lreplace L[1000] unshared 0 (1:-1) elems at 1 with 10 elems 1 times.
221.   0.82400|   0.32800|2.51  |lreplace L[1000] unshared 0 (500:-1) elems at 500 with 1 elems 1 times.
222.   0.51200|   0.88000|0.58  |lreplace L[1000] unshared 0 (500:-1) elems at 500 with 10 elems 1 times.
223.   0.29600|   0.76270|0.39  |lreplace L[1000] unshared 0 (end-1:-1) elems at end-1 with 1 elems 1 times.
224.   0.52800|   0.84800|0.62  |lreplace L[1000] unshared 0 (end-1:-1) elems at end-1 with 10 elems 1 times.
225.   0.27730|   0.74930|0.37  |lreplace L[1000] unshared 0 (end:-1) elems at end with 1 elems 1 times.
226.   0.36270|   0.39200|0.93  |lreplace L[1000] unshared 0 (end:-1) elems at end with 10 elems 1 times.
227.   2.29090|   0.27250|8.41  |lreplace L[10000] unshared 0 (0:-1) elems at 0 with 1 elems 1 times.
228.   3.16880|   0.34930|9.07  |lreplace L[10000] unshared 0 (0:-1) elems at 0 with 10 elems 1 times.
229.   2.31570|   0.26000|8.91  |lreplace L[10000] unshared 0 (1:-1) elems at 1 with 1 elems 1 times.
230.   3.12450|   1.53010|2.04  |lreplace L[10000] unshared 0 (1:-1) elems at 1 with 10 elems 1 times.
231.   1.36030|   1.02910|1.32  |lreplace L[10000] unshared 0 (5000:-1) elems at 5000 with 1 elems 1 times.
232.   2.33390|   1.58240|1.47  |lreplace L[10000] unshared 0 (5000:-1) elems at 5000 with 10 elems 1 times.
233.   0.36160|   0.31870|1.13  |lreplace L[10000] unshared 0 (end-1:-1) elems at end-1 with 1 elems 1 times.
234.   0.34850|   1.26880|0.27  |lreplace L[10000] unshared 0 (end-1:-1) elems at end-1 with 10 elems 1 times.
235.   0.30770|   0.30590|1.01  |lreplace L[10000] unshared 0 (end:-1) elems at end with 1 elems 1 times.
236.   0.38990|   1.24130|0.31  |lreplace L[10000] unshared 0 (end:-1) elems at end with 10 elems 1 times.

Pure deletes in an unshared list

There is no measured difference in performance.

Note: this has to be looked at further. I would have expected a 2x improvement for deletions from the head for the 10000 element list based on other results.

237.   0.87500|   1.00000|0.88  |lreplace L[10] unshared 0:0 with 0 elems 1 times.
238.   1.00000|   1.00000|1.00  |lreplace L[10] unshared 1:1 with 0 elems 1 times.
239.   1.00000|   1.79170|0.56  |lreplace L[10] unshared 5:5 with 0 elems 1 times.
240.   1.08330|   0.37500|2.89  |lreplace L[10] unshared end-1:end-1 with 0 elems 1 times.
241.   0.58330|   0.50000|1.17  |lreplace L[10] unshared end:end with 0 elems 1 times.
242.   0.96940|   0.37410|2.59  |lreplace L[100] unshared 0:0 with 0 elems 1 times.
243.   0.39120|   0.45920|0.85  |lreplace L[100] unshared 1:1 with 0 elems 1 times.
244.   0.53400|   0.34690|1.54  |lreplace L[100] unshared 50:50 with 0 elems 1 times.
245.   0.94900|   0.40820|2.32  |lreplace L[100] unshared end-1:end-1 with 0 elems 1 times.
246.   0.46260|   0.43540|1.06  |lreplace L[100] unshared end:end with 0 elems 1 times.
247.   0.86400|   0.41870|2.06  |lreplace L[1000] unshared 0:0 with 0 elems 1 times.
248.   0.88800|   0.38400|2.31  |lreplace L[1000] unshared 1:1 with 0 elems 1 times.
249.   0.38400|   0.90670|0.42  |lreplace L[1000] unshared 500:500 with 0 elems 1 times.
250.   0.99470|   0.99200|1.00  |lreplace L[1000] unshared end-1:end-1 with 0 elems 1 times.
251.   0.97070|   0.42400|2.29  |lreplace L[1000] unshared end:end with 0 elems 1 times.
252.   0.39170|   0.36000|1.09  |lreplace L[10000] unshared 0:0 with 0 elems 1 times.
253.   0.34560|   0.40590|0.85  |lreplace L[10000] unshared 1:1 with 0 elems 1 times.
254.   0.40850|   0.38690|1.06  |lreplace L[10000] unshared 5000:5000 with 0 elems 1 times.
255.   0.54130|   0.67390|0.80  |lreplace L[10000] unshared end-1:end-1 with 0 elems 1 times.
256.   0.44610|   0.44750|1.00  |lreplace L[10000] unshared end:end with 0 elems 1 times.

Replacements in unshared list

The TIP 625 implementation is a few times faster (293, 295, 296, 341, 343, 344) when the starting replacement index is much closer to the head than the tail. Again this is because TIP 625 permits moving the shorter segment to make room for insertions.

257.   1.00000|   1.00000|1.00  |lreplace L[10] unshared 0:1 with 3 elems 1 times.
258.   0.37500|   0.37500|1.00  |lreplace L[10] unshared 0:1 with 2 elems 1 times.
259.   1.00000|   1.00000|1.00  |lreplace L[10] unshared 0:1 with 1 elems 1 times.
260.   0.50000|   1.04170|0.48  |lreplace L[10] unshared 1:2 with 3 elems 1 times.
261.   1.00000|   0.87500|1.14  |lreplace L[10] unshared 1:2 with 2 elems 1 times.
262.   0.50000|   2.50000|0.20  |lreplace L[10] unshared 1:2 with 1 elems 1 times.
263.   1.12500|   1.12500|1.00  |lreplace L[10] unshared 0 (end-2:end-1) elems at end-2 with 3 elems 1 times.
264.   1.00000|   1.12500|0.89  |lreplace L[10] unshared 0 (end-2:end-1) elems at end-2 with 2 elems 1 times.
265.   1.25000|   0.66670|1.87  |lreplace L[10] unshared 0 (end-2:end-1) elems at end-2 with 1 elems 1 times.
266.   0.41670|   1.00000|0.42  |lreplace L[10] unshared 0 (end-1:end) elems at end-1 with 3 elems 1 times.
267.   1.08330|   0.58330|1.86  |lreplace L[10] unshared 0 (end-1:end) elems at end-1 with 2 elems 1 times.
268.   0.58330|   1.12500|0.52  |lreplace L[10] unshared 0 (end-1:end) elems at end-1 with 1 elems 1 times.
269.   0.96940|   0.41500|2.34  |lreplace L[100] unshared 0:1 with 3 elems 1 times.
270.   0.42520|   0.91840|0.46  |lreplace L[100] unshared 0:1 with 2 elems 1 times.
271.   0.48640|   0.90480|0.54  |lreplace L[100] unshared 0:1 with 1 elems 1 times.
272.   0.47280|   0.43880|1.08  |lreplace L[100] unshared 1:2 with 3 elems 1 times.
273.   0.91160|   0.98640|0.92  |lreplace L[100] unshared 1:2 with 2 elems 1 times.
274.   0.53740|   0.32990|1.63  |lreplace L[100] unshared 1:2 with 1 elems 1 times.
275.   0.99660|   1.02040|0.98  |lreplace L[100] unshared 0 (end-2:end-1) elems at end-2 with 3 elems 1 times.
276.   0.47280|   0.42520|1.11  |lreplace L[100] unshared 0 (end-2:end-1) elems at end-2 with 2 elems 1 times.
277.   0.51360|   0.50000|1.03  |lreplace L[100] unshared 0 (end-2:end-1) elems at end-2 with 1 elems 1 times.
278.   0.97960|   0.98640|0.99  |lreplace L[100] unshared 0 (end-1:end) elems at end-1 with 3 elems 1 times.
279.   0.94560|   0.96600|0.98  |lreplace L[100] unshared 0 (end-1:end) elems at end-1 with 2 elems 1 times.
280.   0.48300|   0.52720|0.92  |lreplace L[100] unshared 0 (end-1:end) elems at end-1 with 1 elems 1 times.
281.   0.56800|   0.44000|1.29  |lreplace L[1000] unshared 0:1 with 3 elems 1 times.
282.   0.46130|   0.91200|0.51  |lreplace L[1000] unshared 0:1 with 2 elems 1 times.
283.   0.53870|   0.55470|0.97  |lreplace L[1000] unshared 0:1 with 1 elems 1 times.
284.   1.14400|   0.40000|2.86  |lreplace L[1000] unshared 1:2 with 3 elems 1 times.
285.   0.41600|   0.37600|1.11  |lreplace L[1000] unshared 1:2 with 2 elems 1 times.
286.   0.44000|   0.39730|1.11  |lreplace L[1000] unshared 1:2 with 1 elems 1 times.
287.   0.98400|   0.50670|1.94  |lreplace L[1000] unshared 0 (end-2:end-1) elems at end-2 with 3 elems 1 times.
288.   0.78930|   0.49870|1.58  |lreplace L[1000] unshared 0 (end-2:end-1) elems at end-2 with 2 elems 1 times.
289.   1.01070|   0.99200|1.02  |lreplace L[1000] unshared 0 (end-2:end-1) elems at end-2 with 1 elems 1 times.
290.   0.96530|   0.48270|2.00  |lreplace L[1000] unshared 0 (end-1:end) elems at end-1 with 3 elems 1 times.
291.   1.00000|   0.98130|1.02  |lreplace L[1000] unshared 0 (end-1:end) elems at end-1 with 2 elems 1 times.
292.   0.46930|   0.44000|1.07  |lreplace L[1000] unshared 0 (end-1:end) elems at end-1 with 1 elems 1 times.
293.   2.44610|   0.45010|5.43  |lreplace L[10000] unshared 0:1 with 3 elems 1 times.
294.   0.41490|   0.39600|1.05  |lreplace L[10000] unshared 0:1 with 2 elems 1 times.
295.   1.81360|   0.39630|4.58  |lreplace L[10000] unshared 0:1 with 1 elems 1 times.
296.   2.60000|   0.38850|6.69  |lreplace L[10000] unshared 1:2 with 3 elems 1 times.
297.   0.44320|   0.40720|1.09  |lreplace L[10000] unshared 1:2 with 2 elems 1 times.
298.   1.49570|   0.46590|3.21  |lreplace L[10000] unshared 1:2 with 1 elems 1 times.
299.   0.54000|   0.52080|1.04  |lreplace L[10000] unshared 0 (end-2:end-1) elems at end-2 with 3 elems 1 times.
300.   0.42930|   0.49250|0.87  |lreplace L[10000] unshared 0 (end-2:end-1) elems at end-2 with 2 elems 1 times.
301.   0.48510|   0.52480|0.92  |lreplace L[10000] unshared 0 (end-2:end-1) elems at end-2 with 1 elems 1 times.
302.   0.53410|   0.47120|1.13  |lreplace L[10000] unshared 0 (end-1:end) elems at end-1 with 3 elems 1 times.
303.   0.49710|   0.48210|1.03  |lreplace L[10000] unshared 0 (end-1:end) elems at end-1 with 2 elems 1 times.
304.   0.44850|   0.49230|0.91  |lreplace L[10000] unshared 0 (end-1:end) elems at end-1 with 1 elems 1 times.
305.   0.37500|   0.37500|1.00  |lreplace L[10] unshared-span 0:1 with 3 elems 1 times.
306.   0.37500|   0.87500|0.43  |lreplace L[10] unshared-span 0:1 with 2 elems 1 times.
307.   0.37500|   0.87500|0.43  |lreplace L[10] unshared-span 0:1 with 1 elems 1 times.
308.   0.37500|   0.37500|1.00  |lreplace L[10] unshared-span 1:2 with 3 elems 1 times.
309.   0.87500|   0.41670|2.10  |lreplace L[10] unshared-span 1:2 with 2 elems 1 times.
310.   0.37500|   1.16670|0.32  |lreplace L[10] unshared-span 1:2 with 1 elems 1 times.
311.   1.00000|   1.00000|1.00  |lreplace L[10] unshared-span 0 (end-2:end-1) elems at end-2 with 3 elems 1 times.
312.   1.00000|   1.00000|1.00  |lreplace L[10] unshared-span 0 (end-2:end-1) elems at end-2 with 2 elems 1 times.
313.   0.45830|   1.00000|0.46  |lreplace L[10] unshared-span 0 (end-2:end-1) elems at end-2 with 1 elems 1 times.
314.   1.00000|   1.00000|1.00  |lreplace L[10] unshared-span 0 (end-1:end) elems at end-1 with 3 elems 1 times.
315.   1.00000|   1.12500|0.89  |lreplace L[10] unshared-span 0 (end-1:end) elems at end-1 with 2 elems 1 times.
316.   1.00000|   0.45830|2.18  |lreplace L[10] unshared-span 0 (end-1:end) elems at end-1 with 1 elems 1 times.
317.   0.41500|   0.91500|0.45  |lreplace L[100] unshared-span 0:1 with 3 elems 1 times.
318.   0.40140|   0.38100|1.05  |lreplace L[100] unshared-span 0:1 with 2 elems 1 times.
319.   0.96600|   0.37760|2.56  |lreplace L[100] unshared-span 0:1 with 1 elems 1 times.
320.   0.42180|   0.92520|0.46  |lreplace L[100] unshared-span 1:2 with 3 elems 1 times.
321.   0.40140|   0.87070|0.46  |lreplace L[100] unshared-span 1:2 with 2 elems 1 times.
322.   1.00680|   0.91500|1.10  |lreplace L[100] unshared-span 1:2 with 1 elems 1 times.
323.   0.45240|   1.02040|0.44  |lreplace L[100] unshared-span 0 (end-2:end-1) elems at end-2 with 3 elems 1 times.
324.   1.00340|   0.44900|2.23  |lreplace L[100] unshared-span 0 (end-2:end-1) elems at end-2 with 2 elems 1 times.
325.   0.45580|   1.01020|0.45  |lreplace L[100] unshared-span 0 (end-2:end-1) elems at end-2 with 1 elems 1 times.
326.   0.97620|   0.99660|0.98  |lreplace L[100] unshared-span 0 (end-1:end) elems at end-1 with 3 elems 1 times.
327.   0.98640|   0.93540|1.05  |lreplace L[100] unshared-span 0 (end-1:end) elems at end-1 with 2 elems 1 times.
328.   0.48980|   0.47960|1.02  |lreplace L[100] unshared-span 0 (end-1:end) elems at end-1 with 1 elems 1 times.
329.   0.54130|   0.91200|0.59  |lreplace L[1000] unshared-span 0:1 with 3 elems 1 times.
330.   0.90930|   0.87730|1.04  |lreplace L[1000] unshared-span 0:1 with 2 elems 1 times.
331.   1.02670|   0.92000|1.12  |lreplace L[1000] unshared-span 0:1 with 1 elems 1 times.
332.   0.89870|   0.39200|2.29  |lreplace L[1000] unshared-span 1:2 with 3 elems 1 times.
333.   0.89330|   0.93330|0.96  |lreplace L[1000] unshared-span 1:2 with 2 elems 1 times.
334.   0.48800|   0.88800|0.55  |lreplace L[1000] unshared-span 1:2 with 1 elems 1 times.
335.   1.67200|   0.99470|1.68  |lreplace L[1000] unshared-span 0 (end-2:end-1) elems at end-2 with 3 elems 1 times.
336.   0.52800|   0.44800|1.18  |lreplace L[1000] unshared-span 0 (end-2:end-1) elems at end-2 with 2 elems 1 times.
337.   0.50400|   0.44530|1.13  |lreplace L[1000] unshared-span 0 (end-2:end-1) elems at end-2 with 1 elems 1 times.
338.   0.48270|   0.42930|1.12  |lreplace L[1000] unshared-span 0 (end-1:end) elems at end-1 with 3 elems 1 times.
339.   0.44530|   0.45330|0.98  |lreplace L[1000] unshared-span 0 (end-1:end) elems at end-1 with 2 elems 1 times.
340.   0.48530|   0.99470|0.49  |lreplace L[1000] unshared-span 0 (end-1:end) elems at end-1 with 1 elems 1 times.
341.   2.48640|   0.40530|6.13  |lreplace L[10000] unshared-span 0:1 with 3 elems 1 times.
342.   0.41890|   0.40930|1.02  |lreplace L[10000] unshared-span 0:1 with 2 elems 1 times.
343.   1.79730|   0.39870|4.51  |lreplace L[10000] unshared-span 0:1 with 1 elems 1 times.
344.   2.42000|   0.41730|5.80  |lreplace L[10000] unshared-span 1:2 with 3 elems 1 times.
345.   0.37920|   0.41360|0.92  |lreplace L[10000] unshared-span 1:2 with 2 elems 1 times.
346.   1.77710|   0.41440|4.29  |lreplace L[10000] unshared-span 1:2 with 1 elems 1 times.
347.   0.50530|   0.42830|1.18  |lreplace L[10000] unshared-span 0 (end-2:end-1) elems at end-2 with 3 elems 1 times.
348.   0.46240|   0.46690|0.99  |lreplace L[10000] unshared-span 0 (end-2:end-1) elems at end-2 with 2 elems 1 times.
349.   0.74880|   0.47840|1.57  |lreplace L[10000] unshared-span 0 (end-2:end-1) elems at end-2 with 1 elems 1 times.
350.   0.41440|   0.46510|0.89  |lreplace L[10000] unshared-span 0 (end-1:end) elems at end-1 with 3 elems 1 times.
351.   0.40290|   0.47520|0.85  |lreplace L[10000] unshared-span 0 (end-1:end) elems at end-1 with 2 elems 1 times.
352.   0.64530|   0.45630|1.41  |lreplace L[10000] unshared-span 0 (end-1:end) elems at end-1 with 1 elems 1 times.

Total run time

353.2129.60240|1799.40910|1.18  |lreplace total run time

lreverse

TIP 625 does not change the implementation of lreverse.

           [1]           [2]
1.     0.28000|   0.32230|0.87  |lreverse L[10] shared
2.     0.54080|   0.52420|1.03  |lreverse L[100] shared
3.     3.12020|   2.99680|1.04  |lreverse L[1000] shared
4.     3.12240|   2.97590|1.05  |lreverse L[1000] shared-span
5.    28.84760|  28.37830|1.02  |lreverse L[10000] shared
6.    29.05440|  28.26280|1.03  |lreverse L[10000] shared-span
7.     0.08260|   0.04570|1.81  |lreverse L[10] unshared
8.     0.16640|   0.11280|1.48  |lreverse L[100] unshared
9.     0.13310|   0.07190|1.85  |lreverse L[100] unshared-span
10.    0.60120|   0.74040|0.81  |lreverse L[1000] unshared
11.    0.35760|   0.37410|0.96  |lreverse L[1000] unshared-span
12.    3.32980|   3.39540|0.98  |lreverse L[10000] unshared
13.    3.29130|   3.27690|1.00  |lreverse L[10000] unshared-span
14.   72.92740|  71.47740|1.02  |lreverse total run time

lsort

TIP 625 does not change the implementation of lsort.

           [1]           [2]
1.  1235.98330|1076.14330|1.15  |lsort L[10000] shared
2.  1204.60000|1050.87670|1.15  |lsort L[9998] shared-span
3.  1195.14670|1038.43000|1.15  |lsort L[10000] unshared
4.  1201.93670|1051.67330|1.14  |lsort L[9998] unshared-span
5.  4837.66670|4217.12330|1.15  |lsort total run time

lsearch

TIP 625 does not change the implementation of lsearch.

           [1]           [2]
1.     0.43450|   0.39900|1.09  |lsearch L[10] shared
2.     1.27670|   1.25140|1.02  |lsearch L[100] shared
3.     9.97910|   9.79560|1.02  |lsearch L[1000] shared
4.    96.00840|  94.60320|1.01  |lsearch L[10000] shared
5.     0.44090|   0.40390|1.09  |lsearch L[10] shared-span
6.     1.28580|   1.28200|1.00  |lsearch L[100] shared-span
7.    10.00410|   9.80580|1.02  |lsearch L[1000] shared-span
8.    96.09630|  93.87000|1.02  |lsearch L[10000] shared-span
9.   215.52570| 211.41090|1.02  |lsearch total run time

concat

The performance of concat is more or less the same. The implementation in TIP 625 is a little different however. Since the list store no long directly represents the contents of a Tcl list in the presence of a span in the internal representation, the canonical list marker has been moved from the element storage structure (List pre-625, ListStore post-625) to the ListSpan structure.

           [1]           [2]
1.     0.39210|   0.45290|0.87  |concat L[10] pure lists with elements of length 1
2.     0.39130|   0.42740|0.92  |concat L[10] canonical lists with elements of length 1
3.     0.52120|   0.51800|1.01  |concat L[10] non-canonical lists with elements of length 1
4.     0.39150|   0.44130|0.89  |concat L[10] pure lists with elements of length 100
5.     0.39300|   0.43200|0.91  |concat L[10] canonical lists with elements of length 100
6.     0.49680|   0.55880|0.89  |concat L[10] non-canonical lists with elements of length 100
7.     1.02070|   0.88440|1.15  |concat L[100] pure lists with elements of length 1
8.     1.01440|   0.88620|1.14  |concat L[100] canonical lists with elements of length 1
9.     0.54440|   0.54540|1.00  |concat L[100] non-canonical lists with elements of length 1
10.    1.02290|   0.89080|1.15  |concat L[100] pure lists with elements of length 100
11.    1.01180|   0.88060|1.15  |concat L[100] canonical lists with elements of length 100
12.    1.15390|   1.13920|1.01  |concat L[100] non-canonical lists with elements of length 100
13.    7.55860|   6.06680|1.25  |concat L[1000] pure lists with elements of length 1
14.    7.55550|   6.02160|1.25  |concat L[1000] canonical lists with elements of length 1
15.    0.59930|   0.51360|1.17  |concat L[1000] non-canonical lists with elements of length 1
16.    7.54490|   6.06080|1.24  |concat L[1000] pure lists with elements of length 100
17.    7.53940|   6.10690|1.23  |concat L[1000] canonical lists with elements of length 100
18.    5.61890|   5.89150|0.95  |concat L[1000] non-canonical lists with elements of length 100
19.   73.01750|  60.45310|1.21  |concat L[10000] pure lists with elements of length 1
20.   73.15510|  60.58030|1.21  |concat L[10000] canonical lists with elements of length 1
21.    1.51330|   1.68590|0.90  |concat L[10000] non-canonical lists with elements of length 1
22.   73.16820|  60.36880|1.21  |concat L[10000] pure lists with elements of length 100
23.   73.03110|  60.63200|1.20  |concat L[10000] canonical lists with elements of length 100
24.  560.61300| 561.31200|1.00  |concat L[10000] non-canonical lists with elements of length 100
25.    0.38680|   0.42730|0.91  |concat L[10] pure spanned lists with elements of length 1
26.    0.38390|   0.42340|0.91  |concat L[10] canonical spanned lists with elements of length 1
27.    0.39030|   0.47080|0.83  |concat L[10] pure spanned lists with elements of length 100
28.    0.39880|   0.45830|0.87  |concat L[10] canonical spanned lists with elements of length 100
29.    1.01650|   0.88040|1.15  |concat L[100] pure spanned lists with elements of length 1
30.    1.01970|   0.88460|1.15  |concat L[100] canonical spanned lists with elements of length 1
31.    1.02070|   0.88790|1.15  |concat L[100] pure spanned lists with elements of length 100
32.    1.01970|   0.88440|1.15  |concat L[100] canonical spanned lists with elements of length 100
33.    7.57620|   6.31530|1.20  |concat L[1000] pure spanned lists with elements of length 1
34.    7.58030|   6.18480|1.23  |concat L[1000] canonical spanned lists with elements of length 1
35.    7.60980|   6.33390|1.20  |concat L[1000] pure spanned lists with elements of length 100
36.    7.58360|   6.18870|1.23  |concat L[1000] canonical spanned lists with elements of length 100
37.   73.03940|  61.31010|1.19  |concat L[10000] pure spanned lists with elements of length 1
38.   73.09240|  61.00820|1.20  |concat L[10000] canonical spanned lists with elements of length 1
39.   73.10410|  60.94180|1.20  |concat L[10000] pure spanned lists with elements of length 100
40.   72.63530|  60.26010|1.21  |concat L[10000] canonical spanned lists with elements of length 100
41. 1227.12620|1117.61030|1.10  |concat total run time

lindex

TIP 625 does not fundamentally change the implementation of lindex except the index lookup has a level of indirection when a span is present.

           [1]           [2]
1.     0.34410|   0.34050|1.01  |lindex L[10] shared at 5
2.     0.30290|   0.32290|0.94  |lindex L[100] shared at 50
3.     0.35450|   0.33670|1.05  |lindex L[100] shared-span at 50
4.     0.32070|   0.34110|0.94  |lindex L[1000] shared at 500
5.     0.31040|   0.34520|0.90  |lindex L[1000] shared-span at 500
6.     0.28380|   0.28780|0.99  |lindex L[10000] shared at 5000
7.     0.33510|   0.31780|1.05  |lindex L[10000] shared-span at 5000
8.     2.25130|   2.29190|0.98  |lindex total run time

join

TIP 625 does not change the implementation of join.

           [1]           [2]
1.     0.63350|   0.73150|0.87  |join L[10] shared
2.     3.31150|   3.51940|0.94  |join L[100] shared
3.    28.70850|  29.40520|0.98  |join L[1000] shared
4.   283.47030| 301.63530|0.94  |join L[10000] shared
5.     0.68130|   0.66160|1.03  |join L[10] shared-span
6.     3.20260|   3.18550|1.01  |join L[100] shared-span
7.    30.30590|  29.93550|1.01  |join L[1000] shared-span
8.   292.52900| 282.82870|1.03  |join L[10000] shared-span
9.   642.84250| 651.90270|0.99  |join total run time

split

The split command is primarily a test of string conversion to lists. TIP 625 does not fundamentally change this as no spans are created or additional free space allocated.

           [1]           [2]
1.     1.13950|   1.20560|0.95  |split L[10]
2.     7.84830|   8.06740|0.97  |split L[100]
3.    67.91360|  71.40540|0.95  |split L[1000]
4.   745.95000| 741.73270|1.01  |split L[10000]
5.   822.85130| 822.41110|1.00  |split total run time

llength

TIP 625 does not fundamentally change the implementation of llength except the index lookup has a level of indirection when a span is present.

           [1]           [2]
1.     0.16300|   0.16470|0.99  |llength L[10] shared
2.     0.16430|   0.15990|1.03  |llength L[100] shared
3.     0.16770|   0.16350|1.03  |llength L[100] shared-span
4.     0.16100|   0.15750|1.02  |llength L[1000] shared
5.     0.17380|   0.17630|0.99  |llength L[1000] shared-span
6.     0.15780|   0.17000|0.93  |llength L[10000] shared
7.     0.21030|   0.19790|1.06  |llength L[10000] shared-span
8.     1.19790|   1.19000|1.01  |llength total run time

lrepeat

TIP 625 does not change the implementation of lrepeat.

           [1]           [2]
1.     0.32680|   0.29960|1.09  |lrepeat L[10] 1 elems at a time
2.     0.40190|   0.42080|0.96  |lrepeat L[10] 5 elems at a time
3.     0.47420|   0.44520|1.07  |lrepeat L[100] 1 elems at a time
4.     1.18740|   1.41090|0.84  |lrepeat L[100] 5 elems at a time
5.     2.04560|   1.88900|1.08  |lrepeat L[1000] 1 elems at a time
6.     9.70230|  11.49970|0.84  |lrepeat L[1000] 5 elems at a time
7.    18.70830|  17.58500|1.06  |lrepeat L[10000] 1 elems at a time
8.    91.49820| 110.88470|0.83  |lrepeat L[10000] 5 elems at a time
9.   124.34470| 144.43490|0.86  |lrepeat total run time
10.  124.34470| 144.43490|0.86  |Total run time

lmap

TIP 625 does not change the implementation of lmap.

           [1]           [2]
1.     3.77170|   3.72460|1.01  |lmap L[10] shared
2.    30.98280|  30.33220|1.02  |lmap L[100] shared
3.   281.95500| 296.92430|0.95  |lmap L[1000] shared
4.  2836.64670|2810.33000|1.01  |lmap L[10000] shared
5.     3.43640|   3.35300|1.02  |lmap L[10] shared-span
6.    29.05240|  30.18750|0.96  |lmap L[100] shared-span
7.   278.59670| 303.73630|0.92  |lmap L[1000] shared-span
8.  2791.50330|2765.93670|1.01  |lmap L[10000] shared-span
9.  6255.94490|6244.52470|1.00  |lmap total run time
10. 6255.94490|6244.52470|1.00  |Total run time

foreach

TIP 625 does not change the implementation of foreach.

           [1]           [2]
1.     3.30660|   3.29140|1.00  |foreach L[10] shared
2.    28.85590|  27.62580|1.04  |foreach L[100] shared
3.   289.98170| 283.34770|1.02  |foreach L[1000] shared
4.  2919.51000|2836.30000|1.03  |foreach L[10000] shared
5.     3.08390|   2.66870|1.16  |foreach L[10] shared-span
6.    28.62160|  27.74730|1.03  |foreach L[100] shared-span
7.   287.61600| 283.09830|1.02  |foreach L[1000] shared-span
8.  2908.58670|2822.31330|1.03  |foreach L[10000] shared-span
9.  6469.56230|6286.39250|1.03  |foreach total run time

Memory statistics

The sections below shows memory statistics when compiled with TCL_MEM_DEBUG and with TCL_FINALIZE_ON_EXIT set. The statistics are based on a full run of the performance suite across all commands.

Memory leaks

The following snippets show the output of memory onexit for the two implementations. As seen, both have identical allocation left over on exit.

8.7

0000027E7D6E0428 - 0000027E7D6E0457  48 @ D:\src\tcltk\list-redux\tcl\win\..\generic\tclBasic.c 4877 
0000027E7D6E17A8 - 0000027E7D6E17D7  48 @ D:\src\tcltk\list-redux\tcl\win\..\generic\tclBasic.c 4712 
0000027E7D6E0D28 - 0000027E7D6E0D57  48 @ D:\src\tcltk\list-redux\tcl\win\..\generic\tclExecute.c 2880 
0000027E7D6E16A8 - 0000027E7D6E16D7  48 @ D:\src\tcltk\list-redux\tcl\win\..\generic\tclBasic.c 6660 
0000027E7D28ADE8 - 0000027E7D28AEB3  204 @ D:\src\tcltk\list-redux\tcl\win\..\generic\tclCompile.c 2855 
0000027E7D6E08A8 - 0000027E7D6E08CF  40 @ D:\src\tcltk\list-redux\tcl\win\..\generic\tclObj.c 4541 
0000027E7DA509E8 - 0000027E7DA509EC  5 @ D:\src\tcltk\list-redux\tcl\win\..\generic\tclLiteral.c 255 
0000027E7D6E15A8 - 0000027E7D6E15D7  48 @ D:\src\tcltk\list-redux\tcl\win\..\generic\tclLiteral.c 250 
0000027E7DA76CA8 - 0000027E7DA76CB2  11 @ D:\src\tcltk\list-redux\tcl\win\..\generic\tclStringObj.c 151 
0000027E7D6E0E28 - 0000027E7D6E0E57  48 @ D:\src\tcltk\list-redux\tcl\win\..\generic\tclStringObj.c 2847 
0000027E7CB9CD28 - 0000027E7CB9CD57  48 @ unknown 0 
0000027E7CB9A8A8 - 0000027E7CB9A8D7  48 @ unknown 0 
0000027E7CB9C8A8 - 0000027E7CB9C8D7  48 @ unknown 0 
0000027E7C6D7428 - 0000027E7C6D7457  48 @ unknown 0 
0000027E7C6FFA28 - 0000027E7C6FFA57  48 @ unknown 0 
0000027E7C6FD5A8 - 0000027E7C6FD5D7  48 @ unknown 0 
0000027E7C66DEF8 - 0000027E7C66DF09  18 @ D:\src\tcltk\list-redux\tcl\win\..\generic\tclStringObj.c 338 
0000027E7C5E0008 - 0000027E7C5E0037  48 @ D:\src\tcltk\list-redux\tcl\win\..\generic\tclIOUtil.c 3942 
0000027E7C5CFD88 - 0000027E7C5CFDAF  40 @ D:\src\tcltk\list-redux\tcl\win\..\win\tclWinLoad.c 392 
0000027E7C63F4C8 - 0000027E7C63F4CC  5 @ D:\src\tcltk\list-redux\tcl\win\..\generic\tclStringObj.c 338 
0000027E7C62BDC8 - 0000027E7C62BDF7  48 @ unknown 0 
0000027E7A97A3C8 - 0000027E7A97A3C9  2 @ D:\src\tcltk\list-redux\tcl\win\..\generic\tclLiteral.c 255 
0000027E7A96E4A8 - 0000027E7A96E4D7  48 @ D:\src\tcltk\list-redux\tcl\win\..\generic\tclLiteral.c 250 
0000027E7A72E988 - 0000027E7A72E9F7  112 @ D:\src\tcltk\list-redux\tcl\win\..\generic\tclBasic.c 1071 
0000027E7A7231C8 - 0000027E7A7231DF  24 @ D:\src\tcltk\list-redux\tcl\win\..\generic\tclPreserve.c 329

TIP 625

000001EF07518AA8 - 000001EF07518AD7  48 @ d:\src\tcltk\core-8-branch\tcl\win\..\generic\tclBasic.c 4877 
000001EF07519328 - 000001EF07519357  48 @ d:\src\tcltk\core-8-branch\tcl\win\..\generic\tclBasic.c 4712 
000001EF07518EA8 - 000001EF07518ED7  48 @ d:\src\tcltk\core-8-branch\tcl\win\..\generic\tclExecute.c 2880 
000001EF07519BA8 - 000001EF07519BD7  48 @ d:\src\tcltk\core-8-branch\tcl\win\..\generic\tclBasic.c 6660 
000001EF071BBF18 - 000001EF071BBFE3  204 @ d:\src\tcltk\core-8-branch\tcl\win\..\generic\tclCompile.c 2855 
000001EF075185A8 - 000001EF075185CF  40 @ d:\src\tcltk\core-8-branch\tcl\win\..\generic\tclObj.c 4541 
000001EF06EF0AE8 - 000001EF06EF0AEC  5 @ d:\src\tcltk\core-8-branch\tcl\win\..\generic\tclLiteral.c 255 
000001EF075188A8 - 000001EF075188D7  48 @ d:\src\tcltk\core-8-branch\tcl\win\..\generic\tclLiteral.c 250 
000001EF0722F348 - 000001EF0722F352  11 @ d:\src\tcltk\core-8-branch\tcl\win\..\generic\tclStringObj.c 151 
000001EF075195A8 - 000001EF075195D7  48 @ d:\src\tcltk\core-8-branch\tcl\win\..\generic\tclStringObj.c 2847 
000001EF0681A8A8 - 000001EF0681A8D7  48 @ unknown 0 
000001EF06817CA8 - 000001EF06817CD7  48 @ unknown 0 
000001EF068184A8 - 000001EF068184D7  48 @ unknown 0 
000001EF0642B7B8 - 000001EF0642B7E7  48 @ unknown 0 
000001EF0645CD38 - 000001EF0645CD67  48 @ unknown 0 
000001EF0645B9B8 - 000001EF0645B9E7  48 @ unknown 0 
000001EF0636FF98 - 000001EF0636FFA9  18 @ d:\src\tcltk\core-8-branch\tcl\win\..\generic\tclStringObj.c 338 
000001EF06338E38 - 000001EF06338E67  48 @ d:\src\tcltk\core-8-branch\tcl\win\..\generic\tclIOUtil.c 3942 
000001EF0632ABB8 - 000001EF0632ABDF  40 @ d:\src\tcltk\core-8-branch\tcl\win\..\win\tclWinLoad.c 392 
000001EF063A0258 - 000001EF063A025C  5 @ d:\src\tcltk\core-8-branch\tcl\win\..\generic\tclStringObj.c 338 
000001EF06391828 - 000001EF06391857  48 @ unknown 0 
000001EF05ECA6B8 - 000001EF05ECA6B9  2 @ d:\src\tcltk\core-8-branch\tcl\win\..\generic\tclLiteral.c 255 
000001EF05EBFB78 - 000001EF05EBFBA7  48 @ d:\src\tcltk\core-8-branch\tcl\win\..\generic\tclLiteral.c 250 
000001EF0454D4C8 - 000001EF0454D537  112 @ d:\src\tcltk\core-8-branch\tcl\win\..\generic\tclBasic.c 1071 
000001EF04544598 - 000001EF045445AF  24 @ d:\src\tcltk\core-8-branch\tcl\win\..\generic\tclPreserve.c 329

Memory usage

The comparison below of memory info shows no statistical difference between the two implementation.

    [1]           [2]
5591454.58600|5803295.19000|0.96  |memdbg total mallocs (in thousands)
5591392.09200|5803232.53600|0.96  |memdbg total frees (in thousands)
     62.49400|  62.65400|1.00  |memdbg current packets allocated (in thousands)
   4516.11500|4530.28300|1.00  |memdbg current bytes allocated (in thousands)
     99.94300|  99.94400|1.00  |memdbg maximum packets allocated (in thousands)
   9612.75600|9617.71900|1.00  |memdbg maximum bytes allocated (in thousands)

The same is true of the memory statistics as returned by Windows.

    [1]           [2]
  12.56640|  12.53910|1.00  |Memory (MB) -privatebytes pre-test
  16.53130|  16.17970|1.02  |Memory (MB) -privatebytes post-test
   3.96480|   3.64060|1.09  |Memory (MB) delta -privatebytes
  21.20310|  21.18360|1.00  |Memory (MB) -workingset pre-test
  25.19140|  24.32030|1.04  |Memory (MB) -workingset post-test
   3.98830|   3.13670|1.27  |Memory (MB) delta -workingset
  21.20700|  21.18750|1.00  |Memory (MB) -workingsetpeak pre-test
  29.62890|  29.45310|1.01  |Memory (MB) -workingsetpeak post-test
   8.42190|   8.26560|1.02  |Memory (MB) delta -workingsetpeak

The above numbers however do not tell the whole story because they only shows statistics at the end of a program. They do not make any statement about how long objects are held on to in a real application.

Memory wastage in the pre-TIP 625 implementation comes from overallocation of space in the list storage area which makes further list append operations O(1). The TIP 625 implementation also has this overallocation overhead but in addition may keep objects alive for longer than needed which contributes to memory overhead. This is offset by increased sharing of memory between lists.

Consider the following sequence of pseudo-commands.

1. while {[incr i] <= 1000} {lappend L $i}
2. set R [lrange $L 250 749]
3. unset L
4. lappend R X

After 1. both implementations use the same amount of memory for the list (ignoring fixed overhead) - 1000 allocated element Tcl_Obj's plus 1000 allocated list slots for the elements plus up to the same number of unused slots for further appends.

After 2. the pre-TIP 625 implementation will have allocated another block of internal storage for 500 elements, copied the appropriate element pointers and incremented their reference counts. The TIP 625 implementation on the other hand, only needs a small additional block for a ListSpan and thus is more memory efficient in addition to being significantly faster.

After 3. the situation is reversed. In the pre-TIP 625 implementation, the original element array will be freed and only the second 500+ element block will remain allocated. In TIP 625 on the other hand, the original 1000+ element array will remain. Moreover, 500 element Tcl_Obj's remain allocated even though they are "garbage" (assuming there are no other references to them). They will be reclaimed (well, reference counts decremented) on the next access to R if there are no other references to the list storage. During that time these objects are unnecessary memory overhead.

Note: as an aside this last delayed freeing of objects can be avoided with the use of the K operator but should generally not be necessary.

After 4. The access to R causes the garbage objects to be reclaimed.

In consideration of the above, the TIP 625 implementation adopts the following policy. A ListRep for a list of N elements will only be implemented with a ListSpan component provided all the following conditions are met. This puts some boundaries on overhead due to late release of objects.

N must be at least TCL_LIST_SPAN_MINSIZE
N must be at least half the size of the currently in-use space of the corresponding ListStore
N must be at least 3/8 the size of the total allocated space for the ListStore.

If any of the above conditions are not met, the list internal representation will just allocate a ListStore similar to the pre-TIP 625 implementation without a ListSpan component.

In addition, whereas the current implementation never reduces allocated space, the TIP 625 implementation will reallocate if the used space falls below (currently) a quarter of the allocated space. This saves memory at the cost of speed. Changing this behaviour is orthogonal to rest of the TIP.

In the light of the above, the question posed is whether the TIP 625 memory usage is higher in practice than the pre-TIP 625 implementation and if so, whether the difference is large enough to make the TIP non-viable despite the improvements in speed.

Measurements with long-lived real world applications are needed to ascertain memory impact (memory is less of consideration with ephemeral programs). It is worth keeping in mind that

the garbage objects only occur with range operations and not (for example) prepending etc.
the impact is only felt on usage patterns where the "parent" list's lifetime is shorter than the "child" spanned list and the latter is long lived (for instance, not a local) and is not subsequently modified.

Tests

The Tcl test suite passes with no failures. The existing test suite has been extended with a new test script listRep.test which focuses on code paths in the list implementation in addition to functional tests.

Implementation

See branch tip-625.

Copyright

This document has been placed in the public domain.

TIP 625: Re-implementation of lists

Abstract

Rationale

Specification

Internal representation

Invariants

ListStore space allocation

Apportioning of additional space

Space management in unshared representation

Span management

Performance

Performance testing scripts

Performance measurements

list and list expansion

lappend

linsert

lrange

lassign

lpop

lset

lremove

lreplace

lreverse

lsort

lsearch

concat

lindex

join

split

llength

lrepeat

lmap

foreach

Memory statistics

Memory leaks

Memory usage

Tests

Implementation

Copyright