Obsah
1. Profilery pro programovací jazyk Lua
2. Stažení a překlad projektu LuaProfiler
3. Načtení modulu s profilovacími funkcemi
6. Praktičtější příklad: výpočet faktoriálu různými způsoby
8. Příloha: bajtkód funkcí pro výpočet faktoriálu
1. Profilery pro programovací jazyk Lua
Mezi užitečné programátorské nástroje, které se při vývoji a laděni aplikací velmi často používají, patří mj. i různé debuggery a profilery. V základní instalaci balíčku s programovacím jazykem Lua se sice tyto nástroje nenachází (nalezneme zde totiž pouze interpret představovaný spustitelným souborem lua a překladač zdrojového kódu do bajtkódu reprezentovaný souborem luac), nicméně existuje hned několik podpůrných nástrojů, které je možné relativně snadno nainstalovat a následně používat. Jedním z těchto nástrojů je i profiler nazvaný jednoduše LuaProfiler. Tento nástroj si dnes stručně popíšeme a ukážeme si jeho základní použití při analýze několika variant algoritmu pro výpočet faktoriálu. Tento výpočet byl zvolen zejména z toho důvodu, že se jedná o známou (typicky školní :-) úlohu, kterou navíc lze v programovacím jazyce Lua realizovat hned několika možnými způsoby.
2. Stažení a překlad projektu LuaProfiler
Zdrojové kódy profileru LuaProfiler jsou dostupné na GitHubu na adrese https://github.com/luaforge/luaprofiler. Jedná se o běžný GIT repositář, takže je možné si ho naklonovat příkazem:
git clone https://github.com/luaforge/luaprofiler Cloning into 'luaprofiler'... remote: Counting objects: 388, done. remote: Total 388 (delta 0), reused 0 (delta 0), pack-reused 388 Receiving objects: 100% (388/388), 106.90 KiB | 73.00 KiB/s, done. Resolving deltas: 100% (255/255), done. Checking connectivity... done.
Profiler je implementován v programovacím jazyku C a nevyužívají se v něm žádné další knihovny kromě standardních knihoven céčka a knihovny jazyka Lua ve verzi 5.1 (překlad oproti verzi 5.2 je problematičtější). Pro úspěšný překlad je tedy nutné mít k dispozici překladač ANSI C (gcc, Clang, …) a balíček pojmenovaný většinou liblua5.1.0-dev či podobným způsobem. Ještě před překladem je nutné upravit soubor nazvaný config.linux takovým způsobem, aby proměnná LUA_INCLUDE ukazovala do správného adresáře s hlavičkovými soubory interptretru jazyka Lua. Na 64bitové platformě je navíc nutné upravit proměnnou CFLAGS, konkrétně do ní přidat volbu -fPIC (nic by se však nemělo stát ani při přidání tohoto přepínače na 32bitovém systému). Podívejme se na ukázku, jak soubor config.linux vypadá na mém systému. Změněný text je zvýrazněn:
LUA_INCLUDE= /usr/include/lua5.1 PROFILER_OUTPUT= bin/profiler.so INCS= -I$(LUA_INCLUDE) CC= gcc WARN= -ansi -W -Wall EXTRA_LIBS= CFLAGS= -O2 -DTESTS $(WARN) $(INCS) -I./src -fPIC
Samotný překlad je otázkou jediného příkazu:
make -f Makefile.linux
Výsledkem překladu je buď zpráva o chybě :-), nebo méně častěji nativní knihovna nazvaná profiler.so, která je umístěna v podadresáři bin.
3. Načtení modulu s profilovacími funkcemi
Použití profileru je poměrně snadné. Jediné, co musíme zajistit, je umístění knihovny profiler.so tak, aby ji měřený skript našel, takže v nejjednodušším případě stačí vytvořit symlink do pracovního adresáře. Nejprve je nutné profiler načíst příkazem require(„profiler“), čímž dojde k vytvoření globální tabulky nazvané „profiler“. Následně se (prakticky kdykoli) spustí profiling voláním profiler.start(jméno_souboru), kde do souboru se jménem jméno_souboru budou zapisovány informace o volaných funkcích atd. Profiling se vypíná voláním profiler.stop(). To je vlastně vše, takže se pojďme podívat na jednoduchý příklad, v němž je profiler načten, spuštěn a na konci příkladu i řádně vypnut:
require("profiler")
profiler.start("test.prof")
function first()
local x = ""
for i = 0, 1000 do
x = x .. tostring(i) .. ","
print(i)
end
end
function second()
local tbl = {}
for i = 1, 1000 do
tbl[i] = i
end
print(#tbl)
end
first()
second()
profiler.stop()
4. Spuštění profileru
Samotné spuštění programu je jednoduché (připomeňme však ještě jednou nutnost vytvoření symlinku na nativní knihovnu profiler.so). Nejdříve pro jistotu vymažeme soubor s profilovacími informacemi, jinak by došlo k pouhému připojení dalších dat (což nechceme) a následně se spustí interpret s naším skriptem. Vzhledem k tomu, že na systému mám nainstalovánu Luu 5.1 i Luu 5.2, musel jsem zvolit správnou verzi interpretru:
rm -f test.prof lua5.1 test.lua
Po doběhnutí skriptu by se v aktuálním adresáři měl nacházet i soubor nazvaný test.prof, jehož obsah bude vypadat přibližně takto (jednotlivé časy se samozřejmě budou lišit):
stack_level file_defined function_name line_defined current_line local_time total_time 0 (string) profiler_init -1 -1 0.000014 0.000013 1 (string) tostring -1 9 0.000012 0.000011 2 (string) called from print -1 -1 0.000006 0.000006 1 (string) print -1 10 0.000037 0.000046 1 (string) tostring -1 9 0.000010 0.000010 2 (string) called from print -1 -1 0.000007 0.000007 1 (string) print -1 10 0.000022 0.000031 1 (string) tostring -1 9 0.000009 0.000009 2 (string) called from print -1 -1 0.000005 0.000006 1 (string) print -1 10 0.000021 0.000030 1 (string) tostring -1 9 0.000007 0.000008 2 (string) called from print -1 -1 0.000005 0.000005
5. Analýza výsledků
Datový soubor zmíněný v předchozí kapitole obsahuje pouze surová data, pro jejichž další zpracování a vygenerování výsledků je zapotřebí použít ještě jeden nástroj. Tento nástroj je reprezentován skriptem nazvaným summary.lua, který naleznete v podadresáři src/analyzer projektu LuaProfiler. Skript načte výsledek běhu profileru a vytvoří čitelnou tabulku s kumulativními časy trvání jednotlivých funkcí, průměrným časem běhu každé funkce atd. Důležité je, aby profiler nezapsal do jednoho souboru profilovací informace vícekrát za sebou, jinak dojde k běhové chybě, protože summary.lua není příliš robustní. Podívejme se na výsledek jeho práce. Skript spustíme s volbou -v, abychom dostali více informací:
lua5.1 summary.lua -v test.prof > test.out
Výsledkem bude tato tabulka:
Node name Calls Average per call Total time %Time print 1002 1.1568862275449e-05 0.011592 43.541298876911 first 1 0.006767 0.006767 25.417871765015 tostring 1001 4.3506493506494e-06 0.004355 16.358036284416 called from print 1002 3.8413173652694e-06 0.003849 14.457424031852 second 1 4.4e-05 0.000044 0.1652706306577 profiler_init 1 1.4e-05 0.000014 0.0525861097547 stop 1 2e-06 0.000002 0.0075123013935
Výsledky jsou částečně předvídatelné – funkce print() byla volána 1002× (1001× ve smyčce + jedenkrát v další funkci) a skript v ní strávil nejvíce času. I funkce first() byla časově náročná, což je dáno jejím tělem s programovou smyčkou (volána byla pouze jedenkrát). Celých 16% času skript strávil i ve funkci tostring atd. atd.
6. Praktičtější příklad: výpočet faktoriálu různými způsoby
Podívejme se nyní na poněkud praktičtější příklad. Mějme čtyři různé implementace výpočtu faktoriálu:
- Klasický „školní“ rekurzivní výpočet
- Rekurzivní výpočet používající tail call optimization (TCO), tj. optimalizaci prováděnou interpretrem
- Nerekurzivní výpočet realizovaný počítanou smyčkou typu for
- Nerekurzivní výpočet realizovaný smyčkou typu while
Celý skript se zmíněnými čtyřmi implementacemi výpočtu (který volá i profiler) vypadá následovně:
require("profiler")
profiler.start("factorials.prof")
--
-- Rekurzivni vypocet faktorialu
--
function fact_recursive(n)
if n==0 then
return 1
else
return n*fact_recursive(n-1)
end
end
--
-- Rekurzivni vypocet faktorialu vyuzivajici tail call optimization
--
function fact_tail_call(n, accum)
accum = accum or 1
if n == 0 then
return accum
else
return fact_tail_call(n-1, n*accum)
end
end
--
-- Nerekurzivni vypocet faktorialu vyuzivajici programovou smycku typu for
--
function fact_loop(n)
if n==0 then
return 1
else
local x = 1
for i = 1,n do
x = x * i
end
return x
end
end
--
-- Nerekurzivni vypocet faktorialu vyuzivajici programovou smycku typu while
--
function fact_loop_2(n)
local x = 1
while n > 0 do
x = x * n
n = n - 1
end
return x
end
for i = 0, 149 do
print(i, fact_recursive(i), fact_tail_call(i), fact_loop(i), fact_loop_2(i))
end
profiler.stop()
7. Výsledky měření
Skript spustíme a následně analyzujeme výsledky běhu profileru:
rm factorials.prof lua5.1 factorials.lua echo "--------------------------------------" lua5.1 summary.lua -v factorials.prof > factorials.out
Nejprve malá kontrola správnosti výpočtu:
0 1 1 1 1 1 1 1 1 1 2 2 2 2 2 3 6 6 6 6 4 24 24 24 24 5 120 120 120 120 6 720 720 720 720 7 5040 5040 5040 5040 8 40320 40320 40320 40320 9 362880 362880 362880 362880 10 3628800 3628800 3628800 3628800 11 39916800 39916800 39916800 39916800 12 479001600 479001600 479001600 479001600 13 6227020800 6227020800 6227020800 6227020800 14 87178291200 87178291200 87178291200 87178291200 15 1307674368000 1307674368000 1307674368000 1307674368000 16 20922789888000 20922789888000 20922789888000 20922789888000 17 3.5568742809600e+14 3.5568742809600e+14 3.5568742809600e+14 3.5568742809600e+14 18 6.4023737057280e+15 6.4023737057280e+15 6.4023737057280e+15 6.4023737057280e+15 19 1.2164510040883e+17 1.2164510040883e+17 1.2164510040883e+17 1.2164510040883e+17 ... ... ... 146 1.1749972043909e+254 1.1749972043909e+254 1.1749972043909e+254 1.1749972043909e+254 147 1.7272458904546e+256 1.7272458904546e+256 1.7272458904546e+256 1.7272458904546e+256 148 2.5563239178729e+258 2.5563239178729e+258 2.5563239178729e+258 2.5563239178729e+258 149 3.8089226376306e+260 3.8089226376306e+260 3.8089226376306e+260 3.8089226376306e+260
Podle očekávání je klasický rekurzivní výpočet nejpomalejší (navíc i paměťově nejnáročnější), ovšem těsně za ním je výpočet s TCO (což mě osobně překvapilo, čekal jsem lepší výsledky tohoto výpočtu). Naproti tomu jsou výpočty využívající programovou smyčku for či while mnohem rychlejší, což ukazuje na fakt, že samotný výpočet (násobení, odečtení jedničky, skok…) je v porovnání s voláním funkce v tomto případě neporovnatelně rychlejší.
Node name Calls Average per call Total time %Time fact_recursive 11325 3.2175805739514e-05 0.364391 49.717297517076 fact_tail_call 11325 3.1855894039735e-05 0.360768 49.222977490225 print 150 2.4233333333333e-05 0.003635 0.49595729991841 called from print 750 4.1626666666667e-06 0.003122 0.42596387629857 fact_loop_2 150 3.6e-06 0.00054 0.073677288020892 fact_loop 150 3.06e-06 0.000459 0.062625694817758 profiler_init 1 9e-06 0.000009 0.0012279548003482 stop 1 2e-06 0.000002 0.00027287884452182
8. Příloha: bajtkód funkcí pro výpočet faktoriálu
Pro zajímavost se podívejme na bajtkód všech čtyř funkcí pro výpočet faktoriálu. Asi nejzajímavější je způsob realizace TCO (zvýrazněné instrukce se starají o provedení další iterace):
--
-- Rekurzivni vypocet faktorialu
--
function <factorials.lua:5,11> (11 instructions, 44 bytes at 0x246d790)
1 param, 3 slots, 0 upvalues, 1 local, 3 constants, 0 functions
1 [6] EQ 0 0 -1 ; - 0
2 [6] JMP 3 ; to 6
3 [7] LOADK 1 -2 ; 1
4 [7] RETURN 1 2
5 [7] JMP 5 ; to 11
6 [9] GETGLOBAL 1 -3 ; fact_recursive
7 [9] SUB 2 0 -2 ; - 1
8 [9] CALL 1 2 2
9 [9] MUL 1 0 1
10 [9] RETURN 1 2
11 [11] RETURN 0 1
--
-- Rekurzivni vypocet faktorialu vyuzivajici tail call optimization
--
function <factorials.lua:13,20> (13 instructions, 52 bytes at 0x246dd20)
2 params, 5 slots, 0 upvalues, 2 locals, 3 constants, 0 functions
1 [14] TEST 1 0 1
2 [14] JMP 1 ; to 4
3 [14] LOADK 1 -1 ; 1
4 [15] EQ 0 0 -2 ; - 0
5 [15] JMP 2 ; to 8
6 [16] RETURN 1 2
7 [16] JMP 5 ; to 13
8 [18] GETGLOBAL 2 -3 ; fact_tail_call
9 [18] SUB 3 0 -1 ; - 1
10 [18] MUL 4 0 1
11 [18] TAILCALL 2 3 0
12 [18] RETURN 2 0
13 [20] RETURN 0 1
--
-- Nerekurzivni vypocet faktorialu vyuzivajici programovou smycku typu for
--
function <factorials.lua:22,32> (14 instructions, 56 bytes at 0x246e200)
1 param, 6 slots, 0 upvalues, 6 locals, 2 constants, 0 functions
1 [23] EQ 0 0 -1 ; - 0
2 [23] JMP 3 ; to 6
3 [24] LOADK 1 -2 ; 1
4 [24] RETURN 1 2
5 [24] JMP 8 ; to 14
6 [26] LOADK 1 -2 ; 1
7 [27] LOADK 2 -2 ; 1
8 [27] MOVE 3 0
9 [27] LOADK 4 -2 ; 1
10 [27] FORPREP 2 1 ; to 12
11 [28] MUL 1 1 5
12 [27] FORLOOP 2 -2 ; to 11
13 [30] RETURN 1 2
14 [32] RETURN 0 1
--
-- Nerekurzivni vypocet faktorialu vyuzivajici programovou smycku typu while
--
function <factorials.lua:34,41> (8 instructions, 32 bytes at 0x246d8a0)
1 param, 2 slots, 0 upvalues, 2 locals, 2 constants, 0 functions
1 [35] LOADK 1 -1 ; 1
2 [36] LT 0 -2 0 ; 0 -
3 [36] JMP 3 ; to 7
4 [37] MUL 1 1 0
5 [38] SUB 0 0 -1 ; - 1
6 [38] JMP -5 ; to 2
7 [40] RETURN 1 2
8 [41] RETURN 0 1
9. Odkazy na Internetu
- Factorial (Rosetta Code)
http://rosettacode.org/wiki/Factorial#Lua - Lua Profiler (GitHub)
https://github.com/luaforge/luaprofiler - Lua Profiler (LuaForge)
http://luaforge.net/projects/luaprofiler/ - ctrace
http://webserver2.tecgraf.puc-rio.br/~lhf/ftp/lua/ - LuaJIT – Just in Time překladač pro programovací jazyk Lua
http://www.root.cz/clanky/luajit-just-in-time-prekladac-pro-programovaci-jazyk-lua/ - 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/ - 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/ - 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/ - 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/ - 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/ - 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/ - 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/ - 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/ - 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/ - 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/ - 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/ - The Lua VM, on the Web
https://kripken.github.io/lua.vm.js/lua.vm.js.html - Lua.vm.js REPL
https://kripken.github.io/lua.vm.js/repl.html - lua2js
https://www.npmjs.com/package/lua2js - lua2js na GitHubu
https://github.com/basicer/lua2js-dist - Seriál o programovacím jazyku Lua
http://www.root.cz/serialy/programovaci-jazyk-lua/ - Source-to-source compiler
https://en.wikipedia.org/wiki/Source-to-source_compiler - JavaScript is Assembly Language for the Web: Sematic Markup is Dead! Clean vs. Machine-coded HTML
http://www.hanselman.com/blog/JavaScriptIsAssemblyLanguageForTheWebSematicMarkupIsDeadCleanVsMachinecodedHTML.aspx - JavaScript is Web Assembly Language and that's OK.
http://www.hanselman.com/blog/JavaScriptIsWebAssemblyLanguageAndThatsOK.aspx - Dart
https://www.dartlang.org/ - CoffeeScript
http://coffeescript.org/ - TypeScript
http://www.typescriptlang.org/ - Lua (programming language)
http://en.wikipedia.org/wiki/Lua_(programming_language) - Static single assignment form (SSA)
http://en.wikipedia.org/wiki/Static_single_assignment_form - Wikipedia: Mezijazyk
http://cs.wikipedia.org/wiki/Mezijazyk - LuaJIT 2.0 SSA IRhttp://wiki.luajit.org/SSA-IR-2.0
- The LuaJIT Project
http://luajit.org/index.html - LuaJIT FAQ
http://luajit.org/faq.html - LuaJIT Performance Comparison
http://luajit.org/performance.html - LuaJIT 2.0 intellectual property disclosure and research opportunities
http://article.gmane.org/gmane.comp.lang.lua.general/58908 - LuaJIT Wiki
http://wiki.luajit.org/Home - LuaJIT 2.0 Bytecode Instructions
http://wiki.luajit.org/Bytecode-2.0 - Programming in Lua (first edition)
http://www.lua.org/pil/contents.html - Lua 5.2 sources
http://www.lua.org/source/5.2/ - Tcl Plugin Version 3
http://www.tcl.tk/software/plugin/ - JavaScript: The Web Assembly Language?
http://www.informit.com/articles/article.aspx?p=1856657 - asm.js
http://asmjs.org/ - List of languages that compile to JS
https://github.com/jashkenas/coffeescript/wiki/List-of-languages-that-compile-to-JS - REPL
https://en.wikipedia.org/wiki/Read%E2%80%93eval%E2%80%93print_loop - The LLVM Compiler Infrastructure
http://llvm.org/ProjectsWithLLVM/ - clang: a C language family frontend for LLVM
http://clang.llvm.org/ - emscripten
http://kripken.github.io/emscripten-site/ - LLVM Backend („Fastcomp“)
http://kripken.github.io/emscripten-site/docs/building_from_source/LLVM-Backend.html#llvm-backend - Emscripten – Fastcomp na GitHubu
https://github.com/kripken/emscripten-fastcomp - Clang (pro Emscripten) na GitHubu
https://github.com/kripken/emscripten-fastcomp-clang - Why not use JavaScript?
https://ckknight.github.io/gorillascript/ - Lambda the Ultimate: Coroutines in Lua,
http://lambda-the-ultimate.org/node/438 - Coroutines Tutorial,
http://lua-users.org/wiki/CoroutinesTutorial - Lua Coroutines Versus Python Generators,
http://lua-users.org/wiki/LuaCoroutinesVersusPythonGenerators
