NativeJIT – JIT compilation of expressions involving C data structures | Hacker News Reader

NativeJIT – JIT compilation of expressions involving C data structures

github.com

130 pointsAnbeSivam33 comments

Title seems incorrect, or at least misleading. It is not a JIT for C++ code (ie. not "C++ to..."), it is a JIT library for C++ that seems focused on compiling arithmetic algorithms as used in bing.

Interestingly, it requires the functions called by the JIT'd code to be side-effect free, since it guarantees it will call any given function invocation at least once, since it evaluates both sides of any but top level branches. See "Design Notes and Warnings" in https://github.com/BitFunnel/NativeJIT/blob/master/Documenta...

Thanks, we updated the title from “NativeJIT – a C++ to x64 JIT used in Bing”.

The real question is why would you use it instead of mature LLVM.

It seems to solve a different usecase. LLVM is (by their own documentation) not really intended for ad-hoc JIT compilation for queries. It doesn't put a lot of priority on making the compilation fast (but rather makes the produced code fast).

On top of that, LLVM is a massive dependency.

I only looked at NativeJIT a few minutes but it seems to solve both of these issues. It's pretty small in terms of API surface // total amount of code and is explicitly designed for a usecase where compilation happens as part of a user-issued query (that needs to be fast).

LLVM is a fairly heavyweight tool to use for simplistic or really frequent JIT use-cases. There is definitely room for smaller and simpler tools for that purpose, imo. Like, I'm pretty sure LuaJIT runs rings around LLVM in terms of how quickly it generates code, but at the cost of doing considerably less optimization. This is sometimes a useful tradeoff.

"but at the cost of doing considerably less optimization"

That's arguable. Ravi[1] is a Lua implemented with an LLVM-based JIT. The benchmarks here[2] compare runtime performance of Ravi vs. LuaJIT. The Ravi timings don't include compilation time, the LuaJIT timings do. Sometimes LuaJIT siginficantly outperforms Ravi, sometimes it's on par, sometimes worse. But the results don't suggest that there is less (effective) optimisation going on.

[1] https://github.com/dibyendumajumdar/ravi

[2] http://the-ravi-programming-language.readthedocs.io/en/lates...

The parent post is correct. LLVM's optimizations are low-level optimizations tuned for C and C++. By contrast, the optimizations you want to do for dynamic languages (and high-level languages in general) are high-level optimizations that are better done on language-specific IRs. Moreover, dynamic languages need dynamic optimizations such as polymorphic inline caching, speculation and bailouts with on stack replacement, etc.

Optimization pipelines are invariably language-specific. If you were to somehow make LuaJIT into a C/C++ compiler without doing any work on its optimizer, you would get similarly poor results.

> If you were to somehow make LuaJIT into a C/C++ compiler

Clang -> Sulong -> Java bytecode -> Luje [1]? May need more turtles :)

Technically, one reason -of several- this probably wouldn't work without significant effort is that Sulong relies on Graal's FFI intrinsics. But those should be convertible to LuaJIT FFI calls (in theory).

[1] https://cowlark.com/luje/

True. Although, LuaJIT does pretty well on C-style code using its FFI library. But that's something it's designed for, so not really surprising.

I think it's a bit more complex than that. I'm pretty sure that LLVM does use more optimisation passes and techniques than LuaJIT's backend, however LuaJIT optimises with knowledge of the semantics of Lua, whereas LLVM optimises as if it was optimising something like C.

> I'm pretty sure LuaJIT runs rings around LLVM in terms of how quickly it generates code, but at the cost of doing considerably less optimization. This is sometimes a useful tradeoff.

You can't really compare LuaJIT and LLVM directly, because LuaJIT is a trace compiler. A LuaJIT trace is a linear sequence of instructions with no control flow, which makes optimization much easier. LLVM on the other hand is statically compiling code consisting of many basic blocks and potentially complicated control flow between them.

So LLVM's job is much harder. LuaJIT's optimizer doesn't have to work nearly as hard to get a similar quality of code.

Because LLVM isn't a JIT in the sense of PyPy, the JVM or Lua. It is more in the sense of the CLR, a late bound AoT compiler. It doesn't watch data access patterns, it doesn't watch arms of a switch statement, there is no feedback.

The same reason regex engines have their own specific JIT emitters. Limited overhead and size constraints because it's not a strict requirement to pre-compile regexes. It's basically a native dialect of existing automaton generators, where the abstract code is replaced with machine instructions.

