Posted in

The Implementation of Lua 5.0

The Implementation of Lua 5.0

VALUES AND O BJECTS
• Values represent all Lua values
• Objects represent values that involve memory allocation
• strings, tables, functions, heavy userdata, threads
• Representation of Values: tagged unions typedef union { typedef struct lua_TValue {
GCObject *gc; Value value;
void *p; int tt
lua_Number n; } TValue;
int b;
} Value;

O BJECTS
• Pointed by field GCObject *gc in values
• Union with common head:
GCObject *next; lu_byte tt; lu_byte marked
• Redundant tag used by GC
• Strings are hibrid
• Objects from an implementation point of view
• Values from a semantics point of view

S TRINGS
• Represented with explicit length
• Internalized
• save space
• save time for comparison/hashing
• more expensive when creating strings

IMPLEMENTATION OF T ABLES
• Each table may have two parts, a “hash” part and an “array” part
• Example:
{n = 3; 100, 200, 300}

T ABLES : H ASH P ART
• Hashing with internal lists for collision resolution
• Run a rehash when table is full:

T ABLES : A RRAY P ART
• Problem: how to distribute elements among the two parts of a table?
• or: what is the best size for the array?
• Sparse arrays may waste lots of space
• A table with a single element at index 10,000 should not have 10,000 elements

COMPUTING THE S IZE OF A T ABLE
• When a table rehashes, it recomputes the size of both its parts
• The array part has size N , where N satisfies the following rules:
• N is a power of 2
• the table contains at least N/2 integer keys in the interval [1, N ]
• the table has at least one integer key in the interval [N/2 + 1, N ]
• Algorithm is O(n), where n is the total number of elements in the table

COMPUTING THE S IZE OF A T ABLE (3)
• Now, all we have to do is to traverse the array:
total = 0
bestsize = 0
for i=0,32 do
if a[i] > 0 then
total += a[i]
if total >= 2^(i-1) then
bestsize = i
end
end
end

VIRTUAL MACHINE
• Most virtual machines use a stack model
• heritage from Pascal p-code, followed by Java, etc.
• Example in Lua 4.0:
while a<lim do a=a+1 end
3 GETLOCAL 0 ; a
4 GETLOCAL 1 ; lim
5 JMPGE 4 ; to 10
6 GETLOCAL 0 ; a
7 ADDI 1
8 SETLOCAL 0 ; a
9 JMP -7 ; to 3

A NOTHER MODEL FOR V IRTUAL MACHINES
• Stack-machine instructions are too low level
• Interpreters add high overhead per instruction
• Register machines allow more powerful instructions ADD 0 0 [1] ; a=a+1
• Overhead to decode more complex instruction is compensated by fewer instructions
• “registers” for each function are allocated on the execution stack at activation time
• large number of registers (up to 256) simplifies code generation

INSTRUCTION FORMATS
• Three-argument format, used for most operators
0 5 6 13 14 22 23 31
C B A OP
• All instructions have a 6-bit opcode
• Operand A refers to a register
• Operands B and C can refer to a register or a constant
• a constant can be any Lua value, stored in an array of constants private to each function

INSTRUCTION FORMATS
• There is an alternative format for instructions that do not need three arguments or with arguments that do not fit in 9 bits
• used for jumps, access to global variables, access to constants with indices greater than 256, etc.

INSTRUCTION EXAMPLES
GETGLOBAL 0 260 ; a = x
SETGLOBAL 1 260 ; x = t
LT 0 259 ; a < 1 ?
JMP * 13
• assuming that the variable a is in register 0, t is in register 1, the number 1 is at index 3 in the array of constants, and the string « x » is at index 4.
• conceptually, LT skips the next instruction (always a jump) if the test fails. In the current implementation, it does the jump if the test succeeds.
• jumps interpret the Bx field as a signed offset (in excess-217)

Si le lien ne fonctionne pas correctement, veuillez nous contacter (mentionner le lien dans votre message)
The Implementation of Lua (187 KO) (Cours PDF)
The Implementation of Lua

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *