benchmark : Java Glossary

Designing a Benchmark

• You want some conformance tests that the candidate code actually works, especially in a competitive situation.
• Try to keep the overhead inside your inner test loop to a bare minimum. Don’t call any additional functions or access instance or statics. Ideally, do nothing more than sum += result; where sum is local. You want to measure the speed of you candidates, not your harness.
• You need to repeat the test many times to a get a good sampling of over a minute.
• You can use System.nanoTime instead of System. currentTimeInMillis for more accurate timing.
• You must not throw the results of computation away. If you do, the compiler might optimise code out of existence that produced them.

Signum Benchmark Source Code

Signum Benchmark Conformance Results

Signum Benchmark Timing Results from Roedy’s 32-bit Athlon Machine

Signum Benchmark Timing Results from Rob Skedgell 64-bit Opteron Machine

Discoveries

1. The best I algorithm I could come up with in assembler was three machine cycles, which should take about 1.5 nanoseconds per call. Piotr’s algorithm under JET beats that with 1.17 nanoseconds. This is a great feather in both Piotr and JET’s cap, doing even better than hand-written assembler.
2. Comparing their best work, the 32-bit optimisers are best in this order:

   Ranking 32-bit optimisers as result of the Signum benchmark

   Ranking 32-bit Optimisers From Signum Benchmark Results
   Run Time	Warm SI	Best Warm Algorithm	Cold SI	Best Cold Algorithm
   JET 5.0	252.2	piotr	247.88	piotr
   Java -server	74.53	signOf	71.65	signOf
   Java -client	23.96	wibble	26.37	kobzda

3. fastest code depends on the JVM. You don’t know till you measure the alternatives. The rankings change drastically depending on platform and whether you run warm or cold.
4. The quality of algorithm for any given platform ranges from twice as fast from slowest to fastest to twenty times as fast. So that choice is crucial.
5. The fastest 32-bit time was piotr under JET. This is 3.5 times faster than Piotr under Java -client. The fastest 64-bit time overall, was Oracle’s Long. signum, running under Mustang, by a huge margin.
6. The secret of the speed of the piotr algorithm is it does its work at a low level on ints, not longs. On 32-bit hardware, 64-bit longs are clumsily simulated. It also took advantage of the fact hardware can most easily split a long exactly down the middle. In compiler listing I speculate on ways the algorithm could be implemented in assembler. JET does better than I can do with hand assembler.
7. Though Oracle’s Long.signum algorithm is terse, it is a pretty much a pig in 32-bit mode. Oracle’s Long. signum is implemented as (int) ((i >> 63) | (-i >>> 63)); It does much better on the 64-bit benchmarks.
8. Even though piotr, signOf, signHalf and Kobzda each beat Long. signum, they are not true signums, so can’t replace Oracle’s algorithm. However, two ifs beat Oracle Long. signum in nearly every case so should replace it in 32-bit JVMs (Java Virtual Machines).
9. JRockit doubles its speed between the cold and warm trials. It is thus important to call high level routines many times to exercise them to get them warmed up with inline optimisation, not just the leaf methods. If you only run them once for hours rattling around inside, they may never become candidates for optimisation. I removed the JRockit results since they were done with an older version of the program and it would be misleading to compare them with the new results.
10. Even with nanosecond accurately timers, benchmarks are not that repeatable. Random background processes presumably are interfering (even in a nominally idle machine) or perhaps even random processing inside the JVM itself.
11. Lohi was expressly designed for a 32-bit processor with aggressive peephole optimisation. Yet in the 64-bit Java -server 1.5 competition it won, massively, in a 64-bit machine without optimisation. Strange! Even stranger, optimisation made it run 2.25 times slower! I suspect the problem is simply the immaturity of JVM 1.5 64-bit -server mode. It is a 32-bit JVM in 64-bit drag, not through the full sex change yet. I suspect the 1.5 JVM essentially uses a 64-bit machine to emulate a 32-bit one, with pockets of true 64-bit.
12. Oracle’s team might heed the physician’s advice and above all, do no harm. They are often doing serious damage with their optimisations that fail to take into account the relative speed characteristics of the particular processor model, not just the general architecture. There is little incentive for them to do all that work collecting the lore about different models. If they optimise for Oracle hardware and let the chips fall where they may on other hardware, that gives Oracle hardware an edge running Java benchmarks, which is as it should be, given that this edge is the only thing financing Java development.
13. Java 1.6.0_04 -client is about half the speed of the 1.5 -client runtime.

The Bottom Line

Piotr, kobzda or signhalf are the best algorithms, depending on platform. Wibble does best before the optimiser has time to kick in.

This is a very narrow test and should not be taken as indicative of overall speed in real world situations.

I would like to thank every who participated and especially congratulate to Peter Kobzda who designed the overall fastest algorithm and the JET compiler team whose optimisation skills embedded in the JET AOT (Ahead Of Time) compiler converted it into the fasted machine code.

If you think you can beat these results, please feel free to submit more entries.

It would be nice to see some JET results on a 64-bit machine (you can use the free or evaluation version).

It would also be nice to see what happens on some high end 64-bit hardware, especially various Oracle workstations. After all, this is the hardware the Java developers were using the tune the JVM code.

Coaxing the Optimiser Along

This is why TestSignum does a pretrial, to give the optimiser time to notice what needs optimising and collect statistics. The main task sleeps for 5 seconds after the warmup to give the background optimising threads plenty of time to complete their optimisations. It would be silly to do this in a real application, but it is a reasonable solution for a microbenchmark.

To discover how much warmup time you need with JRockit, run with -Xverbose:opt which prints out trace details on optimizations as they happen. When messages stop appearing, you’ve reached stable state. The time varies from a few seconds (for a microbenchmark) to many minutes (for a large application with thousands of classes).