Higher Order Instructions - microsoft.public.dotnet.framework.clr

Message from discussion Higher Order Instructions

Christopher Diggins

View profile

More options Apr 15 2007, 12:40 pm

Newsgroups: microsoft.public.dotnet.framework.clr

From: "Christopher Diggins" <cdigg...@gmail.com>

Date: 15 Apr 2007 09:40:14 -0700

Local: Sun, Apr 15 2007 12:40 pm

Subject: Re: Higher Order Instructions

  Reply to author
  |
  Forward
  | Print
  | View thread
  | Show original
  | Report this message
  | Find messages by this author
  

[snip]

> > > Also, it needs to magically turn into machine code or stay as a
> > > graph, depending on whether it's going to be called or composed again.

> > I don't see why you wouldn't just turn it into machine code right off
> > the bat, and use that as your representation.

> How would it allocate registers? How are arguments passed in? How does
> it compose, yet ensure that the parts composed don't clobber each
> other's registers and locals?

I won't get into this here, but in many cases these are easily solved
with a bit of compiler intelligence.

> Efficient allocation of registers is probably the most important thing a
> compiler does that relies on seeing as much of the source structure as
> possible before doing stuff, and is also one of the more important
> issues in efficient compilation.

I would say parallelization of instructions is more important now on
multi-core machines.

> > > Turning it into machine code for calling isn't going to be totally
> > > trivially cheap, it's going to have to enter a compiler somewhere...

> > Well yes, just like any byte code.

> My point being though, that it will have to enter the compiler every
> time, rather than just once, if the operations created through
> composition are to be efficient.

No, not neccessarily.

> The alternative is to have a fast
> interpreter, maybe using your self-described naive scheme where simple
> cookie-cutter machine code blocks get pasted together.

That's one approach. There are more sophistciated approaches as well.

> I will say that I know much thought has gone into this kind of thing in
> the Lisp world, and I'm not deeply familiar with optimization techniques
> that have been applied there, so I'm actually unqualified to object to
> it. But I brought it up anyway, since no one else is reacting :)

Okay, but you have to realize that in typed functional languages like
OCaml and Haskell there are new classes of optimization techniques,
like higher order function fusion, and deforestation, which is very
effective. Untyped languages like Lisp/Scheme, have their own set of
problems which obfuscate the issues of compiling higher order
functions.

[snip]

> Yes, I would say that interpreting would typically be faster than an
> efficient compiler for less-complex inputs, i.e. dependent on a low 'n'.
> But when I think about it now, it's like layering e.g. the Hotspot JIT
> inside itself; that is, the JIT generates code that interprets yet falls
> over to (re)compilation if enough reps are done...

That is simply not the case, but I'm not going to argue it anymore.

> You'll have to forgive me, I'm a little slow for new ideas :)

> > What would you say, if I generated assembly code for the following
> > example:

> > int[] a = new array[1000000];
> > for (int i=0; i < a.length(); ++i) a[i] = i;
> > Map(a, MapDelegate(int x) { return x % 2 == 0 ? x * 2 : x })
> > int sum = Fold(a, FoldDelegate(int x, int y) { return x + y; })

> > And it was over 20 times as fast as C#? Would you buy me a pint of
> > guinness?

> Well now, technically, a Lisp compiler could evaluate that at compile
> time :P

Well I intended 100000, and 2 to be run-time values, but either way it
demonstrates the same thing:
if we had higher-order isntructions in the byte-code we could pre-
evaluate many instructions at compile-time.

I think you are stuck with the assumption that higher-order
instructions always neccessitate dynamic functions, where in the
majority of cases the higher-order expressions can be expanded inline
and pre-evaluated.

> The main limiting factors on the speed of typical CLR & C#
> implementation of above snippet are the cost of calling through a
> delegate, and the opaqueness of a delegate to optimization - that is,
> when the compiler is processing the definitions of Map and Fold, it
> can't use information about the actual arguments to optimize as much as
> it could if things were coded as a loop. That isn't to say that Map &
> Fold aka Reduce don't have interesting optimization strategies in their
> own right, the point is that the extra indirection of delegates is a
> black box for the compiler.

And delegates are black boxes because higher order code can't be
expressed as byte-code.

One of the points of higher-order instructiosn is to be able to apply
the optimizations strategies of Map and Fold to the byte-code.

I'm going to have to stop the conversation dead here thought because I
simply don't have time to continue and I've made my point as clear as
I can. Whether the CLR team wants to consider these ideas is their own
choice (but you'd think at least one member of the team would have had
something to say by this point?!). Anyway I will continue work on Cat,
and the Cat to assembly compiler for now.

Thanks for the stimulating discourse Barry,
Christopher Diggins
http://www.cdiggins.,com

Reply to author Forward