AMPC 1.4.3 released (C to Java Class Files compiler suite) - Compilers

If you don't mind talking a little about the internals, I'm always
interested in how people get around the pointer dereferencing issue in
the JVM. The JVM doesn't inherantly support this (it doesn't let you
load a value given a memory address) and many of the work-arounds are
klunky.

Eric

Eric wrote:

> If you don't mind talking a little about the internals, I'm always
> interested in how people get around the pointer dereferencing issue in
> the JVM. The JVM doesn't inherantly support this (it doesn't let you
> load a value given a memory address) and many of the work-arounds are
> klunky.

I don't know about AMPC, but the obvious one to me is that a pointer
variable has an array object reference and offset into the array.
Pointer arithmetic adds or subtracts from the offset, and the offset is
used when the pointer is dereferenced. When pointers are subtracted or
compared with relational operators other than == and !=, only the offset
is subtracted or compared. C makes no guarantee of the results of
subtraction or non-equality comparison of pointers to different objects.

(A pointer variable might also need some type information so that
functions like memcpy() can properly handle copies to/from unsigned char.)

-- glen

The problem comes in the form of terrible efficiency. As I understand
it, array indexing in the JVM wouldn't be able to take advantage of the
fact that you're accessing a sequential range of bytes. Something like
this is very efficient in native code, but would slow down by maybe
10-100 times if you have to use array indexing and you have to re-index
into the array each time thru the loop.

This C code is very efficient:

while(*p++)
do_something(p);

Maybe a Java translation might be something like this:

for (int i=0; i < p.length(); i++)
do_something(p[i]);

These look similar, but the C-produced native code can use an index
register to scan memory efficiently. The Java-produced byte code would
likely re-index into the array for each iteration through the loop.
Array indexing is pretty slow because you don't get the advantage of
knowing that you're accessing a sequential range of bytes. Maybe a JIT
compiler could do something to make this more efficient, but it seems
like this would perform poorly in an interpreted JVM.

However, if the JVM understood the concept of dereferencing a pointer
to a memory location this could be much faster. This is done in the
..NET CLR and they were able to do it while still keeping type safety
and verifiable code. It's actually simple to define this type of
operation, but it looks to me that Sun went out of their way to avoid
doing this. Their fear of pointers was taken to an extreme, even though
it could have been done in a safe manner.

Eric

Eric wrote:
>
> The problem comes in the form of terrible efficiency. As I understand
> it, array indexing in the JVM wouldn't be able to take advantage of the
> fact that you're accessing a sequential range of bytes. Something like
> this is very efficient in native code, but would slow down by maybe
> 10-100 times if you have to use array indexing and you have to re-index
> into the array each time thru the loop.

Sorry, I get the impression that you don't understand address
calculations at all :-(

How should indexing be applied to an array, other than by adding an
offset to the base address of the array? Iff the array were not a
contiguous memory area, it would be impossible as well to traverse it
using pointer arithmetic.

>
> This C code is very efficient:
>
> while(*p++)
> do_something(p);

.... in detail because it misses to process the first element :-(

>
> Maybe a Java translation might be something like this:
>
> for (int i=0; i < p.length(); i++)
> do_something(p[i]);
>
> These look similar, but the C-produced native code can use an index
> register to scan memory efficiently.

This code does not hinder an (JIT...) compiler from doing optimizations,
which can outperform the not further optimizable pointer code in the
first example. The only runtime critical item is p.length(), as long as
it is not guaranteed that this value will not change during execution of
the loop.

IMO it's not justified to assume that nothing can be faster than pointer
operations. This assumption may hold for an single pointer, but not
necessarily for multiple pointers and/or other variables, which the
compiler cannot optimize as a whole - in contrast to e.g. indexing
multiple arrays in the same loop. Other languages have true counted
loops, where the bounds are evaluated only once, so that the number of
iterations is known before entering the loop. I'm not sure about the
Java conventions here...


> However, if the JVM understood the concept of dereferencing a pointer
> to a memory location this could be much faster. This is done in the
> .NET CLR and they were able to do it while still keeping type safety
> and verifiable code.

You understand the difference between pointer dereferencing and pointer
arithmetic?

> It's actually simple to define this type of
> operation, but it looks to me that Sun went out of their way to avoid
> doing this. Their fear of pointers was taken to an extreme, even though
> it could have been done in a safe manner.

It's actually much simpler to optimize pointerless code, *because* it
leaves room for optimizations. IMO nowadays pointers are good only for
people which *think* that they can optimize code better and safer than a
compiler can do. Just the chance for errors, like in your first example,
should discourage everybody from using pointers at all.

DoDi

Eric wrote:

> The problem comes in the form of terrible efficiency. As I understand
> it, array indexing in the JVM wouldn't be able to take advantage of the
> fact that you're accessing a sequential range of bytes. Something like
> this is very efficient in native code, but would slow down by maybe
> 10-100 times if you have to use array indexing and you have to re-index
> into the array each time thru the loop.

> This C code is very efficient:

> while(*p++)
> do_something(p);

I would say that the difference could be very system dependent.
Also, it assumes no bounds checking on the array. JVM and Java
always do bounds checking.

> Maybe a Java translation might be something like this:

> for (int i=0; i < p.length(); i++)
> do_something(p[i]);

> These look similar, but the C-produced native code can use an index
> register to scan memory efficiently. The Java-produced byte code would
> likely re-index into the array for each iteration through the loop.

Well, more important is what JIT can do. There is discussion that JIT
can recognize the loop bounds are the length of the array, or if not and
constant do the compare outside the loop. Many processor now should be
able to overlap the loop compare and the array access. Also, branch
prediction may be better on the loop.

I might also believe it more for a simple assignment, but if it includes
a call to do_something() in either language there is probably enough
overhead not to notice the difference.

> Array indexing is pretty slow because you don't get the advantage of
> knowing that you're accessing a sequential range of bytes. Maybe a JIT
> compiler could do something to make this more efficient, but it seems
> like this would perform poorly in an interpreted JVM.

For fairly small arrays, the difference is probably within the overhead,
especially if it involves allocation. My feeling is always that OO
programming tends to be slow because of excessive array allocation and
deallocation, independent of the language.

> However, if the JVM understood the concept of dereferencing a pointer
> to a memory location this could be much faster. This is done in the
> .NET CLR and they were able to do it while still keeping type safety
> and verifiable code. It's actually simple to define this type of
> operation, but it looks to me that Sun went out of their way to avoid
> doing this. Their fear of pointers was taken to an extreme, even though
> it could have been done in a safe manner.

I have used large arrays with Java, and usually wasn't too worried about
how slow they were. That is with JIT, though.

-- glen