LuaJIT – Just in Time překladač pro programovací jazyk Lua (8 – základní vlastnosti trasovacího JITu)

Obsah

1. LuaJIT – Just in Time překladač pro programovací jazyk Lua (8 – vlastnosti trasovacího JITu)

2. Princip činnosti trasovacích JITů

3. Sledování činnosti trasovacího JITu v runtime: modul „v.lua“ (verbose mode)

4. Demonstrační příklad test40.lua – prostá interpretace počítané programové smyčky typu for

5. Demonstrační příklady test41.lua a test42.lua – JIT překlad počítané programové smyčky typu for

6. Demonstrační příklad test43.lua – JIT překlad smyčky typu while

7. Demonstrační příklady test44.lua, test45.lua a test46.lua – vnořené počítané smyčky typu for

8. Demonstrační příklad test47.lua – trasování dvou větví ve vnořené programové smyčce

9. Zdrojové kódy všech osmi dnešních demonstračních příkladů

10. Literatura

11. Odkazy na Internetu

1. LuaJIT – Just in Time překladač pro programovací jazyk Lua (8 – vlastnosti trasovacího JITu)

Po poměrně podrobném vysvětlení principu překladu zdrojových textů napsaných v programovacím jazyce Lua do bajtkódu používaného v projektu LuaJIT již máme dostatek informací na to, abychom se mohli začít soustředit na zajímavější a vlastně i mnohem důležitější oblast – na vlastní just-in-time překlad, tj. na detekci těch částí kódu (bajtkódu), které se budou překládat do nativního (strojového) kódu optimalizovaného pro aktuálně používanou architekturu. Důležité je, že v projektu LuaJIT se využívá takzvaný „trasovací JIT překladač“, který se v několika ohledech odlišuje od dnes asi známějších JIT překladačů typu hot spot (typickým příkladem je HotSpot JIT použitý v JVM, jehož poměrně podrobnému popisu jsme se již v tomto seriálu věnovali).

