6 ms·

NativeJIT: A C++ expression –> x64 JIT (2018)

75 points by nateb2022 1y ago

anon-3988 1y ago
Interesting, this is very similar to llvmlite.Builder which is a wrapper over llvm. I am probably going to create something similar for my Python -> C -> assembly JIT.
- Twirrim 1y ago
  There's also libgccjit, https://gcc.gnu.org/wiki/JIT https://gcc.gnu.org/wiki/JIT, though all of the third party language bindings appear to be stale for it.
  - cout 1y ago
    Interesting, I didn't know about that one! Does it ship with GCC?
    - Twirrim 1y ago
      Yes, has done for a while
- globalnode 1y ago
  that project sounds interesting as well, but what do you do with libraries in python.. have the generated C code translate back to python calls?
  - anon-3988 1y ago
    The point is not to compile entire Python programs, the point is to optimize specific parts of Python that matters. To illustrate, consider a calculating sum of 1 to N in python def sum(N): x = 0 for i in range(N): x += i return x There's absolute zero reason why this code has to involve pushing and popping stuff on the python virtual stack. This should be compiled into assembly with a small conversion between C/PyObject. The goal is to get to a point where we can even do non-trivial things inside this optimized context. Python will never be able to go down to assembly because Python support doing "weird shit" like dynamically creating modules, hell, even creating a Python file, running eval on that, and loading it as a new module. How are you even going to transpile that to assembly? So I approach the problem the same way numba is approaching. But hopefully more modern and simpler (implementation wise). Planning on doing it using Rust and the backend should be agnostic (GCC, Clang, whatever C compiler there is)
    - hayley-patton 1y ago
      > "weird shit" like dynamically creating modules, hell, even creating a Python file, running eval on that, and loading it as a new module. Expect that you don't, and deoptimise when you do: https://bibliography.selflanguage.org/_static/dynamic-deoptimization.pdf https://bibliography.selflanguage.org/_static/dynamic-deopti... It's really not that impossible.
- lhames 1y ago
  The LLVM ORC and Clang-REPL projects would be worth checking out if you haven't already: there's a healthy community of high performance computing folks working in this space over at https://compiler-research.org https://compiler-research.org. In particular, this talk might be interesting: "Unlocking the Power of C++ as a Service: Uniting Python's Usability with C++'s Performance" Video: https://www.youtube.com/watch?v=rdfBnGjyFrc https://www.youtube.com/watch?v=rdfBnGjyFrc Slides: https://llvm.org/devmtg/2023-10/slides/techtalks/Vassilev-UnlockingThePowerofCppAsAService.pdf https://llvm.org/devmtg/2023-10/slides/techtalks/Vassilev-Un...
  - almostgotcaught 1y ago
    it's mostly upstream now, no need to dig around in their repos https://github.com/llvm/llvm-project/tree/main/clang/tools/clang-repl https://github.com/llvm/llvm-project/tree/main/clang/tools/c...
b0a04gl 1y ago
how deterministic is the emit really. if i feed same expression tree twice,same node layout same captures. do i get exact same bytes out every time (ignoring reloc) or not. if output produced is byte stable across runs for same input graph ,that opens up memoized JIT paths.worth checking if current impl already does this or needs a pass to normalise alloc order
- jdnend 1y ago
  Why wouldn't it be deterministic?
  - xnacly 1y ago
    Several possible reasons: - parallelism - concurrent machine code gen - different optimisations for different runs, producing differing machine code order, etc
nurettin 1y ago
It really sounds like a job for Java (Microsoft, I know, I know.)
- adwn 1y ago
  > It really sounds like a job for Java Why?
  - dontlaugh 1y ago
    Because the JVM's JIT does already specialise based on runtime values.
  - nurettin 1y ago
    Hotspot (TM) JIT compiles java code to machine code when it detects hot code paths, speeding up execution during runtime, exactly the use case described in the article.
    - adwn 1y ago
      Doesn't Hotspot have notoriously long warm-up times? Have those been exaggerated, or have they recently improved? If you know beforehand that you'll execute some piece of code many times, the most efficient approach is to JIT-compile it right away, and not only after a lot of time has passed.
      - eddythompson80 1y ago
        They have not been exaggerated and they have not improved (well, nothing outside standard, keeping up with inflation, type improvement) The JVM ecosystem has given up on jit warm up time for hotspot. There are other solutions like graal. Whenever I have to deal with Java projects I'm always astonished at how completely "normal" a 4 minute startup time for a REST endpoint project on a single core machine.
      - nurettin 1y ago
        I don't know the latest metrics, I remember java servers being slow at first, then gradually picking up momentum. Are you saying that Java doesn't do what the article describes?
