Friday, February 29, 2008

Why JIT? How to JIT?

I started using Matlab circa version 4 and I still cringe every time I have to write a loop in Matlab. The main reason is that I got conditioned (like the generations of matlab users) that loops are really slow because they have to be interpreted. Matrix or index operations on the other hand turn into internal function calls and are fast. The old view - almost always using clever indexing one can avoid loops. However, this is 21st century and we have better ways...

The goal for using JIT (just-in-time compilation) is to speed up interpreted code by compiling it in run time. This is very tricky for dynamic languages such as Matlab (also Python, Perl, etc. ). The main reason is that the variable types are determined at runtime. For example:

for j=1:10
if j > 5
a = int8(j);
else
a = float(j);
end
end

What's the type of a? Compiler has to know the variable size and type to emit correct code. One can imagine using an object to represent variables (the object would carry a type and pointer to memory where data is stored) and assignement operator which would assign both value and type. However, such implementation results in code that is not much faster than interpreted code.

However, code like the snippet above is rare. In most cases variables have well defined type at runtime. For such a code we can generate very fast machine code.

Here's the current approach that FreeMat takes is:
  • Compile code that would most benefit from speedup (loops, functions)
  • If code cannot be compiled fall back to using the interpreter (slow, but at least you always get an answer).
  • Check for variable type changes between running JIT compiled code.
  • JIT compiled code works on the same data structures as the interpreter.
Samit and I looked at three jit compilers: Java JIT, Mono JIT, and LLVM. Java JIT seemed better suited for Java language. Mono JIT isn't mature.

LLVM was our choice. It is not perfect - the library is really huge and quite hard to compile and use. However, you can generate and optimize code on the fly and get near optimal performance (the only thing you can't do with JIT code is interprocedural optimizations).

We plan to have functional JIT compiler in Freemat 4.

2 comments:

rittika said...

I really need your help. I am working on a project, where I have to analyze the null space of very large matrices. I have been using FreeMat to write all my code since the last month.Now I am almost done with all the required code and I just realized that FreeMat doesn't have a function to find the null space. What can I do? Do you have the source code for null space?Thank you very muh!

ayana said...

I'ld like to know can functions that is created in freemat can be interfaced with java applications? Thanks in advance.