Re: Hash table performance
On 23 Lis, 18:01, Patricia Shanahan <p...@acm.org> wrote:
Marcin Rze=C5=BAnicki 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=C5=BAnik\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=C5=BAnik
*/
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.