Alex Rivera | Logout

How can I code Java to allow SSE use and bounds-check elimination (or other advanced optimizations)?

Asked 2009-08-29T21:28:13.057
41

The Situation:

I'm optimizing a pure-java implementation of the LZF compression algorithm, which involves a lot of byte[] access and basic int mathematics for hashing and comparison. Performance really matters, because the goal of the compression is to reduce I/O requirements. I am not posting code because it isn't cleaned up yet, and may be restructured heavily.

The Questions:

  • How can I write my code to allow it to JIT-compile to a form using faster SSE operations?
  • How can I structure it so the compiler can easily eliminate array bounds checks?
  • Are there any broad references about the relative speed of specific math operations (how many increments/decrements does it take to equal a normal add/subtract, how fast is shift-or vs. an array access)?
  • How can I work on optimizing branching -- is it better to have numerous conditional statements with short bodies, or a few long ones, or short ones with nested conditions?
  • With current 1.6 JVM, how many elements must be copied before System.arraycopy beats a copying loop?

What I've already done:

Before I get attacked for premature optimization: the basic algorithm is already excellent, but the Java implementation is less than 2/3 the speed of equivalent C. I've already replaced copying loops with System.arraycopy, worked on optimizing loops and eliminated un-needed operations.

I make heavy use of bit twiddling and packing bytes into ints for performance, as well as shifting & masking.

For legal reasons, I can't look at implementations in similar libraries, and existing libraries have too restrictive license terms to use.

Requirements for a GOOD (accepted) answer:

  • Unacceptable answers: "this is faster" without an explanation of how much AND why, OR hasn't been tested with a JIT compiler.
  • Borderline answers: have not been tested with anyth
java performance optimization jvm-hotspot bounds-check-elimination
Edit
Report

1 Answer

2

Lots of answers so far, but couple of additional things:

  • Measure, measure, measure. As much as most Java developers warn against micro-benchmarking, make sure you compare performance between changes. Optimizations that do not result in measurable improvements are generally not worth keeping (of course, sometimes it's combination of things, and that gets trickier)
  • Tight loops matter as much with Java as with C (and ditto with variable allocations -- although you don't directly control it, HotSpot will eventually have to do it). I manage to practically double the speed of UTF-8 decoding by rearranging tight loop for handling single-byte case (7-bit ascii) as tight(er) inner loop, leaving other cases out.
  • Do not underestimate cost of allocating and/or clearing large arrays -- if you want lzf encoding/decoding to be faster for small/medium chunks too (not just megabyte sized), keep in mind that ALL allocations of byte[]/int[] are somewhat costly; not because of GC, but because JVM MUST clear the space.

H2 implementation has also been optimized quite a bit (for example: it does not clear the hash array any more, this often makes sense); and I actually helped modify it for use in another Java project. My contribution was mostly just changing it do be more optimal for non-streaming case, but that did not touch the tight encode/decode loops.

answered 2009-12-08T05:38:50.203

Your Answer