Philip Reames
2014-Aug-12 17:31 UTC
[LLVMdev] Heuristic for choosing between MCJIT and Interpreter
On 08/11/2014 04:21 AM, David Chisnall wrote:> Hi Josh, > > On 9 Aug 2014, at 21:33, Josh Klontz <josh.klontz at gmail.com> wrote: > >> I'm facing a situation where I have generated IR that only needs to be executed once. I've noticed for simple IR it's faster to run the interpreter on it, but for complex IR it's much better to JIT compile and execute it. I'm seeking suggestions for a good heuristic to decide which approach to take for any given IR. I'm leaning in favor of deciding based on the presence/absence of loops. > What are you generating IR from? You may find that an AST interpreter, although slow, will be faster than going to the effort of generating LLVM IR and then interpreting it. LLVM IR is much slower than bytecodes for high-level languages because you have the overhead of interpreting for things that often map to a single machine instruction, whereas high-level bytecodes tend to amortise the interpretation cost by having complex operations. > > I've found having a working AST interpreter to be good for testing an LLVM-based JIT, as you can run the same code with both check that the same actions externally visible happen in the same order.David makes a good set of points here. The only reason not to take the approach he is suggesting is that it does involve writing and maintaining additional code. If you don't really care about the performance of your cold code, using the LLVM interpreter is definite an option. (Keep in mind that there's little active development happening on the interpreter and it may have started to bitrot.) Given your original question, I'm guessing you do care about the performance of your cold code. Given that, David has suggested the best approach.> > You can probably find some heuristics at the AST layer that will work well. For example, does it contain any loops with more than N iterations (where N is a number you determine experimentally)? Does it operate on data over a certain size? > > David > > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Josh Klontz
2014-Aug-12 20:02 UTC
[LLVMdev] Heuristic for choosing between MCJIT and Interpreter
Thanks to everyone for the helpful feedback. I was able to incorporate the interpreter and loop heuristic with very little additional code, so I'm not immediately concerned about the extra maintenance introduced. An AST interpreter does sound sensible in the long run, but is more effort than I can justify spending at the moment. If the IR interpreter does bitrot (a shame) the MCJIT alone is probably still fast enough for my use. v/r, Josh On Tue, Aug 12, 2014 at 1:31 PM, Philip Reames <listmail at philipreames.com> wrote:> > On 08/11/2014 04:21 AM, David Chisnall wrote: > >> Hi Josh, >> >> On 9 Aug 2014, at 21:33, Josh Klontz <josh.klontz at gmail.com> wrote: >> >> I'm facing a situation where I have generated IR that only needs to be >>> executed once. I've noticed for simple IR it's faster to run the >>> interpreter on it, but for complex IR it's much better to JIT compile and >>> execute it. I'm seeking suggestions for a good heuristic to decide which >>> approach to take for any given IR. I'm leaning in favor of deciding based >>> on the presence/absence of loops. >>> >> What are you generating IR from? You may find that an AST interpreter, >> although slow, will be faster than going to the effort of generating LLVM >> IR and then interpreting it. LLVM IR is much slower than bytecodes for >> high-level languages because you have the overhead of interpreting for >> things that often map to a single machine instruction, whereas high-level >> bytecodes tend to amortise the interpretation cost by having complex >> operations. >> >> I've found having a working AST interpreter to be good for testing an >> LLVM-based JIT, as you can run the same code with both check that the same >> actions externally visible happen in the same order. >> > David makes a good set of points here. The only reason not to take the > approach he is suggesting is that it does involve writing and maintaining > additional code. If you don't really care about the performance of your > cold code, using the LLVM interpreter is definite an option. (Keep in mind > that there's little active development happening on the interpreter and it > may have started to bitrot.) > > Given your original question, I'm guessing you do care about the > performance of your cold code. Given that, David has suggested the best > approach. > >> >> You can probably find some heuristics at the AST layer that will work >> well. For example, does it contain any loops with more than N iterations >> (where N is a number you determine experimentally)? Does it operate on >> data over a certain size? >> >> David >> >> >> _______________________________________________ >> LLVM Developers mailing list >> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu >> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >> > >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20140812/eee561df/attachment.html>
David Chisnall
2014-Aug-13 10:15 UTC
[LLVMdev] Heuristic for choosing between MCJIT and Interpreter
On 12 Aug 2014, at 21:02, Josh Klontz <josh.klontz at gmail.com> wrote:> Thanks to everyone for the helpful feedback. I was able to incorporate the interpreter and loop heuristic with very little additional code, so I'm not immediately concerned about the extra maintenance introduced. An AST interpreter does sound sensible in the long run, but is more effort than I can justify spending at the moment. If the IR interpreter does bitrot (a shame) the MCJIT alone is probably still fast enough for my use.Longer term, you might want to look at the Alphabet Soup project from Oracle Labs. They apply type feedback to an AST interpreter and get very good performance out of it (>20% of compiled code - they did have JavaScript running faster than V8 for a while, but V8 is now quite a bit faster). The ASTs that they produce as a result of the type feedback are then ideal sources for feeding into your LLVM back end. Of course, this is without knowing anything about your source language. If it has a strict static type system, then this approach will not be relevant. David