[ANN] Lua 5.2.0 (beta-rc2) now available

classic Classic list List threaded Threaded
70 messages Options
1234
Reply | Threaded
Open this post in threaded view
|

Re: SV: [ANN] Lua 5.2.0 (beta-rc2) now available

Alex Queiroz
Hallo,

On Thu, Jun 23, 2011 at 2:46 PM, David Given <[hidden email]> wrote:
>
> ...allocates at least four heap cells *every time* statemachine() is
> called; don't forget, the state functions themselves are upvalues...
>

     Yes, but not everytime you call one of the state functions. I
don't see a problem here.

--
-alex
http://www.artisancoder.com/

Reply | Threaded
Open this post in threaded view
|

Re: SV: [ANN] Lua 5.2.0 (beta-rc2) now available

David Given
Alex Queiroz wrote:
[...]
>      Yes, but not everytime you call one of the state functions. I
> don't see a problem here.

I'm using it[*] for a compiler backend, where state functions correspond
to basic blocks in a top-level function, and an entire state machine
corresponds to a single top-level function. Which means I'm calling my
state machines recursively a lot. As I said, one size does not fit all.


[*] Or rather I *would* be using it, but Lua didn't have goto --- it
would constructive to update the clue backend to use the new Lua 5.2
beta and see what the performance difference is like.

--
┌─── dg@cowlark.com ───── http://www.cowlark.com ─────
│ "I have always wished for my computer to be as easy to use as my
│ telephone; my wish has come true because I can no longer figure out
│ how to use my telephone." --- Bjarne Stroustrup


