Re: Hash table performance

On 23 Lis, 18:01, Patricia Shanahan <p...@xxxxxxx> wrote:
Marcin Rzeźnicki wrote:

...> It is true in general, furthermore it is always true in F# or any
language implemented on top of CLR where there is no notion of
"primitive type". The thing we should discuss after filtering half-
truths out is whether difference between value types and reference
types might cause 32x performance degradation

...

I would back off even further to something like "What are the probable
causes of Jon's observations?".

Patricia

I profiled his example in net beans.

That's my JVM
C:\Users\Rzeźnik\Documents\java>java -version
java version "1.6.0_17"
Java(TM) SE Runtime Environment (build 1.6.0_17-b04)
Java HotSpot(TM) Client VM (build 14.3-b01, mixed mode, sharing)

Here is the code I used:

package hashmapexample;

import java.util.HashMap;

/**
*
* @author Rzeźnik
*/
public class Main {

/**
* @param args the command line arguments
*/
public static void main(String[] args) {
HashMap<Double, Double> hashtable = new HashMap<Double, Double>
();
for (int i = 1; i <= 1000000; ++i) { /* changed upper bound to
1m - sorry no, patience */
double x = i;
hashtable.put(x, 1.0 / x);
}

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

I used -Xms512m -Xmx512m to eliminate extensive collections.

The results of profiling are as follows:
54.2% of time spent in java.util.HashMap.put(Object, Object) (1m
invocations)
of which:
* * 19.5% in java.util.HashMap.addEntry(int, Object, Object, int)
* * * * 11.1% in java.util.HashMap.resize(int) (17 invocations)
<--- !!!
* * * * 3.3% self-time
* * * * 1.4% in java.util.HashMap$Entry.<init>(int, Object, Object,
java.util.HashMap.Entry) <-- so the cost of allocating entries is
negligible
* * 8.1% in java.lang.Double.hashCode() <--- that's too much (?)
.... rest of put omitted, circa 1%

Now, the interesting part is
30.3% of time spent in java.lang.Double.valueOf(double) <--- that's
boxing
Furthermore, there were 2m + 1 calls to new Double meaning that no
caching occurred.
.

Relevant Pages

  • Re: ?meterware? WebConversation jar
    ... @param args the command line arguments ... public static void mainthrows MalformedURLException, ... I wanted to use libcurl for Java but couldn't ...
    (comp.lang.java.help)
  • cant launch link.exe or cl.exe from a java prog
    ... I have a big trouble with the link.exe and cl.exe. ... I try to lauch there from a java application and I don't ... public static void main{ ...
    (microsoft.public.vstudio.general)
  • Re: Question about sample Java application
    ... > private static String name; ... > public static void main{ ... In most of what I've been doing, when I have to do a Java ... application within that one .java file. ...
    (comp.lang.java.programmer)
  • Re: beginners question
    ... It must accept a String array as a parameter. ... public static void main ... When java tells you that it cannot find a method, ... requiring an applet viewer. ...
    (comp.lang.java)
  • JNI - unresolved _ZNSs4_Rep11_S_terminalE
    ... which (the main-driver) calls JAVA again to ... do the real work for processing the message. ... when starting the JAVA MainWrapper ... public static void main{ ...
    (comp.lang.java.programmer)