Lua 5.1+ and variable-argument tables

classic Classic list List threaded Threaded
45 messages Options
123
Reply | Threaded
Open this post in threaded view
|

Lua 5.1+ and variable-argument tables

Adam D. Moss
Hi!

I seem to recall someone (lhf?) mentioning that Lua 5.1's behaviour
might change in some way regarding the implicit creation of vararg
tables from '...' argument lists.

Are there any more details on what direction this might take in
the future?  I'm currently rationalising my app's use of these
vararg tables in situations where they need to be passed to another
vararg-using function, after discovering that my app is spending
25% of its lua-time in unpack().  Since this rationalisation
involves changing a lot of code, I'd rather change things in a
way that is performant and syntax-friendly to whatever varargs
changes might be coming along.

Thanks,
--Adam
--
Adam D. Moss   . ,,^^   [hidden email]   http://www.foxbox.org/   co:3


Reply | Threaded
Open this post in threaded view
|

Re: Lua 5.1+ and variable-argument tables

Roberto Ierusalimschy
> I seem to recall someone (lhf?) mentioning that Lua 5.1's behaviour
> might change in some way regarding the implicit creation of vararg
> tables from '...' argument lists.
> 
> Are there any more details on what direction this might take in
> the future? [...]

In 5.1 the "..." will be itself an expression that results in the
variable arguments of a vararg function. So, the equivalent of
<<unpack(arg)>> will be simply "...". If you really want a table
with all parameters, you can collect them with <<{...}>>.

To keep compatibility, a vararg function that does not use any "..."
will still build its arg parameter.

-- Roberto

Reply | Threaded
Open this post in threaded view
|

Re: Lua 5.1+ and variable-argument tables

Adam D. Moss
Roberto Ierusalimschy wrote:
I seem to recall someone (lhf?) mentioning that Lua 5.1's behaviour
might change in some way regarding the implicit creation of vararg
tables from '...' argument lists.

Are there any more details on what direction this might take in
the future? [...]

In 5.1 the "..." will be itself an expression that results in the
variable arguments of a vararg function. So, the equivalent of
<<unpack(arg)>> will be simply "...". If you really want a table
with all parameters, you can collect them with <<{...}>>.

Thanks, that's very interesting!  So as I understand it, '...'
essentially becomes a way to read the contents of a slice of
the stack.

Thanks,
--Adam
--
Adam D. Moss   . ,,^^   [hidden email]   http://www.foxbox.org/   co:3


Reply | Threaded
Open this post in threaded view
|

Re: Lua 5.1+ and variable-argument tables

Roberto Ierusalimschy
> '...' essentially becomes a way to read the contents of a slice of
> the stack.

A very controlled way to read a very specific slice of the stack :)

-- Roberto

Reply | Threaded
Open this post in threaded view
|

Re: Lua 5.1+ and variable-argument tables

Wim Couwenberg-4
In reply to this post by Roberto Ierusalimschy
> If you really want a table with all parameters, you 
> can collect them with <<{...}>>.

Unfortunately, this does not record the *number* of
arguments.  A subsequent unpack call will clip at the
first nil entry.  Does it make sense to add a `pack'
function to the base lib that sets the `n' field (as
the arg table did)?

--
Wim


__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around 
http://mail.yahoo.com 

Reply | Threaded
Open this post in threaded view
|

Re: Lua 5.1+ and variable-argument tables

Roberto Ierusalimschy
> Does it make sense to add a `pack' function to the base lib that sets
> the `n' field (as the arg table did)?

We plan to add a function that returns its number of arguments, so
you can write

  local arg = table.setn({...}, newfunction(...))

It is more verbose than a function that packs and sets n at once, but
there will be times where we do not want to pack.

We also plan a new function select(i, ...), that returns its i-th
argument. So you can loop over the varargs with something like

  for i=1,newfunction(...) do
    local a = select(i, ...)
    dosomethingwith(a)
  end

With all overheads of function calls and parameter passing, this loop
is much faster than packing the arguments, for few arguments (less than
four or five).

select is also useful for other purposes, like

  local e = select(2, string.find(...))

-- Roberto

Reply | Threaded
Open this post in threaded view
|

