Varargs efficiency

["Soni L." <fakedme@...>]

Hello,

How are varargs implemented? Are they array-backed, or linkedlist-backed? I'd think a linkedlist-backed approach would be better/faster:

With the array approach, you have to copy it every time you want to pass it around.

With the linked list approach, (assuming a singly linked list) you just pass the first node around. You don't have to worry about copying, moving, etc. To push an item you just make a new first node that links to the previous first node. To pop an item you just replace the first node with the next from the first node. To replace an item you don't have to copy the whole thing.

With arrays:
- Creation of varargs is fast.
- Reading varargs is fast.
- Passing varargs around is SLOW!
- Replacing an item is SLOW!
- Pushing and popping is SLOW!
- select(n, ...) is SLOW, as it requires copying the varargs, not once, but twice. First it does a full copy of ... to pass it in, then a copy of len(...)-n to return the new one.
- Memory cost can be HUGE in some cases. (see below)

With linked lists:
- Creation of varargs is so-so. (requires allocating nodes, altho the allocation could be batched so you only allocate once for, say, 100 nodes)
- Reading varargs is SLOW!
- Passing varargs around is fast.
- Replacing an item is so-so! (it's slow, but doesn't require a full copy, unlike with arrays)
- Pushing and popping is fast.
- select(n, ...) is fast, as it does no copying, and instead only returns the n-th node.
- Memory cost can be TINY in some cases. (see below)

Memory cost example:

Say you have a function f(...) that calls coroutines g(...), h(...), i(...), j(v, ...), with arguments g(1, ...), h(select(2, ...)), i(2, select(2, ...)), j(...).

With arrays:

The call to f(...) makes a copy.
The call to g(1, ...) makes a copy with space for the extra arg.
The call to h(select(2, ...)) makes a copy when calling into select(), followed by making another copy without the first argument, followed by making another copy when calling h.
The call to i(2, select(2, ...)) makes a copy when calling into select(), followed by making another copy without the first argument, followed by making another copy when calling i, with space for the extra arg.
The call to j(...) makes a copy without the first argument, and puts that first argument into a register.

With linked lists:

The call to f(...) passes a pointer to f.
The call to g(1, ...) creates a node and passes a pointer to g.
The call to h(select(2, ...)) passes a pointer to select(), which returns a pointer to the next node, which's then passed to h.
The call to i(2, select(2, ...)) passes a pointer to select(), which returns a pointer to the next node, which's linked to by the node that's passed to i.
The call to j(...) puts the first node into a register and passes a pointer to the next node.

I don't know, but linked lists seem much better. (Did I miss any pros/cons?)

-- 
Disclaimer: these emails are public and can be accessed from <TODO: get a non-DHCP IP and put it here>. If you do not agree with this, DO NOT REPLY.