Re: [DotGNU]Melody and "code morphing" performance

[Rhys Weatherley]

Remy Saville wrote:

> A while ago I read an article on HP's Dynamo, which sounds a lot like what
> transmeta's code morphing software does.

Actually to get the order correct, transmeta sounds a lot like
what Dynamo does.  I believe Dynamo was out first.  It was
a software solution, running on top of an ordinary OS and CPU.

Transmeta pushed the dynamic recompiler down into the
hardware.  It also uses two instructions sets, compared to
Dynamo's one.  Crusoe is based on a VLIW CPU core that
runs a program to dynamically interpret and optimize x86.

> URL for Dynamo info:
> http://www.arstechnica.com/reviews/1q00/dynamo/dynamo-1.html
>
> Dynamo is "an interpreter for HP's PA-8000 instruction set that itself runs
> on a PA-8000 processor" and "Programs "interpreted" by Dynamo are often
> faster than if they were run natively. Sometimes by 20% or more."

It's not just an interpreter.  It's an interpreter plus a dynamic
optimizer.  The interpreter chomps through the code until a
trigger fires off (e.g. loop detected).  It then hands the code to
a dynamic optimizer that rearranges the PA-8000 code by
inlining jumps, function calls, applying common optimizations,
etc.  The result is then run as normal PA-8000 code with
no interpretation.  When the optimized code terminates,
it traps back to the interpreter and the process repeats.

The speed comes from undoing the programmer, basically.
When we program, we structure things nicely to help
ourselves understand our own code.  But that usually
involves additional data structure and function call
overheads.  Static compilers try to use global analysis
to undo this a bit.  But without knowledge of how the
program performs at runtime, static analysis is limited.
Dynamo was the first to show that analysis can be done
at runtime and a faster program results.

The interesting thing about Dynamo, that the researchers
discovered, is that "interpreter plus optimizer" can be faster
than the native CPU.  But this is due to programmer laziness
and poor static compilers more than anything.

> I assume both the x86 and PA-8000 instruction sets weren't designed to be
> run this way, so could an instruction set designed to run in this form be
> even faster?

They *were* designed to be run this way.  Dynamo is
basically "straightening" the code.  You can write your
own programs as straight code with few jumps if you
want to, but the result is unmaintainable.  So we
naturally write "inefficient" code that Dynamo fixes up.

> I'm really just asking out of curiosity as I'm still not 100% sure how
> Melody works, although I'm getting pretty close to understanding its
> intentions.

Melody would be a program representation format.  Kind of
like CPU or VM instructions, but with greater semantic
content.  Dynamo-like techniques would help make things
faster, once it has been JIT'ed to native CPU code.

Cheers,

Rhys.