Trasovací JIT jsou sice založeny na poměrně staré myšlence, která byla v minulosti populární především v akademických projektech, ovšem do popředí zájmu se dostávají až v současnosti, a to společně s rozvojem a stále větším rozšiřováním dynamicky typovaných programovacích jazyků – Python, JavaScript apod. Příkladem může být implementace trasovacích JITů v projektech TraceMonkey (https://wiki.mozilla.org/Ja­vaScript:TraceMonkey), který je dnes postupně nahrazován poněkud složitějším JITem JägerMonkey či pravděpodobně ještě známější projekt PyPy (http://pypy.org/), na němž se testují nové myšlenky a technologie trasovacích JITů. Navíc se v PyPy objevuje zajímavá alternativa, v níž se trasuje nikoli bajtkód ale vlastní interpret, jenž je naprogramovaný v Pythonu (viz též desátou kapitolu s odkazy na literaturu).

2. Princip činnosti trasovacích JITů

Činnost trasovacích JITů je založena na dvou snadno pochopitelných předpokladech. Prvním předpokladem je, že typické aplikace tráví nejvíce času (přesněji řečeno strojového času) v programových smyčkách (tento předpoklad je někdy rozšířen i o tail rekurzi). Druhým předpokladem je, že pokud se vykonává programová smyčka, bude cesta v kódu pravděpodobně vždy stejná popř. v horším případě že bude existovat jen několik cest v programovém kódu (cestou je myšlena sekvence instrukcí). Trasovací JITy založené na těchto předpokladech se soustředí na detekci tzv. hot-loops, tedy často vykonávaných programových smyček. Tyto smyčky jsou následně optimalizovány a přeloženy do nativního kódu mikroprocesoru.

Při optimalizacích se provádí mnoho operací, s nimiž se můžeme setkat i s běžných překladačích – eliminace mrtvého kódu (zmenšují se nároky na instrukční cache), rozbalení smyček (snižuje se počet skoků a tím pádem se i vylepšuje využití instrukční pipeline) atd. Detekce hot-loops byla v tradičních trasovacích JITech implementována analýzou zpětných podmíněných skoků (vedoucích na začátek smyčky), ovšem v LuaJITu to není nutné, a to díky speciálním instrukcím bajtkódu: LOOP a FORI.

Zpracování programu v trasovacích JITech je rozdělena do několika fází:

Záznam historie neboli „stopy“ prováděného kódu je z hlediska implementace nejzajímavější částí trasovacího JITu. Samotná stopa je většinou reprezentována jednoduše jako seznam prováděných operací, ve skutečnosti se ovšem ve smyčce mohou nacházet různé podmínky vedoucí k větvení kódu a tím pádem i ke vzniku dalších „stop“. Aby se zajistilo korektní vykonání jedné iterace smyčky, nachází se v generovaném nativním kódu na místě každého možného větvení takzvané guard instrukce detekující jakoukoli odchylku. Detekce odchylky může vést k dalšímu JITování, což si ukážeme na jednom demonstračním příkladu níže.

3. Sledování činnosti trasovacího JITu v runtime: modul „v.lua“ (verbose mode)

V LuaJITu existuje možnost jednoduchého sledování základní činnosti trasovacího JITu. Postačuje použít volbu -jv. V tomto případě se bude informace o trasování vypisovat na standardní výstup:

luajit -jv test47.lua

Alternativně je možné specifikovat výstupní soubor, do něhož se budou postupně vypisovat informace o trasování:

luajit -jv=test47.out test47.lua

Podívejme se na příklad výstupu:

[TRACE   1 test47.lua:14 loop]
[TRACE   2 test47.lua:12 -> 1]
[TRACE   3 (1/3) test47.lua:16 -> 2]
[TRACE   4 (2/1) test47.lua:18 -> 2]
[TRACE   5 (3/1) test47.lua:11 -> 2]

Význam jednotlivých hodnot je stručně vypsán v následující tabulce:

4. Demonstrační příklad test40.lua – prostá interpretace počítané programové smyčky typu for

Podívejme se na dnešní první demonstrační příklad nazvaný test40.lua. Tento příklad je velmi jednoduchý, protože se v něm nachází pouze jediná počítaná programová smyčka typu for, která je prováděna celkem 50×:

--
-- LuaJIT: demonstrační příklad číslo 40.
--
-- Test JITu.
--
 
 
 
local i
local sum = 0
 
for i = 1,50 do
    sum = sum + 1
end
 
print(sum)
 
 
 
--
-- Finito.
--

Při spuštění tohoto demonstračního příkladu příkazem:

luajit -jv test40.lua

se na standardní výstup nevypíše žádná zpráva začínající na [TRACE…], což znamená, že trasovací JIT nedokázal detekovat žádnou hot loop. Jak je to možné? Při pohledu na zdrojový kód lj_jit.h, který je dostupný na adrese http://repo.or.cz/w/luajit-2.0.git/blob_plain/HEAD:/src/lj_jit.h. to snadno zjistíme:

...
...
...
  _(\007, hotloop,  56) /* # of iter. to detect a hot loop/call. */ \
...
...
...

To znamená, že hot loop se bude detekovat až po proběhnutí minimálně 57 iterací! Proč se jedná zrovna o tuto konstantu, je trošku záhada, můžeme jen předpokládat, že jde o výsledek měření chování JITu v reálných aplikacích.

5. Demonstrační příklady test41.lua a test42.lua – JIT překlad počítané programové smyčky typu for

Upravme si tedy demonstrační příklad tak, že ve smyčce použijeme větší počet iterací:

--
-- LuaJIT: demonstrační příklad číslo 41.
--
-- Test JITu.
--
 
 
 
local i
local sum = 0
 
for i = 1,60 do
    sum = sum + 1
end
 
print(sum)
 
 
 
--
-- Finito.
--

Zde je již situace zajímavější, protože po spuštění tohoto příkladu se na standardní výstup vypíšou dva řádky:

[TRACE   1 test41.lua:12 loop]
60

Druhý řádek je zcela jistě vypsán samotným příkladem, ovšem řádek první již naznačuje, že trasovací JIT našel (a následně přeložil) hot loop. Tato smyčka začíná na řádku dvanáct a jedná se o první a jedinou zaznamenanou stopu (historii), která byl LuaJITem zpracována. To je dosti podstatný rozdíl například při porovnání s HotSpotem, kde se ještě před vlastním spuštěním aplikace (i typu „Hello world!“ přeloží několik desítek i stovek metod.

Zkusme si zvýšit počet iterací až na 1 00 000 000:

--
-- LuaJIT: demonstrační příklad číslo 42.
--
-- Test JITu.
--
 
 
 
local i
local sum = 0
 
for i = 1,1e8 do
    sum = sum + 1
end
 
print(sum)
 
 
 
--
-- Finito.
--

I přesto, že je počet iterací o mnoho řádů vyšší než v předchozím příkladu, bude trasovací JIT provádět překlad stejné programové smyčky:

[TRACE   1 test42.lua:12 loop]
100000000

6. Demonstrační příklad test43.lua – JIT překlad smyčky typu while

Trasovací JIT dokázal detekovat počítanou programovou smyčku for díky tomu, že se tato smyčka přeloží do bajtkódu LuaJITu následujícím způsobem vysvětleným minule i předminule:

+--->  FORI --+  ; vstup do počítané programové smyčky typu for
|      ?      |
|      ?      |  ; instrukce tvořící tělo smyčky
|      ?      |  ; instrukce tvořící tělo smyčky
|      ?      |  ; instrukce tvořící tělo smyčky
|      ?      |
+----- FORL   |  ; další iterace, skok na začátek programové smyčky
      <-------+

V předchozích částech jsme si taktéž řekli, jak se přeloží programová smyčka typu while s podmínkou vyhodnocovanou na začátku. Zde se namísto speciální instrukce FORI používá instrukce LOOP:

+---> IS??     ; podmínka odvozená z invertované podmínky zapsané ve zdrojovém kódu
|     JMP --+  ; podmíněný skok ZA konec programové smyčky
|     LOOP  |  ; označení generické programové smyčky (pro detekci hot spotů)
|     ?     |
|     ?     |  ; instrukce tvořící tělo smyčky
|     ?     |  ; instrukce tvořící tělo smyčky
|     ?     |  ; instrukce tvořící tělo smyčky
|     ?     |
|     ?     |  ; end loop
+---- JMP   |  ; nepodmíněný skok na začátek programové smyčky
      <-----+

Trasovací JIT by tedy neměl mít problém ani s detekcí tohoto typu smyčky, což si ostatně ihned otestujeme na dalším demonstračním příkladu:

--
-- LuaJIT: demonstrační příklad číslo 43.
--
-- Test JITu.
--
 
 
 
local i = 0
local sum = 0
 
while i < 100 do
    sum = sum + 1
    i = i + 1
end
 
print(sum)
 
 
 
--
-- Finito.
--

A skutečně, podívejme se na výsledek:

[TRACE   1 test43.lua:12 loop]
100

Z tohoto výpisu je patrné, že trasovací překladač bez problémů detekoval i existenci smyčky typu while.

7. Demonstrační příklady test44.lua, test45.lua a test46.lua – vnořené počítané smyčky typu for

V předchozích kapitolách jsme si ukázali, jak dokáže trasovací JIT detekovat jednoduché programové smyčky. Nyní se podívejme na to, co se stane v případě, že použijeme dvojici vnořených počítaných smyček typu for. V demonstračním příkladu nazvaném test44.lua jsou použity dvě vnořené smyčky, přičemž počet iterací je v obou smyčkách nastaven pouze na deset iterací, což by v případě jednoduchých smyček znamenalo, že trasovací JIT bude tyto smyčky ignorovat (nebude se jednat o hot loop). Ovšem vzhledem k tomu, že jsou smyčky vnořené, je situace ve skutečnosti dosti odlišná:

--
-- LuaJIT: demonstrační příklad číslo 44.
--
-- Test JITu.
--
 
 
 
local i,j
local sum = 0
 
for i = 1,10 do
    for j = 1,10 do
        sum = sum + 1
    end
end
 
print(sum)
 
 
 
--
-- Finito.
--

Z výpisu je patrné, že byla detekována hot loop začínající na řádku třináct. Jedná se tedy o vnitřní smyčku, která bude „JITována“ (přeložena) do nativního kódu, zatímco smyčka vnější nikoli:

[TRACE   1 test44.lua:13 loop]
100

Nyní se pokusme počet iterací provedených ve vnější a současně i vnitřní smyčce zvýšit, a to (v obou případech) nad hodnotu, která již bude trasovacím JIT chápána jako hot loop. Víme, že hranice je 57 iterací, takže použijeme hodnotu vyšší, konkrétně sto iterací:

--
-- LuaJIT: demonstrační příklad číslo 45.
--
-- Test JITu.
--
 
 
 
local i,j
local sum = 0
 
for i = 1,100 do
    for j = 1,100 do
        sum = sum + 1
    end
end
 
print(sum)
 
 
 
--
-- Finito.
--

Výstup trasovacího JIT je již mnohem zajímavější, protože zde můžeme vidět dvě skutečnosti – nejprve byla detekována hot loop ve vnitřní smyčce začínající na řádku třináct (první řádek) a teprve poté byla jako hot loop označena i vnější smyčka. První historie (stopa) dostala číslo 1, druhá stopa pak číslo 2, přičemž druhá stopa je navázána na stopu první:

[TRACE   1 test45.lua:13 loop]
[TRACE   2 (1/3) test45.lua:12 -> 1]
10000

Pojďme ještě dále a vyzkoušejme si detekci tří vnořených hot loop:

--
-- LuaJIT: demonstrační příklad číslo 46.
--
-- Test JITu.
--
 
 
 
local i,j,k
local sum = 0
 
for i = 1,100 do
    for j = 1,100 do
        for k = 1,100 do
            sum = sum + 1
        end
    end
end
 
print(sum)
 
 
 
--
-- Finito.
--

Podle očekávání byla jako hot loop nejdříve detekována nejvnitřnější programová smyčka začínající na řádku čtrnáct. Posléze našel trasovací JIT další hot loop začínající na řádku třináct a navázanou na první hot loop (první číslice v závorce). Nakonec našel trasovací JIT i poslední hot loop, a to podle očekávání na řádku dvanáct s návazností na druhou hot loop (opět viz první číslice v závorce):

[TRACE   1 test46.lua:14 loop]
[TRACE   2 (1/3) test46.lua:13 -> 1]
[TRACE   3 (2/1) test46.lua:12 -> 1]
1000000

8. Demonstrační příklad test47.lua – trasování dvou větví ve vnořené programové smyčce

Až doposud byla práce trasovacího JITu poměrně jednoduchá, ovšem již v úvodních kapitolách jsme si řekli, že se při trasování musí vzít v úvahu všechny možné cesty. Upravme tedy jeden demonstrační příklad takovým způsobem, že se ve vnitřní smyčce bude provádět rozvětvení, přičemž jedna z větví bude taktéž obsahovat programovou smyčku:

--
-- LuaJIT: demonstrační příklad číslo 47.
--
-- Test JITu.
--
 
 
 
local i,j,k
local sum = 0
 
for i = 1,100 do
    for j = 1,100 do
        if j >= 50 then
            for k = 1,100 do
                sum = sum + 1
            end
        else
            sum = sum / 100
        end
    end
end
 
print(sum)
 
 
 
--
-- Finito.
--

Výsledek je v tomto případě již dosti složitější:

[TRACE   1 test47.lua:15 loop]
[TRACE   2 test47.lua:13 -> 1]
[TRACE   3 (1/3) test47.lua:17 -> 2]
[TRACE   4 (2/1) test47.lua:19 -> 2]
[TRACE   5 (3/1) test47.lua:12 -> 2]
5100

Prvně byla jako hot loop detekována nejvnitřnější smyčka, což se dalo očekávat (viz hranice pro detekci hot loop). Další stopa/historie odpovídá prostřední smyčce, přičemž konec této smyčky je shodný s koncem první hot loop. Další dvě stopy vlastně neodpovídají celému tělu programové smyčky, ale jen jeho části (třetí řádek nejvnitřnější smyčce, řádek čtvrtý pak smyčce prostřední). Nakonec byla detekována i vnější smyčka se stejným koncovým bodem, jako předchozí fragmenty. To je zajímavé, protože tento výsledek neodpovídá přesně intuici programátora. Proč tomu tak je si řekneme příště.

9. Zdrojové kódy všech osmi dnešních demonstračních příkladů

Všech osm dnes použitých demonstračních příkladů bylo, jak je tomu ostatně v tomto seriálu již dlouhodobějším zvykem, uloženo do Git (přesněji řečeno do GitHub) repositáře umístěného na adrese https://github.com/tisnik/luajit-examples.

Následuje tabulka s odkazy na poslední verze dnešních příkladů:

10. Literatura

1. Bolz, Cuni, Fijalkowski, Rigo:
   „Tracing the Meta-Level: PyPy's Tracing JIT Compiler“
2. Vasanth Bala, Evelyn Duesterwald, Sanjeev Banerjia:
   „Dynamo: A Transparent Dynamic Optimization System“
3. Bolz, Cuni, Fijalkowski, Leuschel, Pedroni, Rigo:
   „Allocation removal by partial evaluation in a tracing JIT“
4. Bolz:
   „Automatic JIT Compiler Generation with Runtime Partial Evaluation“
5. Bolz, Kuhn, Lienhard, Matsakis, Nierstrasz, Renggli, Rigo and T. Verwaest:
   „Back to the Future in One Week – Implementing a Smalltalk VM in PyPy“
   pages 123–139. 2008.
6. Bolz and Rigo:
   „How to not write a virtual machine“
   In Proceedings of the 3rd Workshop on Dynamic Languages and Applications (DYLA), 2007
7. Bruni, Verwaest:
   „PyGirl: generating Whole-System VMs from High-Level prototypes using PyPy“
   In Tools, accepted for publication, 2009.
8. Sullivan, Bruening, Baron, Garnett and Amarasinghe:
   „Dynamic native optimization of interpreters“
   In Proceedings of the 2003 Workshop on Interpreters,
   Virtual Machines and Emulators pages 50–57, San Diego, California, 2003. ACM.

11. Odkazy na Internetu

1. Have tracing JIT compilers won?
   http://lambda-the-ultimate.org/node/3851
2. Tracing just-in-time compilation
   http://en.wikipedia.org/wi­ki/Tracing_just-in-time_compilation
3. How does LuaJIT's trace compiler work?
   http://www.freelists.org/pos­t/luajit/How-does-LuaJITs-trace-compiler-work,1
4. How does LuaJIT's trace compiler work?
   http://stackoverflow.com/qu­estions/20266523/how-does-luajits-trace-compiler-work
5. TraceMonkey
   https://wiki.mozilla.org/Ja­vaScript:TraceMonkey
6. TraceMonkey
   http://brendaneich.com/2008/08/tra­cemonkey-javascript-lightspeed/
7. Improving JavaScript performance with JägerMonkey
   http://hacks.mozilla.org/2010/03/im­proving-javascript-performance-with-jagermonkey/
8. Wikipedia: Mezijazyk
   http://cs.wikipedia.org/wi­ki/Mezijazyk
9. The LuaJIT Project
   http://luajit.org/index.html
10. LuaJIT FAQ
    http://luajit.org/faq.html
11. LuaJIT Performance Comparison
    http://luajit.org/performance.html
12. LuaJIT 2.0 intellectual property disclosure and research opportunities
    http://article.gmane.org/gma­ne.comp.lang.lua.general/58908
13. LuaJIT Wiki
    http://wiki.luajit.org/Home
14. LuaJIT 2.0 Bytecode Instructions
    http://wiki.luajit.org/Bytecode-2.0
15. Programming in Lua 9.1 – Coroutine Basics,
    http://www.lua.org/pil/9.1.html
16. Programming in Lua (first edition)
    http://www.lua.org/pil/contents.html
17. Programming in Lua: 6 – More about Functions
    http://www.lua.org/pil/6.html
18. Lua Lanes
    http://kotisivu.dnainternet­.net/askok/bin/lanes/
19. Programming in Lua: 6.1 – Closures
    http://www.lua.org/pil/6.1.html
20. Programming in Lua: 9.1 – Coroutine Basics
    http://www.lua.org/pil/9.1.html
21. Programming in Lua: Numeric for
    http://www.lua.org/pil/4.3.4.html
22. Programming in Lua: break and return
    http://www.lua.org/pil/4.4.html
23. Programming in Lua: Tables
    http://www.lua.org/pil/2.5.html
24. Programming in Lua: Table Constructors
    http://www.lua.org/pil/3.6.html
25. Programovací jazyk Lua
    http://palmknihy.cz/web/kni­ha/programovaci-jazyk-lua-12651.htm
26. Lua: Tables Tutorial
    http://lua-users.org/wiki/TablesTutorial
27. Lua: Control Structure Tutorial
    http://lua-users.org/wiki/ControlStruc­tureTutorial
28. Lua Types Tutorial
    http://lua-users.org/wiki/LuaTypesTutorial
29. Goto Statement in Lua
    http://lua-users.org/wiki/GotoStatement
30. Lua 5.2 sources
    http://www.lua.org/source/5.2/
31. Lua 5.2 sources – lopcodes.h
    http://www.lua.org/source/5­.2/lopcodes.h.html
32. Lua 5.2 sources – lopcodes.c
    http://www.lua.org/source/5­.2/lopcodes.c.html
33. Lambda the Ultimate: Coroutines in Lua,
    http://lambda-the-ultimate.org/node/438
34. Coroutines Tutorial,
    http://lua-users.org/wiki/CoroutinesTutorial
35. Lua Coroutines Versus Python Generators,
    http://lua-users.org/wiki/LuaCorouti­nesVersusPythonGenerators