Re: Hash table performance
Thomas Pornin wrote:
According to Patricia Shanahan <pats@acm.org>:
Given current division speeds, does it really make sense to use a
power-of-two bucket count?
Integer division tends to be slow on modern hardware. The Intel
optimization manual which happens to conveniently reside on my harddisk
states that latency for a simple "idiv" opcode is between 56 and 70
clock cycles, while masking uses only a fraction of a clock cycle.
Division actually becomes slower over time; on a 80386, signed division
took 43 clock cycles while a bit masking operation used 2 clock cycles.
I do not have Intel manuals for newer processors (these should be
downloadable from Intel's web site), but I expect integer division to
remain slow on newer designs.
On some RISC architectures (e.g. Alpha), there is no integer division
opcode at all; division is performed in software and is even slower.
In Sun's JRE, Hashtable and HashMap differ in their strategy.
Hashtable uses a bucket count initially set to the provided value,
or 11 by default. If the count is n and must be increased, then the
new count is 2*n+1. Conversely, HashMap uses only powers of two for
its bucket count (if given an initial capacity, it rounds it up to
the next power of two).
--Thomas Pornin
I did a quick microbench to test division versus shifting. I was
surprised by the result, I expected them to be "close enough", but it
looks like, on my machine at least, there is an order of magnitude
difference:
<results>
Nothing: count = 874270000
Shift: count = 869828000
Divide: count = 91958000
Nothing: count = 832932000
Shift: count = 760583000
Divide: count = 82123000
Nothing: count = 890739000
Shift: count = 881628000
Divide: count = 92349000
</results>
<code>
public class TestDivs {
private static final int INNER_LOOP = 1000;
private static final long RUNFOR = 1000 * 1000 * 1000 ;
public static void main(String[] args) {
doNothing();
doShift();
doDivide();
doNothing();
doShift();
doDivide();
doNothing();
doShift();
doDivide();
}
private static void doNothing() {
final long start = System.nanoTime();
long ns;
while (start == (ns = System.nanoTime())) ;
ns += RUNFOR;
int count = 0;
int s = 100;
while (System.nanoTime() < ns) {
for (int i = 0; i < INNER_LOOP; ++i) {
++count;
s += 9999;
}
}
System.out.println("Nothing: count = " + count);
}
private static void doDivide() {
final long start = System.nanoTime();
long ns;
while (start == (ns = System.nanoTime())) ;
ns += RUNFOR;
int count = 0;
int s = 100;
while (System.nanoTime() < ns) {
for (int i = 0; i < INNER_LOOP; ++i) {
++count;
s %= 37;
s += 9999;
}
}
System.out.println("Divide: count = " + count);
}
private static void doShift() {
final long start = System.nanoTime();
long ns;
while (start == (ns = System.nanoTime())) ;
ns += RUNFOR;
int count = 0;
int s = 100;
while (System.nanoTime() < ns) {
for (int i = 0; i < INNER_LOOP; ++i) {
++count;
s >>= 5;
s += 9999;
}
}
System.out.println("Shift: count = " + count);
}
}
</code>