kookamamie 1y ago
> auto & rsquared = expression.Mul(expression.GetP1(), expression.GetP1()); This is C++, no? Why not use operator overloading for the project?
- plq 1y ago
  This line is part of the code that creates an AST-like structure that is then fed into the compiler. The actual multiplication is done by calling the function handle returned from the Compile method.
  - OskarS 1y ago
    Yes, but what I suspect the commenter was saying is that you can build the expression usung operator overloading as well, so you can type ”a + b”, not ”a.Add(b)”. I love it when libraries like this do that. z3 in python is similar, you just build your constraints using normal syntax and it all just works. Great use of operator overloading.
    - kookamamie 1y ago
      Yes, exactly. See Eigen as an example.
    - BearOso 1y ago
      Except that's not what's happening. expression.Mul isnt multiplying itself against something, it's adding a Mul instruction to its list. Maybe it would have been more obvious if the method name was insertMul instead.
  - whizzter 1y ago
    I think what GP was referring to that there is nothing stopping the code from being designed so that: AST<float> p1 = exp.GetP1(); AST<float> rsqr = p1 * p1; // AST<float> implements an operator* overload that produces an AST<float> object Even if many frown upon operator overloading due to the annoying magical-ness of the standard-librarys appropriation of the shift operators for "piping" (<< and >>), it's still what makes many people prefer C++ for vector-math,etc tasks. So whilst the result isn't a direct multiplication it should still be an acceptable use since the resulting code will actually be doing multiplications. Considering what goes on under the hood however, I guess there might be some compiler optimization reasons to keep everything in the expression object in the example as the holder of data instead of spread out in an allocation tree with lots of pointer-chasing.
