5 ms·

NativeJIT – JIT compilation of expressions involving C data structures

130 points by AnbeSivam 10y ago

paulasmuth 10y ago
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/ https://eventql.io/
stormbrew 10y ago
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/Documentation/README.md https://github.com/BitFunnel/NativeJIT/blob/master/Documenta...
- AstralStorm 10y ago
  The real question is why would you use it instead of mature LLVM.
  - taspeotis 10y ago
    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.
    - gliptic 10y ago
      LLVM is neither high-throughput nor low-latency. It does probably generate faster code, though.
      - taspeotis 10y ago
        Surely LLVM is high-throughput? Otherwise your dev-test cycle of edit/compile/run would suffer from long compilation/link times.
        jdub 10y ago
        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".
        barrkel 10y ago
        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.
  - stormbrew 10y ago
    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.
    - haberman 10y ago
      > 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.
      - sitkack 10y ago
        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.
    - RossBencina 10y ago
      "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 https://github.com/dibyendumajumdar/ravi [2] http://the-ravi-programming-language.readthedocs.io/en/latest/ravi-benchmarks.html http://the-ravi-programming-language.readthedocs.io/en/lates...
  - paulasmuth 10y ago
    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).
  - jonathanstrange 10y ago
    GNU lightning would be a better choice. However, it does not optimize.
  - cm3 10y ago
    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.
- sctb 10y ago
  Thanks, we updated the title from “NativeJIT – a C++ to x64 JIT used in Bing”.
eDameXxX 10y ago
More information: http://bitfunnel.org http://bitfunnel.org
willvarfar 10y ago
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.. :)
- deleted 10y ago
  [deleted]
- mkup 10y ago
  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.
deleted 10y ago
[deleted]
AnbeSivam 10y ago
Related - http://bitfunnel.org/debugging-nativejit/ http://bitfunnel.org/debugging-nativejit/ https://twitter.com/danluu/status/771622870132809729 https://twitter.com/danluu/status/771622870132809729
deno 10y ago
Better link: http://bitfunnel.org/getting-started-with-nativejit/ http://bitfunnel.org/getting-started-with-nativejit/
zokier 10y ago
So would it make sense to use this as the engine for something akin to jq or xsv?
EgoIncarnate 10y ago
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;
- RossBencina 10y ago
  "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?
- sctb 10y ago
  Thanks, we updated the title from “NativeJIT – a C++ to x64 JIT used in Bing”.
bedatadriven 10y ago
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.html http://www.renjin.org/blog/2015-06-28-renjin-at-rsummit-2015...
SCHiM 10y ago
Looks very similar to https://github.com/asmjit/asmjit https://github.com/asmjit/asmjit
samfisher83 10y ago
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?
- bedatadriven 10y ago
  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.html http://www.renjin.org/blog/2015-06-28-renjin-at-rsummit-2015...

130 points by AnbeSivam 10y ago

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/ https://eventql.io/

stormbrew 10y ago

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/Documentation/README.md https://github.com/BitFunnel/NativeJIT/blob/master/Documenta...

AstralStorm 10y ago
The real question is why would you use it instead of mature LLVM.
- taspeotis 10y ago
  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.
  - gliptic 10y ago
    LLVM is neither high-throughput nor low-latency. It does probably generate faster code, though.
    - taspeotis 10y ago
      Surely LLVM is high-throughput? Otherwise your dev-test cycle of edit/compile/run would suffer from long compilation/link times.
      - jdub 10y ago
        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".
      - barrkel 10y ago
        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.
- stormbrew 10y ago
  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.
  - haberman 10y ago
    > 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.
    - sitkack 10y ago
      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.
  - RossBencina 10y ago
    "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 https://github.com/dibyendumajumdar/ravi [2] http://the-ravi-programming-language.readthedocs.io/en/latest/ravi-benchmarks.html http://the-ravi-programming-language.readthedocs.io/en/lates...
- paulasmuth 10y ago
  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).
- jonathanstrange 10y ago
  GNU lightning would be a better choice. However, it does not optimize.
- cm3 10y ago
  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.
sctb 10y ago
Thanks, we updated the title from “NativeJIT – a C++ to x64 JIT used in Bing”.

eDameXxX 10y ago

More information: http://bitfunnel.org http://bitfunnel.org

willvarfar 10y ago

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.. :)

deleted 10y ago
[deleted]
mkup 10y ago
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.

deleted 10y ago

[deleted]

AnbeSivam 10y ago

Related - http://bitfunnel.org/debugging-nativejit/ http://bitfunnel.org/debugging-nativejit/ https://twitter.com/danluu/status/771622870132809729 https://twitter.com/danluu/status/771622870132809729

deno 10y ago

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

zokier 10y ago

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

EgoIncarnate 10y ago

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;

RossBencina 10y ago
"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?
sctb 10y ago
Thanks, we updated the title from “NativeJIT – a C++ to x64 JIT used in Bing”.

bedatadriven 10y ago

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.html http://www.renjin.org/blog/2015-06-28-renjin-at-rsummit-2015...

SCHiM 10y ago

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

samfisher83 10y ago

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?

bedatadriven 10y ago
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.html http://www.renjin.org/blog/2015-06-28-renjin-at-rsummit-2015...