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 2017/01/13 14:34:45 UTC
svn commit: r1778598 - in
/uima/uimaj/branches/experiment-v3-jcas/uimaj-core/src:
main/java/org/apache/uima/jcas/impl/ test/java/org/apache/uima/jcas/impl/
Author: schor
Date: Fri Jan 13 14:34:45 2017
New Revision: 1778598
URL: http://svn.apache.org/viewvc?rev=1778598&view=rev
Log:
[UIMA-5249] remove getReserved call, add putIfAbsent with IntSupplier arg., simplify locking, improve performance
Modified:
uima/uimaj/branches/experiment-v3-jcas/uimaj-core/src/main/java/org/apache/uima/jcas/impl/JCasHashMap.java
uima/uimaj/branches/experiment-v3-jcas/uimaj-core/src/main/java/org/apache/uima/jcas/impl/JCasHashMapSubMap.java
uima/uimaj/branches/experiment-v3-jcas/uimaj-core/src/test/java/org/apache/uima/jcas/impl/JCasHashMapCompareTest.java
uima/uimaj/branches/experiment-v3-jcas/uimaj-core/src/test/java/org/apache/uima/jcas/impl/JCasHashMapTest.java
Modified: uima/uimaj/branches/experiment-v3-jcas/uimaj-core/src/main/java/org/apache/uima/jcas/impl/JCasHashMap.java
URL: http://svn.apache.org/viewvc/uima/uimaj/branches/experiment-v3-jcas/uimaj-core/src/main/java/org/apache/uima/jcas/impl/JCasHashMap.java?rev=1778598&r1=1778597&r2=1778598&view=diff
==============================================================================
--- uima/uimaj/branches/experiment-v3-jcas/uimaj-core/src/main/java/org/apache/uima/jcas/impl/JCasHashMap.java (original)
+++ uima/uimaj/branches/experiment-v3-jcas/uimaj-core/src/main/java/org/apache/uima/jcas/impl/JCasHashMap.java Fri Jan 13 14:34:45 2017
@@ -19,18 +19,20 @@
package org.apache.uima.jcas.impl;
+import java.util.function.IntFunction;
+
import org.apache.uima.internal.util.Misc;
import org.apache.uima.jcas.cas.TOP;
/**
- * Version 2 (2014) of map between CAS addr and JCasCover Objects
+ * Version 3 (2016, for Java 8) of map between id's (ints) JCasCover Objects
*
* Note: in the general case, the cover object may *not* be a JCas one, but rather the general one
* This happens if there is no JCas cover object defined for the type.
*
- * Assumptions: Each addr has a corresponding JCas; it is not
- * permitted to "update" an addr with a different JCas
- * cover class (unless the table is cleared first).
+ * Assumptions: Each addr has a corresponding JCas;
+ * it is permitted to "update" an addr with a different JCas
+ * cover class (use case: low level APIs changing the type of an object)
*
* Table always a power of 2 in size - permits faster hashing
*
@@ -46,20 +48,16 @@ import org.apache.uima.jcas.cas.TOP;
*
* version 1 at load factor .5 ran about 570 ms * 1.x
* (did 2 lookups for fetches if not found,)
- *
- * No "get" method, only getReserve. This method, if it doesn't
- * find the key, eventually finds an empty (null) slot - it then
- * stores a special "reserve" item with the same key value in that slot.
- * Other threads doing getReserve calls, upon encountering this
- * reserve item, wait until the reserve is converted to a
- * real value (a notifyAll happens when this is done), and
- * then the getReserve returns the real item.
- *
- * getReserve calls - when they find the item operate without any locking
- *
+ *
+ * Has standard get method plus a
+ * putIfAbsent method, which if not absent, returns the value gotten.
+ * Value is a IntSupplier, not invoked unless absent.
+ *
* Locking:
+ * get calls which find the element operate without locking.
+ *
* There is one lock used for reading and updating the table
- * -- not used for reading when item found, only if item not found or is reserved
+ * -- not used for reading when item found, only if item not found
*
* Strategy: have 1 outer implementation delegating to multiple inner ones
* number = concurrency level (a power of 2)
@@ -67,11 +65,8 @@ import org.apache.uima.jcas.cas.TOP;
* The hash uses some # of low order bits to address the right inner one.
*
* This table is used to hold JCas cover classes for CAS feature structures.
- * There is one instance of this table associated with each CAS that is using it.
- * <p>
- * The update occurs in the code in JCasGenerated classes, which do:
- * a call to get the value of the map for a key
- * if that is "null", it creates the new JCas cover object, and does a "put" to add the value.
+ * There are potentially multiple instances of this table associated with each CAS that is using it,
+ * when PEARs are involved.
* <p>
* The creation of the new JCas cover object can, in turn, run arbitrary user code,
* which can result in updates to the JCasHashMap which occur before this original update occurs.
@@ -90,21 +85,34 @@ import org.apache.uima.jcas.cas.TOP;
* Locking occurs on the sub-maps; the outer method calls are not synchronized
* 2) The number of sub maps is rounded to a power of 2, to allow the low order bits of the hash of the key
* to be used to pick the map (via masking).
- * 3) A getReserve that results in not-found returns a null, but adds to the table a special reserved element.
- * 3a) This adding may result in table resizing
- * 4) A getReserve that finds a special reserved element, knows that some other thread
- * is in the process of adding an entry for that key, so it waits.
- * 5) A put, if it finds a reserved-for-that-key element, replaces that with the real element,
- * and then does a notifyAll to wake up any threads that were waiting (on this sub-map),
- * and these threads then re-do the get. Multiple threads could be waiting on this, and they will all
- * wake-up.
+ * 3) a put:
+ * 3a) locks
+ * 3b) does a find; if found, updates that, if not, adds new value
+ * 3c) unlocks
+ * 4) a putIfAbsent:
+ * 4a) does a find (not under lock)
+ * - if found returns that (not under lock)
+ * - note: this has a race condition if another thread is updating / changing that slot
+ * -- this only happens for unsupported conditions, so is not checked
+ * -- changing the type of an existing FS while another thread is accessing the CAS
+ * 4b) if not found, locks
+ * 4c) does find again
+ * 4d) if found, return that and release lock
+ * 4e) if not found, eval the creator form and use to set the value, and release lock
+ *
+ * Note: if eval of creator form recursively calls this, that's OK because sync locks can
+ * be recursively gotten and released in a nested way.
+ *
+ * 5) get does a find, if found, returns that.
+ * - if not, get lock, redo search
+ * -- if not resized, start find from last spot. else start from beginning.
+ * - if found, return that (release lock). if not found return null (release lock)
+ *
* <p>
- * All calls are of the getReserved, followed by a put if the getReserved returns null.
- *
- * (Experiment - disabled after no change noted
- * To improve locality of reference, an aux data structure of size to fit in one cache line of a Power7 (128 bytes)
- * caches the latest lookups)
- *
+ * Supports
+ * put(pre-computed-value),
+ * putIfAbsent(value-to-be-computed, as an IntSupplier)
+ * get
*/
public class JCasHashMap {
@@ -274,58 +282,38 @@ public class JCasHashMap {
return (null != oneSubmap) ? oneSubmap : subMaps[hash & concurrencyBitmask];
}
- public TOP getReserve(int key) {
-// for (int i = 0; i < cacheInt.length; i++) {
-// final int vi = cacheInt[i];
-// if (vi == 0) {
-// break;
-// }
-//
-// if (vi == key) {
-// if (MEASURE_CACHE) {
-// cacheHits.incrementAndGet();
-// }
-// TOP fsi = cacheFS[i];
-// if (fsi.getAddress() != key) { // recheck to avoid sync
-// break; // entry was overwritten
-// }
-// return fsi;
-////
-//// if (i != 0) {
-//// // manage lru - measurement showed no significant boost
-//// System.arraycopy(cache, 0, cache, 2, i);
-//// cache[0] = keyI;
-//// cache[1] = r;
-//// }
-//// return r;
-//// }
-// }
-// }
-
-// if (MEASURE_CACHE) {
-// cacheMisses.incrementAndGet(); // includes creates
-// }
+ public TOP putIfAbsent(int key, IntFunction<TOP> creator) {
final int hash = hashInt(key);
- final TOP r = getSubMap(hash).getReserve(key, hash >>> concurrencyLevelBits);
+ final TOP r = getSubMap(hash).putIfAbsent(key, hash >>> concurrencyLevelBits, creator);
+ return r;
+ }
-// if (r != null) {
-// updateCache(key, r);
-// }
+ /**
+ * @param key -
+ * @return the item or null
+ */
+ public TOP get(int key) {
+ final int hash = hashInt(key);
+ final TOP r = getSubMap(hash).get(key, hash >>> concurrencyLevelBits);
return r;
}
-
-// private void updateCache(int key, TOP value) {
-// final int newIdx = cacheNewIndex;
-// cacheNewIndex = (cacheNewIndex == (CACHE_SIZE - 1)) ? 0 : cacheNewIndex + 1;
-// cacheFS[cacheNewIndex] = value; // update this first to avoid putting in the same value multiple times
-// cacheInt[cacheNewIndex] = key;
-// }
+ /**
+ * @param value -
+ * @return previous value or null
+ */
public TOP put(TOP value) {
- final int key = value._id();
-// updateCache(key, value);
+ return put (value._id(), value);
+ }
+
+ /**
+ * @param value -
+ * @param key -
+ * @return previous value or null
+ */
+ public TOP put(int key, TOP value) {
final int hash = hashInt(key);
- return getSubMap(hash).put(key, value, hash >>> concurrencyLevelBits);
+ return getSubMap(hash).put(key, value, hash >>> concurrencyLevelBits);
}
// The hash function is derived from murmurhash3 32 bit, which
@@ -375,8 +363,11 @@ public class JCasHashMap {
return r;
}
- //test case use
- int getApproximateSize() {
+ /**
+ * get the approximate size (subject to multithreading inaccuracies)
+ * @return the size
+ */
+ public int getApproximateSize() {
int s = 0;
for (JCasHashMapSubMap subMap : subMaps) {
synchronized (subMap) {
Modified: uima/uimaj/branches/experiment-v3-jcas/uimaj-core/src/main/java/org/apache/uima/jcas/impl/JCasHashMapSubMap.java
URL: http://svn.apache.org/viewvc/uima/uimaj/branches/experiment-v3-jcas/uimaj-core/src/main/java/org/apache/uima/jcas/impl/JCasHashMapSubMap.java?rev=1778598&r1=1778597&r2=1778598&view=diff
==============================================================================
--- uima/uimaj/branches/experiment-v3-jcas/uimaj-core/src/main/java/org/apache/uima/jcas/impl/JCasHashMapSubMap.java (original)
+++ uima/uimaj/branches/experiment-v3-jcas/uimaj-core/src/main/java/org/apache/uima/jcas/impl/JCasHashMapSubMap.java Fri Jan 13 14:34:45 2017
@@ -21,27 +21,32 @@ package org.apache.uima.jcas.impl;
import java.util.Arrays;
-import java.util.concurrent.locks.Condition;
-import java.util.concurrent.locks.ReentrantLock;
+import java.util.function.IntFunction;
+import org.apache.uima.internal.util.Misc;
import org.apache.uima.jcas.cas.TOP;
+/**
+ * Part of the JCasHashMap.
+ * There are multiple instances of this class, one per concurrancy level
+ */
class JCasHashMapSubMap {
// set to true to collect statistics for tuning
// you have to also put a call to jcas.showJfsFromCaddrHistogram() at the end of the run
private static final boolean TUNE = JCasHashMap.TUNE;
-
+ // info kept per probe: the address, and the current "delta"
+ // the delta is the one to use to go to the next "probe" address
+ // it starts at 1, and goes up by 1 to 23 (a prime)
+ // These are kept in thread local constants, one per thread.
private static final int PROBE_ADDR_INDEX = 0;
private static final int PROBE_DELTA_INDEX = 1;
+
static final ThreadLocal<int[]> probeInfoGet = new ThreadLocal<int[]>() {
protected int[] initialValue() { return new int[2]; } };
- static final ThreadLocal<int[]> probeInfoPut = new ThreadLocal<int[]>() {
- protected int[] initialValue() { return new int[2]; } };
-
static final ThreadLocal<int[]> probeInfoPutInner = new ThreadLocal<int[]>() {
protected int[] initialValue() { return new int[2]; } };
@@ -51,11 +56,16 @@ class JCasHashMapSubMap {
int maxProbeAfterContinue = 0;
int continues = 0;;
- private final ReentrantLock lock = new ReentrantLock();
- private final Condition lockCondition = lock.newCondition();
+ /**
+ * This lock is sometimes held by put, putIfAbsent, get, clear
+ * - not held if putIfAbsent or get find existing (non-reserve) item
+ * -- assumes no "remove" operation
+ */
+ private final Object synclock = new Object();
private int sizeWhichTriggersExpansion;
- int size; // number of elements in the table
+ int size; // number of elements in the table
+
volatile TOP [] table;
private boolean secondTimeShrinkable = false;
@@ -88,17 +98,18 @@ class JCasHashMapSubMap {
}
private void incrementSize() {
- assert(lock.getHoldCount() > 0);
- if (size >= sizeWhichTriggersExpansion) {
- increaseTableCapacity();
- }
- size++;
+// synchronized(synclock) { // guaranteed by caller
+ // assert(lock.getHoldCount() > 0);
+ if (size >= sizeWhichTriggersExpansion) {
+ increaseTableCapacity();
+ }
+ size++;
+// }
}
// Does size management - shrinking overly large tables after the 2nd time
void clear() {
- lock.lock();
- try {
+ synchronized(synclock) {
// see if size is less than the 1/2 size that triggers expansion
if (size < (sizeWhichTriggersExpansion >>> 1)) {
// if 2nd time then shrink by 50%
@@ -121,14 +132,13 @@ class JCasHashMapSubMap {
}
size = 0;
Arrays.fill(table, null);
- } finally {
- lock.unlock();
- }
+ }
}
/**
+ * find a real item or a reserve item, matching the key
* Can be called under lock or not.
- * It gets a ref to the current value of table, and then searches that int array.
+ * Using a ref to the current value of table, searches that int array.
* If, during the search, the table is resized, it continues using the
* ** before the resize ** int array referenced by localTable
* The answer will only be OK if the key is found for a real value.
@@ -137,70 +147,90 @@ class JCasHashMapSubMap {
* @param key -
* @param hash -
* @param probeInfo - used to get/receive multiple int values;
- * 0: (in/out) startProbe or -1,
+ * 0: (in/out) startProbe or -1; -1 starts at the hash & bitMask
* 1: (in/out) probeDelta (starts at 1)
* @return the probeAddr in original table (which might have been resized)
*/
private TOP find(final TOP[] localTable, final int key, final int hash, final int[] probeInfo) {
- final int bitMask = localTable.length - 1;
- final int startProbe = probeInfo[PROBE_ADDR_INDEX];
- final int probeAddr = (startProbe < 0) ? (hash & bitMask) : startProbe;
- final TOP m = localTable[probeAddr];
- // fast paths
- if (m == null) {
- // not in table
- setProbeInfo(probeInfo, probeAddr, 0);
- return m; // returns null
- }
+ int nbrProbes = 1; // for histogram
+ final int localTblLength = localTable.length;
+ final int bitMask = localTblLength - 1;
+
+ final int startProbe = probeInfo[PROBE_ADDR_INDEX];
+ final boolean isInitialProbe = startProbe == -1;
+ final boolean isContinue = TUNE && !isInitialProbe;
+ int probeAddr = isInitialProbe ? (hash & bitMask) : startProbe;
- if (m.getAddress() == key) {
- setProbeInfo(probeInfo, probeAddr, 0);
- if (TUNE) {
- updateHistogram(1, probeInfo[PROBE_ADDR_INDEX] != -1);
- }
- return m;
+ int probeDelta = probeInfo[PROBE_DELTA_INDEX];
+ //debug
+ if (probeDelta <= 0) {
+ System.out.println("debug");
}
+ assert probeDelta > 0;
- return find2(localTable, key, probeInfo, probeAddr);
- }
+ // Next modification is overall, slower (very slightly)
+
+// int initialAdj = 0;
+// if (probeDelta == 1) {
+// // This is an attempt to reduce collision chain clustering for things that hash to
+// // the same spot, by slightly varying the starting delta
+// // xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx
+// // x xxxx xxxx xxxx xxxx xxxx xxxx xxxx zzz after >>> concurrencyLevelBits eg 3
+// // | || 3 bits for randomizing
+// final int shiftAmt = 32 - concurrencyLevelBits // number of significant bits
+// - 3; // 3 gives low order 3 bits, a number from 0 to 7
+// initialAdj = (hash >>> shiftAmt);
+// }
+
+ TOP m = localTable[probeAddr]; // first probe doesn't add delta, facilitates restarting after acquiring lock
- private TOP find2(final TOP[] localTable, final int key, final int[] probeInfo, int probeAddr) {
- final boolean isContinue = TUNE && (probeInfo[PROBE_ADDR_INDEX] != -1);
- final int bitMask = localTable.length - 1;
-// assert((startProbe < 0) ? probeInfo[PROBE_DELTA_INDEX] == 1 : true);
- int probeDelta = probeInfo[PROBE_DELTA_INDEX];
- int nbrProbes = 2;
- probeAddr = bitMask & (probeAddr + (probeDelta++));
- TOP m = localTable[probeAddr];
-
- while (null != m) { // loop to traverse bucket chain
- if (m.getAddress() == key) {
- setProbeInfo(probeInfo, probeAddr, 0);
+ while (true) {
+ if (m == null) {
+ // not in table
+ setProbeInfo(probeInfo, probeAddr, probeDelta);
+ return null;
+ }
+
+ if (m._id() == key) {
+ setProbeInfo(probeInfo, probeAddr, probeDelta);
if (TUNE) {
updateHistogram(nbrProbes, isContinue);
}
return m;
}
- nbrProbes++;
- probeAddr = bitMask & (probeAddr + (probeDelta++));
+ if (TUNE) {
+ nbrProbes++;
+ if (nbrProbes > localTblLength) {
+ Misc.internalError();
+ }
+ }
+ probeAddr = bitMask & (probeAddr + probeDelta
+// + initialAdj
+ );
+// initialAdj = 0;
m = localTable[probeAddr];
+
+ if (probeDelta < 11) { // a prime
+ // insures all possible slots in the table are probed,
+ // and improves locality of reference (saw measurable improvement)
+ probeDelta ++;
+ }
}
- setProbeInfo(probeInfo, probeAddr, probeDelta);
- return m; // returns null
}
-
+
private void updateHistogram(int nbrProbes, boolean isContinue) {
- /* LOCK if not already, to update stats */
- final boolean needUnlock;
- if (!lock.isHeldByCurrentThread()) {
- lock.lock();
- needUnlock = true;
- } else {
- needUnlock = false;
- }
+ synchronized(synclock) {
+// /* LOCK if not already, to update stats */
+// final boolean needUnlock;
+// if (!lock.isHeldByCurrentThread()) {
+// lockit();
+// needUnlock = true;
+// } else {
+// needUnlock = false;
+// }
- try {
+// try {
histogram[nbrProbes] += 1;
if (maxProbe < nbrProbes) {
maxProbe = nbrProbes;
@@ -211,139 +241,306 @@ class JCasHashMapSubMap {
}
continues ++;
}
- } finally {
- if (needUnlock) {
- lock.unlock();
- }
+// } finally {
+// if (needUnlock) {
+// lock.unlock();
+// }
}
}
/**
- * Gets a value, but if the value isn't there, it reserves the slot where it will go
- * with a new instance where the key matches, but the _casView is null.
+ * If an entry isn't already present for this key,
+ * calls a Supplier to create a value and puts it into the table.
+ * otherwise, doesn't call the Supplier and returns the already present value.
+ *
+ * If the key isn't present, gets a lock, and
+ * (partially, as necessary) redoes the find.
+ * - assert key still not present.
+ * - add a "reserve" for the slot where it will go
+ * -- reserve is a pseudo FS with a matching key, but with null _casView
+ * - release the lock
+ * -- eval the creator to create the item (may cause table to be updated)
+ * - require the lock
+ * - if resized, redo the find() till find the reserved item, and replace it with value.
+ * - if not resized, replace the prev reserved spot.
*
- * Threading: not synchronized for main path where get is finding an element.
- * Since elements are never updated, there is no race if an element is found.
+ * Threading: not synchronized for main path where finding the element (if already in table).
+ * Since elements are never updated, there is no race if an element is found, except for
+ * table being resized.
* And it doesn't matter if the table is resized (if the element is found).
- * If it is not found, or a reserve is found, need to get the lock, and
- * start over if resized, or
- * continue from reserved or null spot if not
- *
- * @param key - the addr in the heap
+ *
+ * @param key - the id to use as the key
* @param hash - the hash that was already computed from the key
- * @return - the found fs, or null
+ * @param creatorFromKey - the function to call to create the item.
+ * @return - the found fs in the table with the same key, or the newly created item.
*/
- TOP getReserve(final int key, final int hash) {
+
+ TOP putIfAbsent(final int key, final int hash, final IntFunction<TOP> creatorFromKey) {
- boolean isLocked = false;
final int[] probeInfo = probeInfoGet.get();
- try {
-
- retry:
- while (true) { // loop back point after locking against updates, to re-traverse the bucket chain from the beginning
- resetProbeInfo(probeInfo);
- final TOP m;
- final TOP[] localTable = table;
-
- if (isReal(m = find(localTable, key, hash, probeInfo))) {
- return m; // fast path for found item
- }
-
- // is reserve or null. Redo or continue search under lock
- // need to do this for reserve-case because otherwise, could
- // wait, but notify could come before wait - hence, wait forever
- if (!isLocked) {
- lock.lock();
- isLocked = true;
- }
- /*****************
- * LOCKED *
- *****************/
- final TOP[] localTable3;
- if (localTable != table) {
- // redo search from top, because table resized
- resetProbeInfo(probeInfo);
- localTable3 = table;
- } else {
- localTable3 = localTable;
- }
-// // re acquire the FeatureStructure m, because another thread could change it before the lock got acquired
-// final TOP m2 = localTable[probeInfo[PROBE_ADDR_INDEX]];
-// if (isReal(m2)) {
-// return m2; // another thread snuck in before the lock and switched this
+
+ // not locked
+
+ resetProbeInfo(probeInfo);
+ TOP[] localTable = table;
+ TOP m = find(table, key, hash, probeInfo);
+
+ if (m != null) {
+ if (!m._isJCasHashMapReserve()) {
+ return m;
+ }
+
+// // another thread is in the process of setting this value
+// // wait for it and return it
+// synchronized(synclock) {
+// if (localTable == table) { table wasn't resized
+// return
// }
+// }
+// return waitForReserve(localTable, key, hash, probeInfo);
+ }
+
+ synchronized(synclock) {
+// lockit();
+// boolean isLocked = true;
+//
+// try {
+
+ // locked
+// localTable = table; // in case table was updated, to get updated values into localTable
+ m = re_find(localTable, key, hash, probeInfo);
+ if (m != null) {
+ assert !m._isJCasHashMapReserve();
+ return m;
+ }
+// }
+// System.out.println("debug never get here");
+// throw new RuntimeException();
+// lock.unlock();
+// isLocked = false;
+// return waitForReserve(localTable, key, hash, probeInfo);
+
+
+ /*************
+ * RESERVE *
+ *************/
+ // is null. Reserve this slot to prevent other "putIfAbsent" calls for some other key
+ // from using this slot. This could happen when the createFromKey.apply is called,
+ // since arbitrary Java code can run here (on the same thread). Other threads are
+ // blocked due to synclock.
+
+ TOP reserve = TOP._createJCasHashMapReserve(key);
+ table[probeInfo[PROBE_ADDR_INDEX]] = reserve;
+ localTable = table; // to see if table gets resized.
+ int saved_reserved_index = probeInfo[PROBE_ADDR_INDEX]; // because the creator.get() call might recursively invoke this
+
+ incrementSize();
+
+// assert lock.isLocked();
+// lock.unlock();
+
+ // may recursively invoke this method, may throw exception
+ m = creatorFromKey.apply(key);
+
+ // System.out.println("debug waiting to reacquire lock after creator." + Thread.currentThread().getName());
+// lockit();
+ // System.out.println("debug after reacquire lock after creator." + Thread.currentThread().getName());
+
+ if (localTable == table) {
- // note: localTable not used from this point, unless reset
- // note: this "find" either finds from the top (if size changed) or finds from current spot.
- final TOP m2 = find(localTable3, key, hash, probeInfo);
- if (isReal(m2)) {
- return m2; // fast path for found item
- }
-
- while (isReserve(m2)) {
- final TOP[] localTable2 = table; // to see if table gets resized
- // can't wait on reserved item because would need to do lock.unlock() followed by wait, but
- // inbetween these, another thread could already do the notify.
- try {
- /**********
- * WAIT *
- **********/
- lockCondition.await(); // wait on object that needs to be unlocked
- } catch (InterruptedException e) {
- }
-
- // at this point, the lock was released, and re-aquired
- if (localTable2 != table) { // table was resized
- continue retry;
- }
- final TOP m3 = localTable2[probeInfo[PROBE_ADDR_INDEX]];
- if (isReserve(m3)) {
- continue; // case = interruptedexception && no resize && not changed to real, retry
- }
- return m3; // return real item
- }
+ assert table[saved_reserved_index] == reserve;
+ table[saved_reserved_index] = m;
+// debugcheck(saved_reserved_index);
- /*************
- * RESERVE *
- *************/
- // is null. Reserve this slot to prevent other "getReserved" calls for this same instance from succeeding,
- // causing them to wait until this slot gets filled in with a FS value
- // Use table, not localTable, because resize may have occurred
- table[probeInfo[PROBE_ADDR_INDEX]] = TOP._createJCasHashMapReserve(key);
- incrementSize();
- return null;
- }
- } finally {
- if (isLocked) {
- lock.unlock();
+ } else {
+ resetProbeInfo(probeInfo);
+ TOP r = find(table, key, hash, probeInfo);
+ assert isReserve(r);
+// assert r == null;
+// assert r._id() == key;
+ table[probeInfo[PROBE_ADDR_INDEX]] = m; // set real value
+// debugcheck(probeInfo[PROBE_ADDR_INDEX]);
}
+// } finally {
+// if (isLocked) {
+// if (notifyAllNeeded.getAndSet(false)) { // set must be done under lock, test must be done before unlock
+// lock.unlock(); // must be done outside of syncForWait
+// synchronized (syncForWait) {
+// syncForWait.notifyAll(); // in case waiting on resolution of Reserved
+// }
+// } else {
+// lock.unlock();
+// }
+// }
}
+ return m;
}
+
+// private void debugcheck(int i) {
+// TOP v = table[i];
+// TOP b = (i > 1) ? table[i - 1] : null;
+// TOP a = (i < table.length - 1) ? table[i + 1] : null;
+// if (b != null && v._id() == b._id()) {
+// System.out.println("debug");
+// }
+// if (a != null && v._id() == a._id()) {
+// System.out.println("debug");
+// }
+// }
+
+
+ // got a reserve - just wait for it
+ // may need to loop this because lock in thread holding the reserve is temporarily released
+ // when running the creator code
+// private TOP waitForReserve(TOP[] localTable, int key, int hash, int[] probeInfo) {
+// TOP m;
+// lockit(); // serves to wait for reserve to finish
+// try {
+// if (table == localTable) {
+// m = table[probeInfo[PROBE_ADDR_INDEX]];
+// } else {
+// resetProbeInfo(probeInfo);
+// m = find(table, key, hash, probeInfo);
+// }
+// assert m != null;
+// if (!m._isJCasHashMapReserve()) {
+// return m;
+// }
+//
+// // need to wait for reserve to clear
+// System.out.println("debug never get here");
+// throw new RuntimeException();
+//// while (true) {
+////// notifyAllNeeded.set(true);
+//// synchronized (syncForWait) {
+//// try {
+//// lock.unlock();
+//// syncForWait.wait();
+//// } catch (InterruptedException e) {
+//// }
+//// }
+//// lockit();
+////
+//// if (table == localTable) {
+//// m = table[probeInfo[PROBE_ADDR_INDEX]];
+//// } else {
+//// resetProbeInfo(probeInfo);
+//// m = find(table, key, hash, probeInfo);
+//// }
+//// assert m != null;
+//// if (!m._isJCasHashMapReserve()) {
+//// break;
+//// }
+//// // otherwise, loop around, got a spurious wakeup.
+//// }
+//// return m;
+// } finally {
+//// if (lock.getHoldCount() > 1) {
+//// System.out.println("debug");
+//// }
+// lock.unlock();
+// }
+////
+//// // start the sleep at 1 microsec, incr by 2x each time around the loop
+//// if (i > 10_000_000_000L) {
+//// throw new RuntimeException("Reserve not obtained in more than 10 seconds");
+//// }
+//// i = i * 2;
+//// long d = System.nanoTime();
+//// while (true) {
+//// try {
+//// Thread.sleep((int)(i / 1000000), (int)(i % 1000000)); // better than yield, which might be ignored?
+//// } catch (InterruptedException e) {
+//// }
+//// if (System.nanoTime() - d > i) break;
+////// System.out.println("debug retry nanotime - start = " + (System.nanoTime() - d));
+//// }
+////// System.out.println("debug i = " + i);
+//// }
+// }
+
+ /**
+ * Puts a new value into the table, replacing an existing one if there is an entry already,
+ * or adding a new entry
+ *
+ * Starts by acquiring the lock.
+ *
+ * @param key - the id to use as the key
+ * @param hash - the hash that was already computed from the key
+ * @param creator - the new value
+ * @return - the previous fs in the table with the same key, or null
+ */
+ TOP put(final int key, final TOP value, final int hash) {
+
+ final int[] probeInfo = probeInfoGet.get();
+ resetProbeInfo(probeInfo);
+
+ synchronized(synclock) {
+// lockit();
+ TOP previous;
+// try {
+ previous = find(table, key, hash, probeInfo);
+
+ if (previous != value) {
+ table[probeInfo[PROBE_ADDR_INDEX]] = value;
+// debugcheck(probeInfo[PROBE_ADDR_INDEX]);
+ }
+ if (previous == null) {
+ incrementSize();
+ }
+// } finally {
+// lock.unlock();
- TOP put(int key, TOP value, int hash) {
+ return previous;
+ }
+ }
+
+ /**
+ * Gets a value.
+ *
+ * Threading: not synchronized for main path where get is finding an element.
+ * Since elements are never updated, there is no race if an element is found.
+ * And it doesn't matter if the table is resized (if the element is found).
+ * If it is not found, need to get the lock in order to get memory synch, and
+ * start over if resized, or
+ * continue from reserved or null spot if not
+ *
+ * @param key - the addr in the heap
+ * @param hash - the hash that was already computed from the key
+ * @return - the found fs, or null
+ */
+ TOP get(final int key, final int hash) {
- lock.lock();
- try {
- final int[] probeInfo = probeInfoPut.get();
- resetProbeInfo(probeInfo);
- final TOP[] localTable = table;
- final TOP prevValue = find(localTable, key, hash, probeInfo);
- localTable[probeInfo[PROBE_ADDR_INDEX]] = value;
- if (isReserve(prevValue)) {
- lockCondition.signalAll();
- // dont update size - was updated when reserve was added
- return null;
- } else if (prevValue == null) {
- incrementSize(); // otherwise, adding a new value
- } // else updating an existing value - don't increment the size
- return prevValue;
- } finally {
- lock.unlock();
+ final int[] probeInfo = probeInfoGet.get();
+ resetProbeInfo(probeInfo);
+
+ TOP[] localTable = table;
+ TOP m = find(localTable, key, hash, probeInfo);
+ if (m != null) {
+ if (!isReserve(m)) {
+ return m;
+ }
+// } else {
+// return waitForReserve(localTable, key, hash, probeInfo);
+// }
}
- }
-
+
+
+ // redo under lock to get memory synch
+ synchronized(synclock) {
+// lockit();
+// try {
+ m = re_find(localTable, key, hash, probeInfo);
+// } finally {
+// lock.unlock();
+ }
+// if (m != null) {
+// assert isReal(m);
+// }
+ return m;
+ }
/**
* Only used to fill in newly expanded table
@@ -353,9 +550,10 @@ class JCasHashMapSubMap {
* @param hash -
*/
- private void putInner(int key, TOP value, int hash) {
- assert(lock.getHoldCount() > 0);
- final int[] probeInfo = probeInfoPutInner.get();
+ // called under lock
+ private void putInner(int key, TOP value, int hash, int[] probeInfo) {
+// assert(lock.getHoldCount() > 0);
+
resetProbeInfo(probeInfo);
final TOP[] localTable = table;
@@ -375,12 +573,13 @@ class JCasHashMapSubMap {
System.out.println("Capacity increasing from " + oldCapacity + " to " + newCapacity);
}
table = newTableKeepSize(newCapacity);
+ final int[] probeInfo = probeInfoPutInner.get();
for (int i = 0; i < oldCapacity; i++) {
TOP fs = oldTable[i];
if (fs != null) {
- final int key = fs.getAddress();
+ final int key = fs._id();
final int hash = JCasHashMap.hashInt(key);
- putInner(key, fs, hash >>> concurrencyLevelBits);
+ putInner(key, fs, hash >>> concurrencyLevelBits, probeInfo);
}
}
}
@@ -389,9 +588,9 @@ class JCasHashMapSubMap {
return m != null && m._isJCasHashMapReserve();
}
- private static boolean isReal(TOP m) {
- return m != null && !m._isJCasHashMapReserve();
- }
+// private static boolean isReal(TOP m) {
+// return m != null && !m._isJCasHashMapReserve();
+// }
private static void resetProbeInfo(int[] probeInfo) {
probeInfo[PROBE_ADDR_INDEX] = -1;
@@ -402,7 +601,71 @@ class JCasHashMapSubMap {
probeInfo[PROBE_ADDR_INDEX] = probeAddr;
probeInfo[PROBE_DELTA_INDEX] = probeDelta;
}
-
+
+ private TOP re_find(TOP[] localTable, int key, int hash, int[] probeInfo) {
+ if (localTable != table) {
+ resetProbeInfo(probeInfo);
+ }
+ return find(table, key, hash, probeInfo);
+ }
+
+// private void lockit() {
+// // might have recursive locking on same thread if creator invokes this recursively
+//// if (lock.getHoldCount() > 0) {
+//// System.out.println("debug");
+//// }
+//// assert lock.getHoldCount() == 0;
+// lock.lock();
+// }
+// private TOP locked_find(int key, int hash, int[] probeInfo) {
+//
+// retry_find:
+// while (true) { // loop context while finding a reserved element
+// final TOP[] localTable = table;
+//
+// TOP m = find(localTable, key, hash, probeInfo);
+// if (isReal(m)) {
+// return m; // fast path for found item
+// }
+//
+// while (isReserve(m)) {
+// // is for another FS, and could occur in use case:
+// // the create-fs code creates other FSs
+// // also in test case,
+//
+// // get here when another thread has a reserve pending on this slot
+// // assert must be for another key.
+// final TOP[] localTable2 = table; // save ref to see if table gets resized
+// // can't wait on reserved item because would need to do lock.unlock() followed by wait, but
+// // inbetween these, another thread could already do the notify.
+// try {
+// /**********
+// * WAIT *
+// **********/
+// lockCondition.await(); // wait on the lock, lockCondition is the condition for "lock" object.
+// } catch (InterruptedException e) {
+// }
+//
+// // at this point, the lock was released, and re-aquired
+// if (localTable2 != table) { // table was resized
+// resetProbeInfo(probeInfo); // redo find from the top
+// continue retry_find;
+// }
+// final TOP m3 = localTable2[probeInfo[PROBE_ADDR_INDEX]];
+// if (isReserve(m3)) {
+// // still reserved - wait some more.
+// // case = interruptedexception && no resize && not changed to real, retry
+// // not continuing from the top, but from the current probe
+// // redoes the wait
+// continue;
+// }
+// }
+//
+// // is not reserved anymore, and no table size change. re-find from here
+// m = find(table, key, hash, probeInfo);
+// assert m == null;
+// }
+// }
}
Modified: uima/uimaj/branches/experiment-v3-jcas/uimaj-core/src/test/java/org/apache/uima/jcas/impl/JCasHashMapCompareTest.java
URL: http://svn.apache.org/viewvc/uima/uimaj/branches/experiment-v3-jcas/uimaj-core/src/test/java/org/apache/uima/jcas/impl/JCasHashMapCompareTest.java?rev=1778598&r1=1778597&r2=1778598&view=diff
==============================================================================
--- uima/uimaj/branches/experiment-v3-jcas/uimaj-core/src/test/java/org/apache/uima/jcas/impl/JCasHashMapCompareTest.java (original)
+++ uima/uimaj/branches/experiment-v3-jcas/uimaj-core/src/test/java/org/apache/uima/jcas/impl/JCasHashMapCompareTest.java Fri Jan 13 14:34:45 2017
@@ -45,6 +45,9 @@ public class JCasHashMapCompareTest exte
// private static final int SIZEm1 = SIZE - 1;
// private JCasHashMap jhm;
private ConcurrentMap<Integer, TOP> concurrentMap;
+
+ private long custAcc = 0;
+ private long custNbr = 0;
public void testComp() throws Exception {
@@ -52,21 +55,29 @@ public class JCasHashMapCompareTest exte
int numberOfThreads = Utilities.numberOfCores;
numberOfThreads = Math.min(8, Utilities.nextHigherPowerOf2(numberOfThreads)); // avoid too big slowdown on giant machines.
System.out.format("test JCasHashMapComp with %d threads%n", numberOfThreads);
- runCustom(numberOfThreads);
+ for (int i = 0; i < 3; i++) {
+// for (int j = 0; j < 10000; j++) {
+// for (int j = 0; j < 10000; j++) {
+ runCustom(numberOfThreads);
+// }
+// for (int j = 0; j < 10000; j++) {
runConCur(numberOfThreads);
+// }
+// }
runCustom(numberOfThreads*2);
runConCur(numberOfThreads*2);
runCustom(numberOfThreads*4);
runConCur(numberOfThreads*4);
+
// stats("custom", runCustom(numberOfThreads)); // not accurate, use yourkit retained size instead
// stats("concur", runConCur(numberOfThreads));
Set<Integer> ints = new HashSet<Integer>();
for (Entry<Integer, TOP> e : concurrentMap.entrySet()) {
assertFalse(ints.contains(Integer.valueOf(e.getKey())));
- assertEquals(e.getValue().getAddress(), (int)(e.getKey()));
+ assertEquals(e.getValue()._id(), (int)(e.getKey()));
ints.add(e.getKey());
}
-
+ }
// System.out.println("Found " + i);
// launch yourkit profiler and look at retained sizes for both
@@ -90,38 +101,39 @@ public class JCasHashMapCompareTest exte
for (int i = 0; i < sizeOfTest*threadNumber; i++) {
final int key = hash(i, threadNumber) / 2;
final Object waiter = waiters[key & (numberOfWaiters - 1)];
- TOP fs = m.putIfAbsent(key, TOP._createJCasHashMapReserve(key));
- while (fs != null && fs._isJCasHashMapReserve()) {
- // someone else reserved this
-
- // wait for notify
- synchronized (waiter) {
- fs = m.get(key);
- if (fs._isJCasHashMapReserve()) {
- try {
- waiter.wait();
- } catch (InterruptedException e) {
- }
- }
- }
- }
-
-// TOP fs = m.get(key);
- if (null == fs) {
-// puts ++;
- TOP prev = m.put(key, TOP._createSearchKey(key));
- if (prev._isJCasHashMapReserve()) {
- synchronized (waiter) {
- waiter.notifyAll();
- }
- }
-// puts --; // someone beat us
-// founds ++;
- }
-
- }
-// System.out.println("concur Puts = " + puts + ", founds = " + founds);
- }
+ TOP newFs = TOP._createSearchKey(key);
+ TOP fs = m.putIfAbsent(key, newFs);
+// while (fs != null && fs._isJCasHashMapReserve()) {
+// // someone else reserved this
+//
+// // wait for notify
+// synchronized (waiter) {
+// fs = m.get(key);
+// if (fs._isJCasHashMapReserve()) {
+// try {
+// waiter.wait();
+// } catch (InterruptedException e) {
+// }
+// }
+// }
+// }
+//
+//// TOP fs = m.get(key);
+// if (null == fs) {
+//// puts ++;
+// TOP prev = m.put(key, TOP._createSearchKey(key));
+// if (prev._isJCasHashMapReserve()) {
+// synchronized (waiter) {
+// waiter.notifyAll();
+// }
+// }
+//// puts --; // someone beat us
+//// founds ++;
+// }
+//
+ } // end of for loop
+//// System.out.println("concur Puts = " + puts + ", founds = " + founds);
+ }
};
long start = System.currentTimeMillis();
MultiThreadUtils.tstMultiThread("JCasHashMapTestCompConcur", numberOfThreads, 10, run2isb,
@@ -129,7 +141,7 @@ public class JCasHashMapCompareTest exte
public void run() {
m.clear();
}});
- System.out.format("JCasCompTest - using ConcurrentHashMap, threads = %d, time = %,f seconds%n", numberOfThreads, (System.currentTimeMillis() - start) / 1000.f);
+ System.out.format("JCasCompTest - using ConcurrentHashMap, threads = %d, time = %,f seconds%n", numberOfThreads, ((double)(System.currentTimeMillis() - start)) / 1000.d);
return m.size();
}
@@ -141,18 +153,18 @@ public class JCasHashMapCompareTest exte
public void call(int threadNumber, int repeatNumber, StringBuilder sb) {
// int founds = 0, puts = 0;
for (int i = 0; i < sizeOfTest*threadNumber; i++) {
- final int key = hash(i, threadNumber
- ) / 2;
+ final int key = hash(i, threadNumber) / 2;
+ m.putIfAbsent(key, TOP::_createSearchKey);
// if (key == 456551)
// System.out.println("debug");
- TOP fs = m.getReserve(key);
+// TOP fs = m.getReserve(key);
- if (null == fs) {
-// puts++;
- m.put(TOP._createSearchKey(key));
- } else {
+// if (null == fs) {
+// puts++
+// m.put(TOP._createSearchKey(key));
+// } else {
// founds ++;
- }
+// }
}
// System.out.println("custom Puts = " + puts + ", founds = " + founds);
}
@@ -163,7 +175,17 @@ public class JCasHashMapCompareTest exte
public void run() {
m.clear();
}});
- System.out.format("JCasCompTest - using JCasHashMap, threads = %d, time = %,f seconds%n", numberOfThreads, (System.currentTimeMillis() - start) / 1000.f);
+ long el = System.currentTimeMillis() - start;
+ if (custNbr == 100) {
+ custNbr = 1;
+ custAcc = el;
+ } else {
+ custAcc += el;
+ custNbr ++;
+ }
+
+
+ System.out.format("JCasCompTest - using JCasHashMap, threads = %d, time = %,f seconds avg = %,f%n", numberOfThreads, ((double)el) / 1000.d, (((double)custAcc)/custNbr) / 1000.d);
m.showHistogram();
return m.getApproximateSize();
}
Modified: uima/uimaj/branches/experiment-v3-jcas/uimaj-core/src/test/java/org/apache/uima/jcas/impl/JCasHashMapTest.java
URL: http://svn.apache.org/viewvc/uima/uimaj/branches/experiment-v3-jcas/uimaj-core/src/test/java/org/apache/uima/jcas/impl/JCasHashMapTest.java?rev=1778598&r1=1778597&r2=1778598&view=diff
==============================================================================
--- uima/uimaj/branches/experiment-v3-jcas/uimaj-core/src/test/java/org/apache/uima/jcas/impl/JCasHashMapTest.java (original)
+++ uima/uimaj/branches/experiment-v3-jcas/uimaj-core/src/test/java/org/apache/uima/jcas/impl/JCasHashMapTest.java Fri Jan 13 14:34:45 2017
@@ -23,6 +23,7 @@ import java.util.Arrays;
import java.util.Random;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;
+import java.util.concurrent.atomic.AtomicBoolean;
import org.apache.uima.internal.util.Misc;
import org.apache.uima.internal.util.MultiThreadUtils;
@@ -51,6 +52,8 @@ public class JCasHashMapTest extends Tes
addrs[ir] = temp;
}
}
+
+ private final AtomicBoolean okToProceed = new AtomicBoolean();
public void testBasic() {
JCasHashMap m;
@@ -102,10 +105,12 @@ public class JCasHashMapTest extends Tes
for (int k = 0; k < 4; k++) {
for (int i = 0; i < SIZE / 4; i++) {
final int key = addrs[random.nextInt(SIZE / 16)];
- TOP fs = m.getReserve(key);
- if (null == fs) {
- m.put(TOP._createSearchKey(key));
- }
+ m.putIfAbsent(key, x -> TOP._createSearchKey(x));
+// TOP fs = m.getReserve(key);
+// if (null == fs) {
+//
+// m.put(TOP._createSearchKey(key));
+// }
}
try {
Thread.sleep(0, random.nextInt(1000));
@@ -127,15 +132,16 @@ public class JCasHashMapTest extends Tes
public void testMultiThreadCompare() throws Exception {
final Random random = new Random();
+ random.setSeed(1234L); // debug
int numberOfThreads = Misc.numberOfCores;
System.out.format("test JCasHashMap with compare with up to %d threads%n", numberOfThreads);
- final ConcurrentMap<Integer, TOP> check =
+ final ConcurrentMap<Integer, TOP> check = // one check map, run on multiple threads
new ConcurrentHashMap<Integer, TOP>(SIZE, .5F, numberOfThreads * 2);
for (int th = 2; th <= numberOfThreads; th *= 2) {
JCasHashMap.setDEFAULT_CONCURRENCY_LEVEL(th);
- final JCasHashMap m = new JCasHashMap(200);
+ final JCasHashMap m = new JCasHashMap(200); // one JCasHashMap run on multiple threads
MultiThreadUtils.Run2isb run2isb = new MultiThreadUtils.Run2isb() {
@@ -143,17 +149,22 @@ public class JCasHashMapTest extends Tes
for (int k = 0; k < 4; k++) {
for (int i = 0; i < SIZE / 4; i++) {
final int key = addrs[random.nextInt(SIZE / 16)];
- TOP fs = m.getReserve(key);
- if (null == fs) {
- fs = TOP._createSearchKey(key);
- check.put(key, fs);
- m.put(fs);
+ final TOP[] createdFS = new TOP[1];
+ TOP fs = m.putIfAbsent(key, x -> {
+ TOP tmp = createdFS[0] = TOP._createSearchKey(x);
+ check.put(key, tmp);
+ return tmp;
+ });
+
+
+ if (createdFS[0] != null) {
+// check.put(key, createdFS[0]);
} else {
TOP fscheck = check.get(key);
if (fscheck == null || fscheck != fs) {
String msg = String.format("JCasHashMapTest miscompare, repeat=%,d, count=%,d key=%,d"
+ ", checkKey=%s JCasHashMapKey=%,d",
- k, i, key, (null == fscheck) ? "null" : Integer.toString(fscheck.getAddress()), fs.getAddress());
+ k, i, key, (null == fscheck) ? "null" : Integer.toString(fscheck._id()), fs._id());
System.err.println(msg);
throw new RuntimeException(msg);
}
@@ -180,12 +191,16 @@ public class JCasHashMapTest extends Tes
}
/**
* Create situation
- * make a set of indexed fs instances, no JCas
- * on multiple threads, simultaneously, attempt to get the jcas cover object for this
- * one getReserve should succeed, but reserve, and the others should "wait".
- * then put
- * then the others should "wakeup" and return the same instance
- *
+// * make a set of indexed fs instances, no JCas
+// * on multiple threads, simultaneously, attempt to get the jcas cover object for this
+// * one getReserve should succeed, but reserve, and the others should "wait".
+// * then put
+// * then the others should "wakeup" and return the same instance
+ * on multiple threads, attempt to putIfAbsent a special search key instance, simultaneously
+ * one thread should succeed, the others should block while the succeeding one is
+ * awaiting an external "go" signal.
+ * Once that go signal happens, the other threads should succeed, and return the
+ * == fs to the first one.
* @throws Exception
*/
public void testMultiThreadCollide() throws Exception {
@@ -208,13 +223,40 @@ public class JCasHashMapTest extends Tes
for (int i = 0; i < numberOfThreads; i++) {
final int finalI = i;
threads[i] = new MultiThreadUtils.ThreadM() {
+ /**
+ * for thread 0 -> nbr of threads -1:
+ * wait,
+ * sleep,
+ * do a putIfAbsent of "fs" - first one will succeed, others should wait till success
+ * set found[thread#] to m.putIfAbsent(hashkey);
+ *
+ * loop above until terminate thread
+ */
public void run() {
while (true) {
+// System.err.println("in loop about to wait4go " + this.getName() );
if (!MultiThreadUtils.wait4go(this)) {
break;
}
MultiThreadUtils.sleep(r.nextInt(500000)); // 0-500 microseconds
- found[finalI] = m.getReserve(hashKey);
+ found[finalI] = m.putIfAbsent(hashKey, k -> {
+ // k is ignored, hashKey is final, the fs returned is constant
+ threads[finalI].utilBoolean.set(true);
+ try {
+ while (true) {
+ try {
+ if (okToProceed.get() == true) {
+ break;
+ }
+ Thread.sleep(5); // 5 milli
+ } catch (InterruptedException e) {
+ }
+ }
+ return fs;
+ } finally {
+ threads[finalI].utilBoolean.set(false);
+ }
+ });
}
}
};
@@ -225,33 +267,42 @@ public class JCasHashMapTest extends Tes
for (int loopCount = 0; loopCount < 10; loopCount ++) {
System.out.println(" JCasHashMap collide loop count is " + loopCount);
- // create threads and start them
+ // release the threads
for (int th = 2; th <= numberOfThreads; th *= 2) {
JCasHashMap.setDEFAULT_CONCURRENCY_LEVEL(th);
Arrays.fill(found, null);
m.clear();
+// System.out.println("debug kickoffthreads");
MultiThreadUtils.kickOffThreads(threads);
- Thread.sleep(20);
- // verify that one thread finished, others are waiting, because of the reserve.
- // this assumes that all the threads got to run.
- int numberWaiting = 0;
- int threadFinished = -1;
- for (int i = 0; i < numberOfThreads; i++) {
- if (threads[i].state == MultiThreadUtils.THREAD_RUNNING) {
- numberWaiting ++;
- } else {
- threadFinished = i;
+ // verify that one thread holds the lock, the others are waiting on that lock
+ int numberWaiting;
+ while (true) { // may take a while for threads to get going
+ Thread.sleep(5);
+ numberWaiting = 0;
+ int threadHoldingLock = -1;
+ for (int i = 0; i < numberOfThreads; i++) {
+ if (threads[i].utilBoolean.get()) {
+ threadHoldingLock = i;
+ } else {
+ numberWaiting ++;
+ }
+ }
+ if (threadHoldingLock != -1) {
+ break;
}
}
-
- assertEquals(numberOfThreads - 1, numberWaiting); // expected 7 but was 8
- m.put(fs);
- found[threadFinished] = fs;
+// System.out.println("debug thread holding lock is " + threadHoldingLock);
+ // all threads except one should be in synch lock wait
+ // one thread should be in wait in while loop.
+ assertEquals(numberOfThreads - 1, numberWaiting);
+
+ okToProceed.set(true);
+// found[threadHoldingLock] = fs;
MultiThreadUtils.waitForAllReady(threads);
-
+ okToProceed.set(false);
// // loop a few times to give enough time for the other threads to finish.
// long startOfWait = System.currentTimeMillis();
// while (System.currentTimeMillis() - startOfWait < 30000) { // wait up to 30 seconds in case of machine stall
@@ -316,11 +367,12 @@ public class JCasHashMapTest extends Tes
long start = System.currentTimeMillis();
for (int i = 0; i < n; i++) {
final int key = addrs[i];
- TOP fs = TOP._createSearchKey(key);
+ m.putIfAbsent(key, k -> TOP._createSearchKey(k));
// TOP v = m.get(fs.getAddress());
// if (null == v) {
// m.get(7 * i);
- m.put(fs);
+// m.getReserve(key);
+// m.put(fs);
// }
}
@@ -337,18 +389,22 @@ public class JCasHashMapTest extends Tes
for (int i = 0; i < n; i++) {
final int key = addrs[i];
- TOP fs = TOP._createSearchKey(key);
+ m.putIfAbsent(key, k -> TOP._createSearchKey(k));
+
+// TOP fs = TOP._createSearchKey(key);
+
// TOP v = m.get(fs.getAddress());
// if (null == v) {
// m.get(7 * i);
// m.findEmptySlot(key);
- m.put(fs);
+// m.getReserve(key);
+// m.put(fs);
// }
}
for (int i = 0; i < n; i++) {
final int key = addrs[i];
- TOP fs = (TOP) m.getReserve(key);
+ TOP fs = (TOP) m.get(key);
if (fs == null) { // for debugging
System.out.println("stop");
}
@@ -374,8 +430,10 @@ public class JCasHashMapTest extends Tes
System.out.print("JCasHashMapTest: after fill to switch point: ");
assertTrue(checkSubsCapacity(m, sub_capacity));
System.out.print("JCasHashMapTest: after 1 past switch point: ");
- int key = addrs[switchpoint + 1];
- m.put(TOP._createSearchKey(key));
+ final int key = addrs[switchpoint + 1];
+ m.putIfAbsent(key, k -> TOP._createSearchKey(k));
+// m.getReserve(key);
+// m.put(TOP._createSearchKey(key));
assertTrue(checkSubsCapacity(m, sub_capacity));
m.clear();
@@ -386,8 +444,11 @@ public class JCasHashMapTest extends Tes
fill(switchpoint, m);
System.out.print("JCasHashMapTest: after fill to switch point: ");
assertTrue(checkSubsCapacity(m, sub_capacity));
- key = addrs[switchpoint + 1];
- m.put(TOP._createSearchKey(key));
+ final int key2 = addrs[switchpoint + 1];
+// m.putIfAbsent(key, k -> TOP._createSearchKey(key2)); // k is ignored
+ m.putIfAbsent(key2, k -> TOP._createSearchKey(k));
+// m.getReserve(key);
+// m.put(TOP._createSearchKey(key));
System.out.print("JCasHashMapTest: after 1 past switch point: ");
assertTrue(checkSubsCapacity(m, sub_capacity));
@@ -446,7 +507,7 @@ public class JCasHashMapTest extends Tes
private String intList(TOP[] a) {
StringBuilder sb = new StringBuilder();
for (TOP i : a) {
- sb.append(i == null ? "null" : i.getAddress()).append(", ");
+ sb.append(i == null ? "null" : i._id()).append(", ");
}
return sb.toString();
}
@@ -454,8 +515,11 @@ public class JCasHashMapTest extends Tes
private void fill (int n, JCasHashMap m) {
for (int i = 0; i < n; i++) {
final int key = addrs[i];
- TOP fs = TOP._createSearchKey(key);
- m.put(fs);
+ m.putIfAbsent(key, k -> TOP._createSearchKey(k));
+//
+// TOP fs = TOP._createSearchKey(key);
+// m.getReserve(key);
+// m.put(fs);
// System.out.format("JCasHashMapTest fill %s%n", intList(m.getCapacities()));
}
}