Hi,
it is pretty easy to generate Java source code, compile it at
runtime and instantiate and run the generated code, see e.g. here:
http://stackoverflow.com/questions/2946338/how-do-i-programmatically-compile-and-instantiate-a-java-class
I think this could allow us to implement a JIT-compiler for the
match finder. The idea is that for simple rules that are applied
very often, the interpreter could generate match finder code
specifically for this rule and use it instead of the generic match
finder. I think we can really gain performance here. Particularly
for simple nested rules, the current match finder is not ideal,
because for every nesting level, the match finding process basically
starts all over again. For a simple rule that just matches one node
and all nodes that it has links to, a compiled match finder should
be much faster and the generated code should be fairly simple.
The first steps to implement this could be as follows:
1) We need something like a JITCompiler class which takes a rule,
analyzes it and if possible generates match finder code and
instantiates the generated class. The generated class should
probably implement Iterable<Match> and have a method
setEGraph(Egraph).
2) This JITCompiler can then be used in the current EngineImpl
class. When the rule info is initially generated, the engine could
start a separate thread that tries to generate the match finder
code. If the generation was successful the generated match finder is
stored in the engine and can be used later.
For the start, I would try the following simple case: generate match
finder code only for rules where the LHS consists of a single node
with no further application condition. If we get this to work, we
can stepwise incorporate more complex patterns. In the beginning, we
can also run the JITCompiler in the same thread as the engine. The
first goal is to see if we can make it work.
Is anyone interested in starting to implement this? I think for an
initial version that we can experiment with we really need very
little amount of code. I am happy to assist or to implement part of
it.
Cheers,
Christian
|