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.
They built this to translate a search query that is only known at runtime. Presumably they already have an AST or similar, so calling methods as it is being walked isn't any harder than operators.
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.
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.
> 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.
First, nope, if it's not multiplication it should not be using the * operator, period. Operator overloading is already overused and it leads to so much problematic code that looks fine to the untrained eye (string concat using operator+ being a famous example).
That said, you may also want to pass more options to the Mul node in the future and operator*() can only accept two arguments.
As another example, run the following Python code to see how python represents its own AST:
So basically you're saying that if I want to add mathematical expressions to my JIT'ed code I should obfuscate the purpose by writing multi-line operations to build them instead of having the ability to plonk it in more or less verbatim?
As I said, I fully agree that operator overloading is horribly overused but the purpose of this JIT is to quickly create JIT code with customized expressions then those expressions should be possible to write fairly verbatim instead of following something with a religious zeal (is even matrix multiplication allowed to overload?).
And yes, AST's usually contain a lot more information such as source-location,etc for debugging (here it'd be interesting if an operator overload is able to take C++20 source_location as default parameters), but again this is for a specialized jit.
As for passing more options to mul nodes, a mul node is just that and nothing more (only extra interesting data in a restricted scenario as this would possibly be source_location as noted above).
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.
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.
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.
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.
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.
In particular, this talk might be interesting:
"Unlocking the Power of C++ as a Service:
Uniting Python's Usability with C++'s Performance"
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)
this looks convenient to use from c++, but the example code it generates is rather suboptimal (see 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?
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.
Having written small compilers or other code-generators targeting both the JVM and .NET runtimes, i can say that the .NET equivalents have some extra simple options for scenarios like this.
Both have always supported building libraries/assemblies and loading them (the ASM library+custom classloaders for Java and AssemblyBuilder in .NET are about equally capable).
However .NET also has DynamicMethod that is specifically built to quickly build just small functions that aren't tied to larger contexts (similar API to asm/assemblybuilder).
But an even easier option for stuff exactly like in the article that people don't widely really seem to know about is that Linq (yes that "sql-like" stuff) actually contains parts for deferred method building that can be easily leveraged to quickly produce customized native code methods.
The neat part about the Linq-code generator is that you can just drop in plain C# code-blocks to be translataed by the C# compiler into Linq snippets and then with some helpers transform everything to Linq-tree's that can then be compiled.
The benefit over Asm/AssemblyBuilder/DynamicMethod is that Linq nodes are basically an built-in AST that can be directly leveraged whereas the other API's requires some mapping of your own AST's to the respective stack-machines.
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.
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.
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.
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?
> Are you saying that Java doesn't do what the article describes?
That's right, Java doesn't do what the NativeJIT library does: Hotspot starts in an interpreted mode and only later JIT-compiles frequently executed code; NativeJIT, in contrast, immediately compiles the generated code, at least according to this description:
Bing formulates a custom expression for each query and then uses NativeJIT to compile the expression into x64 code that will be run on a large set of candidate documents spread across a cluster of machines.
I don't know the specifics, but my guess is that by the time Hotspot would even start compiling, the user has already received the results for their query. Ergo, Java – at least with the Hotspot VM – wouldn't be suitable for this task.
Well if you insist, this is what makes me think that there is a gradual process of compiling and running native jitted code as the project runs. Hence, runtime.
> The scoring process attempts to gauge how well each document matches the user's intent, and as such, depends on the specifics of how each query was phrased. Bing formulates a custom expression for each query and then uses NativeJIT to compile the expression into x64 code that will be run on a large set of candidate documents spread across a cluster of machines.
If this is "wrong" to you, then I would like to remain wrong. In fact I would like to have my mental faculties as acutely orthogonally aligned as possible compared to yours in every possible dimension.
The difference between Hotspot on one hand and Bing's use of NativeJIT on the other is that after code generation (the "formulates a custom expression" part), the code is immediately JIT-compiled to machine code, while Hotspot would first interpret the generated code for a while and collect execution metrics before it JIT-compiles the code. This delay between code generation and compilation to machine code would be unacceptable for Bing's use case, hence why Java+Hotspot aren't suitable for this task. Hope this clears it up.
> the code is immediately JIT-compiled to machine code
As I said multiple times, we disagree on this point. There is a scoring process during runtime which mirrors what hotspot does in the non-literal sense. And again, I'm ok with being "wrong" so off you go.
The "scoring process" is the generated code, which scores a page's relevance to the user's query. It has absolutely nothing to do with gathering runtime metrics about the generated code, nor with optimizing the performance of the compiled machine code, which is what Hotspot does.
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
Several possible reasons:
- parallelism
- concurrent machine code gen
- different optimisations for different runs, producing differing machine code order, etc
(2018)
Bing uses internally a better version, but improvements are not merged back to github. See https://github.com/BitFunnel/NativeJIT/issues/84#issuecommen...
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.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/...
> auto & rsquared = expression.Mul(expression.GetP1(), expression.GetP1());
This is C++, no? Why not use operator overloading for the project?
I think they didn't find it useful.
They built this to translate a search query that is only known at runtime. Presumably they already have an AST or similar, so calling methods as it is being walked isn't any harder than operators.
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.
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.
> 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.
First, nope, if it's not multiplication it should not be using the * operator, period. Operator overloading is already overused and it leads to so much problematic code that looks fine to the untrained eye (string concat using operator+ being a famous example).
That said, you may also want to pass more options to the Mul node in the future and operator*() can only accept two arguments.
As another example, run the following Python code to see how python represents its own AST:
So basically you're saying that if I want to add mathematical expressions to my JIT'ed code I should obfuscate the purpose by writing multi-line operations to build them instead of having the ability to plonk it in more or less verbatim?
As I said, I fully agree that operator overloading is horribly overused but the purpose of this JIT is to quickly create JIT code with customized expressions then those expressions should be possible to write fairly verbatim instead of following something with a religious zeal (is even matrix multiplication allowed to overload?).
And yes, AST's usually contain a lot more information such as source-location,etc for debugging (here it'd be interesting if an operator overload is able to take C++20 source_location as default parameters), but again this is for a specialized jit.
As for passing more options to mul nodes, a mul node is just that and nothing more (only extra interesting data in a restricted scenario as this would possibly be source_location as noted above).
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.
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.
Yes, exactly. See Eigen as an example.
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.
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.
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.
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 Slides: https://llvm.org/devmtg/2023-10/slides/techtalks/Vassilev-Un...
it's mostly upstream now, no need to dig around in their repos
https://github.com/llvm/llvm-project/tree/main/clang/tools/c...
There's also libgccjit, https://gcc.gnu.org/wiki/JIT, though all of the third party language bindings appear to be stale for it.
Interesting, I didn't know about that one! Does it ship with GCC?
Yes, has done for a while
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?
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)
> "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-deopti...
It's really not that impossible.
Looks similar to https://github.com/kobalicek/mathpresso
this looks convenient to use from c++, but the example code it generates is rather suboptimal (see 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?
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.
I guess for the first function call not, but subsequent calls yes. They claim that register optimizations are properly done.
It really sounds like a job for Java (Microsoft, I know, I know.)
Having written small compilers or other code-generators targeting both the JVM and .NET runtimes, i can say that the .NET equivalents have some extra simple options for scenarios like this.
Both have always supported building libraries/assemblies and loading them (the ASM library+custom classloaders for Java and AssemblyBuilder in .NET are about equally capable).
However .NET also has DynamicMethod that is specifically built to quickly build just small functions that aren't tied to larger contexts (similar API to asm/assemblybuilder).
But an even easier option for stuff exactly like in the article that people don't widely really seem to know about is that Linq (yes that "sql-like" stuff) actually contains parts for deferred method building that can be easily leveraged to quickly produce customized native code methods.
The neat part about the Linq-code generator is that you can just drop in plain C# code-blocks to be translataed by the C# compiler into Linq snippets and then with some helpers transform everything to Linq-tree's that can then be compiled.
The benefit over Asm/AssemblyBuilder/DynamicMethod is that Linq nodes are basically an built-in AST that can be directly leveraged whereas the other API's requires some mapping of your own AST's to the respective stack-machines.
https://asm.ow2.io/
https://learn.microsoft.com/en-us/dotnet/api/system.reflecti...
https://learn.microsoft.com/en-us/dotnet/api/system.reflecti...
https://learn.microsoft.com/en-us/dotnet/api/system.linq.exp...
Usual remark regarding the age of bytecode systems and JIT (aka dynamic compilation), predating Java.
> It really sounds like a job for Java
Why?
Because the JVM's JIT does already specialise based on runtime values.
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.
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.
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.
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?
> Are you saying that Java doesn't do what the article describes?
That's right, Java doesn't do what the NativeJIT library does: Hotspot starts in an interpreted mode and only later JIT-compiles frequently executed code; NativeJIT, in contrast, immediately compiles the generated code, at least according to this description:
Bing formulates a custom expression for each query and then uses NativeJIT to compile the expression into x64 code that will be run on a large set of candidate documents spread across a cluster of machines.
I don't know the specifics, but my guess is that by the time Hotspot would even start compiling, the user has already received the results for their query. Ergo, Java – at least with the Hotspot VM – wouldn't be suitable for this task.
Ah ok pedantism that's fine thanks.
That's not "pedantism". Java+Hotspot are literally unfit for the task at hand.
They specifically mentioned compiling at runtime in the article. I cannot be convinced otherwise. Sorry.
I started typing a reply to explain that "compiling at runtime" does not mean "having a warm-up phase before JIT-compilation", but this:
> I cannot be convinced otherwise.
made me think "why bother?". If you insist on being wrong, go on being wrong.
Well if you insist, this is what makes me think that there is a gradual process of compiling and running native jitted code as the project runs. Hence, runtime.
> The scoring process attempts to gauge how well each document matches the user's intent, and as such, depends on the specifics of how each query was phrased. Bing formulates a custom expression for each query and then uses NativeJIT to compile the expression into x64 code that will be run on a large set of candidate documents spread across a cluster of machines.
If this is "wrong" to you, then I would like to remain wrong. In fact I would like to have my mental faculties as acutely orthogonally aligned as possible compared to yours in every possible dimension.
The difference between Hotspot on one hand and Bing's use of NativeJIT on the other is that after code generation (the "formulates a custom expression" part), the code is immediately JIT-compiled to machine code, while Hotspot would first interpret the generated code for a while and collect execution metrics before it JIT-compiles the code. This delay between code generation and compilation to machine code would be unacceptable for Bing's use case, hence why Java+Hotspot aren't suitable for this task. Hope this clears it up.
> the code is immediately JIT-compiled to machine code
As I said multiple times, we disagree on this point. There is a scoring process during runtime which mirrors what hotspot does in the non-literal sense. And again, I'm ok with being "wrong" so off you go.
The "scoring process" is the generated code, which scores a page's relevance to the user's query. It has absolutely nothing to do with gathering runtime metrics about the generated code, nor with optimizing the performance of the compiled machine code, which is what Hotspot does.
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
Why wouldn't it be deterministic?
Several possible reasons: - parallelism - concurrent machine code gen - different optimisations for different runs, producing differing machine code order, etc