It sounds like this is both high-throughput and low-latency. I trust LLVM is high-throughput but I imagine it's got a bit of overhead in starting up.

LLVM is neither high-throughput nor low-latency. It does probably generate faster code, though.

Surely LLVM is high-throughput? Otherwise your dev-test cycle of edit/compile/run would suffer from long compilation/link times.

It's "acceptable-throughput" for that use case, and you can balance the tradeoffs of compilation time to optimisation (for time or code size) by adding -On parameters. That's a very different kind of throughput to "compile small functions many times per second".

These are different metrics of throughput. I'd expect NativeJIT to be 100x to 1000x (or possibly more) faster than LLVM for its use case: temporary expressions measured in low 100s of bytes, no loops, no expression-visible side effects.

GNU lightning would be a better choice. However, it does not optimize.

What I find amazing about NativeJIT is how small the codebase seems to be -- under 10k SLOC. Impressive!

Will seriously consider using this to speed up expression execution in EventQL [0] (we shied away from llvm so far because it's such a massive dependency).

[0] https://eventql.io/

This is similar to a technique used in Renjin to compile specific vector computation expressions down to straight-line JVM bytecode, which is then JITed down to machine code. It's a very powerful technique because it removes all the indirection involved in a evaluating dynamic expressions and lets the processor just do its job.

For example, if you evaluate sum(sqrt(x^2 + y^2) * 3) in Renjin, and x or y happen to be very long vectors, then we'll jit out a JVM class for this specific expression that would look something like this in Java:

  class JittedComputation1E5374A3 {
    SEXP compute(SEXP[] args) {
      double[] x = args[0].toDoubleArrayUnsafe();
      double[] y = args[1].toDoubleArrayUnsafe();
      double sum = 0;
      for(int i=0;i<x.length;++i) {
        double xi = x[i];
        double yi = y[i]
        sum += Math.sqrt(xi*xi+yi*yi) * 3;
      }
      return DoubleVector.valueOf(sum);
    }
  }

The computation is specialized to the types of x and y, so if for example x is a sequence 1:1000000 then a new class gets written for that doesn't even use an array for x.

The speedup is so impressive that even if you don't cache the compiled expression you see dramatic improvements: http://www.renjin.org/blog/2015-06-28-renjin-at-rsummit-2015...

https://twitter.com/danluu/status/771622870132809729

Better link: http://bitfunnel.org/getting-started-with-nativejit/

I know it can be sandboxed, but it makes the hair on the back of my neck stand up to think that something people type into a search box on a web page gets turned into machine code and executed.. :)

It's no big deal as long as JIT compiled code is restricted to the safe subset of instructions. For example, in FreeBSD BPFs (berkeley packet filters) are JIT compiled and directly executed in the kernel mode.

More information: http://bitfunnel.org

Can't you use function overloading? or function pointers? Why do you need to recompile the code? Can someone give an example of where this should be used?

This is precisely a strategy for optimizing away the cost of function calls and other indirection.

You basically really want this in any case where you're applying a dynamic expression to a large dataset.

We use the technique in Renjin, an R interpreter built on the JVM, for vectorized expressions such as sqrt(x^2+y^2) where x and y are long arrays.

You can implement this with function pointers, or interfaces in Java, but if you're evaluating the expression millions of times, then the cost of the indirection is huge, and worse yet, it gets in the way of the processor's branch prediction and pipelining.

If you can compile the same dynamic expression down to straightline machine code, the impact is pretty fantastic: http://www.renjin.org/blog/2015-06-28-renjin-at-rsummit-2015...

Looks very similar to https://github.com/asmjit/asmjit

So would it make sense to use this as the engine for something akin to jq or xsv?

The title is wrong. This is not a C++ to x86 JIT (which would be really cool), this is a JIT library for C++ (of which there are a number). It has it's own domain specific language for expressions. It doesn't take arbitrary C++. No std C++ syntax, no classes, etc.

Ex:

    // nativeJIT DSL
    auto & area = expression.Mul(rsquared, expression.Immediate(PI));
    auto function = expression.Compile(area);
    // C++
    auto area = rsquared * PI;

"this is a JIT library for C++ (of which there are a number)"

Out of interest, can you recommend any others that are actively maintained?

Thanks, we updated the title from “NativeJIT – a C++ to x64 JIT used in Bing”.

Reply on news.ycombinator.com