Re: Hash table performance

From:

Patricia Shanahan <pats@acm.org>

Newsgroups:

comp.lang.java.programmer

Date:

Sat, 21 Nov 2009 11:00:13 -0800

Message-ID:

<JsmdnVFw6p0ipZXWnZ2dnUVZ_hpi4p2d@earthlink.com>

Jon Harrop wrote:

I'm having trouble getting Java's hash tables to run as fast as .NET's.
Specifically, the following program is 32x slower than the equivalent
on .NET:

  import java.util.Hashtable;

  public class Hashtbl {
    public static void main(String args[]){
      Hashtable hashtable = new Hashtable();

      for(int i=1; i<=10000000; ++i) {
        double x = i;
        hashtable.put(x, 1.0 / x);
      }

      System.out.println("hashtable(100.0) = " + hashtable.get(100.0));
    }
  }

My guess is that this is because the JVM is boxing every floating point
number individually in the hash table due to type erasure whereas .NET
creates a specialized data structure specifically for a float->float hash
table with the floats unboxed. Consequently, the JVM is doing enormously
numbers of allocations whereas .NET is not.

Is that correct?

I think there has to be something more to it than just the autoboxing.

My reasoning is that you never reuse a key, so every put call creates a
new Entry instance. Creating a Double from a double is about as simple
as object creation can be, so I don't see how the boxing could to more
than triple the time spent in object creation during an average put
call. That cannot, by itself, account for a 32x performance ratio.

Patricia