Re: Higher Order Instructions

Tech-Archive recommends: Fix windows errors by optimizing your registry

Christopher Diggins wrote:

On Apr 11, 2:18 pm, Barry Kelly <barry.j.ke...@xxxxxxxxx> wrote:
Christopher Diggins wrote:
On Apr 8, 3:03 pm, Barry Kelly <barry.j.ke...@xxxxxxxxx> wrote:
Christopher Diggins wrote:

My point was efficiency though, and even more importantly, intuitiveness
of the efficiency of imperative code in the ordinary linear style, with
similar arguments to the old "worse is better" story re C/Lisp etc.

I don't understand what you are saying.

I was referring to this essay:

http://www.dreamsongs.com/WIB.html

So let me be clear here, what I propose requires the introduction of a
new data type, which consists of a list of opcodes. It is like a
method, except it isn't ever seen by the user, only compiler writers.
They use it to emulate higher order functions.

What I'm trying to get at, to make myself clear, is that in the CLR
model, opcodes are compiled by the JIT compiler into machine code; yet
your instructions manipulate opcodes - that is, they manipulate the
source code of the JIT compiler. (This is what I was referring to with
the Lisp reference.)

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?

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.

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. 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.

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 :)

If it turns into a delegate, won't you want to cache that somewhere, to
avoid getting that hit again next time... and doesn't this work seem
like not such a big win over just doing it yourself with
DynamicMethod...?

Sorry, you lost me.

I was musing out loud about possibilities for efficient compilation. I
can't get specific without trying to design something that would work,
which would take too much time out of my day, unfortunately. Though, see
the thoughts below...

It is true that
higher order functions would require a graph reduction machine,
however this is offset by the fact that far fewer instructions are
needed to achieve high-level functionality. A lot of dynamic IL
emitting code, which is currently very expensive, could be replaced by
higher-order IL code.

I guess, the more I think about it, I'm not sure what you're proposing,
because (as I've sketched out above) when I think about how a JIT would
"want" to do it, it seems like it isn't a win, and that you'd be better
off if the runtime *interpreted* your instructions - or at least, that's
the only way to get a net win out of it.

You have come to the conclusion that interpreting higher order
functions would be faster than compiling? I completely disagree.

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...

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

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.

I'm not sure what you're suggesting will improve that specifically
though, it's more oriented towards dynamic composition of new functions,
as I see it - and that case certainly isn't served well by the current
..NET delegate paradigm, because every composition accumulates delegate
invocation costs. Let me make that concrete:

bool P(bool value);

P Not(P pred)
{ return delegate(bool x) { return !pred(x); }; }
P And(P left, T right)
{ return delegate(bool x) { return left(x) && right(x); }; }
// ...

If someone wants to compose a predicate dynamically in C#/.NET,
currently they accumulate these costs. They can mitigate these costs
with the new stuff coming in C# 3.0 though, with LINQ Func<> trees,
which can be passed to a compiler and get the benefit of full
compilation. However, that forces the user to make the interpretation /
compilation tradeoff themselves.

OK. Now that I've thought about it more, it looks interesting, and with
the nesting of JIT compilation, it could be made efficient in both the
seldom-called and repeatedly-called cases. Have you considered modifying
e.g. Mono or one of the other open-source VM implementations to try and
get something along these lines? Because it seems to me that this kind
of thing could indeed make the cases above better, e.g. lambda
constructions could be improved.

I'm curious: can the compose operation itself be composed? :) That would
be something which would be particularly painful to handle in the LINQ
sense, although applications for it don't exactly jump out at me.

-- Barry

--
http://barrkel.blogspot.com/
.

Relevant Pages

  • Re: Higher Order Instructions
    ... it compose, yet ensure that the parts composed don't clobber each ... with a bit of compiler intelligence. ... OCaml and Haskell there are new classes of optimization techniques, ... I think you are stuck with the assumption that higher-order ...
    (microsoft.public.dotnet.framework.clr)
  • Re: Macro: chaining function calls.
    ... But in what way wouldn't a normal macro expanding (COMPOSE #'a #'b ... COMPOSE is much more useful as function than as macro. ... Compiler macros allow you to get best of both worlds: ...
    (comp.lang.lisp)
  • Re: Custom keywords and compiler-supplied code
    ... The compiler, as ... You would replace the anonymous delegate with your code. ... > I'm investiging multi-threaded GUI applications; ... By offloading the synchronisation onto the worker ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: creating ExecuteQuery method
    ... I looked into DbLinq code and found that it "normal" RowEnumerator compiler ... So my commit duplicates essential part of code. ... Alwing to use global conversion delegate. ... However I do'nt know DbLinq code enough to perform such big merge. ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: random sorting a collection
    ... Delegate d = delegate ... While the compiler is complaining about not being able to perform inference on the type, it's my opinion that the expression "=> return rnd.Next;" needs no additional information. ... It seems to me that the real issue here is how the expansion works, in that it's a straight "search and replace" sort of expansion in which a lambda expression is simply not an appropriate input. ... sure...the cast is required...but the real gimmick in the code you posted is the final "" that actually _calls_ the delegate. ...
    (microsoft.public.dotnet.languages.csharp)