Author: schor
Date: Fri Oct 24 21:23:32 2014
New Revision: 1634141
URL: http://svn.apache.org/r1634141
Log:
[UIMA-4061] improve Positive Int Set switching logic and measurements, update
tests
Modified:
uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/IntBitSet.java
uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/IntHashSet.java
uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/PositiveIntSet.java
uima/uimaj/trunk/uimaj-core/src/test/java/org/apache/uima/internal/util/IntBitSetTest.java
uima/uimaj/trunk/uimaj-core/src/test/java/org/apache/uima/internal/util/IntHashSetTest.java
uima/uimaj/trunk/uimaj-core/src/test/java/org/apache/uima/internal/util/PositiveIntSetTest.java
Modified:
uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/IntBitSet.java
URL:
http://svn.apache.org/viewvc/uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/IntBitSet.java?rev=1634141&r1=1634140&r2=1634141&view=diff
==============================================================================
---
uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/IntBitSet.java
(original)
+++
uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/IntBitSet.java
Fri Oct 24 21:23:32 2014
@@ -42,25 +42,25 @@ public class IntBitSet {
private int size = 0; // tracked here to avoid slow counting of cardinality
- private int offset = 0;
+ private final int offset;
- /**
- * Sets the lowest int value that can be kept; trying to add a lower one
throws an error
- * <ul>
- * <li>Allows for a more compact representation, potentially</li>
- * <li>only can be set if the size is 0</li>
- * </ul>
- * @param offset - the lowest value that can be kept in the set. 0 is
allowed.
- */
- public void setOffset(int offset) {
- if (size != 0) {
- throw new IllegalStateException("Cannot set offset unless set is empty");
- }
- if (offset < 0) {
- throw new IllegalArgumentException("Offset must be 0 or a positive int,
was " + offset);
- }
- this.offset = offset;
- }
+// /**
+// * Sets the lowest int value that can be kept; trying to add a lower one
throws an error
+// * <ul>
+// * <li>Allows for a more compact representation, potentially</li>
+// * <li>only can be set if the size is 0</li>
+// * </ul>
+// * @param offset - the lowest value that can be kept in the set. 0 is
allowed.
+// */
+// public void setOffset(int offset) {
+// if (size != 0) {
+// throw new IllegalStateException("Cannot set offset unless set is
empty");
+// }
+// if (offset < 0) {
+// throw new IllegalArgumentException("Offset must be 0 or a positive
int, was " + offset);
+// }
+// this.offset = offset;
+// }
/**
* @return the current offset
*/
@@ -80,7 +80,12 @@ public class IntBitSet {
* @param maxInt the biggest int (perhaps plus an offset) that can be held
without growing the space
*/
public IntBitSet(int maxInt) {
+ this(maxInt, 0);
+ }
+
+ public IntBitSet(int maxInt, int offset) {
set = new BitSet(Math.max(1, maxInt));
+ this.offset = offset;
}
/**
Modified:
uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/IntHashSet.java
URL:
http://svn.apache.org/viewvc/uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/IntHashSet.java?rev=1634141&r1=1634140&r2=1634141&view=diff
==============================================================================
---
uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/IntHashSet.java
(original)
+++
uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/IntHashSet.java
Fri Oct 24 21:23:32 2014
@@ -36,6 +36,7 @@ import org.apache.uima.jcas.impl.JCasHas
*/
public class IntHashSet {
+ public static final float DEFAULT_LOAD_FACTOR = 0.66F;
// set to true to collect statistics for tuning
// you have to also put a call to showHistogram() at the end of the run
private static final boolean TUNE = false;
@@ -49,7 +50,7 @@ public class IntHashSet {
// 3 * 4 12 bytes per entry
// This compares with 160 bytes/entry for the IntArrayRBT impl
- private final float loadFactor = 0.66F;
+ private final float loadFactor = DEFAULT_LOAD_FACTOR;
private final int initialCapacity;
@@ -81,6 +82,32 @@ public class IntHashSet {
}
}
+ /**
+ * The number of 32 bit words that are reserved when
+ * creating a table to hold the specified number of elements
+ *
+ * The number is a power of 2.
+ *
+ * The number is at least 16.
+ *
+ * The number is such that you could add this many elements without
+ * triggering the capacity expansion.
+ *
+ * @param numberOfElements
+ * @return
+ */
+ public int tableSpace(int numberOfElements) {
+ return tableSpace(numberOfElements, loadFactor);
+ }
+
+ public static int tableSpace(int numberOfElements, Float factor) {
+ if (numberOfElements < 0) {
+ throw new IllegalArgumentException("must be > 0");
+ }
+ final int capacity = Math.round(numberOfElements / factor);
+ return Math.max(16, nextHigherPowerOf2(capacity));
+ }
+
private void newTableKeepSize(int capacity) {
capacity = Math.max(16, nextHigherPowerOf2(capacity));
keys = new int[capacity];
@@ -94,8 +121,20 @@ public class IntHashSet {
size++;
}
+ public boolean wontExpand() {
+ return wontExpand(1);
+ }
+
+ public boolean wontExpand(int n) {
+ return (size + n) < sizeWhichTriggersExpansion;
+ }
+
public int getSpaceUsedInWords() {
- return keys.length + 8; // 8 is overhead for this class excluding any
Java object overhead
+ return keys.length; // 8 is overhead for this class excluding any Java
object overhead
+ }
+
+ public static int getSpaceOverheadInWords() {
+ return 8;
}
private void increaseTableCapacity() {
@@ -256,6 +295,12 @@ public class IntHashSet {
if (keys[i] != 0) {
keys[i] = 0;
size--;
+ if (key == mostPositive) {
+ mostPositive --; // a weak adjustment
+ }
+ if (key == mostNegative) {
+ mostNegative ++; // a weak adjustment
+ }
return true;
}
return false;
Modified:
uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/PositiveIntSet.java
URL:
http://svn.apache.org/viewvc/uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/PositiveIntSet.java?rev=1634141&r1=1634140&r2=1634141&view=diff
==============================================================================
---
uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/PositiveIntSet.java
(original)
+++
uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/PositiveIntSet.java
Fri Oct 24 21:23:32 2014
@@ -32,19 +32,29 @@ import java.util.NoSuchElementException;
*
* For more dense ints, it uses bitSets or bitSets with an offset
*
- * It switches when adding new members if the other representation is
sufficiently smaller (using a Hysteresis of 16 words)
+ * It switches when adding new members if the other representation is
sufficiently smaller
*/
public class PositiveIntSet {
// number of words a inthashset has to be better than intbitset to cause
switch
private static final int HYSTERESIS = 16;
-
- private IntBitSet intBitSet;
- private IntHashSet intHashSet;
+ // Extra space in bitset for initial capacity - can add an int up to that
size
+ // 64 *4 is 8 words, = 256.
+ private static final int BIT_SET_OVERALLOCATE = 64 * 4;
+
+ // Extra space in hashset for initial capacity - can add a minimum of that
many more members
+ // without hitting the hash-set doubling.
+ private static final int HASH_SET_OVERALLOCATE = 8;
+ // Extra space in hashset for initial capacity - when creating from bitmap
set - multiplier of existing size
+ private static final int HASH_SET_OVERALLOCATE_MULTIPLIER = 1; // bit shift
right = divide by 2 = 50% of existing capacity
+
+ private IntBitSet intBitSet = null;
+
+ private IntHashSet intHashSet = null;
//package private for test case
- boolean isBitSet;
+ boolean isBitSet = true;
/**
* Set false once we find we have to reduce the bit offset
@@ -52,11 +62,6 @@ public class PositiveIntSet {
//package private for test case
boolean useOffset = true;
- public PositiveIntSet() {
- intBitSet = new IntBitSet();
- isBitSet = true;
- }
-
public IntListIterator getUnorderedIterator() {
if (isBitSet) {
return intBitSet.getIterator();
@@ -166,13 +171,13 @@ public class PositiveIntSet {
*/
private void adjustBitSetForLowerOffset(int key) {
final int largestInt = intBitSet.getLargestMenber();
- final int bitSetSpaceNeeded = getBitSetSpaceFromMaxInt(largestInt); //
doesn't use offset
+ final int bitSetSpaceNeeded = getBitSetSpaceFromMaxInt(largestInt, 0); //
doesn't use offset
final int hashSetSpaceNeeded = getHashSetSpace(intBitSet.size());
if (hashSetSpaceNeeded < (bitSetSpaceNeeded - HYSTERESIS)) {
switchToHashSet(size());
} else {
- IntBitSet bs = new IntBitSet(largestInt);
+ IntBitSet bs = new IntBitSet(largestInt + BIT_SET_OVERALLOCATE);
IntListIterator it = intBitSet.getIterator();
while (it.hasNext()) {
bs.add(it.next());
@@ -224,40 +229,75 @@ public class PositiveIntSet {
}
/**
- * number of 32 bit words in use by bit set, given the max key (less offset)
+ * Only called if key won't fit in existing hashset allocation
+ *
+ * Using existing bitset, compute what its size() (capacity) would be if the
+ * key were added; include the overhead of the intbitset class.
+ *
+ * long words required = larger of double the current size, or the number of
words required
+
* @param maxKeyLessOffset
* @return number of words needed to store the highest value
*/
- private int getBitSetSpaceFromMaxInt(int maxKeyLessOffset) {
+ private int getBitSetSpaceFromMaxInt(int maxKeyLessOffset, int spaceUsed) {
+ int w64 = 1 + (maxKeyLessOffset >> 6); // 64 bits per long, add one
because 0 to 63 takes one word)
+ spaceUsed = spaceUsed >> 5; // in # of long words, * 2 because the alloc
doubles the space
+
+ int newSpace = Math.max(spaceUsed, w64) << 1; // size is in 32 bit words
at the end
// e.g., 31 key => 1 word, 32 key => 2 words
- return 2 + (maxKeyLessOffset >> 5) + 2; // add 2 because the bits are
stored in 2 words (1 long), and 2 more for IntBitSet object overhead
+ return newSpace + 2; // 2 more for IntBitSet object overhead
}
- private int getHashSetSpace(int numberOfEntries) {
- long v = numberOfEntries * 3 + 8; // plus 8 is for the overhead of the
intHashSet object.
- if (v > Integer.MAX_VALUE) {
- throw new RuntimeException("value overflowed int, orig was " +
numberOfEntries);
- }
- return (int) v; // the number of 32 bit words needed is 1.5 to 3; 3 is
worst case
+ /**
+ * Only called if key won't fit in existing allocation
+ *
+ * returns new hash table size ( usually double) + overhead
+ *
+ * @param numberOfEntries
+ * @return
+ */
+ private int getHashSetSpace() {
+ return intHashSet.getSpaceUsedInWords() * 2 +
IntHashSet.getSpaceOverheadInWords();
+ }
+
+ /**
+ * When converting from bitset to hash set, the initial hash set should be
+ * big enough so that it takes a while before it is doubled-expanded.
+ *
+ * @param existingSize
+ * @return
+ */
+ private int getHashSetOverAllocateSize(int existingSize) {
+ return existingSize + (existingSize >> HASH_SET_OVERALLOCATE_MULTIPLIER) +
HASH_SET_OVERALLOCATE;
+ }
+
+ /**
+ * For the case where the intHashSet doesn't yet exist
+ * @param numberOfElements -
+ * @return the size in words
+ */
+ private int getHashSetSpace(int numberOfElements) {
+ return IntHashSet.tableSpace(numberOfElements,
IntHashSet.DEFAULT_LOAD_FACTOR) +
+ IntHashSet.getSpaceOverheadInWords();
}
/**
* logic for switching representation
*
* BitSet preferred - is faster, can be more compact, and permits ordered
iteration
- *
* HashSet used when BitSet is too space inefficient.
- * MaxInt stored determines size: = MaxInt / 8 bytes.
- * HashSet takes 12 bytes / entry.
- *
- * switch to HashSet from BitSet if:
- * HashSet space < BitSet space
- * size * 12 MaxInt / 8
- * with hysteresis
+ *
+ * Avoid switching if the new key being added won't increase the
representation size
+ * - for hash: if number of elements +1 won't cause doubling of the hash
table
+ * - for bitset: if key will fit in existing "capacity"
+ *
+ * Compute space needed after adding
+ * - bitset: array doubles
+ * - hashset: array doubles
*
- * switch to BitSet from HashSet if:
- * BitSet used when its space requirement is less than hashset, with
hysteresis:
- *
+ * Preventing jitters back and forth:
+ * - removes don't cause switching
+ * - compare against other size including its non-linear space jumps.
*/
private void maybeSwitchRepresentation(int key) {
@@ -272,11 +312,24 @@ public class PositiveIntSet {
* unless that has been a bad strategy for this
* instance already
********/
- if (intBitSet.size() == 0 && useOffset) {
- // initialize bitSetOffset to the key, minus some amount to allow a
bit of previous values
- intBitSet.setOffset(Math.max(0, key - 63));
- // because of offset, won't have to switch to hash for this key
- return;
+ if (intBitSet == null) {
+ if (useOffset) {
+
+ // initialize bitSetOffset to the key, minus some amount to allow
some storage of previous values
+ // a minimum of 63, a maximum of 512 == 16 words, when key is > 4K
(128 words)
+ final int spaceForLesserKeys = Math.min(1023, Math.max(63, key >>
3));
+ final int offset = Math.max(0, key - spaceForLesserKeys);
+ intBitSet = new IntBitSet(BIT_SET_OVERALLOCATE + key - offset,
offset);
+ // because of offset, won't have to switch to hash for this key
+ //
+ // force an initial allocation of this sufficient to keep
+ // a) the space below, plus
+ // b)
+ return;
+ } else {
+ intBitSet = new IntBitSet(BIT_SET_OVERALLOCATE + key);
+ // don't return, see if we should immediately switch to hash
representation
+ }
}
final int offset = intBitSet.getOffset();
@@ -287,16 +340,18 @@ public class PositiveIntSet {
}
// return if key fits in existing allocation
- if ((key - offset) < intBitSet.getSpaceUsed_in_bits()) {
+ final int spaceUsed = intBitSet.getSpaceUsed_in_bits();
+ if ((key - offset) < spaceUsed) {
return;
}
// space used in words (32 bit words)
- final int bitSetSpaceNeeded = getBitSetSpaceFromMaxInt(key - offset);
- final int hashSetSpaceNeeded = getHashSetSpace(intBitSet.size());
+ final int bitSetSpaceNeeded = getBitSetSpaceFromMaxInt(key - offset,
spaceUsed);
+ final int hashSetOverAllocateSize =
getHashSetOverAllocateSize(intBitSet.size() + 1);
+ final int hashSetOverAllocateSpace =
getHashSetSpace(hashSetOverAllocateSize);
// switch if hashmap space plus hysteresis would be < bitmap space
- if (hashSetSpaceNeeded < (bitSetSpaceNeeded - HYSTERESIS)) {
- switchToHashSet(intBitSet.size());
+ if (hashSetOverAllocateSpace < (bitSetSpaceNeeded - HYSTERESIS)) {
+ switchToHashSet(hashSetOverAllocateSize);
}
return;
}
@@ -308,12 +363,16 @@ public class PositiveIntSet {
// space used in words (32 bit words)
// don't bother to include the new element - it might not be "added"
// if it was already there, and only serves to decrease hysteresis a bit
+
+ if (intHashSet.wontExpand()) {
+ return;
+ }
- final int hashSetSpaceNeeded = getHashSetSpace(size());
+ final int hashSetSpaceNeeded = getHashSetSpace();
final int maxInt = intHashSet.getMostPositive();
final int offset = useOffset ? intHashSet.getMostNegative() : 0;
- final int bitSetSpaceNeeded = getBitSetSpaceFromMaxInt(maxInt - offset);
+ final int bitSetSpaceNeeded =
getBitSetSpaceFromMaxInt(BIT_SET_OVERALLOCATE + maxInt - offset, 0);
if (bitSetSpaceNeeded < (hashSetSpaceNeeded - HYSTERESIS)) {
switchToBitSet(maxInt, offset);
@@ -332,8 +391,7 @@ public class PositiveIntSet {
private void switchToBitSet(int maxInt, int offset) {
isBitSet = true;
- intBitSet = new IntBitSet(maxInt - offset);
- intBitSet.setOffset(offset);
+ intBitSet = new IntBitSet(BIT_SET_OVERALLOCATE + maxInt - offset, offset);
IntListIterator it = intHashSet.getIterator();
while (it.hasNext()) {
intBitSet.add(it.next());
Modified:
uima/uimaj/trunk/uimaj-core/src/test/java/org/apache/uima/internal/util/IntBitSetTest.java
URL:
http://svn.apache.org/viewvc/uima/uimaj/trunk/uimaj-core/src/test/java/org/apache/uima/internal/util/IntBitSetTest.java?rev=1634141&r1=1634140&r2=1634141&view=diff
==============================================================================
---
uima/uimaj/trunk/uimaj-core/src/test/java/org/apache/uima/internal/util/IntBitSetTest.java
(original)
+++
uima/uimaj/trunk/uimaj-core/src/test/java/org/apache/uima/internal/util/IntBitSetTest.java
Fri Oct 24 21:23:32 2014
@@ -29,8 +29,7 @@ public class IntBitSetTest extends TestC
public void setUp() {
ibs = new IntBitSet();
- ibs1k = new IntBitSet();
- ibs1k.setOffset(1000);
+ ibs1k = new IntBitSet(63, 1000);
}
public void testBasic() {
@@ -62,20 +61,18 @@ public class IntBitSetTest extends TestC
assertEquals(3*64, ibs.getSpaceUsed_in_bits());
assertEquals(6, ibs.getSpaceUsed_in_words());
- ibs = new IntBitSet(64);
- ibs.setOffset(1000);
+ ibs = new IntBitSet(64, 1000);
ibs.add(1064);
assertEquals(1,ibs.size());
assertEquals(2*64, ibs.getSpaceUsed_in_bits());
- ibs = new IntBitSet(64);
- ibs.setOffset(1000);
+ ibs = new IntBitSet(64, 1000);
+
ibs.add(1063);
assertEquals(1*64, ibs.getSpaceUsed_in_bits());
assertEquals(1,ibs.size());
- ibs = new IntBitSet(6 * 64);
- ibs.setOffset(1000);
+ ibs = new IntBitSet(6 * 64, 1000);
ibs.add(1000 + 6 * 64 - 1);
assertEquals(6*64, ibs.getSpaceUsed_in_bits());
@@ -103,8 +100,7 @@ public class IntBitSetTest extends TestC
}
public void testContains() {
- ibs = new IntBitSet();
- ibs.setOffset(1000);
+ ibs = new IntBitSet(63, 1000);
ibs.add(1015);
ibs.add(1188);
Modified:
uima/uimaj/trunk/uimaj-core/src/test/java/org/apache/uima/internal/util/IntHashSetTest.java
URL:
http://svn.apache.org/viewvc/uima/uimaj/trunk/uimaj-core/src/test/java/org/apache/uima/internal/util/IntHashSetTest.java?rev=1634141&r1=1634140&r2=1634141&view=diff
==============================================================================
---
uima/uimaj/trunk/uimaj-core/src/test/java/org/apache/uima/internal/util/IntHashSetTest.java
(original)
+++
uima/uimaj/trunk/uimaj-core/src/test/java/org/apache/uima/internal/util/IntHashSetTest.java
Fri Oct 24 21:23:32 2014
@@ -57,7 +57,7 @@ public class IntHashSetTest extends Test
assertEquals(1000, ihs.getMostPositive());
assertEquals(-1000, ihs.getMostNegative());
ihs.remove(1000);
- assertEquals(1000, ihs.getMostPositive());
+ assertEquals(999, ihs.getMostPositive());
assertEquals(-1000, ihs.getMostNegative());
ihs.add(1001);
assertEquals(1001, ihs.getMostPositive());
@@ -80,7 +80,24 @@ public class IntHashSetTest extends Test
assertTrue(ihs.contains(1188));
assertTrue(ihs.contains(1040));
assertFalse(ihs.contains(0));
- assertFalse(ihs.contains(99));
-
+ assertFalse(ihs.contains(99));
+ }
+
+ public void testTableSpace() {
+ assertEquals(32, IntHashSet.tableSpace(19, 0.6f)); // 19 / .6 = 31.xxx,
round to 32
+ assertEquals(64, IntHashSet.tableSpace(21, 0.6f));
+ assertEquals(32, ihs.tableSpace(21));
+ }
+
+ public void testWontExpand() {
+ ihs = new IntHashSet(21);
+ assertEquals(32, ihs.getSpaceUsedInWords());
+ assertTrue(ihs.wontExpand(20));
+ assertFalse(ihs.wontExpand(21));
}
+
+
+
+
+
}
Modified:
uima/uimaj/trunk/uimaj-core/src/test/java/org/apache/uima/internal/util/PositiveIntSetTest.java
URL:
http://svn.apache.org/viewvc/uima/uimaj/trunk/uimaj-core/src/test/java/org/apache/uima/internal/util/PositiveIntSetTest.java?rev=1634141&r1=1634140&r2=1634141&view=diff
==============================================================================
---
uima/uimaj/trunk/uimaj-core/src/test/java/org/apache/uima/internal/util/PositiveIntSetTest.java
(original)
+++
uima/uimaj/trunk/uimaj-core/src/test/java/org/apache/uima/internal/util/PositiveIntSetTest.java
Fri Oct 24 21:23:32 2014
@@ -53,20 +53,22 @@ public class PositiveIntSetTest extends
s = new PositiveIntSet();
assertTrue(s.useOffset);
s.add(bb);
+
s.add(bb);
s.add(bb+1);
+ assertTrue(s.isBitSet);
s.add(bb+2);
- assertEquals(3, s.size());
assertTrue(s.isBitSet);
+ assertEquals(3, s.size());
assertTrue(s.useOffset);
// test offset converting to hashset
- s.add(bb - 66);
+ s.add(bb - 6000);
assertEquals(4, s.size());
assertFalse(s.isBitSet);
it = s.getOrderedIterator();
- assertEquals(bb-66, it.next());
+ assertEquals(bb-6000, it.next());
assertEquals(bb, it.next());
assertEquals(bb+1, it.next());
assertEquals(bb+2, it.next());
@@ -96,37 +98,28 @@ public class PositiveIntSetTest extends
// test switch from hash set to bit set
s.clear(); // keeps useOffset false
- s.add(767 - 64); // makes the space used by bit set = 25 words
+ s.add(1216); // makes the space used by bit set = 41 words
- for (int i = 1; i < 13; i++) {
+ for (int i = 1; i < 23; i++) {
s.add(i);
// System.out.println("i is " + i + ", isBitSet = " + s.isBitSet);
- assertTrue("i is " + i, (i < 12) ? (!s.isBitSet) : s.isBitSet);
+ assertTrue("i is " + i, (i < 20) ? (!s.isBitSet) : s.isBitSet);
}
it = s.getOrderedIterator();
- assertEquals(1,it.next());
- assertEquals(2,it.next());
- assertEquals(3,it.next());
- assertEquals(4,it.next());
- assertEquals(5,it.next());
- assertEquals(6,it.next());
- assertEquals(7,it.next());
- assertEquals(8,it.next());
- assertEquals(9,it.next());
- assertEquals(10,it.next());
- assertEquals(11,it.next());
- assertEquals(12,it.next());
- assertEquals(767-64,it.next());
+ for (int i = 1; i < 23; i++) {
+ assertEquals(i, it.next());
+ }
+ assertEquals(1216,it.next());
boolean reached = false;
- for (int i = 10; i < 5122; i = i <<1) {
+ for (int i = 10; i < 20000/*5122*/; i = i <<1) {
s.add(i); // switches to hash set when i = 2560. == 1010 0000 0000
(>>5 = 101 0000 = 80 (decimal)
// hash set size for 19 entries = 19 * 3 = 57
// bit set size for 2560 = 80 words
// bit set size for prev i (1280 dec) = 101 0000 0000 (>>5 =
10 1000) = 40 words
// if (!s.isBitSet) {
-// System.out.println("is Bit set? " + s.isBitSet + ", # of entries is
" + s.size());
+// System.out.println("is Bit set? " + s.isBitSet + ", i = " + i + ", #
of entries is " + s.size());
// }
reached = i >= 5120;
assertTrue((!reached) ? s.isBitSet : !s.isBitSet);
