Re: Varargs efficiency

[Sean Conner <sean@...>]

It was thus said that the Great Soni L. once stated:
> Hello,
> 
> How are varargs implemented? Are they array-backed, or 
> linkedlist-backed? I'd think a linkedlist-backed approach would be 
> better/faster:

  Have you tried measuring both approaches?

> With arrays:
> - Passing varargs around is SLOW!

  How do you know this?  For instance:

	function a(...)
	  -- code
	end

	function b(...)
	  a(...)
	end

	function c(...)
	  b(...)
	end

When c() calls b(), a pointer to the array-based stack can be passed to b
(nothing copied, very vast).  Same with b() calling a().  Remember, Lua is
written in C, and in C, when you have a pointer to X, you also have an array
of X (arrays references decay into pointers).

> - Replacing an item is SLOW!

  How so?

> - Pushing and popping is SLOW!

  For arrays, pushing and popping at the front of the array is slow; doing
so at the end is fast.  With a single linked list (say, like Lisp [1]),
pushing and popping from the front is fast, but pushing popping from the end
is slower than any array based version.

> 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)

  You still have to create the links in each node.  

> 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.

  It sounds like you work a lot with varargs [2].  

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

  It would probably complicate the implementation of Lua for potentially
little used programming paridigm?  I don't know how often varargs are used
the way you want to use it?  [3]  

  -spc (Have you tried programming in Lisp? [1])

[1]	From all the posts you make here, I get the impression you would do
	far better programming in Lisp than in Lua (or any other non-Lisp
	language).  Every crazy thing you want to do is possible in Lisp.

	But that's just my impression.

[2]	What are you trying to do anyway?  Create some form of virtual Lua
	environment?

[3]	I don't use it often.  I just checked my own codebase at work, and
	out of 18,204 lines of Lua, only 17 uses of varargs, and only 4 of
	those do not deal with logging of some sort (calling either
	print(...) or f:write(...) or some variation on that).