Author: schor Date: Tue Dec 1 17:04:24 2015 New Revision: 1717468 URL: http://svn.apache.org/viewvc?rev=1717468&view=rev Log: [UIMA-4664] fix index construction order to allow for more final objects. Improve set-sorted index when used for the built-in annotation index to use a custom comparator for that. Improve the insert operation for the frequent case of adding a value that's greater than all previous ones.
Modified: uima/uimaj/branches/experiment-v3-jcas/uimaj-core/src/main/java/org/apache/uima/cas/impl/FSIndexRepositoryImpl.java uima/uimaj/branches/experiment-v3-jcas/uimaj-core/src/main/java/org/apache/uima/cas/impl/FsIndex_bag.java uima/uimaj/branches/experiment-v3-jcas/uimaj-core/src/main/java/org/apache/uima/cas/impl/FsIndex_flat.java uima/uimaj/branches/experiment-v3-jcas/uimaj-core/src/main/java/org/apache/uima/cas/impl/FsIndex_set_sorted.java uima/uimaj/branches/experiment-v3-jcas/uimaj-core/src/main/java/org/apache/uima/cas/impl/FsIndex_singletype.java Modified: uima/uimaj/branches/experiment-v3-jcas/uimaj-core/src/main/java/org/apache/uima/cas/impl/FSIndexRepositoryImpl.java URL: http://svn.apache.org/viewvc/uima/uimaj/branches/experiment-v3-jcas/uimaj-core/src/main/java/org/apache/uima/cas/impl/FSIndexRepositoryImpl.java?rev=1717468&r1=1717467&r2=1717468&view=diff ============================================================================== --- uima/uimaj/branches/experiment-v3-jcas/uimaj-core/src/main/java/org/apache/uima/cas/impl/FSIndexRepositoryImpl.java (original) +++ uima/uimaj/branches/experiment-v3-jcas/uimaj-core/src/main/java/org/apache/uima/cas/impl/FSIndexRepositoryImpl.java Tue Dec 1 17:04:24 2015 @@ -45,7 +45,6 @@ import org.apache.uima.cas.admin.FSIndex import org.apache.uima.cas.admin.FSIndexRepositoryMgr; import org.apache.uima.cas.admin.LinearTypeOrder; import org.apache.uima.cas.admin.LinearTypeOrderBuilder; -import org.apache.uima.cas.text.AnnotationFS; import org.apache.uima.internal.util.IntVector; import org.apache.uima.internal.util.ObjHashSet; import org.apache.uima.jcas.cas.AnnotationBase; @@ -169,7 +168,9 @@ public class FSIndexRepositoryImpl imple /** * lazily created comparator using the built-in annotation index */ - private Comparator<AnnotationFS> annotationFsComparator = null; + private Comparator<TOP> annotationFsComparator = null; + + private Comparator<TOP> annotationFsComparatorWithId = null; /** * optimization only - bypasses some shared (among views) initialization if already done @@ -605,7 +606,7 @@ public class FSIndexRepositoryImpl imple return iicp; } - private boolean isAnnotationIndex(FSIndexComparator c, int indexKind) { + boolean isAnnotationIndex(FSIndexComparator c, int indexKind) { TypeSystemImpl tsi = getTypeSystemImpl(); return indexKind == FSIndex.SORTED_INDEX && getTypeSystemImpl().annotType.subsumes((TypeImpl) c.getType()) && @@ -638,7 +639,7 @@ public class FSIndexRepositoryImpl imple switch (indexType) { case FSIndex.SET_INDEX: - ind = new FsIndex_set_sorted<T>(this.cas, type, indexType, false); // false = is set + ind = new FsIndex_set_sorted<T>(this.cas, type, indexType, comparatorForIndexSpecs, false); // false = is set break; // case FSIndex.FLAT_INDEX: @@ -647,16 +648,15 @@ public class FSIndexRepositoryImpl imple case FSIndex.BAG_INDEX: case FSIndex.DEFAULT_BAG_INDEX: - ind = new FsIndex_bag<T>(this.cas, type, initialSize, indexType); + ind = new FsIndex_bag<T>(this.cas, type, initialSize, indexType, comparatorForIndexSpecs); break; default: // SORTED_INDEX is the default. We don't throw any errors, if the code is unknown, we just create a sorted index. - ind = new FsIndex_set_sorted<T>(this.cas, type, FSIndex.SORTED_INDEX, true); // true = is sorted + ind = new FsIndex_set_sorted<T>(this.cas, type, FSIndex.SORTED_INDEX, comparatorForIndexSpecs, true); // true = is sorted break; } - ind.init(comparatorForIndexSpecs); return ind; } @@ -1492,8 +1492,8 @@ public class FSIndexRepositoryImpl imple // return this.sii.annotationComparator; // } - Comparator<AnnotationFS> getAnnotationFsComparator() { - Comparator<AnnotationFS> r = this.sii.annotationFsComparator; + Comparator<TOP> getAnnotationFsComparator() { + Comparator<TOP> r = this.sii.annotationFsComparator; // lazy creation if (null != r) { return r; @@ -1502,30 +1502,60 @@ public class FSIndexRepositoryImpl imple return createAnnotationFsComparator(); } + Comparator<TOP> getAnnotationFsComparatorWithId() { + Comparator<TOP> r = this.sii.annotationFsComparatorWithId; + // lazy creation + if (null != r) { + return r; + } + + return createAnnotationFsComparatorWithId(); + } - private Comparator<AnnotationFS> createAnnotationFsComparator() { + private Comparator<TOP> createAnnotationFsComparator() { final LinearTypeOrder typeOrder = getDefaultTypeOrder(); - return this.sii.annotationFsComparator = new Comparator<AnnotationFS>() { + return this.sii.annotationFsComparator = (fsx1, fsx2) -> { + Annotation fs1 = (Annotation) fsx1; + Annotation fs2 = (Annotation) fsx2; + + if (fs1 == fs2) return 0; - @Override - public int compare(AnnotationFS fsx1, AnnotationFS fsx2) { - Annotation fs1 = (Annotation) fsx1; - Annotation fs2 = (Annotation) fsx2; - - if (fs1 == fs2) return 0; + int result = Integer.compare(fs1.getBegin(), fs2.getBegin()); + if (result != 0) return result; - int result = Integer.compare(fs1.getBegin(), fs2.getBegin()); - if (result != 0) return result; + result = Integer.compare(fs1.getEnd(), fs2.getEnd()); + if (result != 0) return -result; // reverse compare + + return typeOrder.compare(fs1, fs2); + }; + } + + //unrolled because of high frequency use + private Comparator<TOP> createAnnotationFsComparatorWithId() { - result = Integer.compare(fs1.getEnd(), fs2.getEnd()); - if (result != 0) return -result; // reverse compare - - return typeOrder.compare(fs1, fs2); - } + final LinearTypeOrder typeOrder = getDefaultTypeOrder(); + + this.sii.annotationFsComparatorWithId = (fsx1, fsx2) -> { + if (fsx1 == fsx2) return 0; + + final Annotation fs1 = (Annotation) fsx1; + final Annotation fs2 = (Annotation) fsx2; + + final int r1, r2, r3; + if ((r1 = Integer.compare(fs1.getBegin(), fs2.getBegin())) != 0) return r1; + + if ((r2 = Integer.compare(fs1.getEnd(), fs2.getEnd())) != 0) return -r2; // reverse compare + + if ((r3 = typeOrder.compare(fs1, fs2)) != 0) return r3; + + return Integer.compare(fs1._id, fs2._id); }; + + return this.sii.annotationFsComparatorWithId; } + public TypeSystemImpl getTypeSystemImpl() { return sii.tsi; Modified: uima/uimaj/branches/experiment-v3-jcas/uimaj-core/src/main/java/org/apache/uima/cas/impl/FsIndex_bag.java URL: http://svn.apache.org/viewvc/uima/uimaj/branches/experiment-v3-jcas/uimaj-core/src/main/java/org/apache/uima/cas/impl/FsIndex_bag.java?rev=1717468&r1=1717467&r2=1717468&view=diff ============================================================================== --- uima/uimaj/branches/experiment-v3-jcas/uimaj-core/src/main/java/org/apache/uima/cas/impl/FsIndex_bag.java (original) +++ uima/uimaj/branches/experiment-v3-jcas/uimaj-core/src/main/java/org/apache/uima/cas/impl/FsIndex_bag.java Tue Dec 1 17:04:24 2015 @@ -42,8 +42,8 @@ public class FsIndex_bag<T extends TOP> // The index final private ObjHashSet<TOP> index; - FsIndex_bag(CASImpl cas, Type type, int initialSize, int indexType) { - super(cas, type, indexType); + FsIndex_bag(CASImpl cas, Type type, int initialSize, int indexType, FSIndexComparator comparatorForIndexSpecs) { + super(cas, type, indexType, cleanUpComparator(comparatorForIndexSpecs, cas)); this.index = new ObjHashSet<TOP>(initialSize, TOP.class, TOP.singleton); } @@ -51,7 +51,7 @@ public class FsIndex_bag<T extends TOP> * Substitutes an empty comparator if one is specified - may not be needed * @see org.apache.uima.cas.impl.FSLeafIndexImpl#init(org.apache.uima.cas.admin.FSIndexComparator) */ - boolean init(FSIndexComparator comp) { + private static FSIndexComparator cleanUpComparator(FSIndexComparator comp, CASImpl casImpl) { // The comparator for a bag index must be empty, except for the type. If // it isn't, we create an empty one. FSIndexComparator newComp; @@ -61,7 +61,7 @@ public class FsIndex_bag<T extends TOP> } else { newComp = comp; } - return super.init(newComp); + return newComp; } public void flush() { Modified: uima/uimaj/branches/experiment-v3-jcas/uimaj-core/src/main/java/org/apache/uima/cas/impl/FsIndex_flat.java URL: http://svn.apache.org/viewvc/uima/uimaj/branches/experiment-v3-jcas/uimaj-core/src/main/java/org/apache/uima/cas/impl/FsIndex_flat.java?rev=1717468&r1=1717467&r2=1717468&view=diff ============================================================================== --- uima/uimaj/branches/experiment-v3-jcas/uimaj-core/src/main/java/org/apache/uima/cas/impl/FsIndex_flat.java (original) +++ uima/uimaj/branches/experiment-v3-jcas/uimaj-core/src/main/java/org/apache/uima/cas/impl/FsIndex_flat.java Tue Dec 1 17:04:24 2015 @@ -46,7 +46,8 @@ public class FsIndex_flat<T extends TOP> final private Comparator<TOP> comparator; FsIndex_flat(FsIndex_iicp<T> iicp) { - super(iicp.getCASImpl(), iicp.fsIndex_singletype.getType(), iicp.fsIndex_singletype.getIndexingStrategy()); + super(iicp.getCASImpl(), iicp.fsIndex_singletype.getType(), iicp.fsIndex_singletype.getIndexingStrategy(), + iicp.fsIndex_singletype.getComparatorForIndexSpecs()); this.iicp = iicp; indexedFSs = fillFlatArray(); comparator = iicp.fsIndex_singletype; Modified: uima/uimaj/branches/experiment-v3-jcas/uimaj-core/src/main/java/org/apache/uima/cas/impl/FsIndex_set_sorted.java URL: http://svn.apache.org/viewvc/uima/uimaj/branches/experiment-v3-jcas/uimaj-core/src/main/java/org/apache/uima/cas/impl/FsIndex_set_sorted.java?rev=1717468&r1=1717467&r2=1717468&view=diff ============================================================================== --- uima/uimaj/branches/experiment-v3-jcas/uimaj-core/src/main/java/org/apache/uima/cas/impl/FsIndex_set_sorted.java (original) +++ uima/uimaj/branches/experiment-v3-jcas/uimaj-core/src/main/java/org/apache/uima/cas/impl/FsIndex_set_sorted.java Tue Dec 1 17:04:24 2015 @@ -19,14 +19,19 @@ package org.apache.uima.cas.impl; +import java.util.ArrayList; +import java.util.Collection; +import java.util.Comparator; import java.util.Iterator; import java.util.List; import java.util.NavigableSet; +import java.util.SortedSet; import java.util.TreeSet; import org.apache.uima.cas.FSIterator; import org.apache.uima.cas.FeatureStructure; import org.apache.uima.cas.Type; +import org.apache.uima.cas.admin.FSIndexComparator; import org.apache.uima.jcas.cas.TOP; /** @@ -48,25 +53,82 @@ import org.apache.uima.jcas.cas.TOP; * @param <T> the Java class type for this index */ public class FsIndex_set_sorted<T extends TOP> extends FsIndex_singletype<T> { + + final private SortedSet<TOP> ss = new SortedSet<TOP>() { + + @Override + public int size() { return itemsToBeAdded.size(); } + @Override + public boolean isEmpty() { return false; } + @Override + public boolean contains(Object o) { throw new UnsupportedOperationException(); } + @Override + public Iterator<TOP> iterator() { return itemsToBeAdded.iterator(); } + @Override + public Object[] toArray() { throw new UnsupportedOperationException(); } + @Override + public <U> U[] toArray(U[] a) { throw new UnsupportedOperationException(); } + @Override + public boolean add(TOP e) { throw new UnsupportedOperationException(); } + @Override + public boolean remove(Object o) { throw new UnsupportedOperationException(); } + @Override + public boolean containsAll(Collection<?> c) { throw new UnsupportedOperationException(); } + @Override + public boolean addAll(Collection<? extends TOP> c) { throw new UnsupportedOperationException(); } + @Override + public boolean retainAll(Collection<?> c) { throw new UnsupportedOperationException(); } + @Override + public boolean removeAll(Collection<?> c) { throw new UnsupportedOperationException(); } + @Override + public void clear() { throw new UnsupportedOperationException(); } + @Override + public Comparator<TOP> comparator() { return comparator; } + @Override + public SortedSet<TOP> subSet(TOP fromElement, TOP toElement) { throw new UnsupportedOperationException(); } + @Override + public SortedSet<TOP> headSet(TOP toElement) { throw new UnsupportedOperationException(); } + @Override + public SortedSet<TOP> tailSet(TOP fromElement) { throw new UnsupportedOperationException(); } + @Override + public TOP first() { throw new UnsupportedOperationException(); } + @Override + public TOP last() { throw new UnsupportedOperationException(); } + }; + // The index, a NavigableSet. - // Should be over T, but has to be over FeatureStructure in order to have the comparator take FeatureStructures - final private NavigableSet<TOP> indexedFSs; + final private TreeSet<TOP> indexedFSs; + + final private Comparator<TOP> comparator; + + final private ArrayList<TOP> itemsToBeAdded = new ArrayList<>(); // to batch the adds + + private TOP largestItem = null; - FsIndex_set_sorted(CASImpl cas, Type type, int indexType, boolean useSorted) { - super(cas, type, indexType); - this.indexedFSs = useSorted - ? new TreeSet<TOP>( - (TOP o1, TOP o2) -> { - final int c = compare(o1, o2); - // augment normal comparator with one that compares IDs if everything else equal - return (c == 0) ? (Integer.compare(o1.id(), o2.id())) : c;}) - : new TreeSet<TOP>( (TOP o1, TOP o2) -> compare(o1, o2)); + FsIndex_set_sorted(CASImpl cas, Type type, int indexType, FSIndexComparator comparatorForIndexSpecs, boolean useSorted) { + super(cas, type, indexType, comparatorForIndexSpecs); + FSIndexRepositoryImpl ir = this.casImpl.indexRepository; + + if (ir.isAnnotationIndex(comparatorForIndexSpecs, indexType)) { + comparator = ir.getAnnotationFsComparatorWithId(); + } else { + comparator = useSorted + ? (o1, o2) -> { + final int c = compare(o1, o2); + // augment normal comparator with one that compares IDs if everything else equal + return (c == 0) ? (Integer.compare(o1.id(), o2.id())) : c;} + : (o1, o2) -> compare(o1, o2); + } + this.indexedFSs = new TreeSet<TOP>(comparator); } @Override public void flush() { this.indexedFSs.clear(); + this.itemsToBeAdded.clear(); + this.itemsToBeAdded.trimToSize(); + this.largestItem = null; } /** @@ -86,6 +148,7 @@ public class FsIndex_set_sorted<T extend */ @Override public boolean containsEq(FeatureStructureImplC fs) { + maybeProcessBulkAdds(); return CASImpl.isSameCAS(casImpl, fs.getCAS()) && indexedFSs.contains(fs); } @@ -94,7 +157,29 @@ public class FsIndex_set_sorted<T extend */ @Override boolean insert(T fs) { - return this.indexedFSs.add((TOP)fs); + // measured - not efficient. +// if (indexedFSs.size() > 1024) { +// // optimize for insert at end +// TOP last = indexedFSs.last(); +// if (indexedFSs.comparator().compare(last, fs) <= 0) { +// // insert at end fast path maybe +// return indexedFSs.tailSet(last, true).add(fs); +// } +// } + if (largestItem != null && comparator.compare(fs, largestItem) > 0) { + itemsToBeAdded.add(fs); + largestItem = fs; + return true; + } else { + if (largestItem == null) { + largestItem = fs; + itemsToBeAdded.add(fs); + return true; + } + + maybeProcessBulkAdds(); // we do this so the return value from add is accurate + return this.indexedFSs.add((TOP)fs); + } } /** @@ -117,6 +202,7 @@ public class FsIndex_set_sorted<T extend */ @Override public T find(FeatureStructure templateKeyIn) { + maybeProcessBulkAdds(); TOP templateKey = (TOP) templateKeyIn; if (null == templateKey || this.indexedFSs.size() == 0) { return null; @@ -142,6 +228,7 @@ public class FsIndex_set_sorted<T extend } public T findLeftmost(TOP templateKey) { + maybeProcessBulkAdds(); // descending iterator over elements LessThan templateKey Iterator<T> it = (Iterator<T>) indexedFSs.headSet(templateKey, false).descendingIterator(); @@ -163,7 +250,7 @@ public class FsIndex_set_sorted<T extend */ @Override public int size() { - return this.indexedFSs.size(); + return this.indexedFSs.size() + itemsToBeAdded.size(); } /** @@ -179,11 +266,13 @@ public class FsIndex_set_sorted<T extend */ @Override public boolean deleteFS(T fs) { + maybeProcessBulkAdds(); return this.indexedFSs.remove(fs); } @Override protected void bulkAddTo(List<TOP> v) { + maybeProcessBulkAdds(); v.addAll(indexedFSs); } @@ -193,11 +282,33 @@ public class FsIndex_set_sorted<T extend // } NavigableSet<TOP> getNavigableSet() { //used by FsIterator_sorted to compute various derivitive nav sets + maybeProcessBulkAdds(); return indexedFSs; } @Override public FSIterator<T> iterator() { + maybeProcessBulkAdds(); return new FsIterator_set_sorted<T>(this, getDetectIllegalIndexUpdates(), getTypeCode(), this); } + + private synchronized void maybeProcessBulkAdds() { + final int sz = itemsToBeAdded.size(); + if (sz > 0) { + + // debug + // if (sz > 1) { + // TOP prev = itemsToBeAdded.get(0); + // for (int i = 1; i < sz; i++) { + // TOP next = itemsToBeAdded.get(i); + // if (comparator.compare(next, prev) <= 0) { + // System.out.println("debug"); + // } + // prev = next; + // } + // } + indexedFSs.addAll(ss); + itemsToBeAdded.clear(); + } + } } Modified: uima/uimaj/branches/experiment-v3-jcas/uimaj-core/src/main/java/org/apache/uima/cas/impl/FsIndex_singletype.java URL: http://svn.apache.org/viewvc/uima/uimaj/branches/experiment-v3-jcas/uimaj-core/src/main/java/org/apache/uima/cas/impl/FsIndex_singletype.java?rev=1717468&r1=1717467&r2=1717468&view=diff ============================================================================== --- uima/uimaj/branches/experiment-v3-jcas/uimaj-core/src/main/java/org/apache/uima/cas/impl/FsIndex_singletype.java (original) +++ uima/uimaj/branches/experiment-v3-jcas/uimaj-core/src/main/java/org/apache/uima/cas/impl/FsIndex_singletype.java Tue Dec 1 17:04:24 2015 @@ -46,19 +46,17 @@ public abstract class FsIndex_singletype // A reference to the low-level CAS. final protected CASImpl casImpl; - private FSIndexComparatorImpl comparatorForIndexSpecs; - - private boolean isInitialized = false; + final private FSIndexComparatorImpl comparatorForIndexSpecs; /*********** Info about Index Comparator (not used for bag *********** * Index into these arrays is the key number (indexes can have multiple keys) */ // For each key, the int code of the type of that key. - private Object[] keys; // either a FeatImpl or a LinearTypeOrder; + final private Object[] keys; // either a FeatImpl or a LinearTypeOrder; - private int[] keyTypeCodes; + final private int[] keyTypeCodes; // For each key, the comparison to use. - private boolean[] isReverse; // true = reverse, false = standard + final private boolean[] isReverse; // true = reverse, false = standard final private TypeImpl type; // The type of this @@ -79,6 +77,10 @@ public abstract class FsIndex_singletype this.casImpl = null; this.type = null; this.typeCode = 0; + comparatorForIndexSpecs = null; + keys = null; + keyTypeCodes = null; + isReverse = null; } /** @@ -87,12 +89,36 @@ public abstract class FsIndex_singletype * @param type - * @param indexType - */ - protected FsIndex_singletype(CASImpl cas, Type type, int indexType) { + protected FsIndex_singletype(CASImpl cas, Type type, int indexType, FSIndexComparator comparatorForIndexSpecs) { super(); this.indexType = indexType; this.casImpl = cas; this.type = (TypeImpl) type; this.typeCode = ((TypeImpl)type).getCode(); + FSIndexComparatorImpl compForIndexSpecs = (FSIndexComparatorImpl) comparatorForIndexSpecs; + this.comparatorForIndexSpecs = compForIndexSpecs.copy(); + + // Initialize the comparator info. + final int nKeys = this.comparatorForIndexSpecs.getNumberOfKeys(); + this.keys = new Object[nKeys]; + this.keyTypeCodes = new int[nKeys]; + this.isReverse = new boolean[nKeys]; + + if (!this.comparatorForIndexSpecs.isValid()) { + return; + } + + for (int i = 0; i < nKeys; i++) { + + final Object k = (comparatorForIndexSpecs.getKeyType(i) == FSIndexComparator.FEATURE_KEY) + ? (FeatureImpl) this.comparatorForIndexSpecs.getKeyFeature(i) + : this.comparatorForIndexSpecs.getKeyTypeOrder(i); + keys[i] = k; + if (k instanceof FeatureImpl) { + keyTypeCodes[i] = ((TypeImpl)((FeatureImpl)k).getRange()).getCode(); + } + isReverse[i] = this.comparatorForIndexSpecs.getKeyComparator(i) == FSIndexComparator.REVERSE_STANDARD_COMPARE; + } } /** @@ -143,42 +169,6 @@ public abstract class FsIndex_singletype public int[] getDetectIllegalIndexUpdates() { return this.casImpl.indexRepository.detectIllegalIndexUpdates; } - /** - * Comparators - - * These are converted to use fs instances - * @param comp - * @return - */ - boolean init(FSIndexComparator comp) { - if (this.isInitialized) { - return false; - } - FSIndexComparatorImpl compForIndexSpecs = (FSIndexComparatorImpl) comp; - this.comparatorForIndexSpecs = compForIndexSpecs.copy(); - if (!this.comparatorForIndexSpecs.isValid()) { - return false; - } - - // Initialize the comparator info. - final int nKeys = this.comparatorForIndexSpecs.getNumberOfKeys(); - this.keys = new Object[nKeys]; - this.keyTypeCodes = new int[nKeys]; - this.isReverse = new boolean[nKeys]; - - for (int i = 0; i < nKeys; i++) { - - final Object k = (comp.getKeyType(i) == FSIndexComparator.FEATURE_KEY) - ? (FeatureImpl) this.comparatorForIndexSpecs.getKeyFeature(i) - : this.comparatorForIndexSpecs.getKeyTypeOrder(i); - keys[i] = k; - if (k instanceof FeatureImpl) { - keyTypeCodes[i] = ((TypeImpl)((FeatureImpl)k).getRange()).getCode(); - } - isReverse[i] = this.comparatorForIndexSpecs.getKeyComparator(i) == FSIndexComparator.REVERSE_STANDARD_COMPARE; - } - this.isInitialized = true; - return true; - } /** * @param fs1 -