select

Asko Kauppi-3

I like the 'select()' approach, thumbs up!

It's better than the first(), second(), third() and so approach which I now use, cluttering the global namespace less and still doing the work.

-ak

19.8.2004 kello 23:47, Roberto Ierusalimschy kirjoitti:

 Does it make sense to add a `pack' function to the base lib that sets
the `n' field (as the arg table did)?

We plan to add a function that returns its number of arguments, so
you can write

  local arg = table.setn({...}, newfunction(...))

It is more verbose than a function that packs and sets n at once, but
there will be times where we do not want to pack.

We also plan a new function select(i, ...), that returns its i-th
argument. So you can loop over the varargs with something like

  for i=1,newfunction(...) do
    local a = select(i, ...)
    dosomethingwith(a)
  end

With all overheads of function calls and parameter passing, this loop
is much faster than packing the arguments, for few arguments (less than
four or five).

select is also useful for other purposes, like

  local e = select(2, string.find(...))

-- Roberto



Reply | Threaded
Open this post in threaded view
|

Re: Lua 5.1+ and variable-argument tables

Rici Lake-2
In reply to this post by Wim Couwenberg-4
Rici coughs and points out that functional tuples wouldn't have the problem Wim pointed to, and would be a more general solution.

Outline proposal:

Possible syntax: (replace [...] with preferred punctuation if desired.)

-- make a tuple
tuple = [a, multipleReturns()]
st, fin, [caps] = string.find(str, pat)

-- get a tuple as trailing parameter
function foo(a, b, [caps])

-- expand a tuple
caps()

-- get the tail of a tuple
caps(3)  -- starts with third element

-- get a particular element of a tuple
(caps(3)) -- normal Lua5 scalarization (see implementation note below)

-- syntax missing for (therefore probably library functions):
--   truncate a tuple
--   count elements in a tuple

-- Implementation notes.
This assumes that tuples are implemented as a callable object, which does not seem completely outrageous to me; it is perhaps a tad odd that tuples are indexed with () and tables with [] but the [] syntax (currently) guarantees exactly one value.

The [] notation has one parsing irritation, which is that table constructors can no longer be parsed with an LL(2) parser. The syntax is not ambiguous, but it is not possible to know whether [...] is a tuple array value or a computed hash key until the token following the "]" is encountered. In some sense, this makes no difference, because in either event the value needs to be computed and put on the stack; however, it complicates implementation of reordering array elements. In practice, I don't think this is much of a problem because it is fairly rare to encounter {a, b, c = d, e}, and people who write that might stand to be penalised by a couple of nanoseconds.

Thinking about this issue, it occurred to me that the obvious implementation of table constructors if one didn't have the option of rearranging assignment order was to store the "n" value in the table header itself so that the VM opcode for adding array elements could know where to append from. This would likely be as fast as the current implementation, and would speed up getn and setn a bit; it would also have the side effect of setting n for all table constructors, which might or might not be a bad thing. There would be a small overhead for storing the extra field in the table header (and, irritatingly for me, an enormous overhead with the FreeBSD allocator, which would reserve 64 bytes instead of 32 bytes for the header; however, the dlmalloc, gnumalloc, and Windows allocators would only incur a four-byte penalty.)

Allocating a tuple of this form is presumably slower than the stack hack being proposed for the implementation of ... in 5.1. However, it is significantly faster than creating a table, and it is a more powerful construct than "..."; aside from the syntax, pretty well all the mechanisms are in place (although the current mechanism limits the size of a functional tuple to a fairly small number.)

The speed of allocating tuples on the heap rather than on the stack will be related to the speed of the allocator used; I can't believe that it would be a killer with a reasonable allocator (and you need a reasonable allocator if you want Lua to run fast because it does a lot of little alloc's -- upvalues spring to mind.)

Dumping the entire functional tuple (or the entire tail of the functional tuple) looks a lot worse than it really is. In practice, one might expect most tuples to be reasonably small. In addition, Lua knows how many results it is expecting, even though it does not pass this on to called functions. Currently, the return values are on the stack at return time, and the VM copies the desired number to the correct place (there is always a copy because the original function slot is being overwritten, at a minimum.) Since a functional tuple would simply be a vector of Lua objects, this could be optimised by allowing the functional tuple to return a pointer to its own vector instead of a pointer to the stack; the VM would then copy only the desired number of results from the vector. This optimisation does not look particularly difficult to implement, and has the advantage of simplifying the interface somewhat.

