Re: JIT for Lua

[Reuben Thomas <rrt1001@...>]

> I came across this the other day:
>
>  GNU lightning is a library that generates assembly language code at
>  run-time; it is very fast, making it ideal for Just-In-Time compilers,
>  and it abstracts over the target CPU, as it exposes to the clients a
>  standardized RISC instruction set inspired by the MIPS and SPARC chips.
>
>  http://www.gnu.org/software/lightning/lightning.html
>
> but I haven't tried it at all.

I've also looked at Lightning (my research is in this direction) and had
similar ideas about Lua. I also came to the conclusion that it would be
unlikely to help much with the speed, unless the compiler were much more
sophisticated. At the moment, it seems that executing individual VM
instructions is quite expensive because of all the dynamic lookups and
checks, so the overhead of interpretation is not great. If the code were
JIT-compiled, it would be very bulky if the VM action routines were simply
inlined; if it was simply turned into some sort of threaded code, on the
other hand, then there wouldn't be much speed gain, if any, because all that
would be improved is the VM instruction fetch-decode cycle, which seems not
to take much of the execution time.

Hence, I guess that to improve Lua's speed it would be necessary to write a
new compiler that output rather lower level instructions, and optimised a
lot of the dynamic checks away, based on program context. Even then you
might not gain much (especially not without inter-function optimisation, as
a function's parameters would always need to be typechecked the first time
they were used).

More interesting, IMO, would be to define a typed version of Lua. This could
be compiled much more efficiently, and ordinary dynamic Lua could be
compiled to it, by inserting type checks for values that have to be a
particular type (or types). To be really useful and efficient, table and
userdata types would have to be part of the type system.

What would the extensions look like?

I'd propose something like the following:

0. All variables are declared; global variables must be declared (using
"global"). This is a simplifying assumption; perhaps it's possible to relax
it if you're clever.

1. When a variable is declared, a type is given, e.g.:

local a : number, b : string, c : table = 1, "abc", {key = "foo", value = 42}
local f : string -> number = function (s) return strlen(s) end

2. Get rid of nil, and add a boolean type. Again, this is a simple solution;
a trickier (but more compatible) method might be to remove the nil type, and
lift all the remaining types, making "nil" a valid value for any other type.
This would require lifting the operators such as +, - and .. to check for
nil, and would hence be less efficient.

3. Now the type of all identifiers is statically known, so if you try to
perform an operation on the wrong type, or an unknown type, you can get a
compile-time error, e.g.:

print strlen(45) -- strlen : string -> number
(type mismatch)

function a(t : table) : nil
  -- this is syntactic sugar for a : table -> nil = function (t) ...
  print strlen(t[1])
end
(type of t[1] is unknown at compile time)

Now we seem to have painted ourselves into a corner: how can we ever use
table elements? Answer: with table types! You could rewrite the function
above:

function a(t : table { string }) : nil
  print strlen(t[1])
end

This works, because now we know the type of t[1].

Of course, I've only really scratched the tip here; there are lots of things
still needing elaboration. In particular, tag methods would have to be
statically declared, so you could statically type-check operations such as
+, so it's not at all obvious how to translate dynamic use of such features
into static Lua (sLua?).

There are two reasons I think this line of enquiry is worth pursuing:

1. I've not yet seen a language in which you can write both typed programs
with full type safety, and untyped programs with impunity (well, OPL allows
this, and C sort of does, but they're not very good examples). It ought to
be possible to make typing orthogonal to the rest of the language, and hence
get a language that works well for both quick scripting and more large-scale
programming.

2. Having a typed Lua would allow much more efficient compilation, and ease
larger-scale programming (table types would become object types, when
combined with encapsulation given some sort of module or interface
mechanism). I think it would be nice to move Lua into this arena.

Of course, it's not possible to do this and keep all of Lua's current
advantages of speed and compactness. In particular, the compiler would be
rather larger, slower, and more complex. However, if separated from the
execution environment, it should in fact be possible to run current Lua
programs as quickly and cheaply as at present (or even a bit better, given a
little type inference in cases like:

for i = 1, 10 do
  print (i * 2)
end

where it's obvious that "i" and "2" are of type number, and so don't need to
be dynamically type-checked when being passed to "*").

I'd really love to have a scalable language. The trouble with most good
large-scale languages is that they don't scale down well (even languages
with type inference get in the way; dynamic typing is what you really want
for a quick hack). Lua, on the other hand, might be made to scale up. The
ideal would be to make it as much as possible so that a well-typed dynamic
Lua program should be able to be turned into a static Lua program simply by
the addition of types and type cases, i.e. it should be possible to write a
compiler that infers the types for you. On the other hand, programs that
can't be type-inferred can still be compiled; they just won't be as fast,
and will involve the compiler inserting type-checks and casts at various
places.

-- 
http://sc3d.org/rrt/
"Reality is what refuses to disappear when you stop believing in it" -
Philip K. Dick