izabera 1y ago
this looks convenient to use from c++, but the example code it generates is rather suboptimal (see https://godbolt.org/z/3rWceeYoW https://godbolt.org/z/3rWceeYoW in which no normal compiler would set up and tear down a stack frame for that) so i'm guessing there isn't any support for optimisations? what's the advantage of this over just compiling + calling dlopen/LoadLibrary on the result?
- rurban 1y ago
  I guess for the first function call not, but subsequent calls yes. They claim that register optimizations are properly done.
- whizzter 1y ago
  For simple functions an C compiler will generate code that is perhaps 50% faster than this standard prologue/epilogue (modern CPU's eat up most of the "bloat" whereas the branch to _any_ function will cause some branch predictor pressure), as soon as the function grows the gains will be smaller as long as the code runs somewhat in a straight line and isn't subject to cache misses. Compared to even an optimized interpreter this will be somewhere between 4x to 20x faster (mainly due to having far far smaller branch predictor costs), so even if it doesn't generate optimal code it will still be within an magnitude of optimal native code whereas an interpreter will be much further behind. dlopen/LoadLibrary,etc comes with far more memory pressure and OS bookkeeping.
rurban 1y ago
(2018) Bing uses internally a better version, but improvements are not merged back to github. See https://github.com/BitFunnel/NativeJIT/issues/84#issuecomment-1054669228 https://github.com/BitFunnel/NativeJIT/issues/84#issuecommen...
smartaz42 1y ago
FWIW for C only I've used libtcc repo.or.cz/w/tinycc.git with great success. The API is a joy, as we all expect from a Bellard project. It focuses on compilation speed, the generated code is not at all optimized.
deleted 1y ago
[deleted]
emmanueloga_ 1y ago
Looks similar to https://github.com/kobalicek/mathpresso https://github.com/kobalicek/mathpresso
cout 1y ago
It's interesting to see C++ expressions being used to create what is I think an AST that then gets compiled. I would love to see some syntactic sugar, though. For example, `expression.Mul(rsquared, expression.Immediate(PI))` could be `rsquared * expression.Immediate(PI)`. With overloading, anything that is not a recognized type could be converted to an immediate, so it could simply be `rsquared * PI`. Simple control structures could be even implemented with lambdas. I did this for ruby-libjit, and it made writing a JIT compiler much easier to read. Here's an example: https://github.com/cout/ruby-libjit/blob/master/sample/fib.rb https://github.com/cout/ruby-libjit/blob/master/sample/fib.r... And a real-world example (one of the very earliest JIT compilers for ruby, written in ruby, dates back to the ruby 1.8.x days): https://github.com/cout/ludicrous/blob/master/lib/ludicrous/yarv_instructions.rb https://github.com/cout/ludicrous/blob/master/lib/ludicrous/...

75 points by nateb2022 1y ago

Interesting, this is very similar to llvmlite.Builder which is a wrapper over llvm. I am probably going to create something similar for my Python -> C -> assembly JIT.

Twirrim 1y ago
There's also libgccjit, https://gcc.gnu.org/wiki/JIT https://gcc.gnu.org/wiki/JIT, though all of the third party language bindings appear to be stale for it.
- cout 1y ago
  Interesting, I didn't know about that one! Does it ship with GCC?
  - Twirrim 1y ago
    Yes, has done for a while
globalnode 1y ago
that project sounds interesting as well, but what do you do with libraries in python.. have the generated C code translate back to python calls?
- anon-3988 1y ago
  The point is not to compile entire Python programs, the point is to optimize specific parts of Python that matters. To illustrate, consider a calculating sum of 1 to N in python def sum(N): x = 0 for i in range(N): x += i return x There's absolute zero reason why this code has to involve pushing and popping stuff on the python virtual stack. This should be compiled into assembly with a small conversion between C/PyObject. The goal is to get to a point where we can even do non-trivial things inside this optimized context. Python will never be able to go down to assembly because Python support doing "weird shit" like dynamically creating modules, hell, even creating a Python file, running eval on that, and loading it as a new module. How are you even going to transpile that to assembly? So I approach the problem the same way numba is approaching. But hopefully more modern and simpler (implementation wise). Planning on doing it using Rust and the backend should be agnostic (GCC, Clang, whatever C compiler there is)
  - hayley-patton 1y ago
    > "weird shit" like dynamically creating modules, hell, even creating a Python file, running eval on that, and loading it as a new module. Expect that you don't, and deoptimise when you do: https://bibliography.selflanguage.org/_static/dynamic-deoptimization.pdf https://bibliography.selflanguage.org/_static/dynamic-deopti... It's really not that impossible.
lhames 1y ago
The LLVM ORC and Clang-REPL projects would be worth checking out if you haven't already: there's a healthy community of high performance computing folks working in this space over at https://compiler-research.org https://compiler-research.org. In particular, this talk might be interesting: "Unlocking the Power of C++ as a Service: Uniting Python's Usability with C++'s Performance" Video: https://www.youtube.com/watch?v=rdfBnGjyFrc https://www.youtube.com/watch?v=rdfBnGjyFrc Slides: https://llvm.org/devmtg/2023-10/slides/techtalks/Vassilev-UnlockingThePowerofCppAsAService.pdf https://llvm.org/devmtg/2023-10/slides/techtalks/Vassilev-Un...
- almostgotcaught 1y ago
  it's mostly upstream now, no need to dig around in their repos https://github.com/llvm/llvm-project/tree/main/clang/tools/clang-repl https://github.com/llvm/llvm-project/tree/main/clang/tools/c...

b0a04gl 1y ago

how deterministic is the emit really. if i feed same expression tree twice,same node layout same captures. do i get exact same bytes out every time (ignoring reloc) or not. if output produced is byte stable across runs for same input graph ,that opens up memoized JIT paths.worth checking if current impl already does this or needs a pass to normalise alloc order

jdnend 1y ago
Why wouldn't it be deterministic?
- xnacly 1y ago
  Several possible reasons: - parallelism - concurrent machine code gen - different optimisations for different runs, producing differing machine code order, etc

nurettin 1y ago

It really sounds like a job for Java (Microsoft, I know, I know.)

adwn 1y ago
> It really sounds like a job for Java Why?
- dontlaugh 1y ago
  Because the JVM's JIT does already specialise based on runtime values.
- nurettin 1y ago
  Hotspot (TM) JIT compiles java code to machine code when it detects hot code paths, speeding up execution during runtime, exactly the use case described in the article.
  - adwn 1y ago
    Doesn't Hotspot have notoriously long warm-up times? Have those been exaggerated, or have they recently improved? If you know beforehand that you'll execute some piece of code many times, the most efficient approach is to JIT-compile it right away, and not only after a lot of time has passed.
    - eddythompson80 1y ago
      They have not been exaggerated and they have not improved (well, nothing outside standard, keeping up with inflation, type improvement) The JVM ecosystem has given up on jit warm up time for hotspot. There are other solutions like graal. Whenever I have to deal with Java projects I'm always astonished at how completely "normal" a 4 minute startup time for a REST endpoint project on a single core machine.
    - nurettin 1y ago
      I don't know the latest metrics, I remember java servers being slow at first, then gradually picking up momentum. Are you saying that Java doesn't do what the article describes?

kookamamie 1y ago

> auto & rsquared = expression.Mul(expression.GetP1(), expression.GetP1()); This is C++, no? Why not use operator overloading for the project?

plq 1y ago
This line is part of the code that creates an AST-like structure that is then fed into the compiler. The actual multiplication is done by calling the function handle returned from the Compile method.
- OskarS 1y ago
  Yes, but what I suspect the commenter was saying is that you can build the expression usung operator overloading as well, so you can type ”a + b”, not ”a.Add(b)”. I love it when libraries like this do that. z3 in python is similar, you just build your constraints using normal syntax and it all just works. Great use of operator overloading.
  - kookamamie 1y ago
    Yes, exactly. See Eigen as an example.
  - BearOso 1y ago
    Except that's not what's happening. expression.Mul isnt multiplying itself against something, it's adding a Mul instruction to its list. Maybe it would have been more obvious if the method name was insertMul instead.
- whizzter 1y ago
  I think what GP was referring to that there is nothing stopping the code from being designed so that: AST<float> p1 = exp.GetP1(); AST<float> rsqr = p1 * p1; // AST<float> implements an operator* overload that produces an AST<float> object Even if many frown upon operator overloading due to the annoying magical-ness of the standard-librarys appropriation of the shift operators for "piping" (<< and >>), it's still what makes many people prefer C++ for vector-math,etc tasks. So whilst the result isn't a direct multiplication it should still be an acceptable use since the resulting code will actually be doing multiplications. Considering what goes on under the hood however, I guess there might be some compiler optimization reasons to keep everything in the expression object in the example as the holder of data instead of spread out in an allocation tree with lots of pointer-chasing.

izabera 1y ago

this looks convenient to use from c++, but the example code it generates is rather suboptimal (see https://godbolt.org/z/3rWceeYoW https://godbolt.org/z/3rWceeYoW in which no normal compiler would set up and tear down a stack frame for that) so i'm guessing there isn't any support for optimisations? what's the advantage of this over just compiling + calling dlopen/LoadLibrary on the result?

rurban 1y ago
I guess for the first function call not, but subsequent calls yes. They claim that register optimizations are properly done.
whizzter 1y ago
For simple functions an C compiler will generate code that is perhaps 50% faster than this standard prologue/epilogue (modern CPU's eat up most of the "bloat" whereas the branch to _any_ function will cause some branch predictor pressure), as soon as the function grows the gains will be smaller as long as the code runs somewhat in a straight line and isn't subject to cache misses. Compared to even an optimized interpreter this will be somewhere between 4x to 20x faster (mainly due to having far far smaller branch predictor costs), so even if it doesn't generate optimal code it will still be within an magnitude of optimal native code whereas an interpreter will be much further behind. dlopen/LoadLibrary,etc comes with far more memory pressure and OS bookkeeping.

rurban 1y ago

(2018) Bing uses internally a better version, but improvements are not merged back to github. See https://github.com/BitFunnel/NativeJIT/issues/84#issuecomment-1054669228 https://github.com/BitFunnel/NativeJIT/issues/84#issuecommen...

smartaz42 1y ago

FWIW for C only I've used libtcc repo.or.cz/w/tinycc.git with great success. The API is a joy, as we all expect from a Bellard project. It focuses on compilation speed, the generated code is not at all optimized.

deleted 1y ago

[deleted]

emmanueloga_ 1y ago

Looks similar to https://github.com/kobalicek/mathpresso https://github.com/kobalicek/mathpresso

cout 1y ago

It's interesting to see C++ expressions being used to create what is I think an AST that then gets compiled. I would love to see some syntactic sugar, though. For example, `expression.Mul(rsquared, expression.Immediate(PI))` could be `rsquared * expression.Immediate(PI)`. With overloading, anything that is not a recognized type could be converted to an immediate, so it could simply be `rsquared * PI`. Simple control structures could be even implemented with lambdas. I did this for ruby-libjit, and it made writing a JIT compiler much easier to read. Here's an example: https://github.com/cout/ruby-libjit/blob/master/sample/fib.rb https://github.com/cout/ruby-libjit/blob/master/sample/fib.r... And a real-world example (one of the very earliest JIT compilers for ruby, written in ruby, dates back to the ruby 1.8.x days): https://github.com/cout/ludicrous/blob/master/lib/ludicrous/yarv_instructions.rb https://github.com/cout/ludicrous/blob/master/lib/ludicrous/...