I think it might even be possible to lazily heapify tuples, but I don't know if it would be worth it. Roughly speaking, the idea would be to have a separate tuple stack where tuples were allocated. If a tuple was ever either saved to a non-stack location, or a location on the stack in a call-frame below its allocation frame (or possibly a repeat-block frame below its allocation frame), the tuple would be heapified. Since functional tuples as outlined above are immutable, it would not be necessary to repoint existing stack references to the tuple. The tuple stack would be simply truncated to its remembered location on exit from a call-frame (or possibly repeat frame).

This same mechanism could be useful for other functional-type objects, such as composed and curried functions.

Rici


Reply | Threaded
Open this post in threaded view
|

Re: Lua 5.1+ and variable-argument tables

Edgar Toernig
In reply to this post by Roberto Ierusalimschy
Roberto Ierusalimschy wrote:
>
> We also plan a new function select(i, ...), that returns its i-th
> argument.

Could you make that "returns its i-th and all following arguments"?

Names: argn and argi?  Or, plain english: count and select.  Or pick?

Ciao, ET.

Reply | Threaded
Open this post in threaded view
|

Re: select

Diego Nehab-3
In reply to this post by Asko Kauppi-3
Hi,

> > We also plan a new function select(i, ...), that returns its i-th
> > argument. So you can loop over the varargs with something like

I would prefer a skip() function that simply discarded the first 'n'
arguments. Then you can enclose in () and have the effect of select().

[]s,
Diego.

Reply | Threaded
Open this post in threaded view
|

Re: select

Rici Lake-2

On 19-Aug-04, at 6:03 PM, Diego Nehab wrote:

Hi,

We also plan a new function select(i, ...), that returns its i-th
argument. So you can loop over the varargs with something like

I would prefer a skip() function that simply discarded the first 'n'
arguments. Then you can enclose in () and have the effect of select().

