4.0.0 JNI/reflection invocation 2/4/8 times as slow as in 3.3.3

Sun Jan 30 20:34:00 GMT 2005

On Tue, 2005年01月25日 at 21:21, Tom Tromey wrote:
> That's interesting. Could you write a patch that includes an
> explanation of what is going on internally? And ideally do some
> profiling so we can see the result?

Please excuse the delay. A preliminary patch is attached.
Compared with 4.0 this is now ~800 times faster, but unfortunately not
as fast as 3.3.3 (times in ms):
sh-2.05b$ sh run.sh "3.3.3 4.0 4.0.new" 4000
3.3.3: 5 7
4.0: 5383 5459
4.0.new: 7 8
sh-2.05b$ sh run.sh "3.3.3 4.0.new" 400000
3.3.3: 826 894
4.0.new: 1110 1265
I suspect that it's due to the new getHashCode() function. If we can
guarantee that the System.identityHashCode implementation never changes,
we can take advantage of the fact that it returns values which are
aligned at word boundaries.
The test I've used is also attached.
Jost
-------------- next part --------------

--- 4.0/IdentityHashMap.java	2005年01月30日 21:08:12.000000000 +0100
+++ 4.0.new/IdentityHashMap.java	2005年01月30日 21:16:21.000000000 +0100
@@ -94,8 +94,16 @@
 public class IdentityHashMap extends AbstractMap
 implements Map, Serializable, Cloneable
 {
+ /** 
+ * How many conflicting keys can be stored. The value should be
+ * ceil(CLUSTER_SIZE*.75)+1 <= CLUSTER_SIZE.
+ * @see #hash(Object)
+ * @see #getHashCode(Object)
+ */
+ private static final int CLUSTER_SIZE = 8;
+
 /** The default capacity. */
- private static final int DEFAULT_CAPACITY = 21;
+ private static final int DEFAULT_CAPACITY = CLUSTER_SIZE*3*2;
 
 /**
 * This object is used to mark deleted items. Package visible for use by
@@ -143,7 +151,7 @@
 private transient int threshold;
 
 /**
- * Create a new IdentityHashMap with the default capacity (21 entries).
+ * Create a new IdentityHashMap with the default capacity (3*CLUSTER_SIZE keys).
 */
 public IdentityHashMap()
 {
@@ -163,9 +171,9 @@
 {
 if (max < 0)
 throw new IllegalArgumentException();
- // Need at least two slots, or hash() will break.
- if (max < 2)
- max = 2;
+ // Need at least three clusters
+ if (max < CLUSTER_SIZE*3)
+ max = CLUSTER_SIZE*3;
 table = new Object[max << 1];
 Arrays.fill(table, emptyslot);
 threshold = (max >> 2) * 3;
@@ -180,7 +188,9 @@
 */
 public IdentityHashMap(Map m)
 {
- this(Math.max(m.size() << 1, DEFAULT_CAPACITY));
+ // round to the next odd number of clusters
+ this((m.size()/CLUSTER_SIZE + (m.size()%CLUSTER_SIZE==0?0:1) + 
+	 (m.size()/CLUSTER_SIZE + (m.size()%CLUSTER_SIZE==0?0:1)%2)) * CLUSTER_SIZE * 2);
 putAll(m);
 }
 
@@ -491,9 +501,9 @@
 if (size > threshold)
 {
 Object[] old = table;
- // This isn't necessarily prime, but it is an odd number of key/value
- // slots, which has a higher probability of fewer collisions.
- table = new Object[(old.length * 1) + 2];
+ // This isn't necessarily prime, but it is an odd number of clusters 
+ // which has a higher probability of fewer collisions.
+ table = new Object[(old.length * 2) + (2*CLUSTER_SIZE)];
 Arrays.fill(table, emptyslot);
 size = 0;
 threshold = (table.length >>> 3) * 3;
@@ -629,6 +639,17 @@
 return values;
 }
 
+ /** 
+ * Private function for the hash implementation. 
+ *
+ * <strong> If the System.identityHashCode() is changed, the
+ * getHashCode() must also be changed.</strong><p>
+ */
+ private static int getHashCode(Object key) 
+ {
+ return System.identityHashCode(key)>>>3;
+ }
+
 /**
 * Helper method which computes the hash code, then traverses the table
 * until it finds the key, or the spot where the key would go.
@@ -641,16 +662,21 @@
 // Package visible for use by nested classes.
 int hash(Object key)
 {
- // Implementation note: it is feasible for the table to have no
- // emptyslots, if it is full with entries and tombstones, so we must
- // remember where we started. If we encounter the key or an emptyslot,
- // we are done. If we encounter a tombstone, the key may still be in
- // the array. If we don't encounter the key, we use the first emptyslot
- // or tombstone we encountered as the location where the key would go.
- // By requiring at least 2 key/value slots, and rehashing at 75%
- // capacity, we guarantee that there will always be either an emptyslot
- // or a tombstone somewhere in the table.
- int h = Math.abs(System.identityHashCode(key) % (table.length >> 1)) << 1;
+
+ /* Mappings are stored in clusters of CLUSTER_SIZE elements and the
+ * hash function spreads the keys over these clusters. To make sure
+ * that each cluster gets filled not much more than 75%, the number
+ * of clusters should be a prime or at least be an odd number.
+ *
+ * Within a cluster a linear probe is used. Filling the last
+ * element of a cluster causes the cluster to overflow and the
+ * search expands to the following cluster until the next rehash.
+ *
+ * "tombstones" mark slots which belong to the current cluster;
+ * they can "expand" a cluster into the next one.
+ */
+ int clusters = (table.length>>1)/CLUSTER_SIZE;
+ int h = ((getHashCode(key) % clusters)*CLUSTER_SIZE)<<1;
 int del = -1;
 int save = h;
 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: IdentityHashMap.test.tar.bz2
Type: application/x-bzip
Size: 10911 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/java/attachments/20050130/eb052110/attachment.bin>
