mikemike

The initial LuaJIT ARM port was targeted at low- to middle-end ARM devices without an FPU. It took some time to find another sponsor for the VFP port.

Work on VFP and hard-float EABI (armhf) is already in progress and will be available soon.

No there's no reason to bring this up now. First, it has been worked around and second, VFP support for the LuaJIT ARM port is already in progress (parts are in the git repo, not enabled yet).

There's no explicit API to pin objects from the C side. Ok, so there's an implicit contract on which pointers to internal VM objects are still valid, once the C side has gotten them (const char *lua_tostring() is the biggest offender). But this contract a) does not lead to a practical implementation and b) is violated by plenty of C modules for Lua, because Lua didn't have a moving GC, so nobody bothered to follow it.

Now ... the interesting objects, that benefit most from the defragmentation effects of a moving GC, are the variable-sized objects. Sadly, userdata cannot be moved at all and strings are the only other interesting object type. Well ... see above.

[Table objects are not variable-size. Only their array and hash parts are. But these are singly-linked from the table object and can easily be moved around, anyway. The addresses of these memory blocks are never exposed by the VM.]

Err, I think you mean "why DON'T you get ...". :-/

I guess this has to do with the way the gaming industry works. The smaller game companies have maybe two or three big hits until they go under and/or the talent is bought out. The bigger ones are just wrappers for financial purposes nowadays. Yes, there are a few exceptions (no point in listing them). But overall, there's little continuity.

Sponsoring is an investment into the future. Most game companies drown in their daily business and never get to look beyond that. Making the next deadline is all that counts. Après nous le déluge.

Ok, so maybe this is just my personal impression and I'm all wrong. In fact, I'd love to be corrected ...

Yes, I thought about crowdfunding. But I fear that a) the Lua community is way too small to gather enough interest and b) it looks like the whole crowdfunding idea is rapidly deteriorating into an arms race of marketing experts. So many people are now jumping on that bandwagon. You'll never make it, unless you stay on the frontpages somehow.

Alas, I'm not good at marketing and a garbage collector is a very technical and very unsexy project (for most people, anyway). I should make up a silly name for it, that bears no relation to what it does. Yeah, that would do ...

Thank you for the link to the paper! I'll check it out.

I have good evidence that it's possible to create a non-moving GC that doesn't suck. It's a bit like marrying the best-of-breed of malloc implementations with the best-of-breed of incremental mark & sweep collectors. Plus some crazy ideas I'll have to experiment with first ...

Yes, this is the exact same situation as on iOS.

But 1. the mobile app market was even more locked down before Apple entered it and 2. Apple is the media's darling.

[LuaJIT author here:]

I'm not so sure the business model of LuaJIT can easily be applied to other open source projects. I mean, I've been running a business for more than 15 years. I basically downscaled consulting as I've acquired paid open source work. It pays less, but I'm happier now.

I think you'd have a hard time doing this from zero, without some backup plan or enough funds of your own. Well, have a look at the price point of scripting languages, toolchains and such. Getting a vague business plan for an open source project in the toolchain/middleware business through a VC round? I don't think so.

Business knowledge was essential, too. Negotiating open source sponsorship contracts with corporate lawyers for half a year is not that easy. Some companies were extremely easy to work with, but I guess sponsoring open source projects is simply not an established business procedure at most companies. I don't think you could possibly afford to hire an international IP lawyer to do this for you.

Actually it was the economic downturn of 2008 which triggered all of this. The (rarely followed) advice is to invest in a downturn, because you'll be the first one to come out ahead in the following upturn. Ok, so I invested my time and knowledge into a new project (#). It worked out for me, but in retrospect I realize it was a high risk investment.

Final words: you think we're seeing some kind of downturn again? Carefully assess the risks and the potential for yourself. But don't be shy if you're onto something good. Innovate, don't replicate.

