Skip to main content

Eliminating array bounds checks

9 replies [Last post]
conal
Offline
Joined: 2005-11-30

I'm looking for info on how to write Java programs so that the compiler can safely eliminate array bounds checking. Does anyone have info pointers? I'm running Java version 1.5.0 (build 1.5.0_04-b05) on Windows XP. Thanks, - Conal

Reply viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.
olsonje
Offline
Joined: 2005-08-10

conal-> Ah ok, yea I can't help on that but I will be following this thread to learn what I can from it. Hope something good comes and answers your question! :)

steved
Offline
Joined: 2005-11-30

The server compiler will eliminate bounds checks in the following circumstances:
- Any time there is a preceding reference to the same array element.
- For inner loops, the compiler will generate 2 copies of the loop, an optimized unrolled version without bounds checks
and one with the bounds checks. Tests are inserted before the loop to determine if any array references in the loop might
cause an IndexOutOfBoundsException, if so the checked loop is run, otherwise the optimized loop is used. The checked loop is
also used if there are a leftover iterations due to the unrolling of the optimized loop.

Two suggestions for helping the compiler optimize the array indexing would be to keep the subscript expressions simple (e.g. a simple local variable or a local variable +/- a constant) and make inner loops straight line code (no [b]if[/b] or [b]switch[/b] statements.)

pdoubleya
Offline
Joined: 2004-02-09

Conal--As linuxhippy posted, this looks like a Hotspot server feature (though in Mustang there are rumors that many server optimizations will be merged into Hotspot client). See this article: http://java.sun.com/j2se/1.4/performance.guide.html

and search for "array bounds"; what it says is that this is already done in server mode. I haven't seen any thorough documentation though, which might mean that Sun doesn't want to advertise it, perhaps because it's only applied in very constrained (and possibly rare) situations--if you sign up to see the Mustang code (including the VM), and you're a C/C++ programmer, you might get more clear answers on the Mustang forums.

HTH
Patrick

tmarble
Offline
Joined: 2003-08-22

Generally speaking this is in the 'let the JVM handle it' category.

Do have a code snippet example? Is this for
array accesses in bounded loops?

Regards,

--Tom

conal
Offline
Joined: 2005-11-30

> Generally speaking this is in the 'let the JVM handle it' category.
> Do have a code snippet example? Is this for array accesses in bounded loops?
> Regards,
> --Tom

Thanks for the reply, Tom. I am indeed hoping to let the compiler (javac and/or JIT) handle the [i]safe[/i] check elimination for me, and I'm guessing that I'll have to cooperate in my coding style.

For instance, I'm guessing that the compiler can recognize the safety of
[code] for (int j=0; j

Then there is this case, which also seems simple enough:[code] for (int k=0; k for (int j=0; j ... A[k][j] ...[/code]
A subtler example is the frequent use 1D arrays to simulate 2D arrays:[code] int pixels[rows*columns];

for (int k=0; k for (int j=0; j pixels[k*columns+j] = ... j ... k ... [/code]I'm guessing that the compiler won't deduce the safety of this array reference (and I'd be delighted to be mistaken), so I'd be better off writing the following instead:[code] for (int m=0; m
final int k = m/columns, j = m%columns;
pixels[m] = ... j ... k ...[/code]
Here's another pattern I'd really like to have optimized:[code] int pix = (j>=0 && j

I hope the examples above clarify my questions. I'd like to know which compilers do what kinds of [i]safe[/i] bounds-check elimination, recognizing what coding patterns.

BTW, the project that raises these questions for me is a new implementation of the declarative image synthesis & manipulation language [url=http://conal.net/Pan]Pan[/url], this time generating (highly optimized) Java code instead of C++ code. I would [i]love[/i] to find out that I can use Java instead of C++ with no significant loss of performance. Right now, I'm happy with performance except when there are trig instructions or many array references in my inner loop.

Regards, - Conal ([url]http://conal.net[/url])

linuxhippy
Offline
Joined: 2004-01-07

Hi there,

I can just give you some hints since the whole topic is a bit complex and depends somewhat on experience:

- Use the server-compiler by invoking you java-program with java -server ...; as far as I know only contained in the jdk.
The client-compiler does not remove bounds-checks at all.

- Use the PrintOptoAssambly switch in mustang (google for more details) to see the assembly generated by hotspot. This should help tuning your java-code to highest possible performance.
But keep in mind this is not defined anywhere so it might turn to the opposite with the next java-release..

lg Clemens

olsonje
Offline
Joined: 2005-08-10

Are you saying you want to use an array still, but without bounds checking?

conal
Offline
Joined: 2005-11-30

Thanks for asking, so I can clarify. I want to write in such a style that the compiler (javac and/or JIT) can recognize as safe without the bounds checking. In other words, I'd like to communicate my own knowledge array indices being in bounds so that the run-time overhead of bounds checking may be eliminated [i]with no loss of safety[/i]. I know that this won't always be possible, but I'm looking for those cases when it can. Please see my reply below to tmarble. Cheers, - Conal

conal
Offline
Joined: 2005-11-30

(I meant the previous as a reply to olsonje. Just learning my way around the forum procedures.)