Interpretry, překladače, JIT překladače a transpřekladače programovacího jazyka Lua

Obsah

1. Interpretry, překladače, JIT překladače a transpřekladače programovacího jazyka Lua

2. Překlad programů do bajtkódu a následná interpretace tohoto bajtkódu

3. Bajtkód programovacího jazyka Lua

4. Přímé volání překladače a výpis vygenerovaného bajtkódu

5. LuaJIT – Just in Time překladač pro jazyk Lua

6. Mezikód a výsledný kód generovaný LuaJITem

7. Transpřekladač z jazyka Lua do JavaScriptu

8. Virtuální stroj jazyka Lua transformovaný do JavaScriptu

9. Transpřekladač z jazyka Lua do C

10. Příklad použití transpřekladače

11. Výsledky benchmarku: interpret Lua vs. LuaJIT vs. transpřeklad do C

12. Odkazy na Internetu

1. Interpretry, překladače, JIT překladače a transpřekladače programovacího jazyka Lua

Ve článku Programovací jazyk Lua v roli skriptovacího jazyka pro WWW stránky zveřejněném minulý týden jsme se zabývali popisem dvou projektů, jejichž cílem bylo umožnit spouštění aplikací naprogramovaných v jazyce Lua ve webovém prohlížeči vybaveném pouze interpretrem JavaScriptu. Připomeňme si, že se jednalo o projekt nazvaný lua2js, v němž byla použita technologie takzvaného transpřekladače/transcompileru (program musel být na počítači vývojáře převeden do relativně nečitelného JavaScriptu). Taktéž byl popsán konkurenční projekt pojmenovaný lua.vm.js, v němž byl naopak celý virtuální stroj jazyka Lua (Lua VM) převeden do JavaScriptu s využitím technologie Clang a Emscripten, takže ve výsledku tento VM dokázal přímo spouštět skripty napsané v jazyku Lua bez nutnosti jejich transformace či překladu do jiného programovacího jazyka. To s sebou přináší přednosti, ale taktéž zápory. Přednosti jsou zřejmé – programátor se vůbec nemusí zabývat JavaScriptem, mezi zápory pak patří zejména neexistence debuggeru pro jazyk Lua na straně webového prohlížeče (na druhou stranu ladit JavaScript vzniklý transpřekladačem taktéž není žádná velká zábava :-).

V dnešním článku bude provedeno stručné představení některých dalších možností, které mohou vývojáři preferující programovací jazyk Lua využít pro spouštění či dokonce pro překlad svých aplikací. Nabízené možnosti jsou poměrně široké, což možná může vypadat poněkud zvláštně (když si navíc uvědomíme, že pravděpodobně rozšířenější Java je dosti úzce svázaná se svým bajtkódem a JITem atd.), ovšem právě zde můžeme vidět důsledek toho, že jak samotný programovací jazyk Lua, tak i bajtkód tohoto jazyka jsou navrženy takovým způsobem, aby byly implementačně velmi jednoduché a přitom dostatečně sémanticky bohaté, což některé vývojáře inspiruje k provádění různých experimentů s mnohdy velmi zajímavými výsledky (příkladem může být projekt Metalua či LuaJIT). Ostatně jazyk Lua v žádném případě není v tomto ohledu osamoceným projektem, protože podobně se experimentuje například s Pythonem. Důsledkem je, že kromě původního interpretru CPython existují další interpretry, překladače či transpřekladače, například Jython (Python pro JVM), IronPython (Python pro .NET Framework a Mono), Pyjs/Pyjamas (Python pro JavaScriptové interpretry), Shed Skin (transpřekladač do céčka) a samozřejmě taktéž populární PyPy.

2. Překlad programů do bajtkódu a následná interpretace tohoto bajtkódu

Skripty psané v programovacím jazyku Lua jsou standardně zpracovávány interpretrem dostupným na adrese http://www.lua.org/ftp/. Podobně jako v prakticky všech klasických interpretrech (snad jen s výjimkou různých typů shellů, například BASHe) je ve skutečnosti spouštění skriptů rozděleno na dvě fáze. V první fázi je zdrojový kód rozdělen na lexémy, parsován a analyzován (popř. i optimalizován). Posléze se vygeneruje mezikód a bajtkód (Lua, Python atd.). Výjimkou jsou interpretry klasických BASICů, v nichž se namísto bajtkódu ukládá tokenizovaná forma původního zdrojového kódu, což znamená, že generování tokenů může být navázáno přímo na lexikální analyzátor (zde trošku zjednodušuji). Vraťme se však k moderním interpretrům pracujícím s bajtkódem. Teprve bajtkód je skutečně interpretován, tj. postupně jsou načítány a prováděny jeho instrukce s případnou kontrolou chyb a u některých typů interpretrů může být použit i JIT (nikoli však u standardního interpretru jazyka Lua, ten je pojatý minimalisticky, ostatně jeho velikost včetně základních knihoven nepřesahuje 200 kB). Překladač do bajtkódu se jmenuje luac, samotný interpret pak lua.

3. Bajtkód programovacího jazyka Lua

Bajtkód jazyka Lua je typický tím, že se v něm nepoužívá zásobník operandů, protože indexy operandů jsou přímo součástí instrukčního slova, což sice vede k nutnosti použití většího množství bitů pro zakódování celé instrukce, ovšem celkový počet instrukcí se mnohdy poměrně radikálně sníží a navíc se i zvyšuje efektivita interpretru. I formát instrukčních kódů je například při porovnání s bajtkódem virtuálního stroje Javy (JVM) velmi odlišný, protože zatímco v případě bajtkódu JVM je kód instrukce uložen v celém bajtu (s několika málo výjimkami týkajícími se prefixu wide), je u bajtkódu používaném Lua VM kód instrukce uložen v pouhých šesti bitech, zatímco zbylých 26 bitů instrukčního slova je rezervováno pro uložení indexů operandů či konstant. Bajtkód Lua VM taktéž obsahuje spíše vysokoúrovňové instrukce, které velmi dobře reflektují vlastnosti tohoto programovacího jazyka. Existují například instrukce pro implementaci programové smyčky for, instrukce pro práci s (asociativními) poli tvořícími nejdůležitější strukturovaný datový typ jazyka Lua a dokonce se v bajtkódu nachází instrukce pro vytvoření uzávěru (closure) a pro tail call. Sémantická mezera mezi jazykem Lua a jeho bajtkódem je tedy poměrně malá.

