в который раз возник спор о Jit-компиляции динамических языков, о том как выводить типы etc.
FYI привожу дизайн-документ luajit2 от автора luajit. Старый компилятор практически не не "трогал" официальный дистрибутив, был большей частью написан на луа(!) и увеличивал рантайм всего на 30KB. Ускорял луа раз в 5-10.
Если вас интересуют в основном подробности работы tracing-компилятора — читайте сразу конец.
Subject: LuaJIT roadmap 2008
From: Mike Pall <mikelu-0802@...>
Date: Fri, 1 Feb 2008 19:09:22 +0100
There have been several requests to publish a roadmap for LuaJIT,
so here it is:
LuaJIT 1.x
----------
— LuaJIT 1.1.4 will be released in the next few days. This is
strictly a minor bug fix upgrade to catch up with Lua 5.1.3.
— CoCo 1.1.4 will be released at the same time, because Lua 5.1.3
makes some incompatible changes to the C call depth counting
(basically reverse-patching these parts back to Lua 5.1.2).
LuaJIT 2.x
----------
I've been working on LuaJIT 2.x for quite some time now. It took
much longer than I had expected. I'm now at the third complete
redesign, because the first two approaches I tried didn't work
out: 1. shadow SSA info to augment the old bytecode got too
complex. 2. one-pass on-the-fly SSA generation doesn't work for
Lua because of an ugly corner-case involving upvalue semantics.
However I've gotten quite far with the third approach, namely a
fast interpreter combined with a trace compiler (detailed
description at the end of this posting).
The VM has been designed from the ground up to support the new
execution model. It still shares some components with the
standard Lua 5.1 interpreter, but many parts have changed.
Here are the most interesting changes:
— The bytecode format has been redesigned. It's much more
orthogonal, partially specialized and tuned for faster
dispatch.
— The bytecode interpreter has been completely rewritten in
hand-tuned x86 assembler. It has been optimized to reduce
branch prediction misses and cache misses. Scheduling has been
tuned and instruction-level parallelism has been improved. It
features extremely fast dispatch ("indirect threading") and
it's very compact. The commonly used parts of the code fit into
a single 4K page. Your current-generation out-of-order- and
speculative-execution CPU monster under your desk will love it.
— Object references are still tagged values, but now only use
half the space (8 bytes). IEEE-754 doubles are overlapped with
other object references. The object tags have a special
encoding which is an unused FP NaN. Amongst other things this
means stacks and arrays need 50% less space. D-Caches rejoice.
— The explicit frame stack (CallInfo) is gone. The frame
structure is implicitly stored in the regular Lua stack (tagged
values). This speeds up call handling substantially and also
simplifies the compiler (uniform treatment of slots and frames).
— Exception handling has been redesigned along with the new frame
structure. A pcall() is almost zero-cost now.
— Coroutines are completely "stackless" again. No C stack needs
to be allocated for their use. This is quite a departure from
the concept for LuaJIT 1.x -- the only drawback is that you
cannot yield *and return* to a C function. But you can of
course yield across pcall() and from iterators and metamethods
(which is what most people really want or need).
— Many of the standard library functions are now "internal"
functions. The fast paths are written in assembler, the
fallback paths are written in C. Apart from dramatic speedups
this also enables the stackless nature of coroutines.
Lots of other minor things have changed, like the fast string
hash (see the backport I posted a few weeks ago).
Preliminary benchmarks show that *the interpreter alone* is
already 2x-4x faster in most cases. Embarassingly this is better
than LuaJIT 1.x in a few benchmarks. Much higher speedups are
still to be expected from the trace compiler.
But the VM itself is nowhere near complete. Lots of rough edges
remain. Debug hooks are not yet implemented (I want them to be
zero-cost when not active). Other debug functionality, like
tracebacks, already work fine. Many more library functions need
to be internalized. And a plethora of little details still bear
prominent TODO signs.
The biggest stumbling block right now is the trace compiler and
all the associated machinery. I guess I need to redesign trace
recording (again), because a simple static approach to ucode
generation doesn't seem to work out well. The x86 backend and the
register allocator is not there yet, most optimizations are still
in their infancy. Consider it vaporware for now.
In short: no realistic ETA, yet -- "2008" is the best promise I'm
able to give. Before you ask: prereleases are pointless right
now, because you wouldn't get a fully working VM and I would
drown in support requests.
On the positive side, the new VM should be easier to port to
other CPU architectures. But there's more to consider, like a
different number type (on platforms without hardware FP) or
different pointer sizes (x64). This will certainly complicate
things. In any case, a port is not something I want to embark on
before the x86 version is stable.
My list of things I originally wanted to be in the first release
has already shrunken considerably. Some things NOT to expect:
— Redesigned memory management: faster allocation and
cache-friendly marking. Got many ideas and all the literature
I'd ever want to read -- not sure when I'll approach this.
— Concurrency. I've got a neat idea about a specific concurrency
model: basically a GIL which is only unlocked for the GC, for
blocking on I/O and for CPU-intensive code paths. I.e. the
interpreter would run locked, trace compiled code paths run
unlocked or lock on demand. C calls which block or may take
lots of CPU time need to unlock explicitly. I don't know
whether this works out in practice though.
— A compiler for pattern matches (regexes). I've got the basic
design and some code, but it doesn't fit the current execution
model anymore. Not that important, so it'll have to wait.
How a trace compiler works
--------------------------
The LuaJIT 2.x VM operates in four phases:
1. Interpretation
2. Interpretation + Trace Recording
3. Trace Compilation
4. Trace Execution
Here's a simplified description of the different phases:
1. Interpret the bytecode and keep running statistics on loops
and calls. As soon as certain thresholds are reached, the current
code path is considered "hot" and the VM proceeds to phase 2 and
starts recording.
2. Keep on interpreting the bytecode, but at the same time record
its actions. This involves not just the bytecodes themselves, but
also the individual steps taken to execute them (e.g. think about
a table lookup which might involve metamethods). The relatively
coarse bytecode is translated into a form of SSA-based microcode
(ucode) which captures much more detail.
Recording strictly follows the control flow at runtime, which
effectively flattens only the used parts of the code to a linear
"trace". Dead code paths are never recorded, just like uncommon
("cold") paths. Function calls are treated just like any other
control flow transition and tracing continues across them (which
is equivalent to inlining in a traditional compiler).
Conditional branches, type checks, function dispatch and other
runtime decisions cause "guards" to be inserted into the trace.
These guarantee an exit of the trace whenever their precondition
turns out not to be true in a future execution of a trace.
A really neat consequence is that for a dynamic language (such as
Lua) a trace also captures a particular runtime specialization of
operations and types. A trace is like a statically typed variant
of the code and is well suited to optimization (see below).
Recording is stopped under certain conditions. Some conditions
cause an abort, e.g. if an error is raised or some particular
(hopefully uncommon) combination of events cannot be handled. In
this case the collected trace is thrown away and the VM proceeds
again to phase 1 and continues interpreting the code.
Recording is also stopped whenever the trace reaches certain
points in the control flow. E.g. when the trace start point is
hit again (next loop iteration). In this case the trace is
considered complete and the VM proceeds to phase 3 to compile it.
3. A completed trace is optimized and compiled to machine code.
Since the trace is just a linear stream of statically typed
SSA-based ucode, all the traditional compiler optimizations
apply. I'm only listing the most useful ones here:
— Constant propagation and constant folding replace runtime
operations with their constant results. Guards depending on
constants can be completely eliminated. Runtime specialization
and inlining create many opportunities for this optimization.
E.g. the return address from an inlined function is a constant
(the call is in the same trace) so the guard can be eliminated.
— CSE (common subexpression elimination) eliminates redundancy in
the form of repeated expressions which calculate the same
result. Most of these are not caused by the programmer (e.g.
the classic (a+b)*(a+b) example) but by the translation to
ucode. The most common targets for CSE are repeated guards
(e.g. type checks) and address translations for table lookups.
— Loop-invariant code hosting moves operations out of a loop
which only depend on inputs outside of the loop. This is most
useful to move guards resulting from method resolving and
function dispatch out of a loop. E.g. calling math.abs() can be
reduced to a single machine code instruction inside the loop
plus a check before the start of the loop that math.abs still
resolves to the internal function originally handling it.
Optimization often substantially reduces the number of ucodes in
a trace. Converting the remaining ucode to machine code is pretty
straightforward because it's just a linear stream of instructions.
[This is a bit over-simplified: traces can extend existing traces
to form a trace tree and guards are converted to branches to
compensation code for returning to the interpreter. There are
more complications under the hood.]
Once a trace has been compiled, it's registered with its start
point. Whenever the interpreter hits this part of the code again,
it proceeds with phase 4 and directly runs the machine code. In
the case of a loop this is done right after compilation.
4. The compiled machine code resulting from a trace is run. If
it's truly a "hot" trace, the compiled code will run often enough
to outweigh the effort of optimizing and compiling it.
A guard may occasionally cause a trace to exit. This can happen
when a different control-flow path is taken or a type check or
bounds check fails and so on. In this case compensation code is
called to prepare the state for returning to the interpreter.
Depending on the kind of guard, the VM either switches to phase 1
or phase 2. Errors force a return to the interpreter. Most other
guards start another trace which in turn extends the existing
trace.
Literature:
Descriptions of trace compilation employed on bytecodes are here:
Popular software using this technique are QEMU and Valgrind.
Intel's Netburst architecture (Pentium 4) employs a trace cache
to store a copy of the x86 instruction stream translated by the
instruction decoder to RISC-like micro-ops.
The VM of LuaJIT 2.0 has been rewritten from the ground up and is
relentlessly optimized for performance. It combines a high-speed
interpreter, written in assembler, with a state-of-the-art JIT compiler.
An innovative trace compiler is integrated with advanced, SSA-based
optimizations and a highly tuned code generation backend. This allows a
substantial reduction of the overhead associated with dynamic language
features. It's destined to break into the performance range
traditionally reserved for offline, static language compilers.
Performance on numerical code is already quite competitive (see below).
Support for other areas (e.g. string functions) is still a bit weak.
Although the VM supports all Lua language features and standard library
functions, the JIT compiler is not complete (yet) and falls back to the
interpreter in some cases. All of this works transparently, so unless
you use -jv, you'll probably never notice. The interpreter is quite
fast, too (near the performance of the LuaJIT 1.x JIT compiler).
Preliminary benchmark numbers are shown below -- performance will
likely improve during the beta test phase. These numbers are mainly
intended to give you an idea about the typical speedups you can expect,
depending on the type of application. Your mileage may vary.
Ok, so thanks to everyone for their patience! A big thank you goes to
the alpha testers. And now, please have fun with it -- Happy Halloween!
Кое-какая новая информация от Mike Pall об LuaJit2 и о том, что тем, кто компилирует динамические языки в LLVM, не стоит на многое рассчитывать.
Robert G. Jakabosky wrote:
> One way llvm-lua could improve the speed of static compiled code would be to
> add support for recording hints during runtime and writting those hints to a
> file that would then be passed to the static compiler.
Sure, feedback-directed optimization (FDO) would probably help a
lot. But static compilers face some inherent difficulties when
compiling a dynamic language:
- Dynamic languages generate tons of code paths, even for simple
operations. A static compiler has to compile *all* code paths.
Apart from the overhead, this pessimizes the fast code paths,
too (esp. PRE and register allocation). A JIT compiler only
generates code for paths that are actually executed (this may
also differ between runs).
- Even with FDO, static compilers have to be very conservative
about inlining and specialization to limit code growth. A JIT
compiler can be more aggressive, because it has to deal with a
much lower number of code paths.
- Not even the best C compilers are able to hoist complex control
structures out of loops. Once you lower (say) a load from a hash
table (a loop following the hash chain) to the LLVM IR, you lose
the original semantics. This usually means you cannot optimize
it or eliminate it, either.
That's not to discourage you from your work -- just to point out
some difficulties you'll be facing with llvm-lua.
The following trivial Lua function is a nice optimization challenge:
function f(x, n)
for i=1,n do x = math.abs(x) end
return x
end
The inner loop has two hash table loads (_G["math"], math["abs"]),
a function dispatch and a call to a standard library function.
Here's the corresponding checklist for a Lua compiler in
increasing order of complexity:
LJ1 LJ2
yes yes Type-specializes the hash table loads (object and key type).
yes* yes Inlines both hash table loads (* partially inlined by LJ1).
no yes Specializes the loads to the hash slot (omit chain loop).
yes yes Specializes to a monomorphic function dispatch for abs().
yes yes Inlines the abs() function.
no yes Hoists both hash table loads out of the loop.
no yes Hoists the abs() out of the loop (abs(abs(x)) ==> abs(x)).
no yes Emits an empty loop (could be optimized away, too).
Now try to get 8x yes with a static compiler, while preserving the
full Lua semantics (e.g. somebody might do math.abs = math.sin or
_G might have a metatable etc.). Good luck! :-)
> Below are the results of running scimark-2008-01-22.lua [1] for a performance
> comparison.
>
> # taskset -c 1 /usr/bin/lua scimark-2008-01-22.lua large
The large dataset is an out-of-cache problem and cache thrashing
(esp. for FFT) dominates the timings. IMHO the small dataset is
better suited to compare the performance of the different VMs.
Anyway, for the large dataset LuaJIT 1.1.x gets 89.80 and Lua 5.1.4
gets 13.87 on my box. And here's a preliminary result for LJ2:
FFT 85.91 [1048576]
SOR 821.95 [1000]
MC 73.14
SPARSE 324.05 [100000, 1000000]
LU 820.51 [1000]
SciMark 425.11 [large problem sizes]
(i.e. 31x faster than plain Lua)
For comparison, GCC 4.3.2 -m32 -march=core2 -O3 -fomit-frame-pointer:
FFT 93.00 [1048576]
SOR 883.53 [1000]
MC 180.16
SPARSE 716.08 [100000, 1000000]
LU 1149.43 [1000]
SciMark 604.44 [large problem sizes]
(I've reformatted the C program output to match the Lua output.)
Ok, so LJ2 is getting closer to C's performance. It's already on
par with C for simpler benchmarks (like mandelbrot or spectralnorm).
But there still remains a lot to do ...
--Mike
Здравствуйте, Nuzhny, Вы писали:
N>Что-то я не могу угнаться за твоей мыслью. Предлагаешь как реальную задачу как раз то, о чём постом ранее говорил: "Джититься могу только простенькие мат.вычисления."
В данном случае я не точно выразился. Лучше будет сказать — вычислительную задачу под которую авторы не сделали специализированной оптимизации.
N>Но и это реализовать можно. Как только выйдет релизная версия — займусь.
Давай. Твоим результатам будет больше доверия.
N>Реальные же задачи, на мой взгляд, совсем другого характера. Можно для интереса провести опрос: сколько людей на компилируемых Net-языках или Ява делали свой альфа-бленд. Обычно его вообще на видеокарте реализуют. Так что хотелось бы увидеть "реальную" задачу.
Согласен. Но если мы говорим о джите, то он делается ведь не ради галочки.
В задачи скрипта (коим и является Луа) входит склеивание код написанного на низкоуровневых языках. Его производительности для этих целех хватет не потому, что у него быстрый интерпретатор или мощных джит, а потому, что кода мало и он выполняется в не критичных для скорости местах. Для скрипта важнее не скорость выполнения, а минимальная латентность.
Если же сктип пытаются скомпилировать (а джит — это и есть компиляция), то подразумевается, что скрип уже пытаются использовать не по его прямому назначению, а в качестве языка общего назначения. Но раз так, то логично требовать от такого решения того, что мы превыкли требовать от тех самых языков общего назначения — скорости выполнения сопоставимого с С. Причем не в отдельных тестах или нишах, а в большинстве сценариев использования.
Скажем Ява и дотнет обычно проигрывают С по скорости. Но этот проигрыш весьма незначителен.
А так ли это для джит-нутых скриптов?
Я уверен, что нет.
Почему?
Потому что чудес не бывает. Язык спроектированный для динамической гибкости не может быть столь же эффективным как язык спроектированный в расчете на скорость выполнения.
N>P.S. Приведённые по твоим ссылкам реализации на первый взгляд не самые удачные. Что-то мне подсказывает, что переделка алгоритма под SSE2 и компиляция с соответствующими опциями даже майкрософтовским компилятором даст существенный выигрыш.
Возможно. Но тут у С, на сегодня, имеются определенные преимущества.
1. Имеются реализации компиляторов умеющих автоматически применять SSE.
2. Почти все реализации комплиторов поддерживают расширения позволяющие использовать инлайн-ассемблер. Многие из таких расширений поддерживают и SSE-инструкции.
Что же касается того же Луа, то у меня есть большие сомнения, что текущая версия его джита хотя бы приблизится по скорости генерируемого кода к лобовым реализациям.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, z00n, Вы писали:
Z>Революция грядет!
Агащазблин.
Z>Язык с динамической типизацией и скоростью на SciMark ~= Java client, при том, что многие оптимизации еще не работают.
Чудес не бывает. Даже в твоих данных два теста ниже плинтуса просели.
На реальных задачах все будет еще хуже. И намного.
Динамическая типизация, прототипный ООП, таблицы вместо объектов — это приговор общей производительности.
Джититься могу только простенькие мат.вычисления.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
в который раз возник спор о Jit-компиляции динамических языков, о том как выводить типы etc. Z>FYI привожу дизайн-документ luajit2 от автора luajit. Старый компилятор практически не не "трогал" официальный дистрибутив, был большей частью написан на луа(!) и увеличивал рантайм всего на 30KB. Ускорял луа раз в 5-10. Z>Если вас интересуют в основном подробности работы tracing-компилятора — читайте сразу конец.
Милейший. Чудес не бывает. Читать в сотый раз сказки про белого бычка смысла не имеет.
Если скрипт разогнали в 10 раз, значит, что он исходно тормозил раз в 100 по сравнению с хорошим нэйтивным кодом.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Если скрипт разогнали в 10 раз, значит, что он исходно тормозил раз в 100 по сравнению с хорошим нэйтивным кодом.
Что под ним понимать? Если речь об оптимальном по какому-то параметру коде — это NP-полная задача, или есть мысли по эффективной формализации? Я, посидев в профайлере, смогу утверждать, что результат быстрее такого-то варианта на столько-то, но не скажу, что произвольный набор байт будет работать медленнее.
People who are more than casually interested in computers should have at least some idea of what the underlying hardware is like. Otherwise the programs they write will be pretty weird (c) D.Knuth
Re[2]: Upcoming LuaJIT 2.x's performance comparable to C
Здравствуйте, z00n, Вы писали:
Z>Кое-какая новая информация от Mike Pall об LuaJit2 и о том, что тем, кто компилирует динамические языки в LLVM, не стоит на многое рассчитывать.
Здравствуйте, z00n, Вы писали:
... Z>- The bytecode interpreter has been completely rewritten in Z> hand-tuned x86 assembler.
...
уже только за это в приличных местах могут и выгнать вон.
[имхо] я писал на луа несколько лет весьма активно — там семантика не позволит добиться соответствия кода возможностям железки. то есть на отдельных маразматических примерах, типа приведенного в другом посте ниже
function f(x, n)
for i=1,n do x = math.abs(x) end
return x
end
будут всплески, но ни simd, ни целочисленной арифметики, ни работы нескольких ядер и тп.
Луа весь динамический и за это, как и за простоту его и любят. Многое делается с подгрузкой/перезагрузкой кода, многое делается с подключением на ходу сишных библиотек.
Так что пытаться наточить луа на одну нишу серверов со статическим кодом — бесполезное занятие.[/имхо]
Здравствуйте, VladD2, Вы писали:
VD>Чудес не бывает. Даже в твоих данных два теста ниже плинтуса просели. VD>На реальных задачах все будет еще хуже. И намного.
Гм, на реальных задачах и первый LuaJit показывал себя очень хорошо. Из последнего виденного лично — скрипты для Сталкера. Все конкуренты пока далеко позади.
Ведь скриптование — это и есть прямая и самая что ни на есть реальная задача этого языка. А сейчас всё будет ещё лучше.
Или имеются в виду какие-то другие реальные задачи?
Здравствуйте, Nuzhny, Вы писали:
N>Гм, на реальных задачах и первый LuaJit показывал себя очень хорошо.
Это каких? Луа — это скрип предназначеный для автоматизации задач не требовательных к процессорному времени.
N>Из последнего виденного лично — скрипты для Сталкера. Все конкуренты пока далеко позади.
Ну, дак скрипты они и есть скрипты. Где там конкуренты я не знаю, но ни с одним компилируемым языком (даже с явой) они не сравляться по производительности.
N>Ведь скриптование — это и есть прямая и самая что ни на есть реальная задача этого языка. А сейчас всё будет ещё лучше. N>Или имеются в виду какие-то другие реальные задачи?
Ага. Любая требующая быстрого исполнения. В этой теме, вообще-то, о компиляции говорится.
Реализуй его на новом луа и сравни с результатами компилируемых языков.
Сейчас не могу найти ссылку, но кто-то реализовал это дело на Питоне и использовал PyPy (компилятор в нэйтив). Результат был совершенно печальным.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
VD>Я тут уже рядом писал. Воспроизведите АльфаБлэнд на луа и сравните результат с остальными.
Чем это объективно лучше SciMark , чтобы на это стоило тратить время?
VD>Думаю, что Луа буте в пролете.
Пусть бремя доказывания лежит на вас
Здравствуйте, z00n, Вы писали:
VD>>Я тут уже рядом писал. Воспроизведите АльфаБлэнд на луа и сравните результат с остальными. Z>Чем это объективно лучше SciMark , чтобы на это стоило тратить время?
Тем, что это не тест, а реальная задача. И тем, что авторы не под нее пока что (с огромной вероятностью) не сделали "закладку".
VD>>Думаю, что Луа буте в пролете. Z>Пусть бремя доказывания лежит на вас
А зачем мне это? Я прекрасно знаю что такое скрипы, чем они хороши и плохи.
Как только скрипт начнет компилироваться в качественный нэйтив код, так то час же он потеряет свою привлекательность, так как вся динамика будет не доступна.
Пойми, класс в Луа или Питоне представляет себе эдакую навороченую хэш-таблицу. Доступ к полю — это поиск в хэш-таблице по имени поля. Если его превратить в рельный класс аналогичный структурам С или классам явы, то протитипная гибкость идет к черту. А если этого не сделать, то скорость идет в том же направлении.
Так что чудес не бывает. И чем скорее это поймешь, тем меньше времени будешь тратить на изучение новых реализаций вечных двигателей.
Пойми меня правильно. Любой скрипт имеет некий сабсэт в котором можно вывести типы и скомпилировать маш-код который не будет отличаться от С по скорости. Но это будет не скрипт, а сабсэт скрипта с удобством и возможностями урезанного С. Реальные программы которые пишутся на скриптах используют мощьные возможности этих скриптов, а значит выходят за пределы того где джит может помочь. Так что джит способен повысить скорость в ряде случаев. Но сделать скрипт таким же быстрым как С — это бред сивой кобылы.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
N>>Ведь скриптование — это и есть прямая и самая что ни на есть реальная задача этого языка. А сейчас всё будет ещё лучше. N>>Или имеются в виду какие-то другие реальные задачи?
VD>Ага. Любая требующая быстрого исполнения. В этой теме, вообще-то, о компиляции говорится. VD>В общем, что трепаться то? VD>Вот сравнительно простенький алгоритм трбующий серьезной оптимизации.
Что-то я не могу угнаться за твоей мыслью. Предлагаешь как реальную задачу как раз то, о чём постом ранее говорил: "Джититься могу только простенькие мат.вычисления."
Но и это реализовать можно. Как только выйдет релизная версия — займусь.
Реальные же задачи, на мой взгляд, совсем другого характера. Можно для интереса провести опрос: сколько людей на компилируемых Net-языках или Ява делали свой альфа-бленд. Обычно его вообще на видеокарте реализуют. Так что хотелось бы увидеть "реальную" задачу.
P.S. Приведённые по твоим ссылкам реализации на первый взгляд не самые удачные. Что-то мне подсказывает, что переделка алгоритма под SSE2 и компиляция с соответствующими опциями даже майкрософтовским компилятором даст существенный выигрыш.
