Cours gratuit: Optimising lua

Chapter 1: Introduction

Lua is an embeddable scripting language originally developed at Tecgraf, PUC-Rio in 1993 and now widely used in the interactive entertainment industry1 .Its main goals are to be simple, efficient, portable and lightweight. The objective of this project was to improve the performance of the Lua programming language interpreter by adding a just-in-time (JIT) compiler to the standard run-time environment.
Although it is among the fastest scripting languages, Lua is still approximately a factor of 20 slower than C in the majority of benchmarks [?, ?]. There is still plenty of room for improvement. Admittedly, the performance of the standard Lua virtual machine (VM) is adequate for tasks such as configuration or for use as a ‘glue’ language, but high performance and efficiency are important in games and interactive applications.
1.1 Overview of Lua
The standard Lua distribution includes a standalone command-line interpreter, but Lua is designed primarily to be embedded into a ‘host’ application. The host application controls when a script is loaded, compiled and executed and catches any errors raised during the execution of a script. A script’s capabilities can also be extended by making additional libraries available from the host application. For
1.1.1 Syntax and Semantics
Lua is syntactically similar to Pascal and semantically similar to Scheme. Figure 1.1 shows an example Lua program, which calculates the square root of 2 using Newton’s method.
On line 1 thenewtonfunction is defined, taking 2 argumentsaandx. Since Lua is dynamically-typed, no types are specified in the argument definitions. Lines 2 and 3 declare local variables using thelocalkeyword. The scope of these variables is limited to the newtonfunction. Global variables need no declaration and can be accessed from any scope in the current Lua context.
1.1.2 Dynamic Typing
Lua is a dynamically-typed language, which means it has no type declarations.Types are associated with values, not variables as in statically-typed languages;each variable in Lua stores a pair (t, v), where t is an integer tag identifying the type of the valuev. Figure 1.2 shows how Lua values are represented in C. TheTObjectstructure represents the tagged union (t, v), with thettfield being the type tagtandvalue being the valuev.TheValueunion represents values.
1.1.3 Tables
The table is the only structured data type available in Lua; a table is an associative map, an abstract data type similar to an array but which can be indexed by any value (exceptnil). Commonly used data structures such as trees, lists and graphs can be represented using tables. The code in Figure 1.4 reads lines from standard input, stores them in a linked list and then prints them out in reverse order.
1.1.4 Metamethods
Another powerful concept in Lua is the alteration of the semantics for userdata and table accesses through usingmetamethods. Metamethods allow programs to overload certain operations on tables and userdata objects. Each overloaded object has ametatableof functions (metamethods) associated with it. The metamethods are associated with events, which occur when operations such as addition and comparisons are performed on the object. This can even be used to implement object-oriented mechanisms [?].
1.1.5 Libraries
The standard Lua distribution includes a set of core libraries for performing I/O,math and string operations; it is straightforward to add extra user-defined libraries, written either in C or Lua. These extra libraries can be dynamically loaded at runtime.
It is interesting to note that the majority of Java’s standard libraries are written in Java, whereas Lua’s standard libraries are mainly written in C for speed. With the addition of the JIT compiler, it may be feasible to rewrite many of Lua’s standard libraries in Lua.
Chapter 2: Preparation
Since this was an optimisation project, I was aware that once the basic just-in-time (JIT) compiler had been implemented, any number of further optimisation phases could be added as time permitted. However, preliminary research was necessary before embarking on the implementation itself. I was unfamiliar with the internals of the Lua VM, and I had not done much low-level programming in C or assembly language before.
I read Roberto Ierusalimschy’s book, Programming in Lua [?] and found it very informative and useful for familiarising myself with the Lua language. The Lua community [?] also has a number of resources, including a mailing list [?] and an online collaborative Wiki [?] containing documentation and sample code.
2.1 Requirements Analysis
The following project requirements are based on the original success criteria set ou in the project proposal, included in Appendix C.
1. The JIT compiler should produce results that are as consistent as possi ble with the standard Lua interpreter. This includes coercion of types and the metamethod mechanism, introduced in Section 1.1. Any inconsistencie should be clearly identified.
2. Optimisations should be performed on the intermediate Lua bytecode. 3. Heuristics should be used to determine whether to use the JIT compiler for aparticular sequence of Lua bytecode.
4. The JIT compiler system should result in a reasonable performance increas when compared with the standard Lua interpreter. At this stage, it was dif ficult to quantify a required performance increase. See Section 4.3 for bench mark results.
5. The target machine architecture should be Intel x86 (i386-compatible and above)..