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 2015/03/09 22:44:13 UTC
svn commit: r1665367 - in /uima/uimaj/trunk/uimaj-core/src:
main/java/org/apache/uima/cas/impl/ test/java/org/apache/uima/cas/impl/
Author: schor
Date: Mon Mar 9 21:44:12 2015
New Revision: 1665367
URL: http://svn.apache.org/r1665367
Log:
[UIMA-4281] gradually shrink where reasonable some internal core arrays upon reset().
Added:
uima/uimaj/trunk/uimaj-core/src/test/java/org/apache/uima/cas/impl/CommonAuxHeapTest.java
Modified:
uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/ByteHeap.java
uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/CASImpl.java
uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/CommonAuxHeap.java
uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/Heap.java
uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/LongHeap.java
uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/ShortHeap.java
uima/uimaj/trunk/uimaj-core/src/test/java/org/apache/uima/cas/impl/CasResetResizeTest.java
Modified: uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/ByteHeap.java
URL: http://svn.apache.org/viewvc/uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/ByteHeap.java?rev=1665367&r1=1665366&r2=1665367&view=diff
==============================================================================
--- uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/ByteHeap.java (original)
+++ uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/ByteHeap.java Mon Mar 9 21:44:12 2015
@@ -39,6 +39,14 @@ final class ByteHeap extends CommonAuxHe
final void initMemory() {
this.heap = new byte[this.heapBaseSize];
}
+
+ final void initMemory(int size) {
+ this.heap = new byte[size];
+ }
+
+ final int getCapacity() {
+ return this.heap.length;
+ }
void growHeapIfNeeded() {
if (heap.length >= heapPos)
Modified: uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/CASImpl.java
URL: http://svn.apache.org/viewvc/uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/CASImpl.java?rev=1665367&r1=1665366&r2=1665367&view=diff
==============================================================================
--- uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/CASImpl.java (original)
+++ uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/CASImpl.java Mon Mar 9 21:44:12 2015
@@ -310,7 +310,7 @@ public class CASImpl extends AbstractCas
/**
* This stack corresponds to nested protectIndexes contexts. Normally should be very shallow.
*/
- private final List<FSsTobeAddedback> fssTobeAddedback = new ArrayList<FSsTobeAddedback>();
+ private final ArrayList<FSsTobeAddedback> fssTobeAddedback = new ArrayList<FSsTobeAddedback>();
/**
* This version is for single fs use, by binary deserializers and by automatic mode
@@ -1068,7 +1068,7 @@ public class CASImpl extends AbstractCas
((CASImpl) tcas).mySofaRef = (1 == view) ? -1 : 0;
}
}
- this.getHeap().reset(this.getHeap().getHeapSize() > CASImpl.resetHeapSize);
+ this.getHeap().reset(/*this.getHeap().getHeapSize() > CASImpl.resetHeapSize*/);
resetStringTable();
@@ -1077,7 +1077,7 @@ public class CASImpl extends AbstractCas
this.getLongHeap().reset();
this.indexRepository.flush();
- this.svd.sofaNameSet.clear();
+ this.svd.sofaNameSet = new HashSet<String>();
this.svd.initialSofaCreated = false;
// always an Initial View now!!!
this.svd.viewCount = 1;
@@ -1093,6 +1093,7 @@ public class CASImpl extends AbstractCas
clearTrackingMarks();
this.svd.cache_not_in_index = 0;
this.svd.fssTobeAddedback.clear();
+ this.svd.fssTobeAddedback.trimToSize();
}
/**
@@ -1102,7 +1103,6 @@ public class CASImpl extends AbstractCas
public void flush() {
reset();
}
-
public FSIndexRepository getIndexRepository() {
if (this == this.svd.baseCAS) {
Modified: uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/CommonAuxHeap.java
URL: http://svn.apache.org/viewvc/uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/CommonAuxHeap.java?rev=1665367&r1=1665366&r2=1665367&view=diff
==============================================================================
--- uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/CommonAuxHeap.java (original)
+++ uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/CommonAuxHeap.java Mon Mar 9 21:44:12 2015
@@ -23,6 +23,12 @@ package org.apache.uima.cas.impl;
* Encapsulate 8, 16, and 64 bit storage for the CAS.
*/
abstract class CommonAuxHeap {
+
+ private static final boolean debugLogShrink = false;
+// static {
+// debugLogShrink = System.getProperty("uima.debug.ihs") != null;
+// }
+
// cannot be 0 because it grows by multiplying growth_factor
protected static final int DEFAULT_HEAP_BASE_SIZE = 16;
@@ -44,6 +50,8 @@ abstract class CommonAuxHeap {
protected final int heapMultLimit;
protected int heapPos = FIRST_CELL_REF;
+
+ private int prevSize = 1;
CommonAuxHeap() {
this(DEFAULT_HEAP_BASE_SIZE, DEFAULT_HEAP_MULT_LIMIT);
@@ -57,6 +65,8 @@ abstract class CommonAuxHeap {
}
abstract void initMemory();
+
+ abstract void initMemory(int size);
abstract void resetToZeros();
@@ -66,11 +76,38 @@ abstract class CommonAuxHeap {
this.reset(false);
}
+ /**
+ * Logic for shrinking:
+ *
+ * Based on a short history of the capacity needed to hold the larger of the previous 2 sizes
+ * (Note: can be overridden by calling reset() multiple times in a row)
+ * Never shrink below initialSize
+ *
+ * Shrink in exact reverse sequence of growth - using the subtraction method
+ * and then (for small enough sizes) the dividing method
+ *
+ * Shrink by one jump if that is large enough to hold the larger of the prev 2 sizes
+
+ * @param doFullReset true means reallocate from scratch
+ */
void reset(boolean doFullReset) {
if (doFullReset) {
+ if (debugLogShrink) System.out.format("Debug shrink CommonAux full reset from %,d to %,d for %s%n",
+ getCapacity(), heapBaseSize, this.getClass().getSimpleName());
this.initMemory();
} else {
- resetToZeros();
+ final int curCapacity = getCapacity();
+ final int curSize = getSize();
+ int newSize = computeShrunkArraySize(
+ curCapacity, Math.max(prevSize, curSize), GROWTH_FACTOR, heapMultLimit, heapBaseSize);
+ if (newSize == getCapacity()) { // means didn't shrink
+ resetToZeros();
+ } else {
+ if (debugLogShrink) System.out.format("Debug shrink CommonAux from %,d to %,d, prevSize=%,d for %s%n",
+ curCapacity, newSize, prevSize, this.getClass().getSimpleName());
+ initMemory(newSize);
+ }
+ prevSize = curSize;
}
this.heapPos = FIRST_CELL_REF;
}
@@ -92,9 +129,71 @@ abstract class CommonAuxHeap {
} while (size < needed_size);
return size;
}
+
+ /**
+ * Guard against two resets in a row, by having the minimum size
+ * @param capacity the current capacity
+ * @param size_used the maximum number of used entries, <= current capacity
+ * @param growth_factor is 2
+ * @param multiplication_limit the point where we start adding this limit, vs using the growth factor
+ * @return the capacity shrink down by one step, if that will still hold the size_used number of entries,
+ * minimum limited to min_size.
+ */
+ static int computeShrunkArraySize(
+ int capacity,
+ int size_used,
+ int growth_factor,
+ int multiplication_limit,
+ int min_size) {
+ int nbrOfSteps = 0;
+ if (capacity < size_used) {
+ throw new IllegalArgumentException("The Capacity " + capacity + " must be >= sized_used " + size_used);
+ }
+
+ // this if for shrinking down 1 step if possible
+ int shrunk = ((capacity - multiplication_limit) < multiplication_limit) ?
+ // the last expansion was by multiplying; the next expansion would be by adding
+ capacity / growth_factor :
+ capacity - multiplication_limit;
+
+ return (size_used > shrunk) ? capacity : shrunk;
+
+
+ // this is for shrinking down to the minimum needed, and then expanding back up halfway (by # of steps)
+// while (true) {
+// int shrunk = ((capacity - multiplication_limit) < multiplication_limit) ?
+// // the last expansion was by multiplying; the next expansion would be by adding
+// capacity / growth_factor :
+// capacity - multiplication_limit;
+// if (size_used > shrunk) {
+// return computeHalfWaySize(capacity, nbrOfSteps, growth_factor, multiplication_limit);
+// }
+// if (shrunk < min_size) {
+// return computeHalfWaySize(min_size, nbrOfSteps, growth_factor, multiplication_limit);
+// }
+// nbrOfSteps ++;
+// capacity = shrunk;
+// }
+ }
+
+ static int computeHalfWaySize(int shrunkCapacity, final int nbrOfSteps, int growth_factor, int multiplication_limit) {
+ // n is nbrOfSteps / 2 rounded up, except for 1, where it is rounded down.
+ // to permit shrinking all the way to initial size
+ int n2 = nbrOfSteps >> 1;
+ int n = (nbrOfSteps == 1) ? 0 :
+ ((nbrOfSteps % 2) == 0) ? n2 :
+ n2 + 1;
+
+ for (int i = 0; i < n; i++) {
+ shrunkCapacity = (shrunkCapacity < multiplication_limit)? shrunkCapacity * growth_factor : shrunkCapacity + multiplication_limit;
+ }
+ return shrunkCapacity;
+ }
int getSize() {
return this.heapPos;
}
+
+ abstract int getCapacity();
}
Modified: uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/Heap.java
URL: http://svn.apache.org/viewvc/uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/Heap.java?rev=1665367&r1=1665366&r2=1665367&view=diff
==============================================================================
--- uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/Heap.java (original)
+++ uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/Heap.java Mon Mar 9 21:44:12 2015
@@ -32,6 +32,11 @@ import org.apache.uima.internal.util.Int
*/
public final class Heap {
+ private static final boolean debugLogShrink = false;
+// static {
+// debugLogShrink = System.getProperty("uima.debug.ihs") != null;
+// }
+
/**
* Minimum size of the heap. Currently set to <code>1000</code>.
*/
@@ -58,6 +63,8 @@ public final class Heap {
// End of heap. In the current implementation, this is the same as
// this.heap.length at all times.
private int max;
+
+ private int prevSize = 1;
// Serialization constants. There are holes in the numbering for historical
// reasons. Keep the holes for compatibility.
@@ -103,6 +110,12 @@ public final class Heap {
this.pos = 1; // 0 is not a valid address
this.max = this.heap.length;
}
+
+ private final void initHeap(int size) {
+ this.heap = new int[size];
+ this.pos = 1; // 0 is not a valid address
+ this.max = this.heap.length;
+ }
void reinit(int[] md, int[] shortHeap) {
if (md == null) {
@@ -136,7 +149,8 @@ public final class Heap {
}
// Set position and max.
this.pos = shortHeap.length;
- this.max = this.initialSize;
+// this.max = this.initialSize; // TODO fix me
+ this.max = this.heap.length; // heap could be repl by short heap
}
/**
@@ -162,7 +176,7 @@ public final class Heap {
}
/**
- * @return The overall size of the heap (including unused space).
+ * @return The overall size of the heap (in words) (including unused space).
*/
int getHeapSize() {
return this.heap.length;
@@ -185,7 +199,7 @@ public final class Heap {
private void grow() {
final int start = this.heap.length;
// This will grow the heap by doubling its size if it's smaller than
- // DEFAULT_SIZE, and by DEFAULT_SIZE if it's larger.
+ // MULTIPLICATION_LIMIT, and by MULTIPLICATION_LIMIT if it's larger.
this.heap = IntArrayUtils.ensure_size(this.heap, start + this.initialSize, 2, MULTIPLICATION_LIMIT);
this.max = this.heap.length;
}
@@ -199,12 +213,37 @@ public final class Heap {
/**
* Reset the temporary heap.
+ *
+ * Logic for shrinking:
+ *
+ * Based on a short history of the sizes needed to hold the larger of the previous 2 sizes
+ * (Note: can be overridden by calling reset() multiple times in a row)
+ * Never shrink below initialSize
+ *
+ * Shrink in exact reverse sequence of growth - using the subtraction method
+ * and then (for small enough sizes) the dividing method
+ *
+ * Shrink 1/2 the distance to the size needed to hold the large of the prev 2 sizes
*/
+
void reset(boolean doFullReset) {
if (doFullReset) {
+ if (debugLogShrink) System.out.format("Debug shrink Heap full reset from %,d, prevSize = %n", getHeapSize(), prevSize);
this.initHeap();
} else {
- Arrays.fill(this.heap, 0, this.pos, 0);
+ final int curCapacity = getHeapSize();
+ final int curSize = getCellsUsed();
+ // shrink based on max of prevSize and curSize
+ final int newCapacity = CommonAuxHeap.computeShrunkArraySize(
+ curCapacity, Math.max(curSize, prevSize), 2, MULTIPLICATION_LIMIT, initialSize);
+ if (newCapacity == curCapacity) {
+ Arrays.fill(this.heap, 0, this.pos, 0);
+ } else {
+ if (debugLogShrink) System.out.format("Debug shrink Heap from %,d to %,d, prevSize= %,d%n",
+ curCapacity, newCapacity, prevSize);
+ this.initHeap(newCapacity);
+ }
+ prevSize = curSize;
this.pos = 1;
}
}
Modified: uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/LongHeap.java
URL: http://svn.apache.org/viewvc/uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/LongHeap.java?rev=1665367&r1=1665366&r2=1665367&view=diff
==============================================================================
--- uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/LongHeap.java (original)
+++ uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/LongHeap.java Mon Mar 9 21:44:12 2015
@@ -39,7 +39,15 @@ final class LongHeap extends CommonAuxHe
final void initMemory() {
this.heap = new long[this.heapBaseSize];
}
+
+ final void initMemory(int size) {
+ this.heap = new long[size];
+ }
+ final int getCapacity() {
+ return this.heap.length;
+ }
+
void growHeapIfNeeded() {
if (heap.length >= heapPos)
return;
Modified: uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/ShortHeap.java
URL: http://svn.apache.org/viewvc/uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/ShortHeap.java?rev=1665367&r1=1665366&r2=1665367&view=diff
==============================================================================
--- uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/ShortHeap.java (original)
+++ uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/ShortHeap.java Mon Mar 9 21:44:12 2015
@@ -39,6 +39,14 @@ final class ShortHeap extends CommonAuxH
final void initMemory() {
this.heap = new short[this.heapBaseSize];
}
+
+ final void initMemory(int size) {
+ this.heap = new short[size];
+ }
+
+ final int getCapacity() {
+ return this.heap.length;
+ }
void growHeapIfNeeded() {
if (heap.length >= heapPos)
Modified: uima/uimaj/trunk/uimaj-core/src/test/java/org/apache/uima/cas/impl/CasResetResizeTest.java
URL: http://svn.apache.org/viewvc/uima/uimaj/trunk/uimaj-core/src/test/java/org/apache/uima/cas/impl/CasResetResizeTest.java?rev=1665367&r1=1665366&r2=1665367&view=diff
==============================================================================
--- uima/uimaj/trunk/uimaj-core/src/test/java/org/apache/uima/cas/impl/CasResetResizeTest.java (original)
+++ uima/uimaj/trunk/uimaj-core/src/test/java/org/apache/uima/cas/impl/CasResetResizeTest.java Mon Mar 9 21:44:12 2015
@@ -19,6 +19,10 @@
package org.apache.uima.cas.impl;
+import java.util.Collections;
+import java.util.Map;
+import java.util.Properties;
+
import junit.framework.Assert;
import junit.framework.TestCase;
@@ -27,6 +31,7 @@ import org.apache.uima.analysis_engine.T
import org.apache.uima.analysis_engine.TextAnalysisEngine;
import org.apache.uima.cas.CAS;
import org.apache.uima.cas.Type;
+import org.apache.uima.resource.Resource;
import org.apache.uima.test.junit_extension.JUnitExtension;
import org.apache.uima.util.XMLInputSource;
@@ -48,8 +53,11 @@ public class CasResetResizeTest extends
new XMLInputSource(JUnitExtension
.getFile("TextAnalysisEngineImplTest/TestPrimitiveTae1.xml")));
- // check default setting
- TextAnalysisEngine taeDefault = UIMAFramework.produceTAE(testDescriptor);
+
+ Properties perfSettings = new Properties();
+ perfSettings.put(UIMAFramework.CAS_INITIAL_HEAP_SIZE, "50000");
+ //(UIMAFramework.CAS_INITIAL_HEAP_SIZE, (Object)50000);
+ TextAnalysisEngine taeDefault = UIMAFramework.produceTAE(testDescriptor, Collections.singletonMap(Resource.PARAM_PERFORMANCE_TUNING_SETTINGS, (Object) perfSettings));
CAS cas = taeDefault.newCAS();
int heapSize = ((CASImpl) cas).getHeap().getHeapSize();
int bufSize = ((CASImpl)cas).getHeap().heap.length;
@@ -63,33 +71,42 @@ public class CasResetResizeTest extends
cas.createAnnotation(annotType, i, i);
}
- heapSize = ((CASImpl) cas).getHeap().getHeapSize();
- bufSize = ((CASImpl)cas).getHeap().heap.length;
- //System.out.println("Heap size: " + heapSize + ", buffer size: " + bufSize);
- assertTrue(heapSize <= bufSize);
- Assert.assertTrue(heapSize > CASImpl.DEFAULT_RESET_HEAP_SIZE);
+ // heap growth (words):
+ // 500K is the switchover point
+ // 16 * 1024 *1024 = 16,777,216 is the switchover point
+ // then the additional is 16,777,216
+ // 50k, 100k, 200k, 400k, 800k, 1.6m, 3.2m, 6.4m, 12.8m
+ // 8 7 6 5 4 3 2 1 0
- //reset the CAS - it should shrink
- cas.reset();
heapSize = ((CASImpl) cas).getHeap().getHeapSize();
- bufSize = ((CASImpl)cas).getHeap().heap.length;
- //System.out.println("Heap size: " + heapSize + ", buffer size: " + bufSize);
- assertTrue(heapSize <= bufSize);
- Assert.assertTrue(bufSize < CASImpl.DEFAULT_RESET_HEAP_SIZE);
-
+ assertEquals(12800000, heapSize);
+ //reset the CAS - it should shrink the 4th time
+ // first time, Cas is of capacity 8,500,000, but has 8,000,008 cells used ==> shrunk size should remain the same
+ // second time, prev is 8,500,000, so no shrinking
+ // third time, gets shrunk to half the # of steps
+ // fourth time, gets shrunk to half the # of steps
+
+// int[] expected = new int[] {8300000, 8300000, 3800000, 1300000, 400000, 200000, 100000, 50000}; // for doubling
+
+ int[] expected = {12800000, 12800000, 6400000, 3200000, 1600000, 800000, 400000, 200000}; // for 1 step
+ for (int i = 0; i < 8; i++) {
+ cas.reset();
+ heapSize = ((CASImpl) cas).getHeap().getHeapSize();
+ assertEquals(expected[i], heapSize);
+ }
+
//If instead we create the annotations in smaller chunks and reset each time,
- //the CAS buffer size shouldn't grow
+ //the CAS buffer size shouldn't grow
+ cas = taeDefault.newCAS();
+
for (int j = 0; j < 10; j++) {
for (int i = 0; i < 200000; i++) {
cas.createAnnotation(annotType, i, i);
}
heapSize = ((CASImpl) cas).getHeap().getHeapSize();
- bufSize = ((CASImpl)cas).getHeap().heap.length;
- //System.out.println("Heap size: " + heapSize + ", buffer size: " + bufSize);
- assertTrue(heapSize <= bufSize);
- Assert.assertTrue(bufSize < CASImpl.DEFAULT_RESET_HEAP_SIZE);
+ Assert.assertTrue(heapSize == 1600000);
cas.reset();
}
Added: uima/uimaj/trunk/uimaj-core/src/test/java/org/apache/uima/cas/impl/CommonAuxHeapTest.java
URL: http://svn.apache.org/viewvc/uima/uimaj/trunk/uimaj-core/src/test/java/org/apache/uima/cas/impl/CommonAuxHeapTest.java?rev=1665367&view=auto
==============================================================================
--- uima/uimaj/trunk/uimaj-core/src/test/java/org/apache/uima/cas/impl/CommonAuxHeapTest.java (added)
+++ uima/uimaj/trunk/uimaj-core/src/test/java/org/apache/uima/cas/impl/CommonAuxHeapTest.java Mon Mar 9 21:44:12 2015
@@ -0,0 +1,83 @@
+/*
+ * 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.cas.impl;
+
+import junit.framework.Assert;
+import junit.framework.TestCase;
+
+import org.apache.uima.UIMAFramework;
+import org.apache.uima.analysis_engine.TaeDescription;
+import org.apache.uima.analysis_engine.TextAnalysisEngine;
+import org.apache.uima.cas.CAS;
+import org.apache.uima.cas.Type;
+import org.apache.uima.test.junit_extension.JUnitExtension;
+import org.apache.uima.util.XMLInputSource;
+
+
+public class CommonAuxHeapTest extends TestCase {
+
+ public void testcomputeShrunkArraySize() {
+ CommonAuxHeap cah = new ByteHeap();
+
+ // should return 1/2 way to the size needed
+ // cap sz limit
+ assertEquals(1000, CommonAuxHeap.computeShrunkArraySize(1000, 1000, 2, 1000, 10));
+ boolean ok = false;
+ try {
+ CommonAuxHeap.computeShrunkArraySize(1000, 10000, 2, 1000, 10);
+ } catch (IllegalArgumentException e) {
+ ok = true;
+ }
+ assertTrue(ok);
+ assertEquals(1000, CommonAuxHeap.computeShrunkArraySize(1000, 999, 2, 1000, 10));
+ assertEquals(1000, CommonAuxHeap.computeShrunkArraySize(1000, 501, 2, 1000, 10));
+ assertEquals(500, CommonAuxHeap.computeShrunkArraySize(1000, 500, 2, 1000, 10));
+
+ assertEquals(1000, CommonAuxHeap.computeShrunkArraySize(1000, 999, 2, 999, 10));
+ assertEquals(1000, CommonAuxHeap.computeShrunkArraySize(1000, 501, 2, 999, 10));
+ assertEquals( 500, CommonAuxHeap.computeShrunkArraySize(1000, 500, 2, 999, 10));
+
+ assertEquals(1000, CommonAuxHeap.computeShrunkArraySize(1000, 999, 2, 500, 10));
+ assertEquals(1000, CommonAuxHeap.computeShrunkArraySize(1000, 501, 2, 500, 10));
+ assertEquals( 500, CommonAuxHeap.computeShrunkArraySize(1000, 500, 2, 500, 10));
+
+ assertEquals(1000, CommonAuxHeap.computeShrunkArraySize(1000, 999, 2, 300, 10));
+ assertEquals(1000, CommonAuxHeap.computeShrunkArraySize(1000, 701, 2, 300, 10));
+ assertEquals( 700, CommonAuxHeap.computeShrunkArraySize(1000, 700, 2, 300, 10));
+ assertEquals( 700, CommonAuxHeap.computeShrunkArraySize(1000, 401, 2, 300, 10));
+
+ assertEquals( 700, CommonAuxHeap.computeShrunkArraySize(1000, 400, 2, 300, 10)); // 1000 700 400, 400 700 shrink 2, exp 1
+ assertEquals( 700, CommonAuxHeap.computeShrunkArraySize(1000, 201, 2, 300, 10)); // 1000 700 400, 400 700 shrink 2, exp 1
+ assertEquals( 700, CommonAuxHeap.computeShrunkArraySize(1000, 200, 2, 300, 10)); // 1000 700 400 200, 200 400 700 shrink 3, exp 2
+ assertEquals( 700, CommonAuxHeap.computeShrunkArraySize(1000, 101, 2, 300, 10)); // 1000 700 400 200, 200 400 700 shrink 3, exp 2
+// assertEquals( 400, CommonAuxHeap.computeShrunkArraySize(1000, 100, 2, 300, 10)); // 1000 700 400 200 100 100 200 400 shrink 4, exp 2
+ assertEquals( 400, CommonAuxHeap.computeShrunkArraySize( 700, 100, 2, 300, 10)); // 700 400 200 100 100 200 400 shrink 3, exp 2
+
+ // shrink by 1 tests
+ assertEquals( 700, CommonAuxHeap.computeShrunkArraySize(1000, 200, 2, 300, 399)); // 1000 700 400 399, 399 699 shrink 3, exp 2
+
+ // halving tests
+// assertEquals( 699, CommonAuxHeap.computeShrunkArraySize(1000, 200, 2, 300, 399)); // 1000 700 400 399, 399 699 shrink 3, exp 2
+// assertEquals( 688, CommonAuxHeap.computeShrunkArraySize(1000, 101, 2, 300, 388)); // 1000 700 400 388, 388 688
+// assertEquals( 699, CommonAuxHeap.computeShrunkArraySize(1000, 100, 2, 300, 399)); // 1000 700 400 399, 399 699
+
+ }
+
+}