lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index] 



On 20/06/16 05:02 PM, Dirk Laurie wrote:

2016-06-20 21:04 GMT+02:00 Roberto Ierusalimschy <roberto@inf.puc-rio.br>:

A point that does rate some extra explanation, but perhaps iin PiL
rather than the reference manual, is that 'select' is in fact an
extremely efficient operation, involving no actual copying of
arguments. There is no API equivalent, because none is needed.
It returns the stack exactly as it found it, but reporting a possibly
different number of return values.

That is not true. 'select' can be quite slow for a large number of
parameters (where "large" starts in the order of a few dozen). In
particular, a typical loop in a vararg function using 'select' is
quadratic with the number of arguments, while creating a table and
traversing it is linear.

Could you explain why that happens? luaB_select is clearly O(1).
Does VARARG copy the arguments? If so, why is that necessary?
It's not strictly necessary, but the solution involves a linked list and copy-on-write.
If not handled right, debug.setlocal would affect multiple varargs lists instead of just one, however this can be solved by making varargs copy-on-write. You'd also need a partially-linked list, for example, the following code: (note that there are no tail calls) 

--------------------------------------
function a(...)
  b(1, ...)
end

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

function c(x, ...)
  d(...)
end

function d(...)
  print(1, 2, 3, ...)
end

a(4)
--------------------------------------

Would produce a stack that looks like this in function print:

--------------------------------------
{
  [1]={
    name="a",
    varargs={4,n=1},
    varargcount=1,
  },
  [2]={
    name="b",
varargs={1,n=1,cont={stack[1].varargs, 1}}, -- cont is a {pointer, pos} pair because we care about size 
    varargcount=2,
  },
  [3]={
    name="c",
    varargs={n=0,cont={stack[1].varargs. 1}},
    varargcount=1,
    args={1} -- first arg, `x`, has value `1`
  },
  [4]={
    name="d",
    varargs={n=0,cont={stack[1].varargs. 1}},
    varargcount=1,
  },
  [5]={
    name="print",
    varargs={1, 2, 3,n=3,cont={stack[1].varargs. 1}},
    varargcount=4,
  }
}
--------------------------------------

From this, you can see:
- For tailcall-heavy vararg code, this would have next to no benefit. Tailcalls can be optimized to reuse the caller's varargs list, thus cutting down on allocations and links. 
- For something like [1][2], this would have a huge benefit.
- In most other cases, this would probably make code slower, and would significantly increase the stack complexity, both in terms of the internal call/return stack, and the stack that is exposed through the Lua C API. This means more segfaults, increased GC complexity, etc. 

[1]: https://github.com/SoniEx2/Stuff/tree/master/lua/Forth
[2]: http://blog.ionoclast.com/2015/05/the-future-of-firth-pre-alpha2-and-beyond/
Thus, while I'd greatly benefit from non-copying varargs (I even thought about proposing this once), it would be a maintenance nightmare for the Lua team.
And I didn't even mention the interaction between this specific varargs implementation and multiple returns... 

$ luac -p -l -
function bump(...)
return select(3,...)
end

main <stdin:0,0> (3 instructions at 0x87f780)
0+ params, 2 slots, 1 upvalue, 0 locals, 1 constant, 1 function
     1    [3]    CLOSURE      0 0    ; 0x87f980
     2    [1]    SETTABUP     0 -1 0    ; _ENV "bump"
     3    [3]    RETURN       0 1

function <stdin:1,3> (6 instructions at 0x87f980)
0+ params, 3 slots, 1 upvalue, 0 locals, 2 constants, 0 functions
     1    [2]    GETTABUP     0 0 -1    ; _ENV "select"
     2    [2]    LOADK        1 -2    ; 3
     3    [2]    VARARG       2 0
     4    [2]    TAILCALL     0 0 0
     5    [2]    RETURN       0 0
     6    [3]    RETURN       0 1



--
Disclaimer: these emails may be made public at any given time, with or without reason. If you don't agree with this, DO NOT REPLY.