Instrukce bajtkódu mohou mít jeden z následujících formátů:

iABC

iABx

iAsBx

iAx

Instrukce bajtkódu jsou stručně zmíněny v podkapitolách.

Aritmetické instrukce

Logické operace

Přesuny a konverze dat

Podmíněné a nepodmíněné skoky

Práce s konstantami

Práce s proměnnými

Programové smyčky a volání funkcí

Další instrukce

4. Přímé volání překladače a výpis vygenerovaného bajtkódu

Podívejme se ve stručnosti na použití standardního překladače jazyka Lua. Mějme jednoduchý zdrojový kód uložený v souboru circles.lua:

local i,j,k
 
print("P2")
print("400 400")
print("255")
 
for i = 0, 399 do
    for j = 0, 399 do
        local k = i * i + j * j
        k = k % 0x100
        io.write(k)
        io.write(" ")
    end
end

Ě

Obrázek 1: Rastrový vzorek vygenerovaný demonstračním příkladem.

Pro překlad bajtkódu (do operační paměti) a jeho spuštění či interpretaci se používá příkaz:

lua circles.lua

Pro překlad do bajtkódu s jeho uložením na disk (ovšem bez spuštění interpretru) se naproti tomu použije:

luac circles.lua

o

Popř. se můžeme zbavit ladicích informací (a částečně tak znepříjemnit život lidem pokoušejícím se o reverse engineering v případě, že z nějakého důvodu není možné vyvíjet open source projekt):

luac -s circles.lua

o

Výsledkem je soubor pojmenovaný luac.out, který má (i s ladicími informacemi) velikost 762 bajtů, bez ladicích informací pak 330 bajtů. Výpis vygenerovaného bajtkódu, resp. přesněji řečeno symbolických jmen instrukcí i jejich parametrů, zajistí příkaz:

luac -l circles.lua

Výsledek může vypadat následovně:

main <circles.lua:0,0> (33 instructions at 0x1b313c0)
0+ params, 14 slots, 1 upvalue, 12 locals, 11 constants, 0 functions
        1       [1]     LOADNIL         0 2
        2       [3]     GETTABUP        3 0 -1  ; _ENV "print"
        3       [3]     LOADK           4 -2    ; "P2"
        4       [3]     CALL            3 2 1
        5       [4]     GETTABUP        3 0 -1  ; _ENV "print"
        6       [4]     LOADK           4 -3    ; "400 400"
        7       [4]     CALL            3 2 1
        8       [5]     GETTABUP        3 0 -1  ; _ENV "print"
        9       [5]     LOADK           4 -4    ; "255"
        10      [5]     CALL            3 2 1
        11      [7]     LOADK           3 -5    ; 0
        12      [7]     LOADK           4 -6    ; 399
        13      [7]     LOADK           5 -7    ; 1
        14      [7]     FORPREP         3 17    ; to 32
        15      [8]     LOADK           7 -5    ; 0
        16      [8]     LOADK           8 -6    ; 399
        17      [8]     LOADK           9 -7    ; 1
        18      [8]     FORPREP         7 12    ; to 31
        19      [9]     MUL             11 6 6
        20      [9]     MUL             12 10 10
        21      [9]     ADD             11 11 12
        22      [10]    MOD             11 11 -8
        23      [11]    GETTABUP        12 0 -9 ; _ENV "io"
        24      [11]    GETTABLE        12 12 -10       ; "write"
        25      [11]    MOVE            13 11
        26      [11]    CALL            12 2 1
        27      [12]    GETTABUP        12 0 -9 ; _ENV "io"
        28      [12]    GETTABLE        12 12 -10       ; "write"
        29      [12]    LOADK           13 -11  ; " "
        30      [12]    CALL            12 2 1
        31      [8]     FORLOOP         7 -13   ; to 19
        32      [7]     FORLOOP         3 -18   ; to 15
        33      [14]    RETURN          0 1

5. LuaJIT – Just in Time překladač pro jazyk Lua

Z technologického hlediska je velmi zajímavým a současně i užitečným projektem nástroj nazvaný LuaJIT neboli Just in Time překladač pro Luu. LuaJIT je interně relativně jednoduchý, zejména v porovnání s monstrózním JVM JITem, a navíc používá snadno pochopitelný mezijazyk (anglicky IR – Intermediate Representation), který je následně „JITován“. Tento IR je odlišný od bajtkódu jazyka Lua, s nímž jsme se velmi stručně seznámili v předchozích kapitolách. Zatímco původní bajtkód jazyka Lua byl orientován především s ohledem na možnosti interpretru, je IR v LuaJITu navržen takovým způsobem, aby byl jeho následný překlad do nativního kódu poměrně snadný a rychlý, a to navíc bez ohledu na architekturu použitého mikroprocesoru. LuaJIT je z velké části dílem jediného programátora, který se jmenuje Mike Pall, který se zabýval i vývojem dalších nástrojů a knihoven použitelných vývojáři v jazyku Lua. Rychlost JITovaného skriptu bude porovnána se standardním interpretrem jazyka Lua a s přeloženým kódem v jedenácté kapitole.