signature.asc (270 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: SV: [ANN] Lua 5.2.0 (beta-rc2) now available

Alex Queiroz
Hallo,

On Thu, Jun 23, 2011 at 4:07 PM, David Given <[hidden email]> wrote:
>
> I'm using it[*] for a compiler backend, where state functions correspond
> to basic blocks in a top-level function, and an entire state machine
> corresponds to a single top-level function. Which means I'm calling my
> state machines recursively a lot. As I said, one size does not fit all.
>

     One state machine per top-level function? Really, this is still
no reason for complaining about a few locals shared *per state
machine*. How many top-level functions do you have to analyse at the
same time?

--
-alex
http://www.artisancoder.com/

Reply | Threaded
Open this post in threaded view
|

Re: SV: [ANN] Lua 5.2.0 (beta-rc2) now available

David Given
Alex Queiroz wrote:
[...]
>      One state machine per top-level function? Really, this is still
> no reason for complaining about a few locals shared *per state
> machine*. How many top-level functions do you have to analyse at the
> same time?

Each top-level function is a C function. Each such function turns into a
state machine which represents the flattened basic block graph which is
the contents of the function. C functions call each other reentrantly,
which means my state machines need to be able to call each other
reentrantly. Trust me, I'm creating new state machines *very frequently*.

Using goto, the overhead of a state machine is nil, as the state is
encoded in the Lua program counter and locals are directly accessible
without needing heap cells. Each C function turns into precisely on Lua
function.

--
┌─── dg@cowlark.com ───── http://www.cowlark.com ─────
│ "I have always wished for my computer to be as easy to use as my
│ telephone; my wish has come true because I can no longer figure out
│ how to use my telephone." --- Bjarne Stroustrup


signature.asc (270 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: SV: [ANN] Lua 5.2.0 (beta-rc2) now available

Alex Queiroz
Hallo,

On Thu, Jun 23, 2011 at 4:35 PM, David Given <[hidden email]> wrote:
>
> Each top-level function is a C function. Each such function turns into a
> state machine which represents the flattened basic block graph which is
> the contents of the function. C functions call each other reentrantly,
> which means my state machines need to be able to call each other
> reentrantly. Trust me, I'm creating new state machines *very frequently*.
>

     Oh, I understand your point better now...

> Using goto, the overhead of a state machine is nil, as the state is
> encoded in the Lua program counter and locals are directly accessible
> without needing heap cells. Each C function turns into precisely on Lua
> function.
>

     ...But I still don't think your problem is caused by the locals,
because you need that state anyway, in one form or the other. Instead,
the memory usage is caused by the state functions themselves. One of
the aims of the Lua language is to have a fast, simple compiler, and
it cannot see that it does not need to create those internal closures
in this case. Other compilers can[1]. The fact that it's possible
doesn't help you though, because the Lua compiler won't change.

[1] - http://wingolog.org/archives/2009/08/10/goto-

--
-alex
http://www.artisancoder.com/

Reply | Threaded
Open this post in threaded view
|

Re: SV: [ANN] Lua 5.2.0 (beta-rc2) now available

David Given
Alex Queiroz wrote:
[...]
>      ...But I still don't think your problem is caused by the locals,
> because you need that state anyway, in one form or the other. Instead,
> the memory usage is caused by the state functions themselves.

Yeah, but if I use goto, I don't *have* any state functions!

e.g. the earlier example becomes:

local function statemachine()
        local i = 1
        local j = 2
        goto ::state1::

::state1::
        i = i + 1
        goto ::state2::

::state2::
        j = j + 1
        return
end

Now, all the state machine's state is stored on the stack. No upvalues!
No memory allocations anywhere! Admittedly, we now have a few wasted
goto instructions, but they're *really* cheap. (And omitting such is an
optimisation that could plausibly be done with Lua's compiler.)

However, I'll come clean: I haven't actually *done* any of this, which
means I haven't been able to measure anything, and you don't know
anything until you've measured it. In particular, I really ought to
measure Daurnimator's suggestion about passing state around as
parameters to the state functions. That means that the state functions
don't need upvalues and so won't generate garbage. It would be extremely
instructive to compare against a goto-based state machine implementation.

--
┌─── dg@cowlark.com ───── http://www.cowlark.com ─────
│ "I have always wished for my computer to be as easy to use as my
│ telephone; my wish has come true because I can no longer figure out
│ how to use my telephone." --- Bjarne Stroustrup


signature.asc (270 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: [ANN] Lua 5.2.0 (beta-rc2) now available

Tony Finch
In reply to this post by Roberto Ierusalimschy
On 22 Jun 2011, at 18:14, Roberto Ierusalimschy <[hidden email]> wrote:

>> - disallow a definition of a label if that label is already visible in
>> the scope.
>
> this seems a nice compromise between one-per-function and one-per-block.

I agree. I also like the argument that block scope makes code more composable - easier for automated code generators and for formal analysis.

Tony.
--
f.anthony.n.finch  <[hidden email]>  http://dotat.at/
Reply | Threaded
Open this post in threaded view
|

Re: [ANN] Lua 5.2.0 (beta-rc2) now available

Xavier Wang


在 2011-6-26 晚上9:33,"Tony Finch" <[hidden email]>写道:
>
> On 22 Jun 2011, at 18:14, Roberto Ierusalimschy <[hidden email]> wrote:
>
> >> - disallow a definition of a label if that label is already visible in
> >> the scope.
> >
> > this seems a nice compromise between one-per-function and one-per-block.
>
> I agree. I also like the argument that block scope makes code more composable - easier for automated code generators and for formal analysis.
>
> Tony.
> --
> f.anthony.n.finch  <[hidden email]>  http://dotat.at/
+1 for per block scopes of label :)

Reply | Threaded
Open this post in threaded view
|

Re: [ANN] Lua 5.2.0 (beta-rc2) now available

Tony Finch
In reply to this post by Dirk Laurie
On 23 Jun 2011, at 08:57, Dirk Laurie <[hidden email]> wrote:
>
> Simplest would be: rules for label visibility are exactly the same as
> for local variables.

That would prevent forward jumps.

Tony.
--
f.anthony.n.finch  <[hidden email]>  http://dotat.at/


Reply | Threaded
Open this post in threaded view
|

Re: [ANN] Lua 5.2.0 (beta-rc2) now available

Dirk Laurie
On Tue, Jun 28, 2011 at 12:06:47AM +0200, Tony Finch wrote:
> On 23 Jun 2011, at 08:57, Dirk Laurie <[hidden email]> wrote:
> >
> > Simplest would be: rules for label visibility are exactly the same as
> > for local variables.
>
> That would prevent forward jumps.
>
Consider these operations on a label xxx:
    (1) Define xxx as a label name if it has not yet been done.
    (2) Associate an address with xxx.
    (3) Transfer control to xxx.

Your statement would be correct if `goto xxx` does (3) and `::xxx::`
does (1) and (2).  But I have in mind that `goto xxx` would do
(1) and (3).  Indirect jump to label xxx.

Dirk



1234