Re: Hash table performance
This message is in MIME format. The first part should be readable text,
while the remaining parts are likely unreadable without MIME-aware tools.
---910079544-686117080-1258832665=:26245
Content-Type: TEXT/PLAIN; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 8BIT
On Sat, 21 Nov 2009, Marcin Rze?nicki wrote:
On 21 Lis, 19:33, Jon Harrop <j...@ffconsultancy.com> 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?
You are using Hashtable instead of HashMap - probably the performance
loss you've observed is due to synchronization (though "fat"
synchronization might be optimized away in case of single thread you
still pay the price, though lower). If you took a look at JavaDoc, you'd
notice that HashTable methods are synchronized As of boxing, you are
correct (though there is no type erasure in your example because you did
not specify type parameters at all) but I suspect that these costs are
not the most contributing factor to overall poor performance. I'd blame
synchronization in the first place.
I'd be *very* surprised if that was true. In this simple program, escape
analysis could eliminate the locking entirely - and current versions of
JDK 1.6 do escape analysis. Even if for some reason it didn't, you'd only
be using a thin lock here, which takes two x86 instructions and one memory
access for each lock and unlock operation, far less than the boxing or
unboxing.
I modified the test code to look like this (yes, with no warmup - this is
very quick and dirty):
import java.util.Map;
import java.util.HashMap;
import java.util.Hashtable;
public class HashPerf {
public static void main(String args[]) throws InterruptedException{
for(int i=1; i<=100; ++i) {
long t0 = System.nanoTime();
test();
long t1 = System.nanoTime();
long dt = t1 - t0;
System.out.println(dt);
System.gc();
Thread.sleep(200);
}
}
private static void test(){
Map<Double, Double> hashtable = new HashMap<Double, Double>();
// Map<Double, Double> hashtable = new Hashtable<Double, Double>();
for(int i=1; i<=1000; ++i) {
double x = i;
// synchronized (hashtable) {
hashtable.put(x, 1.0 / x);
// }
}
}
}
And then ran it with three variations on the comments: one as above, one
uncommenting the synchronization of the hashtable, and one switching the
HashMap to a Hashtable. I have java 1.5.0_19 on an elderly and ailing
PowerPC Mac laptop. I ran with -server and otherwise stock settings.
The timings for each show the usual power curve distribution: 80% of the
measurements are no more than 50% longer than the fastest, and 90% are no
more than twice as long, with the last 10% being up to 10 times longer. If
we say that the slowest 10% are artifacts of warmup, GC, the machine doing
other things, etc, and ignore them, then the average times i got were
(with standard error of the mean, which is broadly like a ~60% confidence
limit IIRC):
HashMap 933500 +/- 15006
sync HashMap 1003200 +/- 16187
Hashtable 868322 +/- 11602
That is, adding synchronization to the accesses adds a 7.5% overhead.
Although somehow, the old Hashtable comes out faster!
So, even with java 1.5, adding synchronization to HashMap.put() imposes
only a small performance penalty - i'd expect it to be less with 1.6. I
doubt very much that this is the major factor in the OP's performance
problem.
tom
--
.... the gripping first chapter, which literally grips you because it's
printed on a large clamp.
---910079544-686117080-1258832665=:26245--