Seems like there is at least massive support for this one. (It was also in the long missive I sent earlier, but I'll reinforce it here.)

I still prefer the functional tuples, though...

R.


Reply | Threaded
Open this post in threaded view
|

Re: Lua 5.1+ and variable-argument tables

Edgar Toernig
In reply to this post by Rici Lake-2
Rici Lake wrote:
>
> Rici coughs and points out that functional tuples wouldn't have the 
> problem Wim pointed to, and would be a more general solution.

Maybe.  But the whole point of the change is to avoid allocating
a (usually short-living) heap object on each vararg-function
invocation.

Your tuple proposal just introduces a new datatype.  All the
syntax extensions could equally well be implemented for tables.
Where's the tuple variant better than a regular table?  Any
performance differences would only be implementation details.

Ciao, ET.

Reply | Threaded
Open this post in threaded view
|

Re: Lua 5.1+ and variable-argument tables

Rici Lake-2

On 19-Aug-04, at 6:21 PM, Edgar Toernig wrote:

Maybe.  But the whole point of the change is to avoid allocating
a (usually short-living) heap object on each vararg-function
invocation.

I understand that. Personally I'd be more interested in an
optimisation which avoids allocating short-lived heap objects
for curried functions, for example.

The tuple proposal is an attempt to reduce the number of short-lived
heap objects created for vararg-function invocations from three to one.
That's maybe not as good as zero, but I think it has other advantages.

Your tuple proposal just introduces a new datatype.  All the
syntax extensions could equally well be implemented for tables.
Where's the tuple variant better than a regular table?  Any
performance differences would only be implementation details.

Well, the same could be said for the ... hack; the performance
difference is only an implementation detail. One could attempt to
optimise vararg calls through a different implementation which did
not alter the syntax at all.

Now, it's true that the tuple proposal is (more or less) a new datatype,
although it is actually implemented on top of an existing datatype
(that is, a C-function). The implementation, shorn of the new syntax,
is less than 10 lines of code.

In fact, my first thought here was, well why not just optimise tables
a bit more. That is surely possible. But functional tuples, even with a
naive implementation, turn out to be a massive performance win in a number
of common problems.

For example, they provide a handy way to collect multiple return values,
an issue I believe you yourself noted in an earlier posting on the subject
of ...

Also, they considerably simplify the implementation of tables which logically have multiple values; there are other ways of dealing with this, of course, but functional tuples (in my opinion) lead to cleaner implementations: tables of tables are of course possibly but they are bulky enough that one is motivated to avoid them, while keeping each value in a separate table is fast
but complicates the code.

So one question is, are functional tuples useful enough to add syntax to the
language (and/or make some other adjustments)?

I combine that with another question: is the ... thing worth a fairly considerable complication to the Lua core when functional tuples provide a reasonably optimised solution to the varargs issue, along with other issues?

On balance, my vote is with functional tuples. For what that's worth.


Reply | Threaded
Open this post in threaded view
|

Re: select

Asko Kauppi-3
In reply to this post by Diego Nehab-3

The () enclosing is a BAAD THING.  Really.

I _know_ it, and still I've messed up with it once. It should be banned from Lua, forever! There's too many C people using Lua, and in C that does nothing.

-ak		(don't reply - this is a dejavu thread..)


20.8.2004 kello 02:03, Diego Nehab kirjoitti:

 Hi,

We also plan a new function select(i, ...), that returns its i-th
argument. So you can loop over the varargs with something like

I would prefer a skip() function that simply discarded the first 'n'
arguments. Then you can enclose in () and have the effect of select().

[]s,
Diego.



Reply | Threaded
Open this post in threaded view
|

Re: select

Asko Kauppi-3
In reply to this post by Rici Lake-2

What are "functional tuples"...?   ;P   *looking stupid*


20.8.2004 kello 02:08, Rici Lake kirjoitti:

 I still prefer the functional tuples, though...


Reply | Threaded
Open this post in threaded view
|

Re: Lua 5.1+ and variable-argument tables

Mark Hamburg-4
In reply to this post by Rici Lake-2
Is it correct to summarize functional tuples as being essentially equivalent
to immutable, pure arrays -- i.e., tables that can't be changed and that
only have entries from 1 to n for some value of n?

Presumably, one could actually even have mutable tuples. You just can't
change the number of values in the tuple.

Mark


Reply | Threaded
Open this post in threaded view
|

Re: select

Rici Lake-2
In reply to this post by Asko Kauppi-3
Sorry, I guess I should have been clearer about that. This was a thread from some months ago.

A tuple is (for me in this context) an immutable list of objects. Functional tuples are a representation of tuples as functions; the function returns the tuple'd objects as a multiple return.

A simple pure-lua implementation: (leaving out the "select" feature)

> function tuple(...) return function() return unpack(arg) end end
> foo = tuple(2, 3, 4)
> =foo()
2       3       4

But one can do it *much* more efficiently in C: the following tiny patch
is a very simple implementation, but arguably lacks sufficient error-checking.
Implementing tail (or select, but I think tail is better) means actually
writing the tuple function instead of using lua_pushupvalues but it's only
a couple more lines of code.

The end result is a tuple represented as a simple lua_CFunction with a vector
of objects (but limited in size because nupvalues is a byte).

Some less simple implementations are in the mailing list archives.

R.

-------PATCH-----------
diff -r -u lua-5.0.2/src/lib/lbaselib.c lua-5.0.2-simpletuple/src/lib/lbaselib.c
--- lua-5.0.2/src/lib/lbaselib.c	2004-03-03 19:45:13.000000000 -0500
+++ lua-5.0.2-simpletuple/src/lib/lbaselib.c 2004-05-10 10:34:32.000000000 -0500
@@ -504,6 +504,11 @@

 /* }====================================================== */

+static int l_tuple (lua_State *L) {
+  lua_pushcclosure(L, lua_pushupvalues, lua_gettop(L));
+  return 1;
+}
+

 static const luaL_reg base_funcs[] = {
   {"error", luaB_error},
@@ -531,6 +536,7 @@
   {"dofile", luaB_dofile},
   {"loadstring", luaB_loadstring},
   {"require", luaB_require},
+  {"tuple", l_tuple},
   {NULL, NULL}
 };


Reply | Threaded
Open this post in threaded view
|

Re: Lua 5.1+ and variable-argument tables

Rici Lake-2
In reply to this post by Mark Hamburg-4

On 19-Aug-04, at 7:00 PM, Mark Hamburg wrote:

Is it correct to summarize functional tuples as being essentially equivalent to immutable, pure arrays -- i.e., tables that can't be changed and that
only have entries from 1 to n for some value of n?

Presumably, one could actually even have mutable tuples. You just can't
change the number of values in the tuple.

Yes, that would be the proposal.

As I mentioned at the end of the probably-too-long message from earlier today, there are some potential optimisations which work better if the tuple is immutable. On the other hand, there are probably some applications (vector arithmetic springs to mind) which might like to be able to update in place. I personally prefer the immutable flavour; but it is certainly trivial to implement mutable tuples using the same basic architecture, because iirc
lua_replace() works on pseudo-indices.


Reply | Threaded
Open this post in threaded view
|

Re: Lua 5.1+ and variable-argument tables

marcus.cf
In reply to this post by Rici Lake-2
I'm +1 on tuples. It seems to me as a good generalization over parameter lists
and return lists (i like the ability to collect and unpack values without
creating tables). But i'm not sure about the details of the implemenation:
syntax, type/function names and some other things (- What about tuple
comparisons and hashing by value, like strings? - What's more useful: select or
"cdr"?)


Reply | Threaded
Open this post in threaded view
|

Re: Lua 5.1+ and variable-argument tables

Edgar Toernig
In reply to this post by Rici Lake-2
Rici Lake wrote:
> 
> On 19-Aug-04, at 6:21 PM, Edgar Toernig wrote:
> 
> > Maybe.  But the whole point of the change is to avoid allocating
> > a (usually short-living) heap object on each vararg-function
> > invocation.
> 
> I understand that.

IMHO that's the most important point.  If you accept heap allocation
during vararg-function invocation you can stick with tables.  The
slight performance advantage of your tuple implementation could
be nullified by optimizing the appropriate parts of table creation.

> Personally I'd be more interested in an
> optimisation which avoids allocating short-lived heap objects
> for curried functions, for example.

The currying is supposed to create a new object, isn't it?

The invocation of the curried function is another thing.
The implementation I posted some minutes ago does not allocate
any heap object when calling the curried function...

> The tuple proposal is an attempt to reduce the number of short-lived
> heap objects created for vararg-function invocations from three to one.

Hmmm... nitpicking: from the GC point of view a table is one
object (with one to three malloced areas).

> > Your tuple proposal just introduces a new datatype.  All the
> > syntax extensions could equally well be implemented for tables.
> > Where's the tuple variant better than a regular table?  Any
> > performance differences would only be implementation details.
> 
> Well, the same could be said for the ... hack; the performance
> difference is only an implementation detail.

No.  It's a conceptual difference.  The ... "hack" is designed
to not allocate heap objects, the tuple solution is designed
to allocate a new object.

> Now, it's true that the tuple proposal is (more or less) a new datatype,
> although it is actually implemented on top of an existing datatype
> (that is, a C-function). The implementation, shorn of the new syntax,
> is less than 10 lines of code.

Afaics, only the syntax gives anything new.  The tuples themself
give nothing new.  They are only a subset of tables.

> For example, they [tuples] provide a handy way to collect multiple
> return values, an issue I believe you yourself noted in an earlier
> posting on the subject of ...

I did.  But it's not the tuple that makes it possible to collect
multiple return value but the new syntax.

> I combine that with another question: is the ... thing worth a fairly 
> considerable complication to the Lua core when functional tuples 
> provide a reasonably optimised solution to the varargs issue, along 
> with other issues?

As I said, tuples require heap objects, the dots do not.

And I wouldn't call it a "considerable complication to the Lua core".
I can't speak about Lua5 but I added them to Sol (Lua4 based) and
it's not that hard (I simply move the varargs to the up-to-now
unused upper end of the stack).

Ciao, ET.

123