(#) LuaJIT 2.x is a complete rewrite, using the experience gained working on LuaJIT 1.x, but very little of its code. It's been on my backburner since 2007 and the first public release of LuaJIT 2.0 was at the end of 2009. One might say it's about a two man-year investment before it started to pay back. Most of the time was spent on doing research and prototyping rather than writing code. I coded and then threw away almost three complete virtual machines in the process, because these approaches turned out to be dead ends. I bet you'd need a lot of courage to explain this to a VC. ;-)

Correction: LuaJIT is not yet supported on consoles. I'm confident the remaining legal issues can be resolved soon.

Note this is referring to the high-speed interpreter written in PPC assembler which gives you a 2x-6x speedup over plain Lua. Not as good as with a JIT compiler, but definitely something to consider.

The JIT compiler will be disabled on the consoles for now. This is not the last word on that matter, though.

LuaJIT is written with security in mind. LuaJIT 2.x had permanent write-protection enabled for the generated machine code in the first release, i.e. before anyone else did so.

I do not see how maintainability could somehow have an inverse relation to the engine speed. IMHO the LuaJIT code base is significantly more maintainable than the Mozilla code base.

Related: Fate of Unladen Swallow and TraceMonkey predicted about two years ago, in February 2010: http://www.reddit.com/r/programming/comments/azibq/a_rant_ab...

After some improvements to the code generator, LuaJIT git HEAD now wins on all SciMark sub-benchmarks:

    ARM11    SciMark SMALL | FFT     SOR      MC    SPARSE    LU
    -----------------------+---------------------------------------
    LuaJIT git        4.48*|  2.73*   6.93*   3.96*   3.44*   5.36*
    Dalvik 1.2.0+JIT  3.35 |  2.35    5.65    1.09    3.39    4.27

IMHO Jazelle and ThumbEE are just marketing gimmicks.

Jazelle was (is?) half-proprietary and is only useful for a really stupid Java bytecode interpreter. Nowadays, Java is JIT-compiled with much better performance.

And ThumbEE came way too late for it to be useful. It requires setup/teardown, doesn't work well with existing code and adds several other complications. It has very few features that may be of use for any VM that has already undergone some basic optimizations.

Believe me, you don't want to waste your time with this.

Well, I don't have an estimate of the costs for this feature, yet. And I need to talk with the current sponsor of the ARM port first.

Yes, LuaJIT uses its own memory allocator, which improves performance for workloads with lots of allocations. And LuaJIT's memory footprint for most object types is lower, too.

However LuaJIT 2.0 still has more or less the same GC engine as Lua 5.1. LuaJIT 2.1 will feature a new garbage collector, see the LuaJIT roadmap 2011: http://lua-users.org/lists/lua-l/2011-01/msg01238.html

In the meantime, your best bet is to avoid temporary allocations or to use manual memory management with the LuaJIT FFI, see: http://luajit.org/ext_ffi.html

LuaJIT is a drop-in replacement for Lua. Try it with your apps and report back if you encounter any problems. You need to use git HEAD to get the JIT compiler for ARM (disabled for iOS -- don't complain to me).

Sorry, I have no quantitative comparison for that. It's baked into the design of the register allocator to schedule loads early and to rematerialize constants far ahead of their use. And I'm contemplating to add an extra scheduling pass for some cases that are currently not covered well.

From experience in tuning the interpreter, instruction scheduling (esp. load scheduling) can easily make a 20-50% difference on some tight loops for a simple in-order architecture. This is much less of an issue with an out-of-order architecture, of course. It's still beneficial to do instruction scheduling for all ARM architectures, because there's apparently a huge performance difference compared to the out-of-order engines on contemporary x86/x64 CPUs.

LuaJIT/ARM uses the dual-number VM mode, where numbers can be either represented as 32 bit integers or as a double. It uses lazy normalization, so conversions happen as needed. This is invisible to the user, but internally there are two different number types.

So there's usually already a strong indicator that a variable is an integer or a double just from looking at the internal type. The interpreter usually has two paths for all operations on numbers and the integer path ist the fast path. The JIT compiler adds guards to check for the proper types and emits specialized code.

Also, the JIT compiler pro-actively narrows doubles to integers, whenever it's beneficial to do so. The logic is quite involved -- you can take a look at the big comment block in lj_opt_narrow.c.

This optimization is also active on e.g. x86/x64, where there's only a single underlying number representation (a double). But I should mention that on x86/x64 it doesn't necessarily pay off to perform _all_ operations on integer types, since this would waste the extra FPU registers and the massive extra bandwidth of the FP units in these chips. The branch unit is already quite busy and you're effectively serializing the code with all of those overflow checks.

So the JIT-generated machine code for x86/x64 and for ARM may be quite different for the same inputs. And I'm not talking about the instruction set differences alone.

E.g. compare the output of these two commands:

    luajit -jdump -e "local x=0; for i=1,100 do x=x+1 end"
    luajit -jdump -e "local x=0.5; for i=1,100 do x=x+1 end"

The generated code for the inner loop on x86/x64 is the same in both cases:

    ->LOOP:
    addsd xmm7, xmm0
    add ebp, +0x01
    cmp ebp, +0x64
    jle ->LOOP

The generated code for ARM uses either integers + overflow checks or soft-float code:

    ->LOOP:
    mov   r10, r4
    adds  r4, r4, #1
    blvs  ->exit 2
    add   r11, r11, #1
    cmp   r11, #100
    ble   ->LOOP

    ->LOOP:
    movw  r3, #0
    movt  r3, #16368
    mov   r2, #0
    bl    ->softfp_add
    add   r11, r11, #1
    cmp   r11, #100
    ble   ->LOOP

Note: the mov r10, r4 is to preserve the value prior to the overflowing calculation in exit 2. Yes, one could avoid that for an addition by undoing the calculation. But this won't work in general, e.g. for a multiplication.

LuaJIT/ARM runs fine on an Cortex-A8 or Cortex-A9. The instruction scheduling for the simpler in-order architectures is beneficial for the newer architectures or for out-of-order architectures, too.

And even though it needs at minimum ARMv5, it does take advantage of some ARMv6 and ARMv7 instructions, if available. But this has a rather small impact on the performance.

The only real issue is that this is a soft-float port for now. So it doesn't take advantage of VFP, even if the CPU has it. I'll add hardware floating-point support, when/if I get a follow-up sponsorship for this.

Ok, I made some quick benchmarks, comparing LuaJIT git HEAD and Dalvik 1.2.0 (Android 2.2.1) on the MSM 7201A (528 MHz ARM11 soft-fp). I don't have access to a newer Dalvik VM for this device. The Dalvik JIT compiler is definitely enabled, because performance gets much worse when I disable it.

Here are SciMark scores (HIGHER numbers are better):

    ARM11    SciMark SMALL | FFT     SOR      MC    SPARSE    LU
    -----------------------+---------------------------------------
    Lua 5.1.4         0.60 |  0.50    0.92    0.36    0.55    0.69
    LuaJIT git        4.34*|  2.61*   6.70*   3.91*   3.13    5.36*
    Dalvik 1.2.0+JIT  3.35 |  2.35    5.65    1.09    3.39*   4.27

Those are not too relevant, though, since it's a soft-float device. The maximum speedup is limited by the high cost of the soft-float operations (e.g. 62 cycles for a double-precision FP ADD).

And here are some simple integer benchmarks, run time in seconds (LOWER numbers are better):

    ARM11            fannkuch 10   nsieve-bits 8   binary-trees 11
    ---------------------------------------------------------------
    LuaJIT git           7.45*          3.04*           2.05*
    Dalvik 1.2.0+JIT    12.83          10.42            4.02

Note that binary-trees is a GC-intensive benchmark where LuaJIT usually loses against Java VMs, since they have a much better GC. Not so for Dalvik it seems.

The winner for each benchmark is marked with a '*'. Looks good. ;-)

That post is ancient ... here are newer SciMark results for LuaJIT:

http://lua-users.org/lists/lua-l/2010-12/msg00924.html

So what? Look at the C, Ada or ATS submissions for even more 'crazy hackery'. My programs are quite straightforward in comparison.

If the submissions using low-level types would be included in the total score, LuaJIT would show at around 1.5x instead of 2.5x.

Same experience here with LuaJIT. My submissions using low-level types (byte arrays and such) were put into 'interesting alternative', too.

Almost all other languages can use byte arrays, when they are the appropriate data structure for the job. The C submissions make heavy use of GCC extensions, Haskell gets to use mutable (OMG!) byte arrays and Free Pascal has about as much in common with Wirth's Pascal as the name.

But Python and Lua are not allowed to do that? Apparently not all languages are treated equally. Dismissing submissions by resorting to a flawed definition of 'standard' and then suppressing further debate is really lame.

I contributed almost all of the Lua programs to the shootout, but I do not feel particularly encouraged to continue contributing any programs.

Alias analysis is a good example. A JIT compiler may speculatively add dynamic disambiguation guards (p1 != p2 ==> p1[i] cannot alias p2[i]). If the assumption turns out to be wrong, the JIT compiler dynamically attaches a side branch to the guard using the new assumption (p1 == p2 ==> p1[i] == p2[i], which is an even more powerful result).

Doing this in a static compiler is hard, because it would have to compile both paths for every such disambiguation possibility. This quickly leads to a code explosion. You'd need very, very smart static PGO to cover this case: there are no branch probabilities to measure, since the compiler doesn't know that inserting such a branch might be beneficial. It may only derive this by running PGO on code which has these branches, which leads to the code explosion again.

Auto-vectorization is another example: a static compiler may have to cover all possible alignments for N input vectors and M output vectors. This can get very expensive, so most static compilers simply don't do it and generate slower, generic code. A JIT compiler can specialize to the runtime alignment and even compile secondary branches in case the alignment changes later on (e.g. a filter fed with different kernel lengths at runtime).

This is a common misinterpretation of the Dynamo paper: they compiled their C code at the _lowest_ optimization level and then ran the (suboptimal) machine code through Dynamo. So there was actually something left to optimize.

Think about it this way: a 20% difference isn't unrealistic if you compare -O1 vs. -O3.

But it's completely unrealistic to expect a 20% improvement if you'd try this with the machine code generated by a modern C compiler at the highest optimization level.

Well, here's Euler14 in Lua for a start: http://lua-users.org/lists/lua-l/2010-09/msg00568.html

But obviously for a proper comparison of the runtimes the benchmarks need to be implemented the 'same way' and not simply yield the 'same result'.

The performance problems originate in the design of your trace compiler, not in static vs. dynamic dispatch. Some suggestions:

* The interpreter should have a fast profiling mode (hashed counting of loop backedges) and a slower recording mode (for every instruction call the recorder first, then execute the instruction). Either implement it twice (it's small enough), use a modifiable dispatch table and intercept the dispatch in recording mode (indirect threading), or compute branch offsets relative to a base (change the base to switch modes).

* Don't record traces for a long time and then compile everything together. Do it incrementally:

- Detect a hot loop, switch into recording mode, record a trace, compile it, attach it to the bytecode, switch to profiling mode (which may call your compiled trace right away).

- Make the side exits branch to external stubs which do more profiling (one counter per exit). Start recording hot traces and continue until it hits an existing trace or abort if it hits an uncompiled loop.

- If you completely control the machine code generation (i.e. not with LLVM), you can attach the side traces to their branch points by patching the machine code. Otherwise you may need to use indirections or recompile clusters of the graph after a certain threshold is reached.

- Region selection has a major impact on performance, so be prepared to carefully tune the heuristics.

* Sink all stores, especially updates of the virtual PC, data pointers etc. Don't count on the optimizer to do this for you.

* Due to the nature of the source language you may need to preprocess the IR or you need to teach the optimizer some additional tricks.

- E.g. the loop [-] should really be turned into 'data[0] = 0'.

- Or the loop [->>>+<<<] should be turned into 'data[3] += data[0]; data[0] = 0'.

- It's unlikely any optimizer handles all of these cases, since no sane programmer would write such code ... oh, wait. :-)

Sigh, not that nonsense comparison again.

Apart from using suboptimal Lua code (the author obviously doesn't know about the Lua keyword 'local'), LuaJIT beta2 didn't compile recursion at all. It runs more than 4x faster with the current version and beats MacRuby easily.

Oh, and comparing language implementations based on the speed of a recursive Fibonacci number generator has exactly zero real-world relevance. Try again with a more realistic mix of benchmarks or something domain-specific like SciMark (LuaJIT is only 30% slower than GCC on this one).

Judging from http://antoniocangiano.com/2010/05/16/benchmarking-macruby-0... MacRuby plays in the same league as the other Ruby implementations. And http://shootout.alioth.debian.org/u32/benchmark.php?test=all... tells you where that league can be found, relative to LuaJIT. Hint: scroll to the bottom. :-)

Actually reading the Lua mailing list post http://lua-users.org/lists/lua-l/2010-03/msg00305.html, referenced in the linked text might help:

> For pidigits I'm comparing the pure JS and Lua programs, not the GMP bindings.

I'm comparing these two:

http://shootout.alioth.debian.org/u32/program.php?test=pidig...

http://shootout.alioth.debian.org/u32/program.php?test=pidig...

Both are written in pure Lua and JavaScript and do not use a C binding.

The result of the distance() function is unused and can be optimized away by the compiler. Runs in 0.04s with LuaJIT 2.0. No type declarations needed. :-)

    local radius = 6371

    local function distance(latA, lngA, latB, lngB)
      local latAr = math.rad(latA)
      local lngAr = math.rad(lngA)
      local latBr = math.rad(latB)
      local lngBr = math.rad(lngB)

      local deltaLat = latBr - latAr
      local deltaLng = lngBr - lngAr

      return radius * 2 * math.asin(math.sqrt(
              math.sin(deltaLat/2)^2 + math.cos(latAr)
              * math.cos(latBr) * (math.sin(deltaLng/2)^2)))
    end

    local start = os.clock()

    for latA=-90,90,2.5 do
      for lngA=-90,90,2.5 do
        for latB=-90,90,2.5 do
          for lngB=-90,90,2.5 do
            distance(latA, lngA, latB, lngB)
          end
        end
      end
    end

    local stop = os.clock()
    print(stop-start)

Most of the VM is written in C. Only the core of the interpreter is written in assembler (generates ~13K of machine code).

And the port of the interpreter to x64 is already done, so it was certainly practical. Porting the rest of the VM and the JIT compiler is what takes most of the time.

Mostly resolution and dispatch. Some of this needs very clever caching or the overhead can't be eliminated or hoisted. The control-flow constructs and iterators come to mind, too.

The Rubyists certainly know about these issues, so you'll have to ask them for details.