Implementing Complex Numbers operation in bytecode

[Roedy Green]

ans_re = (ac + bd)/ (c*c + d*d) ;
ans_im = (bc - ad) / (c*c + d*d) ;
and obviously (c*c + d*d) is duplicated (that is easy ... but it was
just z1/z2)
what about (z1*z2*z3) /( (z1+z2)(z2+z3)) (for instance) ??

It seems to me that actual computation is obvious, posted at
http://mindprod.com/jgloss/complex.html

(a + ib) / (c + id) = ((ac + bd) + i(bc - ad)) / (c*c + d*d)

// or in practice:
double bottom = 1.d / (c*c + d*d);
double real = (ac + bd) * bottom;
double imaginary = (bc - ad) * bottom;

 

[P.Hill]

I was wondering if the best implementation in bytecode will still 10
times slower than FORTRAN ? (and which was this best implementation
...)

Sounds like premature optimization to me.

If you are optimizing because of that concern, I think you need to run
some tests, the object allocation stuff is very fast (many times faster
that in earlier versions).

-Paul

 

[Roedy Green]

Sounds like premature optimization to me.

If you are optimizing because of that concern, I think you need to run
some tests, the object allocation stuff is very fast (many times faster
that in earlier versions).

Bill Joy talked about the problem and the possible solutions to it
when he spoke at the Colorado Software Summit. Granted that was in
1999.

 

[oulan bator]

My question was to feed a preliminary though about this topic. My next
steps will be to benchmark naive complex implementation (acknowledging
that instantiation is not that slow, and that in 1.6 will improve that)
, less naive one, and finally find some optimization rules for
mathematical expression involving complex numbers...

I'll look for Bill Joy speech (and papers about it)

thanks all

 

[Chris Uppal]

I'm almost building a FORTRAN compiler for JVM/bytecode (it's not
exactly a FORTRAN compiler, but in the concern of complex numbers, and
the four operations, it's not different

I would be tempted to go for an approach where the generated bytecodes
contained no Complex objects at all -- or rather, as few as possible. So an
array of complex number would be implemented (as far as the JVM could tell from
the code it was executing) just as an array of floats or doubles.
Complex-values variables would be represented by two float/double variables at
the JVM level. Similarly for parameters to methods/functions. The big problem
is returning a complex value from a function; that can't be done in any
straightforward way, so you would have to use a temporary full object -- either
an instance of Complex or a double[2]. Using a real class, Complex, for these
purposes might make interoperation with "normal" Java code easier, in which
case your compiler would be considered to be just "very aggressive" about
autoboxing Complex data.

One important question to consider is /which/ calculations you are worried
about the performance of. If the biggest issue is about the creation of many
temporary "objects" whilst doing complex arithmetic then the escape-analysis in
1.6 may help (so don't do anything complicated until you've tried 1.6 ;-) OTOH
the issue may be the performance of big complex array calculations, where the
space overheads of representing each value as a full object may kill you, or
where the time overhead of a cache miss for accessing each object (via at least
one more level of indirection) may kill you. In such cases representing the
complex values in-line (as above) would be a good option, but you might also
want to think about making complex array operations into a language primitive,
implemented (via JNI) in C/Fortran/Assembler. There would be costs associated
with crossing the JNI barrier (which might involve copying the data), but it
might still be a useful design option.

There's no straightforward way to persuade the JIT to use Intel's SSE
extensions -- not least because the code might not be running on Intel, or even
Intel-compatible, hardware.

(BTW, on a side-note, if you had mentioned what you are trying to do in your
earlier post then I doubt if you would have received quite so many dismissive
or hostile responses. People around here get conditioned to expect stupid
questions, but showing that you are embarking on a challenging and ambitious
project is likely to preempt that.)

-- chris

 

[oulan bator]

ok for the tip, next time I'll try to be more explicit about my
programming skills !

My first "naive" implementation was to perform symbolic "inlining" of
complex operation. But that's too much expensive. for instance :
z3=z1*z2/(z1+z2) leads to two assignation:
z3_re= a real expression ;
z3_im = another real expression;

I had no opportunity to create local var like (c²+b²) in simple
division (due to internal constraints, that i 'm trying to break).

prior to all, I'll have a look at 1.6 current version (if they have
alerady implemented those features) but I'm still looking for
scientific papers on benchmarking complex numbers support in Java ...
does anybody know why IBM hs stopped the ninja project ?

 

[Roedy Green]

Bill Joy talked about the problem and the possible solutions to it
when he spoke at the Colorado Software Summit. Granted that was in
1999.

Unfortunately I doubt it was transcribed. It was one of the high
points of my life.

It was so interesting to learn about the battles within Sun and all
the compromises, and how Joy himself was as keen as I am to do things
correctly.

 

[Roedy Green]

the code it was executing) just as an array of floats or doubles.
Complex-values variables would be represented by two float/double variables at
the JVM level.

you might use a pair of arrays, or real/imaginary pairs at odd/even
slots which I suspect should generate faster code mainly because of
CPU caching.

 

[Roedy Green]

Intel's SSE
extensions

What you would do here is write a native vector method in MASM and a
Java implementation for other platforms. The instructions I doubt
will buy you much until you get a pipeline going to parallel process.
It would be difficult for a compiler to utilize such special purpose
hardware for general java code. You would use SSE to code your FFT or
similar matrix/vector algorithm.

Unfortunately, Java syntax has no means to implement the code for some
platform's native classes is C and some in Java.

 

[Chris Uppal]

My first "naive" implementation was to perform symbolic "inlining" of
complex operation. But that's too much expensive. for instance :
z3=z1*z2/(z1+z2) leads to two assignation:
z3_re= a real expression ;
z3_im = another real expression;

I doubt whether you'll ever be able to avoid that; in fact I don't see how you
could /expect/ to avoid that. If the Intel SIMD extensions can express that
kind of thing in one "instruction" (I'm not familiar with SSE/SSE2) then the
only way you'll be able to use them is either if the JIT is "clever" enough to
spot the opportunity to use them (which I very much doubt[*]) or if you write
your own JIT (I believe that the Sun JVM has hooks for providing a custom JIT,
but I've only ever read of one research group attempting to use it).

([*] The 1.5.0 Sun JVM source appears to have no provision for even emitting
the SIMD instructions except MOVSD/MOVSS)

[...] I'm still looking for
scientific papers on benchmarking complex numbers support in Java ...

Best thing I can suggest is to start with the papers you already have (such as
the Ninja and Java Grande papers) and use Citeseer, and the like, to look for
papers that refer to them.

does anybody know why IBM hs stopped the ninja project ?

I have a vague feeling that I remember IBM saying that they were folding their
efforts into the Java Grande project. But then, Java Grande seems to have gone
quiet too. I don't know whether that impression is correct, but it is at least
conceivable that the big names have largely lost interest in making Java a
replacement for Fortran. (/I/ could never see the point, anyway.)

-- chris