Celý projekt LuaJIT se skládá z několika modulů, které při spuštění aplikace vytvořené v programovacím jazyku Lua musí vzájemně spolupracovat. Prvním modulem je překladač sloužící pro kompilaci zdrojového kódu napsaného v Lue do mezijazyka, který budeme v dalším textu zkráceně označovat IR – Intermediate Representation. IR je navržen takovým způsobem, aby mohl být buď interpretován (jde o ty části kódu, které nejsou spouštěny příliš často) nebo překládán do nativního strojového kódu s využitím JITu (většinou se jedná o opětovně spouštěné části kódu). IR používá takzvaný tříadresový kód a instrukce o pevné šířce třiceti dvou bitů. Přístup k instrukcím je tedy obecně mnohem rychlejší, než při použití instrukcí proměnné délky, tak jako je tomu v JVM.

6. Mezikód a výsledný kód generovaný LuaJITem

Existují dva formáty instrukcí, přesněji řečeno dva způsoby rozdělení 32bitového slova na jednotlivá bitová pole. V obou formátech má operační kód instrukce šířku osmi bitů, obsazení dalších 24 bitů je však odlišné.

První formát se používá u instrukcí s trojicí operandů. Typické použití tohoto formátu je u aritmetických instrukcí:

Druhý formát dokáže adresovat pouze dva operandy, ovšem operand označený písmenem D má šířku šestnáct bitů a lze ho v některých instrukcích použít například k přímému uložení šestnáctibitové celočíselné konstanty se znaménkem (srov. s poměrně velkým množstvím instrukcí v bajtkódu JVM, které se pokouší o totéž, ale mnohem komplikovanějším způsobem):

Pro již ukázaný demonstrační příklad:

local i,j,k
 
print("P2")
print("400 400")
print("255")
 
for i = 0, 399 do
    for j = 0, 399 do
        local k = i * i + j * j
        k = k % 0x100
        io.write(k)
        io.write(" ")
    end
end

Vypadá mezikód používaný LuaJITem následovně:

-- BYTECODE -- circles.lua:0-16
0001    KNIL     0   2
0002    GGET     3   0      ; "print"
0003    KSTR     4   1      ; "P2"
0004    CALL     3   1   2
0005    GGET     3   0      ; "print"
0006    KSTR     4   2      ; "400 400"
0007    CALL     3   1   2
0008    GGET     3   0      ; "print"
0009    KSTR     4   3      ; "255"
0010    CALL     3   1   2
0011    KSHORT   3   0
0012    KSHORT   4 399
0013    KSHORT   5   1
0014    FORI     3 => 0033
0015 => KSHORT   7   0
0016    KSHORT   8 399
0017    KSHORT   9   1
0018    FORI     7 => 0032
0019 => MULVV   11   6   6
0020    MULVV   12  10  10
0021    ADDVV   11  11  12
0022    MODVN   11  11   0  ; 256
0023    GGET    12   4      ; "io"
0024    TGETS   12  12   5  ; "write"
0025    MOV     13  11
0026    CALL    12   1   2
0027    GGET    12   4      ; "io"
0028    TGETS   12  12   5  ; "write"
0029    KSTR    13   6      ; " "
0030    CALL    12   1   2
0031    FORL     7 => 0019
0032 => FORL     3 => 0015
0033 => RET0     0   1

7. Transpřekladač z jazyka Lua do JavaScriptu

