Re: [TCLCORE] Speed/memory tradeoffs on list operations

[Brian G. <bri...@ea...>]

On Apr 17, 2025, at 04:18, apnmbx-public--- via Tcl-Core <tcl...@li...> wrote:

All,

While Tcl 9 supports strings, lists etc. greater than 2**32, even some
basic operations on data of much smaller lengths has practical
difficulties around execution time and memory space. I am experimenting
with approaches to improve efficiency and looking for opinions and some
guidance on time and memory tradeoffs, starting with list operations
(both existing ones like lreverse as well as new ones like merge, zip).

The most obvious way to improve performance is of course to implement
more commands in C. Consider the operation of "zipping" lists written
in script as "lmap x $l1 y $l2 {list $x $y}". Measuring speed (timerate)
and memory (/proc/self/statm) when zipping lists of size 100000 shows:

Memory pre: 3070 1752 1083 1 0 752 0
lmap $a $b: 46985.7 µs/# 22 # 21.283 #/sec 1033.686 net-ms
Memory post lmap: 7701 6293 1083 1 0 5383 0

The same operation implemented as a "lzip" command in C, is obviously
faster.

Memory pre: 3314 2066 1102 1 0 992 0
lzip $a $b: 13895.7 µs/# 72 # 71.965 #/sec 1000.491 net-ms
Memory post lzip: 7747 6417 1102 1 0 5425 0

Note however the memory requirements are (naturally) the same.

Going further, implementing lzip as a TIP 636 abstract list with an
obvious implementation,

Memory pre: 3314 2076 1112 1 0 992 0
lzip $a $b: 0.270993 µs/# 3298677 # 3690129 #/sec 893.919 net-ms
Memory post lzip: 3314 2076 1112 1 0 992 0

Notice (a) orders of magnitude faster (in fact constant time
irrespective of list length), and (b) *zero* memory cost as the list
arguments' storage is simply referenced.

Alas, there is no free lunch.

The cost of indexing and iterating over the list as "foreach x $l {}" is
significantly higher with abstract lists.

traditional list:
iterate: 18256.1 µs/# 55 # 54.776 #/sec 1004.083 net-ms
index: 0.056268 µs/# 10757211 # 17772142 #/sec 605.285 net-ms
Memory post pure iterate: 7747 6483 1102 1 0 5425 0

abstract list:
iterate: 29596.3 µs/# 34 # 33.788 #/sec 1006.274 net-ms
index: 0.169833 µs/# 4926811 # 5888123 #/sec 836.737 net-ms
Memory post pure iterate: 3314 2076 1112 1 0 992 0

Thus cost of construction+iteration is roughly a wash with the abstract
list implementation coming out slightly ahead. However, if iterating
multiple times, the traditional lists will be much more performant.

The difference (which shows up even for lseq) arises because the
non-abstract implementation is basically a direct access into the C
array holding the elements whereas abstract lists have to construct
elements on request.

Note however, the memory disparity remains.

[The above measured using extension. There might be some improvement in
the core with some byte code support but I do not think it would be
substantial].

Given the lack of application benchmarks, it's difficult to make a call
one way or another as to real-life impact. May be the much lower memory
requirements means better cache properties? Conversely, if application
retains constructed elements retrieved during iteration, perhaps the
memory savings are illusory?

Of course, it is possible to choose at runtime between the two internal
representations (abstract/non-abstract) based on the length of the lists
so only "large" lists longer than some threshold would be abstracted.

I am looking for opinions as to all this would be worth
doing ("this" being abstract lists implementing zip, lreverse, concat,
merge, range, and other list operations). There are really two
questions:

1. Is it worth moving above operations into C?

2. If so, are abstract lists worth the construction+memory vs iteration
speed tradeoff?

I'm inclined to say yes to both, particularly as abstract lists will
allow operations on lists too large for the other methods (what was the
point of increasing size limits otherwise?).

Alternatively, we could do just 1. benefiting speed but not memory.

Or neither, which would save me a bunch of work and avoid code bloat in
the core.

Thoughts anyone?

Hi Ashok.,

Nice analysis! Thanks!

I've long been aware of the time/space tradeoff here. That's a decision one needs to make when implementing specific applications. I've always thought that abstract lists are best suited in cases where the dataset is effectively large, and already optimized for efficiency on some axis. And, the consumption is likely (but not necessarily) sparse.

One example is an acyclic graph that represents a very large number of paths, with a much smaller number of nodes. The use case in practice may only explore some subset of the paths. The abstract list interface can provide access to the graph using existing Tcl script level commands, i.e., not  having to create a new custom set of commands to access the custom graph data.

I didn't answer your question directly. I think it depends on the specific application case.


That's my 2¢
-Brian


/Ashok
_______________________________________________
Tcl-Core mailing list
Tcl...@li...<mailto:Tcl...@li...>
https://lists.sourceforge.net/lists/listinfo/tcl-core