On Jun 19, 3:53 pm, Rich Hickey <richhic...@gmail.com> wrote:
> On Jun 19, 2010, at 6:39 AM, Jules wrote:
>
>
>
>
>
> > I know nothing about the JVM, but I do know that on x86 you can handle
> > fixnum -> bignum promotion fairly cheaply. You compile two versions of
> > the code: one for bignums and one for fixnums. After an arithmetic
> > instruction in the fixnum code you check if it overflowed, and if it
> > did you switch to the bignum code.
>
> > while(n < 10) {
> > n = n + 1;
> > }
>
> > =>
>
> > while(n #< 10) {
> > a = n #+ 1;
> > if(overflow){ n = ToBignum(n); goto foo; }
> > n = a;
> > }
>
> > while(n.lessthan(10)) {
> > foo:
> > n = n.add(1);
> > }
>
> > where #< and #+ are the fixnum versions of < and +, and lessthan and
> > add are the bignum versions. Yeah it's slower than ignoring the
> > overflow, but faster than tagged 31-bit fixnums and a whole lot faster
> > than bignums. Can you convince the JVM to produce similar code?
>
> You can do things like that in a closed world of a few operators and
> types (although it gets unwieldy as the number of variables goes up).
> And of course, inside the math ops Clojure already does things like
> that.
>
> But that is not what we are dealing with here. This is an open system,
> where representational issues of functions, arguments and returns come
> into play. The 'operators' +, - etc are actually function calls - they
> are not special to the compiler. And your loop may also contain other
> function calls:
>
> while(n < 10) {
> foo(n)
> n = n + 1;
>
> }
>
> how do I know foo can handle the bigint once I've upgraded?
>
> How about this?
>
> while(n < 10) {
> n = foo(n)
>
> }
>
> Unless you have a tagged architecture you can't have boxed/unboxed arg/
> return uniformity (and even then you lose some bits of range).
>
> Rich
There are two possibilities: either foo gets inlined and the same
optimization is applied to the inlined code. Or foo is not inlined and
then you pass the general boxed representation to foo (but inside foo
the same optimization will be applied).
Suppose that we have a boxed representation like this:
class Num { ... }
class Small {
int val;
Num add(int n){ // argument specialized to int for simplicity of
this example
int sum = val + n;
if(overflow) return val.toBig().add(n);
else return new Small(sum);
}
...
}
class Big {
BigNum val;
Num add(int n){ ... }
}
Now the while loop. I use functional notation because the control flow
is hairy and with while loops this leads to a lot of reorganization.
With functional notation it's easier to see that every step is simple
and mechanical.
Here's our while loop and the library function to add two numbers:
loop(n) = if p(n) then n else loop(add(n,1))
add(Small a, int b) = let sum = a.val+b in if overflow then
add(Big(a.val),b) else Small(sum)
add(Big a, int b) = bigAdd(a,b)
Inline add into the loop:
loop(Small n) = if p(n) then n else let sum = n.val+1 in if overflow
then loop(add(Big(n.val),1)) else loop(Small(sum))
loop(Big n) = if p(n) then n else loop(bigAdd(n,1))
Introduce a new name:
loop_small(n) = if p(n) then n else let sum = n.val+1 in if overflow
then loop(add(Big(n.val),1)) else loop(Small(sum))
loop(Small n) = loop_small(n)
loop(Big n) = if p(n) then n else loop(bigAdd(n,1))
Inline loop into loop_small and eliminate dead code, turning
loop(Small(sum)) into loop_small(Small(sum)):
loop_small(n) = if p(n) then n else let sum = n.val+1 in if overflow
then loop(add(Big(n.val),1)) else loop_small(Small(sum))
loop(Small n) = loop_small(n)
loop(Big n) = if p(n) then n else loop(bigAdd(n,1))
Note that we have eliminated the checks (in this case pattern
matching) from the loop_small loop! Inlining + dead code elimination
did the trick. Sure, we are still using a boxed representation in
loop_small, but it's not polymorphic anymore and standard algorithms
can turn the heap allocated Small instances into stack allocated local
int variables (essentially "inlining" the Small class' instance
variables into the local variables, in this case only val).
It's not trivial to build a compiler that does this, but it's not
impossible either. Perhaps the JVM already does some of this. You can
get best of both worlds: speed *and* correctness. The situation is not
"pick one: speed, correctness", it is "pick two: speed, correctness,
simple compiler".
Jules
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