Alternativou ke klasickému interpretru i k LuaJITu může pro některé vývojáře být projekt nazvaný lua2js, o němž jsme se již zmiňovali v předchozím článku. Připomeňme si tedy, že se jedná o transpřekladač (transcompiler) sloužící pro překlad zdrojových kódů napsaných v programovacím jazyce Lua do JavaScriptu. Samotný transpřekladač lua2js je naprogramován taktéž v JavaScriptu. Překlad jazykových konstrukcí není ve většině případů problematický, ovšem je nutné mít na paměti, že při spuštění skriptu ve webovém prohlížeči nebudou korektně fungovat mnohé funkce základních knihoven, což se týká především modulu/knihovny io [http://lua-users.org/wiki/IoLibraryTutorial] a taktéž modulu os [http://lua-users.org/wiki/OsLibraryTutorial], což je však vzhledem k velkým rozdílům mezi běžným skriptem a aplikací běžící v prohlížeči pochopitelné.

8. Virtuální stroj jazyka Lua transformovaný do JavaScriptu

I o dalším projektu jsme se zmiňovali minule; jedná se o projekt pojmenovaný lua.vm.js. Tento projekt je založen na technologii Emscriptenu, protože lua.vm.js není nic jiného než virtuální stroj jazyka Lua implementovaný v JavaScriptu. Autoři lua.vm.js se však nesnažili o znovuobjevení kola a o implementaci vlastního virtuálního stroje, ale použili infrastrukturu Clang+LLVM+Emscripten pro překlad původního virtuálního stroje (ten je naprogramován v ANSI C) do JavaScriptu. Co to znamená v praxi? Běh skriptů je přibližně o polovinu pomalejší, než v případě použití nativního Lua VM (a ještě pomalejší v porovnání s LuaJITem), ovšem programátoři získávají stoprocentní kompatibilitu s původní implementací programovacího jazyka Lua. Navíc je tento projekt vytvořen takovým způsobem, že se do WWW stránek přímo vkládají skripty psané v Lue. Virtuální stroj si pomocí DOM příslušné skripty načte a následně je vykoná (s převodem do bajtkódu atd., viz též předchozí kapitoly).

9. Transpřekladač z jazyka Lua do C

Mnozí čtenáři si pravděpodobně položili otázku, proč používat Just in Time překladač (tedy konkrétně LuaJIT) a nikoli plnohodnotný překlad programů napsaných v jazyku Lua do nativního kódu. Ukazuje se, že to není tak jednoduché, a to zejména z toho důvodu, že Lua je dynamicky typovaný jazyk, navíc navržený takovým způsobem, že se s využitím takzvaných metatabulek mohou pro uživatelské datové typy měnit významy operátorů. Co to znamená v praxi? Například příkaz local x = a + b nemůže být obecně převeden na nativní instrukci add či fadd, protože ze zapsaného příkazu není patrné, zda je skutečně za všech okolností operátor + použitý v příkazu aplikován na celočíselné či reálné operandy. Podobných – z hlediska překladu problematických – vlastností je v jazyku Lua povícero. Částečné řešení představuje právě již výše zmíněný LuaJIT, který si sám hlídá prováděné operace a dokáže v případě potřeby jeden blok přeložit víckrát či se vrátit k „pouhé“ interpretaci. Druhé částečné řešení je implementováno v projektu lua2c dostupného na adrese http://lua-users.org/wiki/OsLibraryTutorial.

V rámci tohoto projektu je implementován prozatím značně naivní transpřekladač z jazyka Lua do céčka. Podívejme se, jakým způsobem se (trans)přeloží trojice příkazů:

local a = 10
local b = 20
local x = a + b

lua2c vygeneruje céčkový zdrojový soubor dlouhý necelých pět kilobajtů(!), přičemž výše uvedené příkazy jsou přeloženy následujícím způsobem:

static int lcf_main (lua_State * L) {
  enum { lc_nformalargs = 0 };
  const int lc_nactualargs = lua_gettop(L);
  const int lc_nextra = (lc_nactualargs - lc_nformalargs);
 
  /* local a = 10 */
  lua_pushnumber(L,10);
  assert(lua_gettop(L) - lc_nextra == 1);
 
  /* local b = 20 */
  lua_pushnumber(L,20);
  assert(lua_gettop(L) - lc_nextra == 2);
 
  /* local x = a + b */
  lc_add(L,(1 + lc_nextra),(2 + lc_nextra));
  assert(lua_gettop(L) - lc_nextra == 3);
  return 0;

Vidíme, že zdánlivě primitivní operace součtu je zde realizována voláním funkce lc_add. Ta taktéž není triviální:

static void lc_add(lua_State * L, int idxa, int idxb) {
  if (lua_isnumber(L,idxa) && lua_isnumber(L,idxb)) {
    lua_pushnumber(L,lua_tonumber(L,idxa) + lua_tonumber(L,idxb));
  }
  else {
    if (luaL_getmetafield(L,idxa,"__add")||luaL_getmetafield(L,idxb,"__add")) {
      lua_pushvalue(L,idxa < 0 && idxa > LUA_REGISTRYINDEX ? idxa-1 : idxa);
      lua_pushvalue(L,idxb < 0 && idxb > LUA_REGISTRYINDEX ? idxb-2 : idxb);
      lua_call(L,2,1);
    }
    else {
      luaL_error(L, "attempt to perform arithmetic");
    }
  }
}

Transpřekladač se tak vlastně snaží napodobit funkci klasického interpretru jazyka Lua, který při interpretaci uživatelských skriptů musí provádět podobné operace. Zajisté není zapotřebí zdůrazňovat, že výsledek nebude ideální, a to ani z hlediska spotřeby paměti, tak i z hlediska výpočetního výkonu (viz též jedenáctou kapitolu, kde uvidíme, jak špatně na tom ve skutečnosti výsledek transpřekladu je :-).

10. Příklad použití transpřekladače

Naposledy se podívejme na jednoduchý testovací příklad naprogramovaný v jazyku Lua:

local i,j,k
 
print("P2")
print("400 400")
print("255")
 
for i = 0, 399 do
    for j = 0, 399 do
        local k = i * i + j * j
        k = k % 0x100
        io.write(k)
        io.write(" ")
    end
end

Tento příklad s využitím transpřekladače převedeme do zdrojového kódu v céčku:

LUA_PATH=$CWD/lib/?.lua lua lua2c circles.lua > circles.c

Pro zajímavost se podívejme, jak vygenerovaný kód vypadá:

/* WARNING: This file was automatically generated by lua2c. */
 
#ifdef __cplusplus
extern "C" {
#endif
#include <lua.h>
#include <lauxlib.h>
#include <lualib.h>
#ifdef __cplusplus
}
#endif
#include <stdio.h>
#include <stdlib.h>
 
 
#include <string.h>
 
 
#include <assert.h>
 
/* __add metamethod handler.
 * warning: assumes indices in range LUA_REGISTRYINDEX < x < 0 are relative. */
static void lc_add(lua_State * L, int idxa, int idxb) {
  if (lua_isnumber(L,idxa) && lua_isnumber(L,idxb)) {
    lua_pushnumber(L,lua_tonumber(L,idxa) + lua_tonumber(L,idxb));
  }
  else {
    if (luaL_getmetafield(L,idxa,"__add")||luaL_getmetafield(L,idxb,"__add")) {
      lua_pushvalue(L,idxa < 0 && idxa > LUA_REGISTRYINDEX ? idxa-1 : idxa);
      lua_pushvalue(L,idxb < 0 && idxb > LUA_REGISTRYINDEX ? idxb-2 : idxb);
      lua_call(L,2,1);
    }
    else {
      luaL_error(L, "attempt to perform arithmetic");
    }
  }
}
 
 
/* __mul metamethod handler.
 * warning: assumes indices in range LUA_REGISTRYINDEX < x < 0 are relative. */
static void lc_mul(lua_State * L, int idxa, int idxb) {
  if (lua_isnumber(L,idxa) && lua_isnumber(L,idxb)) {
    lua_pushnumber(L,lua_tonumber(L,idxa) * lua_tonumber(L,idxb));
  }
  else {
    if (luaL_getmetafield(L,idxa,"__mul")||luaL_getmetafield(L,idxb,"__mul")) {
      lua_pushvalue(L,idxa < 0 && idxa > LUA_REGISTRYINDEX ? idxa-1 : idxa);
      lua_pushvalue(L,idxb < 0 && idxb > LUA_REGISTRYINDEX ? idxb-2 : idxb);
      lua_call(L,2,1);
    }
    else {
      luaL_error(L, "attempt to perform arithmetic");
    }
  }
}
 
 
#include <math.h>
 
/* __mod metamethod handler.
 * warning: assumes indices in range LUA_REGISTRYINDEX < x < 0 are relative. */
static void lc_mod(lua_State * L, int idxa, int idxb) {
  if (lua_isnumber(L,idxa) && lua_isnumber(L,idxb)) {
    lua_pushnumber(L,lua_tonumber(L,idxa) - floor(lua_tonumber(L,idxa)/lua_tonumber(L,idxb))*lua_tonumber(L,idxb));
  }
  else {
    if (luaL_getmetafield(L,idxa,"__mod")||luaL_getmetafield(L,idxb,"__mod")) {
      lua_pushvalue(L,idxa < 0 && idxa > LUA_REGISTRYINDEX ? idxa-1 : idxa);
      lua_pushvalue(L,idxb < 0 && idxb > LUA_REGISTRYINDEX ? idxb-2 : idxb);
      lua_call(L,2,1);
    }
    else {
      luaL_error(L, "attempt to perform arithmetic");
    }
  }
}
 
 
/* name: (main)
 * function(...) */
static int lcf_main (lua_State * L) {
  enum { lc_nformalargs = 0 };
  const int lc_nactualargs = lua_gettop(L);
  const int lc_nextra = (lc_nactualargs - lc_nformalargs);
 
  /* local i,j,k */
  lua_settop(L,(lua_gettop(L) + 3));
  assert(lua_gettop(L) - lc_nextra == 3);
 
  /* print("P2") */
  lua_getfield(L,LUA_ENVIRONINDEX,"print");
  lua_pushliteral(L,"P2");
  lua_call(L,1,0);
  assert(lua_gettop(L) - lc_nextra == 3);
 
  /* print("400 400") */
  lua_getfield(L,LUA_ENVIRONINDEX,"print");
  lua_pushliteral(L,"400 400");
  lua_call(L,1,0);
  assert(lua_gettop(L) - lc_nextra == 3);
 
  /* print("255") */
  lua_getfield(L,LUA_ENVIRONINDEX,"print");
  lua_pushliteral(L,"255");
  lua_call(L,1,0);
  assert(lua_gettop(L) - lc_nextra == 3);
 
  /* for i = 0, 399 do */
  lua_pushnumber(L,0);
  lua_pushnumber(L,399);
  if (!((lua_isnumber(L,-2) && lua_isnumber(L,-1)))) {
    luaL_error(L,"'for' limit must be a number");
  }
  double lc1_var = lua_tonumber(L,-2);
  const double lc2_limit = lua_tonumber(L,-1);
  const double lc3_step = 1;
  lua_pop(L,2);
  enum { lc4 = 3 };
  while ((((lc3_step > 0) && (lc1_var <= lc2_limit)) || ((lc3_step <= 0) && (lc1_var >= lc2_limit)))) {
 
    /* internal: local i at index 4 */
    lua_pushnumber(L,lc1_var);
  
    /* for j = 0, 399 do */
    lua_pushnumber(L,0);
    lua_pushnumber(L,399);
    if (!((lua_isnumber(L,-2) && lua_isnumber(L,-1)))) {
      luaL_error(L,"'for' limit must be a number");
    }
    double lc5_var = lua_tonumber(L,-2);
    const double lc6_limit = lua_tonumber(L,-1);
    const double lc7_step = 1;
    lua_pop(L,2);
    enum { lc8 = 4 };
    while ((((lc7_step > 0) && (lc5_var <= lc6_limit)) || ((lc7_step <= 0) && (lc5_var >= lc6_limit)))) {
  
      /* internal: local j at index 5 */
      lua_pushnumber(L,lc5_var);
  
      /* local k = i * i + j * j */
      lc_mul(L,(4 + lc_nextra),(4 + lc_nextra));
      lc_mul(L,(5 + lc_nextra),(5 + lc_nextra));
      lc_add(L,-2,-1);
      lua_remove(L,-2);
      lua_remove(L,-2);
      assert(lua_gettop(L) - lc_nextra == 6);
  
      /* k = k % 0x100 */
      lua_pushnumber(L,256);
      lc_mod(L,(6 + lc_nextra),-1);
      lua_remove(L,-2);
      lua_replace(L,(6 + lc_nextra));
      assert(lua_gettop(L) - lc_nextra == 6);
  
      /* io.write(k) */
      lua_getfield(L,LUA_ENVIRONINDEX,"io");
      lua_pushliteral(L,"write");
      lua_gettable(L,-2);
      lua_remove(L,-2);
      lua_pushvalue(L,(6 + lc_nextra));
      lua_call(L,1,0);
      assert(lua_gettop(L) - lc_nextra == 6);
  
      /* io.write(" ") */
      lua_getfield(L,LUA_ENVIRONINDEX,"io");
      lua_pushliteral(L,"write");
      lua_gettable(L,-2);
      lua_remove(L,-2);
      lua_pushliteral(L," ");
      lua_call(L,1,0);
      assert(lua_gettop(L) - lc_nextra == 6);
  
      /* internal: stack cleanup on scope exit */
      lua_pop(L,2);
      lc5_var += lc7_step;
    }
    lua_settop(L,(lc8 + lc_nextra));
    assert(lua_gettop(L) - lc_nextra == 4);
  
    /* internal: stack cleanup on scope exit */
    lua_pop(L,1);
    lc1_var += lc3_step;
  }
  lua_settop(L,(lc4 + lc_nextra));
  assert(lua_gettop(L) - lc_nextra == 3);
  return 0;
}
 
 
/* from lua.c */
static int traceback (lua_State *L) {
  if (!lua_isstring(L, 1))  /* 'message' not a string? */
    return 1;  /* keep it intact */
  lua_getfield(L, LUA_GLOBALSINDEX, "debug");
  if (!lua_istable(L, -1)) {
    lua_pop(L, 1);
    return 1;
  }
  lua_getfield(L, -1, "traceback");
  if (!lua_isfunction(L, -1)) {
    lua_pop(L, 2);
    return 1;
  }
  lua_pushvalue(L, 1);  /* pass error message */
  lua_pushinteger(L, 2);  /* skip this function and traceback */
  lua_call(L, 2, 1);  /* call debug.traceback */
  return 1;
}
 
 
static void lc_l_message (const char *pname, const char *msg) {
  if (pname) fprintf(stderr, "%s: ", pname);
  fprintf(stderr, "%s\n", msg);
  fflush(stderr);
}
 
static int lc_report (lua_State *L, int status) {
  if (status && !lua_isnil(L, -1)) {
    const char *msg = lua_tostring(L, -1);
    if (msg == NULL) msg = "(error object is not a string)";
    /*FIX-IMROVE:progname*/
    lc_l_message("lua", msg);
    lua_pop(L, 1);
  }
  return status;
}
 
static int lc_docall (lua_State *L, int narg, int clear) {
  int status;
  int base = lua_gettop(L) - narg;  /* function index */
  lua_pushcfunction(L, traceback);  /* push traceback function */
  lua_insert(L, base);  /* put it under chunk and args */
  /*FIX? signal(SIGINT, laction); */
  status = lua_pcall(L, narg, (clear ? 0 : LUA_MULTRET), base);
  /*FIX? signal(SIGINT, SIG_DFL); */
  lua_remove(L, base);  /* remove traceback function */
  /* force a complete garbage collection in case of errors */
  if (status != 0) lua_gc(L, LUA_GCCOLLECT, 0);
  return status;
}
 
static int lc_dofile (lua_State *L, const char *name) {
  int status = luaL_loadfile(L, name) || lc_docall(L, 0, 1);
  return lc_report(L, status);
}
 
static int lc_dostring (lua_State *L, const char *s, const char *name) {
  int status = luaL_loadbuffer(L, s, strlen(s), name) || lc_docall(L, 0, 1);
  return lc_report(L, status);
}
 
static int lc_handle_luainit (lua_State *L) {
  const char *init = getenv(LUA_INIT);
  if (init == NULL) return 0;  /* status OK */
  else if (init[0] == '@')
    return lc_dofile(L, init+1);
  else
    return lc_dostring(L, init, "=" LUA_INIT);
}
 
 
typedef struct {
  int c;
  const char ** v;
} lc_args_t;
 
 
/* create global arg table */
static void lc_createarg(lua_State * L, const lc_args_t * const args) {
  int i;
  lua_newtable(L);
  for (i=0; i < args->c; i++) {
    lua_pushstring(L, args->v[i]);
    lua_rawseti(L, -2, i);
  }
  lua_setglobal(L, "arg");
}
 
 
static int lc_pmain(lua_State * L) {
  luaL_openlibs(L);
 
  const lc_args_t * const args = (lc_args_t*)lua_touserdata(L, 1);
  lc_createarg(L, args);
 
  lua_pushcfunction(L, traceback);
 
  const int status1 = lc_handle_luainit(L);
  if (status1 != 0) return 0;
 
  /* note: IMPROVE: closure not always needed here */
  lua_newtable(L); /* closure table */
  lua_pushcclosure(L, lcf_main, 1);
  int i;
  for (i=1; i < args->c; i++) {
    lua_pushstring(L, args->v[i]);
  }
  int status2 = lua_pcall(L, args->c-1, 0, -2);
  if (status2 != 0) {
    const char * msg = lua_tostring(L,-1);
    if (msg == NULL) msg = "(error object is not a string)";
    fputs(msg, stderr);
  }
  return 0;
}
 
 
int main(int argc, const char ** argv) {
  lc_args_t args = {argc, argv};
  lua_State * L = luaL_newstate();
  if (! L) { fputs("Failed creating Lua state.", stderr); exit(1); }
 
  int status = lua_cpcall(L, lc_pmain, &args);
  if (status != 0) {
    fputs(lua_tostring(L,-1), stderr);
  }
 
  lua_close(L);
  return 0;
}

(uff!)

Předposledním krokem je překlad céčkového kódu do nativní (spustitelné) aplikace. Zde je nutné správně nastavit cesty jak k hlavičkovým souborům, tak i ke knihovně jazyka Lua:

gcc circles.c -o circles -I/usr/include/lua5.1 -lm -llua5.1

Program můžeme spustit tak, jako každou jinou nativní aplikaci:

./circles > circles.pgm

11. Výsledky benchmarku: interpret Lua vs. LuaJIT vs. transpřeklad do C

Překlad zdrojového kódu do jazyka C s následnou možností použití všech optimalizací nabízených moderními překladači céčka sice vypadá zajímavě, ovšem kvůli již zmíněnému volání operátorů a metod přes metatabulky vše nebude tak výkonné, jak by se na první pohled mohlo zdát. Pojďme si vše vyzkoušet na benchmarku orientovaném na numerické výpočty s reálnými čísly. Bude se jednat o klasický výpočet Mandelbrotovy množiny, což je dostatečně výpočetně náročný algoritmus i pro soudobé počítače. Céčková verze algoritmu vypadá následovně (výsledkem je obrázek typu PGM):

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
 
/* rozmery bitmapy */
#define BITMAP_WIDTH  2048
#define BITMAP_HEIGHT 1536
 
/* maximalni pocet iteraci */
#define MAXITER 256
 
void recalcMandelbrot()
{
    double zx, zy, zx2, zy2;                    /* slozky komplexni promenne Z a Z^2 */
    double cx, cy;                              /* slozky komplexni konstanty C */
 
    int    x, y;                                /* pocitadla sloupcu a radku v bitmape */
    int    iter;                                /* pocitadlo iteraci */
 
    cy=-1.5;
    for (y=0; y<BITMAP_HEIGHT; y++) {           /* pro vsechny radky v bitmape */
        cx=-2.0;
        for (x=0; x<BITMAP_WIDTH; x++) {        /* pro vsechny pixely na radku */
            zx=0; zy=0;
            for (iter=0; iter<MAXITER; iter++) {/* iteracni smycka */
                zx2=zx*zx;                      /* zkraceny vypocet druhe mocniny slozek Z */
                zy2=zy*zy;
                if (zx2+zy2>4.0) break;         /* kontrola prekroceni meze divergence */
                zy=2.0*zx*zy+cy;                /* vypocet Z(n+1) */
                zx=zx2-zy2+cx;
            }
            printf("%d\n", iter);
            cx+=(4.0)/BITMAP_WIDTH;             /* posun na dalsi bod na radku */
        }
        cy+=(3.0)/BITMAP_HEIGHT;                /* posun na dalsi radek */
    }
}
 
 
 
int main(int argc, char **argv)
{
    puts("P2");
    printf("%d %d\n", BITMAP_WIDTH, BITMAP_HEIGHT);
    puts("255");
    recalcMandelbrot();
    return 0;
}
 
 
 
/* ------------------------------------------------------------------ */
/* finito                                                             */
/* ------------------------------------------------------------------ */

Obrázek 2: Část obrazu Mandelbrotovy množiny vykreslená předchozím demonstračním příkladem.

Ekvivalentní verze stejného algoritmu, tentokrát implementovaného v jazyku Lua:

-- rozmery bitmapy
local BITMAP_WIDTH  = 2048
local BITMAP_HEIGHT = 1536
 
-- maximalni pocet iteraci
local MAXITER = 256
 
function recalcMandelbrot()
    local zx, zy, zx2, zy2                    -- slozky komplexni promenne Z a Z^2
    local cx, cy                              -- slozky komplexni konstanty C
 
    local x, y                                -- pocitadla sloupcu a radku v bitmape
    local iter = 0                            -- pocitadlo iteraci
 
    cy=-1.5
    for y=0, BITMAP_HEIGHT-1 do               -- pro vsechny radky v bitmape
        cx=-2.0
        for x=0, BITMAP_WIDTH-1 do            -- pro vsechny pixely na radku
            zx=0 zy=0
            for i=0, MAXITER do               -- iteracni smycka
                iter = i
                zx2=zx*zx                     -- zkraceny vypocet druhe mocniny slozek Z
                zy2=zy*zy
                if zx2+zy2>4.0 then
                    break                     -- kontrola prekroceni meze divergence
                end
                zy=2.0*zx*zy+cy               -- vypocet Z(n+1)
                zx=zx2-zy2+cx
            end
            print(iter)
            cx=cx+(4.0)/BITMAP_WIDTH          -- posun na dalsi bod na radku
        end
        cy=cy+(3.0)/BITMAP_HEIGHT            -- posun na dalsi radek
    end
end
 
 
 
function main()
    print("P2")
    print(BITMAP_WIDTH .. " " .. BITMAP_HEIGHT)
    print("255")
    recalcMandelbrot()
end
 
 
 
main()
 
 
 
-- ------------------------------------------------------------------
-- finito
-- ------------------------------------------------------------------

Nejzajímavější budou výsledky doby trvání výpočtu změřené (pro jednoduchost) příkazem time. Měřit budeme:

1. Výpočet s využitím céčkového kódu optimalizovaného při překladu (-O3).
2. Výpočet s využitím standardního interpretru lua.
3. Výpočet s využitím LuaJITu
4. Výpočet programem vzniklým z Lua kódu pomocí lua2c, tento program byl taktéž přeložen s optimalizacemi.

Výsledky:

Interpretace výsledků je pro náš benchmark zřejmá: nativní kód je podle očekávání nejrychlejší, ovšem překvapil LuaJIT, který není o moc horší (musíme si totiž uvědomit, že JITování nezačne ihned, navíc se v celkovém času započítává i čas JITování, ostatně zkuste si sami přepsat algoritmus do Javy a porovnat). Interpretovaný kód zpracovávaný nástrojem lua je výrazně pomalejší a kupodivu nejpomalejší je nativní kód získaný s využitím lua2c.

Poznámka na závěr: příklad naprogramovaný v Lue se pro účely benchmarků nijak neupravoval, což znamená, že si podobný benchmark můžete vyzkoušet s (pravděpodobně) jakoukoli aplikací napsanou v Lue a sami si zjistit, jaká metoda spouštění je pro vaši konkrétní aplikaci nejlepší. Já jsem pro porovnání zvolil algoritmus s numerickými výpočty, výsledky však mohou být odlišné při práci s tabulkami atd. (zde je ovšem složité udělat adekvátní verzi v C).

12. Odkazy na Internetu

1. LuaJIT – Just in Time překladač pro programovací jazyk Lua
   http://www.root.cz/clanky/luajit-just-in-time-prekladac-pro-programovaci-jazyk-lua/
2. LuaJIT – Just in Time překladač pro programovací jazyk Lua (2)
   http://www.root.cz/clanky/luajit-just-in-time-prekladac-pro-programovaci-jazyk-lua-2/
3. LuaJIT – Just in Time překladač pro programovací jazyk Lua (3)
   http://www.root.cz/clanky/luajit-just-in-time-prekladac-pro-programovaci-jazyk-lua-3/
4. LuaJIT – Just in Time překladač pro programovací jazyk Lua (4)
   http://www.root.cz/clanky/luajit-just-in-time-prekladac-pro-programovaci-jazyk-lua-4/
5. LuaJIT – Just in Time překladač pro programovací jazyk Lua (5 – tabulky a pole)
   http://www.root.cz/clanky/luajit-just-in-time-prekladac-pro-programovaci-jazyk-lua-5-tabulky-a-pole/
6. LuaJIT – Just in Time překladač pro programovací jazyk Lua (6 – překlad programových smyček do mezijazyka LuaJITu)
   http://www.root.cz/clanky/luajit-just-in-time-prekladac-pro-programovaci-jazyk-lua-6-preklad-programovych-smycek-do-mezijazyka-luajitu/
7. LuaJIT – Just in Time překladač pro programovací jazyk Lua (7 – dokončení popisu mezijazyka LuaJITu)
   http://www.root.cz/clanky/luajit-just-in-time-prekladac-pro-programovaci-jazyk-lua-7-dokonceni-popisu-mezijazyka-luajitu/
8. LuaJIT – Just in Time překladač pro programovací jazyk Lua (8 – základní vlastnosti trasovacího JITu)
   http://www.root.cz/clanky/luajit-just-in-time-prekladac-pro-programovaci-jazyk-lua-8-zakladni-vlastnosti-trasovaciho-jitu/
9. LuaJIT – Just in Time překladač pro programovací jazyk Lua (9 – další vlastnosti trasovacího JITu)
   http://www.root.cz/clanky/luajit-just-in-time-prekladac-pro-programovaci-jazyk-lua-9-dalsi-vlastnosti-trasovaciho-jitu/
10. LuaJIT – Just in Time překladač pro programovací jazyk Lua (10 – JIT překlad do nativního kódu)
    http://www.root.cz/clanky/luajit-just-in-time-prekladac-pro-programovaci-jazyk-lua-10-jit-preklad-do-nativniho-kodu/
11. LuaJIT – Just in Time překladač pro programovací jazyk Lua (11 – JIT překlad do nativního kódu procesorů s architekturami x86 a ARM)
    http://www.root.cz/clanky/luajit-just-in-time-prekladac-pro-programovaci-jazyk-lua-11-jit-preklad-do-nativniho-kodu-procesoru-s-architekturami-x86-a-arm/
12. LuaJIT – Just in Time překladač pro programovací jazyk Lua (12 – překlad operací s reálnými čísly)
    http://www.root.cz/clanky/luajit-just-in-time-prekladac-pro-programovaci-jazyk-lua-12-preklad-operaci-s-realnymi-cisly/
13. The Lua VM, on the Web
    https://kripken.github.io/lu­a.vm.js/lua.vm.js.html
14. Lua.vm.js REPL
    https://kripken.github.io/lu­a.vm.js/repl.html
15. lua2js
    https://www.npmjs.com/package/lua2js
16. lua2js na GitHubu
    https://github.com/basicer/lua2js-dist
17. Seriál o programovacím jazyku Lua
    http://www.root.cz/serialy/pro­gramovaci-jazyk-lua/
18. Source-to-source compiler
    https://en.wikipedia.org/wiki/Source-to-source_compiler
19. JavaScript is Assembly Language for the Web: Sematic Markup is Dead! Clean vs. Machine-coded HTML
    http://www.hanselman.com/blog/Ja­vaScriptIsAssemblyLanguage­ForTheWebSematicMarkupIsDe­adCleanVsMachinecodedHTML­.aspx
20. JavaScript is Web Assembly Language and that's OK.
    http://www.hanselman.com/blog/Ja­vaScriptIsWebAssemblyLangu­ageAndThatsOK.aspx
21. Dart
    https://www.dartlang.org/
22. CoffeeScript
    http://coffeescript.org/
23. TypeScript
    http://www.typescriptlang.org/
24. Lua (programming language)
    http://en.wikipedia.org/wi­ki/Lua_(programming_langu­age)
25. Static single assignment form (SSA)
    http://en.wikipedia.org/wi­ki/Static_single_assignmen­t_form
26. Wikipedia: Mezijazyk
    http://cs.wikipedia.org/wi­ki/Mezijazyk
27. LuaJIT 2.0 SSA IRhttp://wiki.luajit.org/SSA-IR-2.0
28. The LuaJIT Project
    http://luajit.org/index.html
29. LuaJIT FAQ
    http://luajit.org/faq.html
30. LuaJIT Performance Comparison
    http://luajit.org/performance.html
31. LuaJIT 2.0 intellectual property disclosure and research opportunities
    http://article.gmane.org/gma­ne.comp.lang.lua.general/58908
32. LuaJIT Wiki
    http://wiki.luajit.org/Home
33. LuaJIT 2.0 Bytecode Instructions
    http://wiki.luajit.org/Bytecode-2.0
34. Programming in Lua (first edition)
    http://www.lua.org/pil/contents.html
35. Lua 5.2 sources
    http://www.lua.org/source/5.2/
36. Tcl Plugin Version 3
    http://www.tcl.tk/software/plugin/
37. JavaScript: The Web Assembly Language?
    http://www.informit.com/ar­ticles/article.aspx?p=1856657
38. asm.js
    http://asmjs.org/
39. List of languages that compile to JS
    https://github.com/jashke­nas/coffeescript/wiki/List-of-languages-that-compile-to-JS
40. REPL
    https://en.wikipedia.org/wi­ki/Read%E2%80%93eval%E2%80%93prin­t_loop
41. The LLVM Compiler Infrastructure
    http://llvm.org/ProjectsWithLLVM/
42. clang: a C language family frontend for LLVM
    http://clang.llvm.org/
43. emscripten
    http://kripken.github.io/emscripten-site/
44. LLVM Backend („Fastcomp“)
    http://kripken.github.io/emscripten-site/docs/building_from_source/LLVM-Backend.html#llvm-backend
45. Emscripten – Fastcomp na GitHubu
    https://github.com/kripken/emscripten-fastcomp
46. Clang (pro Emscripten) na GitHubu
    https://github.com/kripken/emscripten-fastcomp-clang
47. Why not use JavaScript?
    https://ckknight.github.i­o/gorillascript/
48. Lambda the Ultimate: Coroutines in Lua,
    http://lambda-the-ultimate.org/node/438
49. Coroutines Tutorial,
    http://lua-users.org/wiki/CoroutinesTutorial
50. Lua Coroutines Versus Python Generators,
    http://lua-users.org/wiki/LuaCorouti­nesVersusPythonGenerators