054bFollow-Up to JDK 1.4 HashMap hashCode() Mystery

Author: Dr. Heinz M. KabutzDate: 2002-08-15Java Version: 1.4Category: Performance

Abstract: The "remainder function" is a form of division. "Division" is the most expensive CPU operation. HotSpot can transform "remainder" to a cheaper "multiply" operation. When benchmarking, we need to make sure that the divisor is not constant.

This is just a quick follow-up to the newsletter sent this morning at 2:00am South African time. It seems I was not very careful with the source code and a few errors crept in. Please have a look at the archive for a corrected edition. After finally collapsing in bed at 2:15am, I was rudely reminded that I have a daughter of 11 months old. She kept up her antics until 6:00am, when I had to get up to carry on presenting my Java course. *sigh* - today was not a good day!

Joshua Bloch wrote to me after last night's newsletter, sending me some more information about the remainder performance mystery, and I feel I should pass the information on to you, my readers:

Joshua Bloch: By the way, I now know more about what's going on with mod/division. There is a collection of techniques for doing fast division by a constant. These techniques are covered in great detail in Chapter 10 of a marvelous new book with the unlikely title of "Hacker's Delight" by Henry Warren [ISBN 0201914654] . It turns out that the old ("Classic") VM knew some of these tricks, but Hotspot, in releases up to 1.4, did not. While 1.4.1 can do some of this stuff, I suspect that later releases will do more.

I wrote a FairRemainderBenchmark that calculates the remainder with a variable, the way that the old HashMap would have done, and alas, the speed of the various JDKs is roughly the same:

import java.util.Random;
public class FairRemainderBenchmark implements Benchmark {
  private static final int ITERATIONS = 10 * 1000 * 1000;
  private int memory;
  public int doCalculation() {
    int val = 0;
    Random rand = new Random(0);      
    int bucket_size = (int)(rand.nextDouble() * 101) + 1;
    for (int i = 0; i < ITERATIONS; i++) {
      val = i % bucket_size;
    }
    memory = val;
    return ITERATIONS;
  }
}

The performance is now quite similar between the old and the new versions of the JVM:

JVM version:1.2
18867  18832  18484  19193  18832  18518  19193  18832  18484  18832
Average 18806 iterations per millisecond

JVM version:1.3.1_03
18867  18148  18832  18484  18484  18867  18832  18832  18148  18484
Average 18597 iterations per millisecond

JVM version:1.4.0
18832  19193  19230  19193  19193  19193  19193  19230  19193  19193
Average 19164 iterations per millisecond

JVM version:1.4.1-beta
17825  18148  18148  18148  17543  18484  18148  18148  17513  18518
Average 18062 iterations per millisecond

Heinz

Comments

We are always happy to receive comments from our readers. Feel free to send me a comment via email or discuss the newsletter in our JavaSpecialists Slack Channel (Get an invite here)

Related Articles

Browse the Newsletter Archive