Weblogs Forum - Post-JIT Compilation (Compiling at the last possible moment)

Articles |
News |
Weblogs |
Books |
Forums

Artima Forums | Articles | Weblogs | Java Answers | News

Sponsored Link •

Weblogs Forum
Post-JIT Compilation (Compiling at the last possible moment)

9 replies on 1 page. Most recent reply: Jul 12, 2006 8:03 PM by Emil Cristian Alexandrescu

Welcome Guest
Sign In

Back to Topic List

Reply to this Topic

Search Forum

Threaded View


Previous Topic		Next Topic

Flat View: This topic has 9 replies on 1 page

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Post-JIT Compilation (Compiling at the last possible moment) (View in Weblogs)

Posted: May 4, 2006 8:27 AM

Summary
Imagine a hypothetical language that compiles to assembly only once all input arrives. It would be ridiculously fast, but somewhat limited since it could only be used as a filter. Is this a worthwhile trade-off?

I am thinking about what happens if you only compile/optimize a program once all input arrives. This kind of language would not let you stop and take in new input in the middle of its execution. It would be very easy to optimize this kind of language, the performance would be astounding.

So let's say you are am writing a C# application, and at one point you load a 100 MB spreadsheet into memory and need to sort according to some field. So let's say you submit it to a program written in this hypothetical language (let's call it 'Big Cat' for fun). What would happen is this program would compile to assembly and then execute, but it would be optimized based on the fact that the input becomes a constant in the program.

My brain is spinning with the possibilities. There must be other languages which do this? I have seen applications do a similar kind of ad-hoc on-the-fly compilation with much success.

James Watson

Posts: 2024
Nickname: watson
Registered: Sep, 2005

Re: Post-JIT Compilation (Compiling at the last possible moment)

Posted: May 4, 2006 10:26 AM

I'm probably not knowledgeable enough in the field to comment but here I go anyway. It seems to me that this would be useful in data mining, bioinformatics and the like where tons of raw data is interpreted and combined to produce useful information.

That would fit the requirement, right?

Howard Lovatt

Posts: 321
Nickname: hlovatt
Registered: Mar, 2003

Re: Post-JIT Compilation (Compiling at the last possible moment)

Posted: May 4, 2006 4:13 PM

This is effectively what the Java Server JVM does (java -server ...). It doesn't do the heavy optimization at first, only after it knows what the inputs are. It is particularly cleaver because it can also back out. So if the input changes it can go back to a less optimized version and then reoptimize on the new input.

jerven bolleman

Posts: 3
Nickname: jerven
Registered: Apr, 2006

Re: Post-JIT Compilation (Compiling at the last possible moment)

Posted: May 5, 2006 5:47 AM

I think this is a difficult problem. But I have trouble seeing the benefit of having this at the core language level.

What sould seem useful to me is the determination of what would be the most effective sorting algorithm for the data. e.g. not optimizing the data but the algorithm (much closer to traditional JIT but selected on heuristics applied on the data to sort)

Data Mining and Bioinformatics are throughput driven and changing your data model into machine code is effective for later actions. As, unlike programmming source code, one can easily determine the optimal representation of the data for the machine. See for an example the internal BLAST db binary formats.

Nor is it likely that in this type of system you will do a lot of the same actions on the same data. e.g each piece of data is operated on in one way each time. This lacks the repetition which would repay the cost of optimization.

The sorting is just one action while the compilation might be quite complex for some data types. And as compilation will take O(n) time at least as each piece of data needs to be analyzed for effecitve work and this the same for the best case of many sorting algorithms. While the worst case is often no worse than O(n log n) when doing a comparison sort.

Tim LS

Posts: 37
Nickname: parchandri
Registered: Jul, 2005

Re: Post-JIT Compilation (Compiling at the last possible moment)

Posted: May 6, 2006 6:48 AM

I think a system which dynamically optimizes/and de-optimizes if needed itself as it runs would be similarly effective, but more flexible - It could guess optimizations having received partial input.

See Dynamo, or one of those funky languages I read about - I think it was Self, which can optimize itself for running, and de-optimize back for debugging.

Dynamo:
http://www.hpl.hp.com/techreports/1999/HPL-1999-77.

nes

Posts: 137
Nickname: nn
Registered: Jul, 2004

Re: Post-JIT Compilation (Compiling at the last possible moment)

Posted: May 8, 2006 8:19 AM

I think that is the philosophy behind Armin Rigos pet project: the psyco compiler for python (http://psyco.sourceforge.net/).

Check out this example where psyco optimized better than the C compiler:
http://groups.google.com/group/comp.lang.python/browse_frm/thread/d5575c9f489b0d0d/

Many times an optimizing compilation on the fly takes longer than running an less optimal but already compiled version though. That is why it is tricky to say if a dynamically or statically optimized compiled version will be faster. As in many other cases, "it depends".

Kannan Goundan

Posts: 18
Nickname: cakoose
Registered: Nov, 2005

Partial Evaluation (aka Specialization)

Posted: May 9, 2006 12:46 AM

Things are more interesting when only part of the input is known. A partial evaluator will accept a function and a constrained domain (D) and return an optimized version of the function that only accepts values in D.

For example, if you have:


multiply :: (int, int) -> int
multiply(x, y) = x * y

You could do:


multiply_2 :: int -> int
multiply_2 = specialize(multiply, x = 2)

A smart partial evaluator would convert the operation into a bit shift.

An impressive use of partial evaluation is to automatically convert an interpreter into a JIT compiler. An interpreter is essentially:


run :: (program, input_handle) -> output
run(program, input_handle)

If the entirety of "program" is known ahead of time, it can be specialized for a given program, yielding:


run_myprog :: input_handle -> output
run_myprog = specialize(run, program = myprog)

"Tempo" is a non-toy partial evaluator for C.

http://phoenix.labri.fr/software/tempo/

Emil Cristian Alexandrescu

Posts: 13
Nickname: mkcoos
Registered: Jul, 2006

Re: Post-JIT Compilation (Compiling at the last possible moment)

Posted: Jul 11, 2006 5:26 AM

Call me FP obssesed, but I think you could develop a LAZY JIT compiler. It would do it's job when all the needed informations are available and IF the code is really needed.

Gregg Wonderly

Posts: 317
Nickname: greggwon
Registered: Apr, 2003

Re: Post-JIT Compilation (Compiling at the last possible moment)

Posted: Jul 12, 2006 4:21 PM

> My brain is spinning with the possibilities. There must be
> other languages which do this? I have seen applications do
> a similar kind of ad-hoc on-the-fly compilation with much
> success.

There are tools which do this by programming FPGAs to create hardware representation of software. Imagine having a rack of 1000's of FPGAs that could be reprogrammed, and the ability to load software into them as hardware implementations.

Emil Cristian Alexandrescu

Posts: 13
Nickname: mkcoos
Registered: Jul, 2006

Re: Post-JIT Compilation (Compiling at the last possible moment)

Posted: Jul 12, 2006 8:03 PM

That sounds sensible to me. Could you post some links on that Hardware representation, please?
I am interrested.

Flat View: This topic has 9 replies on 1 page

Previous Topic

Next Topic