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)
