Author: schor
Date: Wed May 6 17:45:59 2015
New Revision: 1678049
URL: http://svn.apache.org/r1678049
Log:
[UIMA-4381] speed up concurrent mod checking for flat iterators
Added:
uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/Int2IntArrayMapFixedSize.java
Modified:
uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/FSIndexFlat.java
uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/FSIndexRepositoryImpl.java
uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/FeatureStructureImpl.java
uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/Subiterator.java
uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/UnambiguousIteratorImpl.java
uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/text/AnnotationIndex.java
Modified:
uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/FSIndexFlat.java
URL:
http://svn.apache.org/viewvc/uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/FSIndexFlat.java?rev=1678049&r1=1678048&r2=1678049&view=diff
==============================================================================
---
uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/FSIndexFlat.java
(original)
+++
uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/FSIndexFlat.java
Wed May 6 17:45:59 2015
@@ -29,6 +29,7 @@ import java.util.concurrent.atomic.Atomi
import org.apache.uima.cas.FSIterator;
import org.apache.uima.cas.FeatureStructure;
import org.apache.uima.cas.impl.FSIndexRepositoryImpl.IndexIteratorCachePair;
+import org.apache.uima.internal.util.Int2IntArrayMapFixedSize;
import org.apache.uima.jcas.cas.TOP;
/**
@@ -105,7 +106,7 @@ public class FSIndexFlat<T extends Featu
* The inner class implementing the Iterator
* The class can't be static - makes ref to "T" invalid
******************************************** */
- public static class FSIteratorFlat<TI extends FeatureStructure> extends
FSIteratorImplBase<TI> {
+ public static class FSIteratorFlat<TI extends FeatureStructure> extends
FSIteratorImplBase<TI> implements LowLevelIterator {
/**
* iterator's Feature Structure array, points to the instance
* in existence when the iterator was created, from the FSIndex
@@ -158,7 +159,7 @@ public class FSIndexFlat<T extends Featu
throw new NoSuchElementException();
}
final TI fs = ifsa[pos];
- final int typeCode = ((TypeImpl)(fs.getType())).getCode();
+ final int typeCode = ((FeatureStructureImpl)fs).getTypeCode();
if (debugTypeCodeUnstable) {
if ((fs instanceof TOP) && // insures jcas in use
!iicp.subsumes(((TOP)fs).jcasType.casTypeCode, typeCode)) {
@@ -254,62 +255,25 @@ public class FSIndexFlat<T extends Featu
fsIndexFlat.idInfo());
}
- // A special wrapper that is just for getAllIndexed FS
- // Doesn't implement moveTo(fs)
- public LowLevelIterator toLLiterator() {
- return new LowLevelIterator() {
-
- @Override
- public void moveToPrevious() {
- FSIteratorFlat.this.moveToPrevious();
- }
-
- @Override
- public void moveToNext() {
- FSIteratorFlat.this.moveToNext();
- }
-
- @Override
- public void moveToLast() {
- FSIteratorFlat.this.moveToLast();
- }
-
- @Override
- public void moveToFirst() {
- FSIteratorFlat.this.moveToFirst();
- }
-
- @Override
- public void moveTo(int fsRef) {
- throw new UnsupportedOperationException();
- }
-
- @Override
- public int ll_indexSize() {
- throw new UnsupportedOperationException();
- }
-
- @Override
- public LowLevelIndex ll_getIndex() {
- throw new UnsupportedOperationException();
- }
-
- @Override
- public int ll_get() throws NoSuchElementException {
- FeatureStructureImpl fsi = (FeatureStructureImpl)
FSIteratorFlat.this.get();
- return fsi.getAddress();
- }
-
- @Override
- public boolean isValid() {
- return FSIteratorFlat.this.isValid();
- }
-
- @Override
- public Object copy() {
- throw new UnsupportedOperationException();
- }
- };
+ // methods for low level iterator
+ @Override
+ public int ll_get() throws NoSuchElementException {
+ return ((FeatureStructureImpl) get()).getAddress();
+ }
+
+ @Override
+ public void moveTo(int fsRef) {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public int ll_indexSize() {
+ return ifsa.length;
+ }
+
+ @Override
+ public LowLevelIndex ll_getIndex() {
+ throw new UnsupportedOperationException();
}
}
@@ -317,7 +281,7 @@ public class FSIndexFlat<T extends Featu
* A reference to the non-flat shared index iterator cache pair
*/
private final IndexIteratorCachePair<T> iicp;
-
+
/**
* The flattened version of the above, or null
* set under fsaLock
@@ -352,7 +316,7 @@ public class FSIndexFlat<T extends Featu
* These are read on multiple threads to determine if a
* flattened iterator is still valid.
*/
- final int[] indexUpdateCountsResetValues;
+ final Int2IntArrayMapFixedSize indexUpdateCountsResetValues;
/**
* a map from type codes to offsets in indexUpdateCountsResetValues
@@ -386,12 +350,8 @@ public class FSIndexFlat<T extends Featu
*/
public FSIndexFlat(IndexIteratorCachePair<T> iicp) {
this.iicp = iicp;
+
indexUpdateCountsResetValues = iicp.createIndexUpdateCountsAtReset();
-// offset_indexUpdateCountsAtReset = new
Int2IntHashMap(iicp.typeCodes.length);
-// int i = 0;
-// for (int typeCode : iicp.typeCodes) {
-// offset_indexUpdateCountsAtReset.put(typeCode, i++);
-// }
debugTypeCode = iicp.getFsLeafIndex().getTypeCode();
casResetCount = iicp.getCASImpl().getCasResets();
casId = iicp.getCASImpl().getCasId();
@@ -524,7 +484,7 @@ public class FSIndexFlat<T extends Featu
System.out.println(String.format("Detected cas reset while iterating in
%s", idInfo()));
return null;
}
- int topCode = iicp.typeCodes[0];
+ int topCode = iicp.getFsLeafIndex().getTypeCode();
String m;
if (topCode != debugTypeCode || topCode !=
iicp.getFsLeafIndex().getTypeCode()) {
m = String.format("TypeCodesWrong: iicp[0]: %d, original=%d,
leafindex=%d%n",
@@ -570,7 +530,7 @@ public class FSIndexFlat<T extends Featu
void captureIndexUpdateCounts() {
iteratorReorderingCount = 0;
- iicp.captureIndexUpdateCounts(indexUpdateCountsResetValues);
+ iicp.captureIndexUpdateCounts();
if (trace || smalltrace) {
casResetCount = iicp.getCASImpl().getCasResets();
}
Modified:
uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/FSIndexRepositoryImpl.java
URL:
http://svn.apache.org/viewvc/uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/FSIndexRepositoryImpl.java?rev=1678049&r1=1678048&r2=1678049&view=diff
==============================================================================
---
uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/FSIndexRepositoryImpl.java
(original)
+++
uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/FSIndexRepositoryImpl.java
Wed May 6 17:45:59 2015
@@ -20,6 +20,7 @@
package org.apache.uima.cas.impl;
import java.util.ArrayList;
+import java.util.Arrays;
import java.util.BitSet;
import java.util.Collections;
import java.util.Comparator;
@@ -48,6 +49,7 @@ import org.apache.uima.cas.admin.LinearT
import org.apache.uima.cas.impl.FSIndexFlat.FSIteratorFlat;
import org.apache.uima.cas.text.AnnotationFS;
import org.apache.uima.internal.util.ComparableIntPointerIterator;
+import org.apache.uima.internal.util.Int2IntArrayMapFixedSize;
import org.apache.uima.internal.util.IntComparator;
import org.apache.uima.internal.util.IntPointerIterator;
import org.apache.uima.internal.util.IntVector;
@@ -225,7 +227,7 @@ public class FSIndexRepositoryImpl imple
/**
* The type codes corresponding to the cachedSubFsLeafIndexes, set up
lazily
*/
- int[] typeCodes;
+ int[] sortedTypeCodes;
@Override
public String toString() {
@@ -306,7 +308,7 @@ public class FSIndexRepositoryImpl imple
final ArrayList<FSLeafIndexImpl<? extends T>> tempSubIndexCache = new
ArrayList<FSLeafIndexImpl<? extends T>>();
final int len = allTypes.size();
if (indexKind == FSIndex.SORTED_INDEX) {
- typeCodes = new int[len];
+ sortedTypeCodes = new int[len];
}
for (int i = 0; i < len; i++) {
@@ -320,11 +322,12 @@ public class FSIndexRepositoryImpl imple
throw new RuntimeException("never happen");
}
if (indexKind == FSIndex.SORTED_INDEX) {
- typeCodes[i] = leafIndex.getTypeCode();
+ sortedTypeCodes[i] = leafIndex.getTypeCode();
}
}
this.cachedSubFsLeafIndexes = tempSubIndexCache;
if (this.fsLeafIndex.getIndexingStrategy() == FSIndex.SORTED_INDEX) {
+ Arrays.sort(sortedTypeCodes);
this.flatIndex = new FSIndexFlat<>(this); // must follow
cachedSubFsLeafIndexes setup
}
// assign to "volatile" at end, after all initialization is complete
@@ -434,27 +437,28 @@ public class FSIndexRepositoryImpl imple
}
}
- int[] createIndexUpdateCountsAtReset() {
- final int ni = cachedSubFsLeafIndexes.size();
- int [] ia = new int[ni];
- for (int i = 0; i < ni; i++) {
- ia[i] = detectIllegalIndexUpdates[typeCodes[i]];
- }
- return ia;
+ Int2IntArrayMapFixedSize createIndexUpdateCountsAtReset() {
+ Int2IntArrayMapFixedSize m = new
Int2IntArrayMapFixedSize(sortedTypeCodes.length);
+ captureIndexUpdateCounts(m);
+ return m;
}
- void captureIndexUpdateCounts(int [] ia) {
- final int ni = ia.length;
- for (int i = 0; i < ni; i++) {
- ia[i] = detectIllegalIndexUpdates[typeCodes[i]];
- }
+ void captureIndexUpdateCounts() {
+ captureIndexUpdateCounts(this.flatIndex.indexUpdateCountsResetValues);
+ }
+
+ private void captureIndexUpdateCounts(Int2IntArrayMapFixedSize m) {
+ final int[] localSortedTypeCodes = sortedTypeCodes;
+ for (int i = 0; i < localSortedTypeCodes.length; i++) {
+ m.putAtIndex(i, detectIllegalIndexUpdates[localSortedTypeCodes[i]]);
+ }
}
boolean isUpdateFreeSinceLastCounterReset() {
- final int[] ia = flatIndex.indexUpdateCountsResetValues;
- final int ni = ia.length;
- for (int i = 0; i < ni; i++) {
- if (ia[i] != detectIllegalIndexUpdates[typeCodes[i]]) {
+ final Int2IntArrayMapFixedSize typeCode2updateCount =
this.flatIndex.indexUpdateCountsResetValues;
+ final int[] localSortedTypeCodes = sortedTypeCodes;
+ for (int i = 0; i < localSortedTypeCodes.length; i++) {
+ if (typeCode2updateCount.getAtIndex(i) !=
detectIllegalIndexUpdates[localSortedTypeCodes[i]]) {
return false;
}
}
@@ -462,21 +466,10 @@ public class FSIndexRepositoryImpl imple
}
boolean isUpdateFreeSinceLastCounterReset(final int typeCode) {
- final int[] ia = flatIndex.indexUpdateCountsResetValues;
- final int ni = ia.length;
- for (int i = 0; i < ni; i++) {
- final int localTypeCode = typeCodes[i];
- if (typeCode != localTypeCode) {
- continue;
- }
- if (ia[i] != detectIllegalIndexUpdates[localTypeCode]) {
- return false;
- }
- break; // just checking one typecode, and found it; no need to check
others
- }
- return true;
+ return this.flatIndex.indexUpdateCountsResetValues.get(typeCode,
sortedTypeCodes) ==
+ detectIllegalIndexUpdates[typeCode];
}
-
+
boolean subsumes(int superType, int subType) {
return cas.getTypeSystemImpl().subsumes(superType, subType);
}
@@ -2893,7 +2886,7 @@ public class FSIndexRepositoryImpl imple
if (FSIndexFlat.trace) {
System.out.format("FSIndexFlattened getAllIndexedFS use: %s%n",
flatIterator.toString());
}
- iteratorList.add(flatIterator.toLLiterator());
+ iteratorList.add(flatIterator);
return;
}
}
Modified:
uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/FeatureStructureImpl.java
URL:
http://svn.apache.org/viewvc/uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/FeatureStructureImpl.java?rev=1678049&r1=1678048&r2=1678049&view=diff
==============================================================================
---
uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/FeatureStructureImpl.java
(original)
+++
uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/FeatureStructureImpl.java
Wed May 6 17:45:59 2015
@@ -52,6 +52,10 @@ public abstract class FeatureStructureIm
return this.getCASImpl().getTypeSystemImpl().ll_getTypeForCode(
this.getCASImpl().getHeapValue(this.getAddress()));
}
+
+ public int getTypeCode() {
+ return this.getCASImpl().getHeapValue(this.getAddress());
+ }
public void setFeatureValue(Feature feat, FeatureStructure fs) {
final int valueAddr = this.getCASImpl().ll_getFSRef(fs);
Modified:
uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/Subiterator.java
URL:
http://svn.apache.org/viewvc/uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/Subiterator.java?rev=1678049&r1=1678048&r2=1678049&view=diff
==============================================================================
---
uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/Subiterator.java
(original)
+++
uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/Subiterator.java
Wed May 6 17:45:59 2015
@@ -46,7 +46,7 @@ public class Subiterator<T extends Annot
}
/**
- * Create a disambiguated iterator.
+ * Create a disambiguated iterator. No concurrent modification exception
checking is done.
*
* @param it
* The iterator to be disambiguated.
@@ -71,6 +71,7 @@ public class Subiterator<T extends Annot
}
}
+
Subiterator(FSIterator<T> it, AnnotationFS annot, final boolean ambiguous,
final boolean strict) {
this();
if (ambiguous) {
Modified:
uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/UnambiguousIteratorImpl.java
URL:
http://svn.apache.org/viewvc/uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/UnambiguousIteratorImpl.java?rev=1678049&r1=1678048&r2=1678049&view=diff
==============================================================================
---
uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/UnambiguousIteratorImpl.java
(original)
+++
uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/UnambiguousIteratorImpl.java
Wed May 6 17:45:59 2015
@@ -34,6 +34,8 @@ import org.apache.uima.cas.text.Annotati
* <p>
* Warning: this implementation creates a copy of the collection, so changes
in the underlying
* collection are not reflected by this iterator.
+ * </p>
+ * <p>This iterator does not check for concurrent modifications and doesn't
throw ConcurrentModificationExceptions.</p>
*
*
*/
Modified:
uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/text/AnnotationIndex.java
URL:
http://svn.apache.org/viewvc/uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/text/AnnotationIndex.java?rev=1678049&r1=1678048&r2=1678049&view=diff
==============================================================================
---
uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/text/AnnotationIndex.java
(original)
+++
uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/text/AnnotationIndex.java
Wed May 6 17:45:59 2015
@@ -68,6 +68,9 @@ public interface AnnotationIndex<T exten
* overlap the span of <code>a</code>.
* </p>
*
+ * <p>An unambiguous iterator makes a snapshot copy of the index containing
just the disambiguated items, and
+ * iterates over that. It doesn't check for concurrent index modifications
(the ambiguous iterator does check for this).
+ *
* @param ambiguous
* If set to false, iterator will be unambiguous.
* @return A annotation iterator.
Added:
uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/Int2IntArrayMapFixedSize.java
URL:
http://svn.apache.org/viewvc/uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/Int2IntArrayMapFixedSize.java?rev=1678049&view=auto
==============================================================================
---
uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/Int2IntArrayMapFixedSize.java
(added)
+++
uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/Int2IntArrayMapFixedSize.java
Wed May 6 17:45:59 2015
@@ -0,0 +1,75 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.uima.internal.util;
+
+import java.util.Arrays;
+
+/**
+ * A map<int, int>
+ *
+ * based on having a key and value int array, where the keys are sorted
+ *
+ * Supports sharing a single key array with multiple value arrays
+ *
+ * Implements Map - like interface:
+ * keys and values are ints
+ *
+ * values can be anything except 0; 0 is the value returned by get if not found
+ *
+ * All adds must occur before any gets; then a sort must be called unless the
adds are in sort order
+ *
+ * Threading: instances of this class may be accessed on multiple threads
+ * (different iterators may be on different threads)
+ */
+public class Int2IntArrayMapFixedSize {
+
+ private final int [] values;
+ private final boolean isSmall;
+
+ public Int2IntArrayMapFixedSize(int length) {
+ values = new int[length];
+ isSmall = length <= 4;
+ }
+
+ public int get(int key, final int[] sortedKeys) {
+ int f = isSmall ? quickFind(key, sortedKeys) :
Arrays.binarySearch(sortedKeys, key);
+ if (f < 0) {
+ throw new RuntimeException(); // return 0; // not found
+ }
+ return values[f];
+ }
+
+ private int quickFind(int key, final int[] sortedKeys) {
+ for (int i = 0; i < sortedKeys.length; i++) {
+ if (key == sortedKeys[i]) {
+ return i;
+ }
+ }
+ throw new RuntimeException(); // not found
+ }
+
+ public int getAtIndex(int index) {
+ return values[index];
+ }
+
+ public void putAtIndex(int index, int value) {
+ values[index] = value;
+ }
+}
