You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@uima.apache.org by sc...@apache.org on 2014/04/03 22:14:33 UTC
svn commit: r1584373 - in /uima/uimaj/trunk/uimaj-core/src:
main/java/org/apache/uima/jcas/impl/JCasHashMap.java
main/java/org/apache/uima/jcas/impl/JCasImpl.java
test/java/org/apache/uima/jcas/impl/JCasHashMapTest.java
Author: schor
Date: Thu Apr 3 20:14:33 2014
New Revision: 1584373
URL: http://svn.apache.org/r1584373
Log:
[UIMA-3722] fix JCasHashMap table expansion / shrinking, and remove faulty optimization
Modified:
uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/jcas/impl/JCasHashMap.java
uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/jcas/impl/JCasImpl.java
uima/uimaj/trunk/uimaj-core/src/test/java/org/apache/uima/jcas/impl/JCasHashMapTest.java
Modified: uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/jcas/impl/JCasHashMap.java
URL: http://svn.apache.org/viewvc/uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/jcas/impl/JCasHashMap.java?rev=1584373&r1=1584372&r2=1584373&view=diff
==============================================================================
--- uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/jcas/impl/JCasHashMap.java (original)
+++ uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/jcas/impl/JCasHashMap.java Thu Apr 3 20:14:33 2014
@@ -76,7 +76,7 @@ public class JCasHashMap {
private final boolean useCache;
- private int indexOfLastFreeCell;
+ private boolean secondTimeShrinkable = false;
// for testing only:
int getbitsMask() {return bitsMask;}
@@ -110,15 +110,34 @@ public class JCasHashMap {
}
// cleared when cas reset
+ // storage management:
+ // shrink if current number of entries
+ // wouldn't trigger an expansion if the size was reduced by 1/2
public void clear() {
if (!this.useCache) {
return;
}
- size = 0;
- if (table.length >>> 4 > initialCapacity) {
- newTable(table.length >>> 1); // shrink table
- return;
+ // see if size is less than the 1/2 size that triggers expansion
+ if (size < (sizeWhichTriggersExpansion >>> 1)) {
+ // if 2nd time then shrink by 50%
+ // this is done to avoid thrashing around the threshold
+ if (secondTimeShrinkable) {
+ secondTimeShrinkable = false;
+ final int newCapacity = Math.max(initialCapacity, table.length >>> 1);
+ if (newCapacity < table.length) {
+ newTable(newCapacity); // shrink table by 50%
+ } else { // don't shrink below minimum
+ Arrays.fill(table, null);
+ }
+ size = 0;
+ return;
+ } else {
+ secondTimeShrinkable = true;
+ }
+ } else {
+ secondTimeShrinkable = false; // reset this to require 2 triggers in a row
}
+ size = 0;
Arrays.fill(table, null);
}
@@ -126,7 +145,6 @@ public class JCasHashMap {
if (!this.useCache) {
return null;
}
-
int probeAddr = hashInt(key);
int probeDelta = 1;
FeatureStructureImpl maybe = table[probeAddr];
@@ -142,14 +160,14 @@ public class JCasHashMap {
histogram[Math.min(histogram.length - 1, nbrProbes)]++;
maxProbe = Math.max(maxProbe, nbrProbes);
}
- indexOfLastFreeCell = (maybe == null) ? probeAddr : -1;
+ // doesn't work - requires no intervening get between save and use
+ // and user code running in readObject() of create instance of JCas cover object
+ // *could* do something here.
+// indexOfLastFreeCell = (maybe == null) ? probeAddr : -1;
return maybe;
}
- public void findEmptySlot(int key) {
- if (!this.useCache) {
- return;
- }
+ private int findEmptySlot(int key) {
int probeAddr = hashInt(key);
int probeDelta = 1;
while (null != table[probeAddr]) {
@@ -162,7 +180,8 @@ public class JCasHashMap {
histogram[Math.min(histogram.length - 1, nbrProbes)]++;
maxProbe = Math.max(maxProbe, nbrProbes);
}
- indexOfLastFreeCell = probeAddr;
+// indexOfLastFreeCell = probeAddr;
+ return probeAddr;
}
/**
@@ -170,21 +189,27 @@ public class JCasHashMap {
* previously used get or findEmptySlot to set the indexOfLastFreeCell
* @param value
*/
- public void putAfterFindingEmptyCell(FeatureStructureImpl value) {
+// public void putAfterFindingEmptyCell(FeatureStructureImpl value) {
+// if (!this.useCache) {
+// return;
+// }
+// if (size >= sizeWhichTriggersExpansion) {
+// increaseSize();
+// findEmptySlot(value.getAddress()); //reset the indexOfLastFreeCell
+// }
+// size++;
+// table[indexOfLastFreeCell] = value;
+// }
+
+ public void put(FeatureStructureImpl value) {
if (!this.useCache) {
return;
}
if (size >= sizeWhichTriggersExpansion) {
- increaseSize();
- findEmptySlot(value.getAddress()); //reset the indexOfLastFreeCell
+ increaseTableCapacity();
}
size++;
- table[indexOfLastFreeCell] = value;
- }
-
- public void put(FeatureStructureImpl value) {
- findEmptySlot(value.getAddress());
- putAfterFindingEmptyCell(value);
+ table[findEmptySlot(value.getAddress())] = value;
}
public int size() {
@@ -220,14 +245,15 @@ public class JCasHashMap {
return h1 & bitsMask;
}
- private void increaseSize() {
+ private void increaseTableCapacity() {
final FeatureStructureImpl [] oldTable = table;
final int oldCapacity = oldTable.length;
int newCapacity = 2 * oldCapacity;
- if (TUNE)
+ if (TUNE) {
System.out.println("Size increasing from " + oldCapacity + " to " + newCapacity);
+ }
newTable(newCapacity);
size = 0;
for (int i = 0; i < oldCapacity; i++) {
@@ -235,7 +261,7 @@ public class JCasHashMap {
if (fs != null) {
put(fs);
}
- }
+ }
}
public void showHistogram() {
Modified: uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/jcas/impl/JCasImpl.java
URL: http://svn.apache.org/viewvc/uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/jcas/impl/JCasImpl.java?rev=1584373&r1=1584372&r2=1584373&view=diff
==============================================================================
--- uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/jcas/impl/JCasImpl.java (original)
+++ uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/jcas/impl/JCasImpl.java Thu Apr 3 20:14:33 2014
@@ -1032,15 +1032,6 @@ public class JCasImpl extends AbstractCa
* @see org.apache.uima.jcas.JCas#putJfsFromCaddr(int, org.apache.uima.cas.FeatureStructure)
*/
public void putJfsFromCaddr(int casAddr, FeatureStructure fs) {
- sharedView.cAddr2Jfs.putAfterFindingEmptyCell((FeatureStructureImpl) fs);
- }
-
- /*
- * (non-Javadoc)
- *
- * @see org.apache.uima.jcas.JCas#putJfsFromCaddr(int, org.apache.uima.cas.FeatureStructure)
- */
- public void putJfsFromCaddrNew(int casAddr, FeatureStructure fs) {
sharedView.cAddr2Jfs.put((FeatureStructureImpl) fs);
}
Modified: uima/uimaj/trunk/uimaj-core/src/test/java/org/apache/uima/jcas/impl/JCasHashMapTest.java
URL: http://svn.apache.org/viewvc/uima/uimaj/trunk/uimaj-core/src/test/java/org/apache/uima/jcas/impl/JCasHashMapTest.java?rev=1584373&r1=1584372&r2=1584373&view=diff
==============================================================================
--- uima/uimaj/trunk/uimaj-core/src/test/java/org/apache/uima/jcas/impl/JCasHashMapTest.java (original)
+++ uima/uimaj/trunk/uimaj-core/src/test/java/org/apache/uima/jcas/impl/JCasHashMapTest.java Thu Apr 3 20:14:33 2014
@@ -23,7 +23,6 @@ import java.util.Random;
import junit.framework.TestCase;
-import org.apache.uima.jcas.JCas;
import org.apache.uima.jcas.cas.TOP;
/**
@@ -86,11 +85,9 @@ public class JCasHashMapTest extends Tes
// }
private void arun(int n) {
- JCasHashMap m = new JCasHashMap(200, true);
+ JCasHashMap m = new JCasHashMap(200, true); // true = do use cache
assertTrue(m.size() == 0);
-
- JCas jcas = null;
-
+
long start = System.currentTimeMillis();
for (int i = 0; i < n; i++) {
final int key = addrs[i];
@@ -98,8 +95,7 @@ public class JCasHashMapTest extends Tes
// FeatureStructureImpl v = m.get(fs.getAddress());
// if (null == v) {
// m.get(7 * i);
- m.findEmptySlot(key);
- m.putAfterFindingEmptyCell(fs);
+ m.put(fs);
// }
}
System.out.format("time for v1 %,d is %,d ms%n",
@@ -109,8 +105,7 @@ public class JCasHashMapTest extends Tes
}
private void arunCk(int n) {
- JCasHashMap m = new JCasHashMap(200, true);
- JCas jcas = null;
+ JCasHashMap m = new JCasHashMap(200, true); // true = do use cache
for (int i = 0; i < n; i++) {
final int key = addrs[i];
@@ -118,8 +113,8 @@ public class JCasHashMapTest extends Tes
// FeatureStructureImpl v = m.get(fs.getAddress());
// if (null == v) {
// m.get(7 * i);
- m.findEmptySlot(key);
- m.putAfterFindingEmptyCell(fs);
+// m.findEmptySlot(key);
+ m.put(fs);
// }
}
@@ -133,5 +128,43 @@ public class JCasHashMapTest extends Tes
}
}
+
+ public void testGrowth() {
+ JCasHashMap m = new JCasHashMap(64, true); // true = do use cache
+ assertTrue(m.size() == 0);
+
+ fill32(m);
+ assertTrue(m.getbitsMask() == 63);
+ m.put(new TOP(addrs[32], null));
+ assertTrue(m.getbitsMask() == 127);
+
+ m.clear();
+ assertTrue(m.getbitsMask() == 127);
+
+ fill32(m);
+ assertTrue(m.getbitsMask() == 127);
+ m.put(new TOP(addrs[32], null));
+ assertTrue(m.getbitsMask() == 127);
+
+ m.clear(); // size is 33, so no shrinkage
+ assertTrue(m.getbitsMask() == 127);
+ m.clear(); // size is 0, so first time shrinkage a possibility
+ assertTrue(m.getbitsMask() == 127); // but we don't shrink on first time
+ m.clear();
+ assertTrue(m.getbitsMask() == 63); // but we don't shrink on first time
+ m.clear();
+ assertTrue(m.getbitsMask() == 63);
+ m.clear();
+ assertTrue(m.getbitsMask() == 63); // don't shrink below minimum
+
+ }
+
+ private void fill32 (JCasHashMap m) {
+ for (int i = 0; i < 32; i++) {
+ final int key = addrs[i];
+ TOP fs = new TOP(key, null);
+ m.put(fs);
+ }
+ }
}