L2: Lua compiler in the works

classic Classic list List threaded Threaded
21 messages Options
12
Reply | Threaded
Open this post in threaded view
|

L2: Lua compiler in the works

Humberto S. N. dos Anjos
Greetings, everyone!

I am working in a Lua 5.1 optimizing compiler, written using Lua and LPeg, and I'm in a dire need of sample programs for testing and optimizing. Ideally, I wanted 3 or 4 programs of a considerable size, written entirely or mostly (the more the better) in Lua 5.1, with a test suite (nothing fancy, just something to demonstrate that the compiled code works), and without (many) external dependencies or special environment needs. Does anyone have any interesting candidates to spare? Or know some?


Thank you for your time,
_______________________
Humberto S. N. dos Anjos

<insert witty quote here>
Reply | Threaded
Open this post in threaded view
|

Re: L2: Lua compiler in the works

David Given
On Sun, 2007-11-18 at 10:32 -0300, Humberto S. N. dos Anjos wrote:
[...]
> I am working in a Lua 5.1 optimizing compiler, written using Lua and
> LPeg, and I'm in a dire need of sample programs for testing and
> optimizing. Ideally, I wanted 3 or 4 programs of a considerable size,
> written entirely or mostly (the more the better) in Lua 5.1, with a
> test suite (nothing fancy, just something to demonstrate that the
> compiled code works), and without (many) external dependencies or
> special environment needs. Does anyone have any interesting candidates
> to spare? Or know some? 

Well, I've got this word processor...

http://wordgrinder.sourceforge.net/

One of the things I've noticed is that it's a bit slow on low-end
machines. I've been looking at speeding up the VM via patches, but I'd
be fascinated to know whether an optimising compiler would help. It's
about 4000-odd lines of Lua, IIRC.

The version on the web site runs on a stock Debian lua5.1 installation
(although with extensions for the screen I/O), so there shouldn't be any
gotchas.

-- 
ââââ ïïïïïïïïïïïïïï âââââ 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 

Attachment: signature.asc
Description: This is a digitally signed message part

Reply | Threaded
Open this post in threaded view
|

Re: L2: Lua compiler in the works

Luiz Henrique de Figueiredo
In reply to this post by Humberto S. N. dos Anjos
> I am working in a Lua 5.1 optimizing compiler, written using Lua and LPeg,

luac could use an optimizing module, but that would be mostly a peephole
optimizer on bytecode only (plus some global analysis). And it'd have to
be written in C. The experience with your optimizing compile could help
identify what optimizations are worth the trouble. Please share your findings.

Reply | Threaded
Open this post in threaded view
|

Re: L2: Lua compiler in the works

Petite Abeille
In reply to this post by Humberto S. N. dos Anjos

On Nov 18, 2007, at 14:32, Humberto S. N. dos Anjos wrote:

Does anyone have any interesting candidates to spare?

Not sure how interesting it is, but here is a HTTP server, with supporting modules, in pure Lua:

http://dev.alt.textdrive.com/browser/HTTP/HTTP.lua
http://dev.alt.textdrive.com/browser/HTTP/MIME.lua
http://dev.alt.textdrive.com/browser/HTTP/URL.lua

No external dependencies aside from Lua itself and tcpserver [1].


Typical HelloWorld.lua example:

local HTTP = require( 'HTTP' )

HTTP[ '/hello(%a*)' ] = function( aName ) return 'Hello ' .. ( aName or 'world' ) end

HTTP()


Start HelloWorld.lua under tcpserver:

% tcpserver -oDHlR 0 1080 lua HelloWorld.lua


Benchmark it with ApacheBench:

% ab -n 1000 -k http://localhost:1080/hello
Requests per second:    1116.07 [#/sec] (mean)


Rinse and repeat.

Cheers,

PA.

[1] http://cr.yp.to/ucspi-tcp/tcpserver.html


Reply | Threaded
Open this post in threaded view
|

Re: L2: Lua compiler in the works

Asko Kauppi
In reply to this post by Humberto S. N. dos Anjos

What kind of optimizations are you planning on?

My interest would be comparing this to LuaJIT and on the other hand to what token filters / macros would allow.

-asko


Humberto S. N. dos Anjos kirjoitti 18.11.2007 kello 15:32:

Greetings, everyone!

I am working in a Lua 5.1 optimizing compiler, written using Lua and LPeg, and I'm in a dire need of sample programs for testing and optimizing. Ideally, I wanted 3 or 4 programs of a considerable size, written entirely or mostly (the more the better) in Lua 5.1, with a test suite (nothing fancy, just something to demonstrate that the compiled code works), and without (many) external dependencies or special environment needs. Does anyone have any interesting candidates to spare? Or know some?


Thank you for your time,
_______________________
Humberto S. N. dos Anjos

<insert witty quote here>


Reply | Threaded
Open this post in threaded view
|

Re: L2: Lua compiler in the works

Humberto S. N. dos Anjos
Right now:

- constant folding (already present) and propagation, dead code elimination, copy propagation and inlining;
- some loop optimizations (fusion, unrolling, invariant code motion);
- and some SSA-based optimizations.

There aren't much static optimizations to do at the bytecode level, other than write a decent code generator.

On Nov 18, 2007 6:07 PM, Asko Kauppi <[hidden email]> wrote:

What kind of optimizations are you planning on?

My interest would be comparing this to LuaJIT and on the other hand
to what token filters / macros would allow.

-asko


Humberto S. N. dos Anjos kirjoitti 18.11.2007 kello 15:32:

> Greetings, everyone!
>
> I am working in a Lua 5.1 optimizing compiler, written using Lua
> and LPeg, and I'm in a dire need of sample programs for testing and
> optimizing. Ideally, I wanted 3 or 4 programs of a considerable
> size, written entirely or mostly (the more the better) in Lua 5.1,
> with a test suite (nothing fancy, just something to demonstrate
> that the compiled code works), and without (many) external
> dependencies or special environment needs. Does anyone have any
> interesting candidates to spare? Or know some?
>
>
> Thank you for your time,
> _______________________
> Humberto S. N. dos Anjos
>
> <insert witty quote here>




--
_______________________
Humberto S. N. dos Anjos

<insert witty quote here>
Reply | Threaded
Open this post in threaded view
|

Re: L2: Lua compiler in the works

Humberto S. N. dos Anjos
In reply to this post by Luiz Henrique de Figueiredo
I'm not sure how much a peephole optimizer can accomplish. Lua's bytecode generator already does a pretty good job, and the optimizations I intend to do work at the AST level, where the program's structure is readily available. After these optimizations, there isn't much left for a peephole optimizer to do...

On Nov 18, 2007 11:03 AM, Luiz Henrique de Figueiredo <[hidden email]> wrote:
> I am working in a Lua 5.1 optimizing compiler, written using Lua and LPeg,

luac could use an optimizing module, but that would be mostly a peephole
optimizer on bytecode only (plus some global analysis). And it'd have to
be written in C. The experience with your optimizing compile could help
identify what optimizations are worth the trouble. Please share your findings.


--
_______________________
Humberto S. N. dos Anjos

<insert witty quote here>
Reply | Threaded
Open this post in threaded view
|

Re: L2: Lua compiler in the works

Mark Hamburg-4
Given metamethods, how much can actually be optimized? Do you have examples
of the sorts of code your optimizer can improve? The prospect of code
optimization is certainly attractive, but my understanding had been that Lua
wasn't particularly friendly to such optimizations.

Mark



Reply | Threaded
Open this post in threaded view
|

Re: L2: Lua compiler in the works

Humberto S. N. dos Anjos
Actually, no dynamic language (think Lua, Python, Ruby and the like) is friendly to static optimizations, because almost everything is left to runtime. This allows for some extremely cool stuff, but the code generator has to assume worst-case scenarios for pretty much everything.

But on most programs, very little truly dynamic code (things such as debug.setmetatable, loadstring with a string built at runtime, explicit setfenv stuff) is actually used, although any uses made are vital to the program's semantics (this is a paraphrase from a paper offering a type inferencer for Python, but the same reasoning applies here). So the main purpose of this compiler is to see how many static optimizations can be reasonably used.

Of course, some assumptions have to be made to make static optimizing viable. I came up with some, although now they seem a bit too strong:

- the debug library isn't used. The Lua manual recommends against it, because it can violate some Lua assumptions (local variables can't be accessed outside of their scope, numbers and functions can't have metatables), and it can be slow. So I assume no hackery of this sort is going on.

- basic modules and functions won't be modified, or at least not in a way that alters their semantics. With this I can rely on documented behavior to precompile functions calls, like compiling string.rep("a", 3) directly to "aaa". This might appear with some frequency when function calls are inlined.


On Nov 19, 2007 2:33 PM, Mark Hamburg <[hidden email]> wrote:
Given metamethods, how much can actually be optimized? Do you have examples
of the sorts of code your optimizer can improve? The prospect of code
optimization is certainly attractive, but my understanding had been that Lua
wasn't particularly friendly to such optimizations.

Mark





--
_______________________
Humberto S. N. dos Anjos

<insert witty quote here>
Reply | Threaded
Open this post in threaded view
|

Re: L2: Lua compiler in the works

Fabien-3


- basic modules and functions won't be modified, or at least not in a way that alters their semantics. With this I can rely on documented behavior to precompile functions calls, like compiling string.rep("a", 3) directly to "aaa". This might appear with some frequency when function calls are inlined.

If you want to eval functions at compile-time, you can do it with metalua. The level-0 block below allows to eval %-prefixed expressions at compile time. Therefore, "%string.rep('a', 5)" compiles straight to "`String 'aaaaa'", as one might expect.

-{ block:

   -- Compile and eval an aexpression AST, then quote the result
   function cteval_builder(x)
      -- Compile and execute the AST at compile-time:
      x = mlc.function_of_ast{`Return{x[1]}}()
      -- Quote back the evaluated result:
      return mlp.x_quote(x)
   end

   -- syntax extension
   mlp.expr:add { "%", mlp.expr, builder = cteval_builder } }

-- Usage sample:
x = %string.rep('a', 5)


With a code walker, you can easily locate side-effect free functions known at compile time, and when their arguments are closed, evaluate them at compile time with a function very similar to cteval_builder().
Reply | Threaded
Open this post in threaded view
|

Re: L2: Lua compiler in the works

Asko Kauppi
In reply to this post by Humberto S. N. dos Anjos

Not to discourage you, but I'd see inlining and the string.rep kind of optimizations easily doable via syntax modding (aka token filtering). It will still be a good thing to find such optimization points (btw, I've never needed string.rep myself...) but the eventual implementation could be merged with one of the filtering tools (MetaLua, luaSuper, ...).

-asko


Humberto S. N. dos Anjos kirjoitti 19.11.2007 kello 20:27:

Actually, no dynamic language (think Lua, Python, Ruby and the like) is friendly to static optimizations, because almost everything is left to runtime. This allows for some extremely cool stuff, but the code generator has to assume worst-case scenarios for pretty much everything.

But on most programs, very little truly dynamic code (things such as debug.setmetatable, loadstring with a string built at runtime, explicit setfenv stuff) is actually used, although any uses made are vital to the program's semantics (this is a paraphrase from a paper offering a type inferencer for Python, but the same reasoning applies here). So the main purpose of this compiler is to see how many static optimizations can be reasonably used.

Of course, some assumptions have to be made to make static optimizing viable. I came up with some, although now they seem a bit too strong:

- the debug library isn't used. The Lua manual recommends against it, because it can violate some Lua assumptions (local variables can't be accessed outside of their scope, numbers and functions can't have metatables), and it can be slow. So I assume no hackery of this sort is going on.

- basic modules and functions won't be modified, or at least not in a way that alters their semantics. With this I can rely on documented behavior to precompile functions calls, like compiling string.rep("a", 3) directly to "aaa". This might appear with some frequency when function calls are inlined.


On Nov 19, 2007 2:33 PM, Mark Hamburg <[hidden email]> wrote:
Given metamethods, how much can actually be optimized? Do you have examples
of the sorts of code your optimizer can improve? The prospect of code
optimization is certainly attractive, but my understanding had been that Lua
wasn't particularly friendly to such optimizations.

Mark





--
_______________________
Humberto S. N. dos Anjos

<insert witty quote here>

Reply | Threaded
Open this post in threaded view
|

Re: L2: Lua compiler in the works

steve donovan
That sounds like a job for a preprocessor, not so?  It would confuse the issue.

A particularly effective optimization would be detecting global table
calls (e.g. table.insert, math.sin) and automatically creating local
aliases. Can L2 do this?

steve d.

On Nov 20, 2007 8:48 AM, Asko Kauppi <[hidden email]> wrote:
>
>
> Not to discourage you, but I'd see inlining and the string.rep kind of
> optimizations easily doable via syntax modding (aka token filtering). It
> will still be a good thing to find such optimization points (btw, I've never
> needed string.rep myself...) but the eventual implementation could be merged
> with one of the filtering tools (MetaLua, luaSuper, ...).
>
> -asko

Reply | Threaded
Open this post in threaded view
|

Re: L2: Lua compiler in the works

Miles Bader
"steve donovan" <[hidden email]> writes:
> A particularly effective optimization would be detecting global table
> calls (e.g. table.insert, math.sin) and automatically creating local
> aliases. Can L2 do this?

Since it seems very hard to guarantee the semantics of a local alias are
the same in typical Lua code, the big question is:  are these slightly
different semantics what the user wants?  95% of the time, they probably
are, but ....

I suppose an important adjunct to a Lua compiler would be a way for
program writers to add annotations declaring their intent about such
things (e.g.  common-lisp's "declare" special-form).

-Miles
-- 
We have met the enemy, and he is us.  -- Pogo

Reply | Threaded
Open this post in threaded view
|

Re: L2: Lua compiler in the works

Humberto S. N. dos Anjos
In reply to this post by Asko Kauppi
Inlining on its own only saves a function call, at the cost of larger code; it's importance comes from enabling other optimizations to work on the inlined function body with specific parameter values available.

The string.rep stuff is there because it's a simple optimization to do, so why not?

On Nov 20, 2007 3:48 AM, Asko Kauppi <[hidden email]> wrote:

Not to discourage you, but I'd see inlining and the string.rep kind of optimizations easily doable via syntax modding (aka token filtering). It will still be a good thing to find such optimization points (btw, I've never needed string.rep myself...) but the eventual implementation could be merged with one of the filtering tools (MetaLua, luaSuper, ...).

-asko


Humberto S. N. dos Anjos kirjoitti 19.11.2007 kello 20:27:

Actually, no dynamic language (think Lua, Python, Ruby and the like) is friendly to static optimizations, because almost everything is left to runtime. This allows for some extremely cool stuff, but the code generator has to assume worst-case scenarios for pretty much everything.

But on most programs, very little truly dynamic code (things such as debug.setmetatable, loadstring with a string built at runtime, explicit setfenv stuff) is actually used, although any uses made are vital to the program's semantics (this is a paraphrase from a paper offering a type inferencer for Python, but the same reasoning applies here). So the main purpose of this compiler is to see how many static optimizations can be reasonably used.

Of course, some assumptions have to be made to make static optimizing viable. I came up with some, although now they seem a bit too strong:

- the debug library isn't used. The Lua manual recommends against it, because it can violate some Lua assumptions (local variables can't be accessed outside of their scope, numbers and functions can't have metatables), and it can be slow. So I assume no hackery of this sort is going on.

- basic modules and functions won't be modified, or at least not in a way that alters their semantics. With this I can rely on documented behavior to precompile functions calls, like compiling string.rep("a", 3) directly to "aaa". This might appear with some frequency when function calls are inlined.


On Nov 19, 2007 2:33 PM, Mark Hamburg <[hidden email]> wrote:
Given metamethods, how much can actually be optimized? Do you have examples
of the sorts of code your optimizer can improve? The prospect of code
optimization is certainly attractive, but my understanding had been that Lua
wasn't particularly friendly to such optimizations.

Mark





--
_______________________
Humberto S. N. dos Anjos

<insert witty quote here>




--
_______________________
Humberto S. N. dos Anjos

<insert witty quote here>
Reply | Threaded
Open this post in threaded view
|

Re: L2: Lua compiler in the works

Duncan Cross
In reply to this post by Humberto S. N. dos Anjos
On Nov 19, 2007 6:27 PM, Humberto S. N. dos Anjos <[hidden email]> wrote:
> - the debug library isn't used. The Lua manual recommends against it,
> because it can violate some Lua assumptions (local variables can't be
> accessed outside of their scope, numbers and functions can't have
> metatables),

On a tangent here, but I wasn't aware the second one was a fundamental
Lua assumption. You can change the metatable of base types easily
through the C API, I thought the only reason that numbers and
functions don't have one in the standard setup is it didn't seem
useful enough to bother (unlike strings), but it wasn't particularly
discouraged from being set up by Lua users through the API if they
wanted it. Am I wrong on that?

Reply | Threaded
Open this post in threaded view
|

Re: L2: Lua compiler in the works

David Jones-2
In reply to this post by Miles Bader

On 20 Nov 2007, at 09:40, Miles Bader wrote:

I suppose an important adjunct to a Lua compiler would be a way for
program writers to add annotations declaring their intent about such
things (e.g.  common-lisp's "declare" special-form).

I have thought so for a long time (in fact I think every language should have something similar to Common Lisp's "declare"), and occasionally I try and think of Lua-like ways of adding it to the core language. To me it seems like the best candidate for a new language feature. A declaration feature that is extensible in a way that language processors (like the PUC-Rio compiler, documentation tools, test harnesses) can invent declarations for their own use, but can still tell when they come across a mandatory declaration that they don't understand (so that they can bail). Like critical chunks in PNG.

drj

Reply | Threaded
Open this post in threaded view
|

Re: L2: Lua compiler in the works

Mike Panetta
Would writing a front end to LLVM accomplish what you want?  Its a
compiler that can do both compile time and run time optimization
through running its 'bytecode' in a jit.  I have never used it, only
looked at it, but it seems interesting enough.

http://www.llvm.org is the URL.

Mike

On Nov 20, 2007 8:23 AM, David Jones <[hidden email]> wrote:
>
> On 20 Nov 2007, at 09:40, Miles Bader wrote:
> >
> > I suppose an important adjunct to a Lua compiler would be a way for
> > program writers to add annotations declaring their intent about such
> > things (e.g.  common-lisp's "declare" special-form).
>
> I have thought so for a long time (in fact I think every language
> should have something similar to Common Lisp's "declare"), and
> occasionally I try and think of Lua-like ways of adding it to the
> core language.  To me it seems like the best candidate for a new
> language feature.  A declaration feature that is extensible in a way
> that language processors (like the PUC-Rio compiler, documentation
> tools, test harnesses) can invent declarations for their own use, but
> can still tell when they come across a mandatory declaration that
> they don't understand (so that they can bail).  Like critical chunks
> in PNG.
>
> drj
>

Reply | Threaded
Open this post in threaded view
|

Re: L2: Lua compiler in the works

Humberto S. N. dos Anjos
Maybe, but this is for my master's, so I'm supposed to do the optimizations myself :)

On Nov 20, 2007 3:04 PM, Mike Panetta <[hidden email]> wrote:
Would writing a front end to LLVM accomplish what you want?  Its a
compiler that can do both compile time and run time optimization
through running its 'bytecode' in a jit.  I have never used it, only
looked at it, but it seems interesting enough.

http://www.llvm.org is the URL.

Mike

On Nov 20, 2007 8:23 AM, David Jones <[hidden email]> wrote:

>
> On 20 Nov 2007, at 09:40, Miles Bader wrote:
> >
> > I suppose an important adjunct to a Lua compiler would be a way for
> > program writers to add annotations declaring their intent about such
> > things (e.g.  common-lisp's "declare" special-form).
>
> I have thought so for a long time (in fact I think every language
> should have something similar to Common Lisp's "declare"), and
> occasionally I try and think of Lua-like ways of adding it to the
> core language.  To me it seems like the best candidate for a new
> language feature.  A declaration feature that is extensible in a way
> that language processors (like the PUC-Rio compiler, documentation
> tools, test harnesses) can invent declarations for their own use, but
> can still tell when they come across a mandatory declaration that
> they don't understand (so that they can bail).  Like critical chunks
> in PNG.
>
> drj
>



--
_______________________
Humberto S. N. dos Anjos

<insert witty quote here>
Reply | Threaded
Open this post in threaded view
|

Re: L2: Lua compiler in the works

Fabio Mascarenhas
Humberto, not to mention that LLVM's target is native code and yours is the Lua VM. :) An Lua-to-LLVM JIT is a lot of work, even if you reuse some parts of the Lua interpreter (garbage collector, layout of values, most of the standard library).

A simpler application of LLVM is dynamically generating native code from Lua, like Javier's binding to TinyCC. LLVM is pretty easy to embed, and the native code it generates is comparable to gcc's -O3.

--
Fabio Mascarenhas

On Nov 20, 2007 4:51 PM, Humberto S. N. dos Anjos <[hidden email]> wrote:
Maybe, but this is for my master's, so I'm supposed to do the optimizations myself :)


On Nov 20, 2007 3:04 PM, Mike Panetta <[hidden email]> wrote:
Would writing a front end to LLVM accomplish what you want?  Its a
compiler that can do both compile time and run time optimization
through running its 'bytecode' in a jit.  I have never used it, only
looked at it, but it seems interesting enough.

http://www.llvm.org is the URL.

Mike

On Nov 20, 2007 8:23 AM, David Jones <[hidden email]> wrote:

>
> On 20 Nov 2007, at 09:40, Miles Bader wrote:
> >
> > I suppose an important adjunct to a Lua compiler would be a way for
> > program writers to add annotations declaring their intent about such
> > things (e.g.  common-lisp's "declare" special-form).
>
> I have thought so for a long time (in fact I think every language
> should have something similar to Common Lisp's "declare"), and
> occasionally I try and think of Lua-like ways of adding it to the
> core language.  To me it seems like the best candidate for a new
> language feature.  A declaration feature that is extensible in a way
> that language processors (like the PUC-Rio compiler, documentation
> tools, test harnesses) can invent declarations for their own use, but
> can still tell when they come across a mandatory declaration that
> they don't understand (so that they can bail).  Like critical chunks
> in PNG.
>
> drj
>



--
_______________________
Humberto S. N. dos Anjos

<insert witty quote here>

Reply | Threaded
Open this post in threaded view
|

Re: L2: Lua compiler in the works

Humberto S. N. dos Anjos
*crickets chirping*

Not that the optimization discussion isn't interesting, but I started this thread primarily to find candidate applications for optimization, and only two were mentioned...

Restating, to refresh everyone's memory:

> Ideally, I wanted 3 or 4 programs of a considerable size,
> written entirely or mostly (the more the better) in Lua 5.1, with a
> test suite (nothing fancy, just something to demonstrate that the
> compiled code works), and without (many) external dependencies or
> special environment needs.

The list got awfully quiet after Thanksgiving...
12