Menu
▾
▴
[Bigdata-commit] SF.net SVN: bigdata:[4863] branches
|
From: <tho...@us...> - 2011-07-08 14:48:27
|
Revision: 4863
http://bigdata.svn.sourceforge.net/bigdata/?rev=4863&view=rev
Author: thompsonbry
Date: 2011-07-08 14:48:19 +0000 (Fri, 08 Jul 2011)
Log Message:
-----------
See https://sourceforge.net/apps/trac/bigdata/ticket/124 (TermIdEncoder needs to use more bits now that ITermIdCodes is gone).
This commit resolves the issue in both the 1.0.0 release branch and the current development branch.
- done. Modify TermIdEncoder to use all bits for pid and ctr,
rejecting only 0L, which is still reserved for null. Modify the
unit tests to verify that TermIdEncoder is now 32-bit clean for
both the pid and ctr values and test encode/decode against random
non-zero 64bit integers.
Files changed: TermIdEncoder, TestTermIdEncoder
- done. Modify BTree.PartitionedCounter to (a) permit the partition
local counter to wrap around, but not to come all the way back to
zero again; and (b) to use a 32-bit clean method to form the
int64 counter from the partitionId and the local counter value.
- done. Modify BTree.Counter to allow the counter to wrap through
the negative long integer values until it would reach ZERO (0L)
again and write unit tests for same.
Files changed: BTree, TestIndexCounter,
- done. Review the data structures which persist the partition
identifier to see if they are using packed (long) integers for
the pid. That will limit us to Integer.MAX_VALUE shards, which
is not all that bad. [it looks like things are 32-bit clean for
pid.]
Modified Paths:
--------------
branches/BIGDATA_RELEASE_1_0_0/bigdata/src/java/com/bigdata/btree/BTree.java
branches/BIGDATA_RELEASE_1_0_0/bigdata/src/test/com/bigdata/btree/TestIndexCounter.java
branches/BIGDATA_RELEASE_1_0_0/bigdata-rdf/src/java/com/bigdata/rdf/lexicon/TermIdEncoder.java
branches/BIGDATA_RELEASE_1_0_0/bigdata-rdf/src/test/com/bigdata/rdf/lexicon/TestTermIdEncoder.java
branches/TERMS_REFACTOR_BRANCH/bigdata/src/java/com/bigdata/btree/BTree.java
branches/TERMS_REFACTOR_BRANCH/bigdata/src/test/com/bigdata/btree/TestIndexCounter.java
branches/TERMS_REFACTOR_BRANCH/bigdata-rdf/src/java/com/bigdata/rdf/lexicon/TermIdEncoder.java
branches/TERMS_REFACTOR_BRANCH/bigdata-rdf/src/test/com/bigdata/rdf/lexicon/TestTermIdEncoder.java
Modified: branches/BIGDATA_RELEASE_1_0_0/bigdata/src/java/com/bigdata/btree/BTree.java
===================================================================
--- branches/BIGDATA_RELEASE_1_0_0/bigdata/src/java/com/bigdata/btree/BTree.java 2011-07-08 14:46:57 UTC (rev 4862)
+++ branches/BIGDATA_RELEASE_1_0_0/bigdata/src/java/com/bigdata/btree/BTree.java 2011-07-08 14:48:19 UTC (rev 4863)
@@ -49,6 +49,7 @@
import com.bigdata.mdi.LocalPartitionMetadata;
import com.bigdata.rawstore.Bytes;
import com.bigdata.rawstore.IRawStore;
+import com.bigdata.rdf.lexicon.TermIdEncoder;
/**
* <p>
@@ -1827,7 +1828,6 @@
* Mutable counter.
*
* @author <a href="mailto:tho...@us...">Bryan Thompson</a>
- * @version $Id$
*/
public static class Counter implements ICounter {
@@ -1835,7 +1835,8 @@
public Counter(final BTree btree) {
- assert btree != null;
+ if (btree == null)
+ throw new IllegalArgumentException();
this.btree = btree;
@@ -1863,11 +1864,10 @@
}
- if (counter == Long.MAX_VALUE) {
+ if (counter == 0L) {
/*
- * Actually, the counter would overflow on the next call but
- * this eager error makes the test for overflow atomic.
+ * The counter has wrapped back to ZERO.
*/
throw new RuntimeException("Counter overflow");
@@ -1876,7 +1876,7 @@
return counter;
- }
+ } // class Counter
}
@@ -1887,12 +1887,13 @@
* int32 word.
*
* @author <a href="mailto:tho...@us...">Bryan Thompson</a>
- * @version $Id$
*/
public static class PartitionedCounter implements ICounter {
private final int partitionId;
private final ICounter src;
+
+ private static final long MAX_LOCAL_COUNTER = 1L << 32;
public PartitionedCounter(final int partitionId, final ICounter src) {
@@ -1904,7 +1905,7 @@
this.src = src;
}
-
+
/**
* Range checks the source counter (it must fit in the lower 32-bit
* word) and then jambs the partition identifier into the high word.
@@ -1916,24 +1917,27 @@
*
* @throws RuntimeException
* if the source counter has overflowed.
+ *
+ * @see TermIdEncoder#combine(pid,ctr), which performs the same
+ * operation and MUST be consistent with this method.
*/
private long wrap(final long tmp) {
- if (tmp > Integer.MAX_VALUE) {
+ if (tmp >= MAX_LOCAL_COUNTER) {
throw new RuntimeException("Counter overflow");
-
+
}
- /*
- * Place the partition identifier into the high int32 word and place
- * the truncated counter value into the low int32 word.
- *
- * Note: You MUST cast [partitionId] to a long or left-shifting
- * 32-bits will always clear it to zero.
- */
+ return combine(partitionId, (int) tmp);
- return (((long)partitionId) << 32) | (int) tmp;
+// /*
+// * Place the partition identifier into the high int32 word and place
+// * the truncated counter value into the low int32 word.
+// */
+//
+//// return (((long)partitionId) << 32) | (int) tmp;
+// return ((long) partitionId) << 32 | (0xFFFFFFFFL & (long) tmp);
}
@@ -1944,13 +1948,59 @@
}
public long incrementAndGet() {
-
- return wrap( src.incrementAndGet() );
+ return wrap(src.incrementAndGet());
+
}
- }
+ /**
+ * Return the partition identifier from the high word of a partitioned
+ * counter.
+ *
+ * @param v
+ * The partitioned counter.
+ *
+ * @return The high word.
+ */
+ public static int getPartitionId(final long v) {
+ return (int) (v >>> 32);
+
+ }
+
+ /**
+ * Return the local counter from the low word of a partitioned counter.
+ *
+ * @param v
+ * The partitioned counter.
+ *
+ * @return The low word.
+ */
+ public static int getLocalCounter(final long v) {
+
+ return (int) v;
+
+ }
+
+ /**
+ * Combines the partition identifier and the local counter using the same
+ * logic as the {@link PartitionedCounter}.
+ *
+ * @param pid
+ * The partition identifier.
+ * @param ctr
+ * The local counter.
+ *
+ * @return The long counter assembled from those values.
+ */
+ public static long combine(final int pid, final int ctr) {
+
+ return ((long) pid) << 32 | (0xFFFFFFFFL & (long) ctr);
+
+ }
+
+ } // class PartitionedCounter
+
/**
* Returns ONE (1).
*/
Modified: branches/BIGDATA_RELEASE_1_0_0/bigdata/src/test/com/bigdata/btree/TestIndexCounter.java
===================================================================
--- branches/BIGDATA_RELEASE_1_0_0/bigdata/src/test/com/bigdata/btree/TestIndexCounter.java 2011-07-08 14:46:57 UTC (rev 4862)
+++ branches/BIGDATA_RELEASE_1_0_0/bigdata/src/test/com/bigdata/btree/TestIndexCounter.java 2011-07-08 14:48:19 UTC (rev 4863)
@@ -27,6 +27,9 @@
package com.bigdata.btree;
+import com.bigdata.btree.BTree.PartitionedCounter;
+import com.bigdata.rdf.lexicon.TermIdEncoder;
+
/**
* Test suite for the {@link IIndex#getCounter()} interface.
*
@@ -48,23 +51,268 @@
super(name);
}
+ /**
+ * Unit test for {@link BTree.Counter} to verify basic increment behavior.
+ */
public void test_counter() {
- BTree btree = getBTree(3);
+ final BTree btree = getBTree(3);
- ICounter counter = btree.getCounter();
-
+ final ICounter counter = btree.getCounter();
+
// initial value is zero for an unpartitioned index
- assertEquals(0,counter.get());
-
+ assertEquals(0, counter.get());
+
// get() does not have a side-effect on the counter.
- assertEquals(0,counter.get());
-
+ assertEquals(0, counter.get());
+
// inc() increments the value and _then_ returns the counter.
- assertEquals(1,counter.incrementAndGet());
- assertEquals(1,counter.get());
- assertEquals(2,counter.incrementAndGet());
+ assertEquals(1, counter.incrementAndGet());
+ assertEquals(1, counter.get());
+ assertEquals(2, counter.incrementAndGet());
}
+
+ /**
+ * Unit test for overflow conditions at the int32 and int64 boundary for
+ * {@link BTree.Counter}.
+ */
+ public void test_counter_overflow() {
+
+ final BTree btree = getBTree(3);
+
+ final ICounter counter = btree.getCounter();
+
+ final long maxSignedInt = (long) Integer.MAX_VALUE;
+ final long minSignedInt = 0xFFFFFFFFL & (long) Integer.MIN_VALUE;
+ final long minusOneInt = 0xFFFFFFFFL & (long) -1;
+ final long int32Overflow = 1L << 32;// bit 33 is on.
+
+ /*
+ * First explore when the counter crosses from max signed int to min
+ * signed int.
+ */
+
+ // Artificially set the counter to max signed int.
+ btree.counter.set(maxSignedInt);
+
+ // Verify current value.
+ assertEquals(maxSignedInt, counter.get());
+
+ // Increment. Should now be min signed int.
+ assertEquals(minSignedInt, counter.incrementAndGet());
+
+ // Increment. Should now be moving towards zero.
+ assertEquals(minSignedInt + 1L, counter.incrementAndGet());
+
+ // Increment. Should now be moving towards zero.
+ assertEquals(minSignedInt + 2L, counter.incrementAndGet());
+
+ /*
+ * Now explore when the counter approaches a value which can only be
+ * expressed in 33 bits (bigger than an unsigned int).
+ */
+
+ btree.counter.set(minusOneInt - 1);
+
+ // Verify current value.
+ assertEquals(minusOneInt - 1, counter.get());
+
+ // Increment. Should now be a long whose lower word is minus one signed
+ // int.
+ assertEquals(minusOneInt, counter.incrementAndGet());
+
+ // Increment. Should now be a long whose lower word is ZERO and whose
+ // upper word as the low bit set.
+ assertEquals(int32Overflow, counter.incrementAndGet());
+
+ /*
+ * Now explore when the counter approaches -1L and 0L.
+ */
+ btree.counter.set(-2L);
+
+ // Verify current value.
+ assertEquals(-2L, counter.get());
+
+ // Increment to -1L.
+ assertEquals(-1L, counter.incrementAndGet());
+
+ // Increment to 0L fails (counter overflow).
+ try {
+ counter.incrementAndGet();
+ fail("Expecting counter overflow");
+ } catch (RuntimeException ex) {
+ if (log.isInfoEnabled())
+ log.info("Ignoring expected exception: " + ex);
+ }
+
+ }
+
+ /**
+ * Unit tests for {@link PartitionedCounter} when the partition identifier
+ * is ZERO (0).
+ */
+ public void test_partitionedCounter_pid0() {
+
+ final BTree btree = getBTree(3);
+
+ final int pid = 0;
+
+ final ICounter counter = new PartitionedCounter(pid, new BTree.Counter(
+ btree));
+
+ final long maxSignedInt = (long) Integer.MAX_VALUE;
+ final long minSignedInt = 0xFFFFFFFFL & (long) Integer.MIN_VALUE;
+ final long minusOneInt = 0xFFFFFFFFL & (long) -1;
+
+ // Verify the initial counter value.
+ assertEquals(0L, counter.get());
+
+ // Increment and get.
+ assertEquals(1L, counter.incrementAndGet());
+
+ // Set the underlying counter to max signed int.
+ btree.counter.set(maxSignedInt);
+
+ // Verify get().
+ assertEquals(maxSignedInt, counter.get());
+
+ // Increment and get (wraps to the long value whose low word is minSignedInt).
+ assertEquals(minSignedInt, counter.incrementAndGet());
+
+ // Increment. Should now be moving towards zero.
+ assertEquals(minSignedInt + 1L, counter.incrementAndGet());
+
+ // Increment. Should now be moving towards zero.
+ assertEquals(minSignedInt + 2L, counter.incrementAndGet());
+
+ /*
+ * Verify behavior as we approach the maximum value which can be
+ * expressed in an int32 local counter.
+ */
+
+ // set the underlying counter.
+ btree.counter.set(minusOneInt - 1);
+
+ // Verify current value.
+ assertEquals(minusOneInt - 1, counter.get());
+
+ // Increment. Should now be a long whose lower word is minus one signed
+ // int.
+ assertEquals(minusOneInt, counter.incrementAndGet());
+
+ // Increment fails (counter overflow).
+ try {
+ counter.incrementAndGet();
+ fail("Expecting counter overflow");
+ } catch (RuntimeException ex) {
+ if (log.isInfoEnabled())
+ log.info("Ignoring expected exception: " + ex);
+ }
+
+ }
+
+ /**
+ * Unit tests for {@link PartitionedCounter} when the partition identifier
+ * is {@link Integer#MAX_VALUE}.
+ */
+ public void test_partitionedCounter_pidMaxSignedInt() {
+
+ doPartitionedCounterTest(Integer.MAX_VALUE);
+
+ }
+
+ /**
+ * Unit tests for {@link PartitionedCounter} when the partition identifier
+ * is {@link Integer#MIN_VALUE}.
+ */
+ public void test_partitionedCounter_pidMinSignedInt() {
+
+ doPartitionedCounterTest(Integer.MIN_VALUE);
+
+ }
+
+ /**
+ * Unit tests for {@link PartitionedCounter} when the partition identifier
+ * is <code>-1</code>.
+ */
+ public void test_partitionedCounter_pidMinusOne() {
+
+ doPartitionedCounterTest(-1);
+
+ }
+
+ private void doPartitionedCounterTest(final int pid) {
+
+ final BTree btree = getBTree(3);
+
+ final ICounter counter = new PartitionedCounter(pid, new BTree.Counter(
+ btree));
+
+ final long maxSignedInt = (long) Integer.MAX_VALUE;
+ final long minusOneInt = 0xFFFFFFFFL & (long) -1;
+
+ // Verify the initial counter value.
+ assertSameCounter(pid, 0/*ctr*/, counter.get());
+
+ // Increment and get.
+ assertSameCounter(pid, 1/*ctr*/, counter.incrementAndGet());
+
+ // Set the underlying counter to max signed int.
+ btree.counter.set(maxSignedInt);
+
+ // Verify get().
+ assertSameCounter(pid, Integer.MAX_VALUE, counter.get());
+
+ // Increment and get (wraps to the long value whose low word is
+ // minSignedInt).
+ assertSameCounter(pid, Integer.MIN_VALUE, counter.incrementAndGet());
+
+ // Increment. Should now be moving towards zero.
+ assertSameCounter(pid, Integer.MIN_VALUE + 1, counter.incrementAndGet());
+
+ // Increment. Should now be moving towards zero.
+ assertSameCounter(pid, Integer.MIN_VALUE + 2, counter.incrementAndGet());
+
+ /*
+ * Verify behavior as we approach the maximum value which can be
+ * expressed in an int32 local counter.
+ */
+
+ // set the underlying counter.
+ btree.counter.set(minusOneInt - 1);
+
+ // Verify current.
+ assertSameCounter(pid, -2, counter.get());
+
+ // Increment. Should now be a long whose lower word is minus one signed
+ // int.
+ assertSameCounter(pid, -1, counter.incrementAndGet());
+
+ // Increment fails (counter overflow).
+ try {
+ counter.incrementAndGet();
+ fail("Expecting counter overflow");
+ } catch (RuntimeException ex) {
+ if (log.isInfoEnabled())
+ log.info("Ignoring expected exception: " + ex);
+ }
+
+ }
+ private static void assertSameCounter(final int pid, final int ctr,
+ final long v0) {
+
+ // sanity check extract of pid.
+ assertEquals("pid", pid, TermIdEncoder.getPartitionId(v0));
+
+ // sanity check extract of ctr.
+ assertEquals("ctr", ctr, TermIdEncoder.getLocalCounter(v0));
+
+ final long v2 = BTree.PartitionedCounter.combine(pid, ctr);
+
+ assertEquals(v0, v2);
+
+ }
+
}
Modified: branches/BIGDATA_RELEASE_1_0_0/bigdata-rdf/src/java/com/bigdata/rdf/lexicon/TermIdEncoder.java
===================================================================
--- branches/BIGDATA_RELEASE_1_0_0/bigdata-rdf/src/java/com/bigdata/rdf/lexicon/TermIdEncoder.java 2011-07-08 14:46:57 UTC (rev 4862)
+++ branches/BIGDATA_RELEASE_1_0_0/bigdata-rdf/src/java/com/bigdata/rdf/lexicon/TermIdEncoder.java 2011-07-08 14:48:19 UTC (rev 4863)
@@ -23,47 +23,42 @@
*/
package com.bigdata.rdf.lexicon;
-import com.bigdata.btree.ICounter;
+import com.bigdata.btree.BTree;
import com.bigdata.btree.BTree.PartitionedCounter;
/**
- * An encoder/decoder for long values formed from a partition identifier in
- * the high word and a local counter in the low word where (1) the sign bit
- * is stolen from both the local counter and the partition identifier; and
- * then (2) the low N bits of the long value are reversed and rotated into
- * the high N bits of the long value. The stolen sign bits are made
- * available for bit flags in the low two-bits of the resulting long value
- * (they will be ZERO(0) and may be overwritten by the caller).
+ * An encoder/decoder for long values formed from a partition identifier in the
+ * high word and a local counter in the low word where the low N bits of the
+ * long value are reversed and rotated into the high N bits of the long value.
* <p>
- * The purpose of this encoding is to cause the N high bits to vary rapidly
- * as the local counter is driven up by writes on the index partition. This
- * has the effect of scattering writes on dependent indices (those using the
- * resulting long value as the sole or leading component of their key).
+ * The purpose of this encoding is to cause the N high bits to vary rapidly as
+ * the local counter is driven up by writes on the index partition. This has the
+ * effect of scattering writes on dependent indices (those using the resulting
+ * long value as the sole or leading component of their key).
* <p>
- * Given a source RDF/XML document with M "terms" distributed uniformly over
- * K TERM2ID index partitions, each term has a uniform likelihood of setting
- * any of the low bits of the local counter. After encoding, this means that
- * the N high-bits of encoded term identifier are uniformly distributed.
- * Assuming that the separator keys for the ID2TERM index divide the key
- * space into equally sized key-ranges, then the reads and writes on the
- * ID2TERM index partitions will be uniformly distributed as well.
+ * Given a source RDF/XML document with M "terms" distributed uniformly over K
+ * TERM2ID index partitions, each term has a uniform likelihood of setting any
+ * of the low bits of the local counter. After encoding, this means that the N
+ * high-bits of encoded term identifier are uniformly distributed. Assuming that
+ * the separator keys for the ID2TERM index divide the key space into equally
+ * sized key-ranges, then the reads and writes on the ID2TERM index partitions
+ * will be uniformly distributed as well.
* <p>
- * The next bits in the encoded values are derived from the partition
- * identifier followed by the term identifier and therefore have a strong
- * bias for the index partition and the sequential assignment of local
- * counter values within an index partition respectively. This means that
- * read / write access within an index partition tends to have some
- * locality, which improves B+Tree performance through several mechanisms
- * (mainly improved cache effects, reduced copy-on-write for dirty leaves
- * and nodes, and less IO costs).
+ * The next bits in the encoded values are derived from the partition identifier
+ * followed by the term identifier and therefore have a strong bias for the
+ * index partition and the sequential assignment of local counter values within
+ * an index partition respectively. This means that read / write access within
+ * an index partition tends to have some locality, which improves B+Tree
+ * performance through several mechanisms (mainly improved cache effects,
+ * reduced copy-on-write for dirty leaves and nodes, and less IO costs).
* <p>
- * When the #of ID2TERM index partitions GT 2^N, only a subset of those
- * index partitions can be directly selected by the N high bits with their
- * uniform distribution. The next bias is the partition identifier, which
- * begins at ZERO (0), is inflated to (0, [1:P]), where P is the #of index
- * partitions generated by a scatter split, and grows relatively slowly
- * thereafter as index partitions are fill up and are split or are moved to
- * redistribute the load on the cluster.
+ * When the #of ID2TERM index partitions GT <code>2^N</code>, only a subset of
+ * those index partitions can be directly selected by the N high bits with their
+ * uniform distribution. The next bias is the partition identifier, which begins
+ * at ZERO (0), is inflated to (0, [1:P]), where P is the #of index partitions
+ * generated by a scatter split, and grows relatively slowly thereafter as index
+ * partitions are fill up and are split or are moved to redistribute the load on
+ * the cluster.
*
* @author <a href="mailto:tho...@us...">Bryan Thompson</a>
* @version $Id$
@@ -89,6 +84,16 @@
}
/**
+ * Return the #of low bits from the local counter that will be reversed and
+ * written into the high-bits of the encoded long value.
+ */
+ public int getNBits() {
+
+ return N;
+
+ }
+
+ /**
* @param N
* The #of low bits from the local counter that will be reversed
* and written into the high-bits of the encoded long value.
@@ -130,70 +135,54 @@
}
/**
+ * Encode a term identifier using the configured value of
+ * {@link #getNBits() NBits}.
*
* @param v
* A 64-bit long counter value as generated by an
- * {@link ICounter}.
+ * {@link BTree.PartitionedCounter}.
*
- * @return A permutation of that long value in which the sign bits have
- * been "stolen" and the low <i>N</i> bits have been reversed
- * and rotated into the high <i>N</i> bits. The low 2 bits are
- * unassigned (these were the sign bits of the partition
- * identifier and the local counter and hence were known to be
- * ZERO(0)) and may be used as bit flags.
+ * @return A permutation of that long value in which the low <i>N</i> bits
+ * have been reversed and rotated into the high <i>N</i> bits.
*/
public long encode(final long v) {
+
+ if (v == 0L) {
+ // 0L is reserved for NULLs.
+ throw new IllegalArgumentException();
+ }
// the partition identifier.
- final int pid = getPartitionId(v);
- if (pid < 0) {
- // must be non-negative.
- throw new IllegalArgumentException("pid is negative: " + pid);
- }
+ final long pid = 0xFFFFFFFFL & getPartitionId(v);
// the local counter.
- final int ctr = getLocalCounter(v);
- if (ctr <= 0) {
- // must be positive (0 reserved for NULL).
- throw new IllegalArgumentException("ctr is not positive: " + ctr);
- }
+ final long ctr = 0xFFFFFFFFL & getLocalCounter(v);
- /*
- * Note: If you want to modify this to use all bits rather than
- * stealing the sign bits then look at the (N-1) term and the << 2
- * term, both of which are involved in stealing the sign bits.
- */
-
// the output value.
long u = 0L;
/*
- * Move pid to high word. The high bit of the pid is the sign bit.
- * The sign bit is zero and will be overwritten by the reverse low N
- * bits of the ctr. Therefore we left shift by 32-(N-1) so that the
- * high bit of the pid winds up in the low bit of the N-bit field
- * where it will be overwritten.
+ * Move pid to high word.
*/
- u |= ((long) pid) << (32 - (N - 1));
+ u |= pid << (32 - N);
/*
* Right shift the counter over the bits that are being reversed,
- * extend to a long value, and then then left shift the long value
- * to make room for the 2 flag bits.
+ * extend to a long value.
*/
- u |= (((long) (ctr >>> N)) << 2);
+ u |= ctr >>> N;
/*
* Use the mask to isolate the low-N bits of the counter, which are
* then reversed into the high-N bits.
*/
- final int rev = Integer.reverse(ctr & mask);
+ final long rev = Integer.reverse(((int) ctr) & mask);
/*
* Overwrite the high N bits of the long value using the reversed
* low N bits from the local counter.
*/
- u |= ((long) rev) << 32;
+ u |= rev << 32;
return u;
@@ -209,35 +198,23 @@
*/
public long decode(final long u) {
- /*
- * Note: If you want to modify this to use all bits rather than
- * stealing the sign bits then look at the (N-1) term and the >>> 2
- * term, both of which are involved in stealing the sign bits.
- */
-
// reverse high word and mask to recover the low-N bits.
final int fwd = Integer.reverse(((int) (u >>> 32))) & mask;
/*
- * Shift down the long value to cover up the flag bits and then
- * left-shift the make room for the (un-)reversed bits. Mask off the
- * high-bit since the sign bit of the local counter is always zero
- * but it was overwritten by the low bit of the partition identifier
- * so we need to clear it to zero when we decode it.
+ * Left-shift to make room for the (un-)reversed bits and then combine
+ * them back in.
*/
- final int ctr = ((int) ((u >>> 2) << N) | fwd) & 0x7fffffff;
+ final int ctr = ((int) (u << N) | fwd);
/*
* Bring the partition identifier back to an int by shifting it the
- * same number of bits in the other direction and masking off the
- * high bit since the sign bit is always zero and if can be non-zero
- * if we don't mask it off since it was overwritten by the reversed
- * low bits from the counter.
+ * same number of bits in the other direction.
*/
- final int pid = ((int) (u >>> (32 - (N - 1)))) & 0x7fffffff;
+ final int pid = ((int) (u >>> (32 - N)));
// reconstruct the long counter value.
- return ((long) (pid) << 32) | ctr;
+ return combine(pid, ctr);
}
@@ -252,7 +229,8 @@
*/
public static int getPartitionId(final long v) {
- return (int) (v >>> 32);
+ return BTree.PartitionedCounter.getPartitionId(v);
+// return (int) (v >>> 32);
}
@@ -266,79 +244,60 @@
*/
public static int getLocalCounter(final long v) {
- return (int) v;
+// return (int) v;
+ return BTree.PartitionedCounter.getLocalCounter(v);
}
/**
- * Combines the partition identifier and the local counter using the
- * same logic as the {@link PartitionedCounter}.
+ * Combines the partition identifier and the local counter using the same
+ * logic as the {@link PartitionedCounter}.
*
* @param pid
* The partition identifier.
* @param ctr
* The local counter.
- *
+ *
* @return The long counter assembled from those values.
+ *
+ * @see BTree.PartitionedCounter, which performs the same operation and MUST
+ * be consistent with this method.
*/
public static long combine(final int pid, final int ctr) {
- return ((long) pid) << 32 | ctr;
+// return ((long) pid) << 32 | (0xFFFFFFFFL & (long) ctr);
+ return BTree.PartitionedCounter.combine(pid, ctr);
}
-// /**
-// * Set the bit flags for the Value type on the 2 low order bits.
-// *
-// * @param id
-// * The encoded term identifier.
-// * @param code
-// * The term code, which is one of the values defined by
-// * {@link ITermIndexCodes}.
-// *
-// * @return The term identifier with the 2 low order bits set to reflect
-// * the term code using the bit flags defined by
-// * {@link ITermIdCodes} which correspond to the specified term
-// * code.
-// */
-// public static long setFlags(long id, final byte code) {
-//
-// switch (code) {
-//
-// case ITermIndexCodes.TERM_CODE_URI:
-//
-// id |= ITermIdCodes.TERMID_CODE_URI;
-//
-// break;
-//
-// case ITermIndexCodes.TERM_CODE_LIT:
-// case ITermIndexCodes.TERM_CODE_DTL:
-// case ITermIndexCodes.TERM_CODE_LCL:
-//
-// id |= ITermIdCodes.TERMID_CODE_LITERAL;
-//
-// break;
-//
-// case ITermIndexCodes.TERM_CODE_BND:
-//
-// id |= ITermIdCodes.TERMID_CODE_BNODE;
-//
-// break;
-//
-// case ITermIndexCodes.TERM_CODE_STMT:
-//
-// id |= ITermIdCodes.TERMID_CODE_STATEMENT;
-//
-// break;
-//
-// default:
-//
-// throw new AssertionError("Unknown term type: code=" + code);
-//
-// }
-//
-// return id;
-//
-// }
+ /*
+ * Alternative versions used for debugging. Package private for the unit
+ * tests.
+ */
+ long encode2(final long v1) {
+ long v2 = v1 >>> N;
+
+ for (int b = 0; b < N; b++) {
+ if ((v1 & (1L << b)) != 0) {
+ final long sv = 1L << (63 - b);
+ v2 |= sv;
+ }
+ }
+
+ return v2;
+ }
+
+ long decode2(final long v2) {
+ long v1 = v2 << N;
+
+ for (int b = 0; b < N; b++) {
+ if ((v2 & (1L << (63 - b))) != 0) {
+ v1 |= 1L << b;
+ }
+ }
+
+ return v1;
+ }
+
}
Modified: branches/BIGDATA_RELEASE_1_0_0/bigdata-rdf/src/test/com/bigdata/rdf/lexicon/TestTermIdEncoder.java
===================================================================
--- branches/BIGDATA_RELEASE_1_0_0/bigdata-rdf/src/test/com/bigdata/rdf/lexicon/TestTermIdEncoder.java 2011-07-08 14:46:57 UTC (rev 4862)
+++ branches/BIGDATA_RELEASE_1_0_0/bigdata-rdf/src/test/com/bigdata/rdf/lexicon/TestTermIdEncoder.java 2011-07-08 14:48:19 UTC (rev 4863)
@@ -92,45 +92,51 @@
final TermIdEncoder encoder = new TermIdEncoder(1);
- // pid may not be negative.
- try {
- encoder.encode(((long) -1/* pid */) << 32 | 1/* ctr */);
- fail("Expecting: " + IllegalArgumentException.class);
- } catch (IllegalArgumentException ex) {
- if (log.isInfoEnabled()) {
- log.info("Ignoring expected exception: " + ex);
- }
- }
+// // pid may not be negative.
+// try {
+// encoder.encode(((long) -1/* pid */) << 32 | 1/* ctr */);
+// fail("Expecting: " + IllegalArgumentException.class);
+// } catch (IllegalArgumentException ex) {
+// if (log.isInfoEnabled()) {
+// log.info("Ignoring expected exception: " + ex);
+// }
+// }
+//
+// // ctr may not be negative.
+// try {
+// encoder.encode(((long) 1/* pid */) << 32 | -1/* ctr */);
+// fail("Expecting: " + IllegalArgumentException.class);
+// } catch (IllegalArgumentException ex) {
+// if (log.isInfoEnabled()) {
+// log.info("Ignoring expected exception: " + ex);
+// }
+// }
+// // ctr may not be zero.
+// try {
+// encoder.encode(((long) 1/* pid */) << 32 | 0/* ctr */);
+// fail("Expecting: " + IllegalArgumentException.class);
+// } catch (IllegalArgumentException ex) {
+// if (log.isInfoEnabled()) {
+// log.info("Ignoring expected exception: " + ex);
+// }
+// }
- // ctr may not be negative.
- try {
- encoder.encode(((long) 1/* pid */) << 32 | -1/* ctr */);
- fail("Expecting: " + IllegalArgumentException.class);
- } catch (IllegalArgumentException ex) {
- if (log.isInfoEnabled()) {
- log.info("Ignoring expected exception: " + ex);
- }
- }
- // ctr may not be zero.
- try {
- encoder.encode(((long) 1/* pid */) << 32 | 0/* ctr */);
- fail("Expecting: " + IllegalArgumentException.class);
- } catch (IllegalArgumentException ex) {
- if (log.isInfoEnabled()) {
- log.info("Ignoring expected exception: " + ex);
- }
- }
+ // termId may not be 0L.
+ try {
+ encoder.encode(0L);
+ fail("Expecting: " + IllegalArgumentException.class);
+ } catch (IllegalArgumentException ex) {
+ if (log.isInfoEnabled()) {
+ log.info("Ignoring expected exception: " + ex);
+ }
+ }
}
/**
* Test of encode/decode when ZERO (0) of the low bits are reversed and
- * placed into the high bits (this corresponds closely to the historical
- * encoding of a term identifier by either an unpartitioned or a partitioned
- * TERM2ID index, however there is a difference in the encoding since the
- * new encoding steals the sign bit from both the partition identifier and
- * the local counter rather than stealing both bits from the partition
- * identifier, which is what the historical encoding scheme was doing).
+ * placed into the high bits. The encoding should be a NOP in this special
+ * case.
*/
public void test_encode_decode_0bits_pid1_ctr1() {
@@ -145,9 +151,9 @@
}
/**
- * Stress test using an encoder with a random number of NO bits reversed and
- * rotated into the high bits of the long value and random values for the
- * partition identifier and the local counter.
+ * Stress test using an encoder with NO bits reversed and rotated into the
+ * high bits of the long value and random values for the partition
+ * identifier and the local counter.
*/
public void test_encode_decode_0bits_stress() {
@@ -157,18 +163,29 @@
for (int i = 0; i < 1000000; i++) {
- // [0:MAX_VALUE-1], but MAX_VALUE is also legal.
- final int pid = r.nextInt(Integer.MAX_VALUE);
+ final long v0 = r.nextLong();
- // [1:MAX_VALUE] since 0 is illegal.
- final int ctr = r.nextInt(Integer.MAX_VALUE) + 1;
+ if (v0 == 0L) {
+ // Do not attempt to encode a NULL.
+ continue;
+ }
- doEncodeDecodeTest(encoder,pid,ctr);
+ // Encode.
+ final long v1 = encoder.encode(v0);
+ final long v2 = encoder.encode2(v0);
+ assertTrue(v1==v2); // verify same behavior.
+ // Verify does not cause any transform of the value.
+ if (v0 != v1)
+ fail(encoder, v0, v1);
+
}
}
+ /**
+ * Unit test with ONE (1) for pid and local counter.
+ */
public void test_encode_decode_1bits_pid1_ctr1() {
doEncodeDecodeTest(new TermIdEncoder(1), 1/* pid */, 1/* ctr */);
@@ -176,6 +193,84 @@
}
/**
+ * Unit test with {@link Integer#MAX_VALUE} for pid and local counter.
+ */
+ public void test_encode_decode_1bits_pidMAX_ctrMAX() {
+
+ doEncodeDecodeTest(new TermIdEncoder(1), Integer.MAX_VALUE/* pid */,
+ Integer.MAX_VALUE/* ctr */);
+
+ }
+
+ /**
+ * Unit test with {@link Integer#MIN_VALUE} for pid and 0L for the local
+ * counter (this combination should not occur in practice since we increment
+ * the local counter before assigning the term identifier rather than after).
+ */
+ public void test_encode_decode_1bits_pidMIN_ctr0() {
+
+ doEncodeDecodeTest(new TermIdEncoder(1), Integer.MIN_VALUE/* pid */,
+ 0/* ctr */);
+
+ }
+
+ public void test_encode_decode_1bits_pidm1_ctr0() {
+
+ doEncodeDecodeTest(new TermIdEncoder(1), -1/* pid */, 0/* ctr */);
+
+ }
+
+ public void test_encode_decode_1bits_pid0_ctrm1() {
+
+ doEncodeDecodeTest(new TermIdEncoder(1), 0/* pid */, -1/* ctr */);
+
+ }
+
+ public void test_encode_decode_1bits_pid0_ctrMIN() {
+
+ doEncodeDecodeTest(new TermIdEncoder(1), 0/* pid */, Integer.MIN_VALUE/* ctr */);
+
+ }
+
+ public void test_encode_decode_1bits_pid0_ctrMAX() {
+
+ doEncodeDecodeTest(new TermIdEncoder(1), 0/* pid */, Integer.MAX_VALUE/* ctr */);
+
+ }
+
+ /**
+ * Unit test with {@link Integer#MIN_VALUE} for the pid and
+ * {@link Integer#MAX_VALUE} for the local counter.
+ */
+ public void test_encode_decode_1bits_pidMIN_ctrMAX() {
+
+ doEncodeDecodeTest(new TermIdEncoder(1), Integer.MIN_VALUE/* pid */,
+ Integer.MAX_VALUE/* ctr */);
+
+ }
+
+ /**
+ * Unit test with {@link Integer#MAX_VALUE} for the pid and
+ * {@link Integer#MIN_VALUE} for the local counter.
+ */
+ public void test_encode_decode_1bits_pidMAX_ctrMIN() {
+
+ doEncodeDecodeTest(new TermIdEncoder(1), Integer.MAX_VALUE/* pid */,
+ Integer.MIN_VALUE/* ctr */);
+
+ }
+
+ /**
+ * Unit test with {@link Integer#MIN_VALUE} for pid and local counter.
+ */
+ public void test_encode_decode_1bits_pidMIN_ctrMIN() {
+
+ doEncodeDecodeTest(new TermIdEncoder(1), Integer.MIN_VALUE/* pid */,
+ Integer.MIN_VALUE/* ctr */);
+
+ }
+
+ /**
* Stress test using an encoder with a random number of bits reversed and
* rotated into the high bits of the long value and random values for the
* partition identifier and the local counter.
@@ -189,12 +284,19 @@
// [0:31]
final int nbits = r.nextInt(32);
- // [0:MAX_VALUE-1], but MAX_VALUE is also legal.
- final int pid = r.nextInt(Integer.MAX_VALUE);
+// // [0:MAX_VALUE-1], but MAX_VALUE is also legal.
+// final int pid = r.nextInt(Integer.MAX_VALUE);
+ final int pid = r.nextInt(); // any int value.
- // [1:MAX_VALUE] since 0 is illegal.
- final int ctr = r.nextInt(Integer.MAX_VALUE) + 1;
-
+// // [1:MAX_VALUE] since 0 is illegal.
+// final int ctr = r.nextInt(Integer.MAX_VALUE) + 1;
+ final int ctr = r.nextInt(); // any int value.
+
+ if (pid == 0 && ctr == 0) {
+ // 0L is reserved for a NULL.
+ continue;
+ }
+
final TermIdEncoder encoder = new TermIdEncoder(nbits);
doEncodeDecodeTest(encoder, pid, ctr);
@@ -227,23 +329,101 @@
// encode.
final long u = encoder.encode(v0);
+ final long u1 = encoder.encode2(v0);
+ assertTrue(u == u1);
- // the low bits are zero (they are left open for bit flags).
- assertTrue((u & 0x03) == 0);
-
// decode.
final long v1 = encoder.decode(u);
+ final long v2 = encoder.decode2(u);
+ assertTrue(v1 == v2);
+
+ // verify v0 == decode(encode(v0))
+ if (v0 != v1)
+ fail(encoder, v0, v1);
- // verify v0 == decode(encode(v0))
- if (v0 != v1) {
- fail(encoder + "\n" + "expected=" + v0
- + " (0x" + Long.toHexString(v0) + ")" + ", actual=" + v1
- + " (0x" + Long.toHexString(v0) + ")"
- + //
- "\n" + Long.toBinaryString(v0) + "\n"
- + Long.toBinaryString(v1));
+ }
+
+ static private void fail(final TermIdEncoder encoder, final long v0, final long v1) {
+ final String msg = encoder + "\n" + //
+ ", expected=" + v0 + " (0x" + Long.toHexString(v0) + ")\n" + //
+ ", actual=" + v1 + " (0x" + Long.toHexString(v1) + ")\n" + //
+ Long.toBinaryString(v0) + "\n" + //
+ Long.toBinaryString(v1)//
+ ;
+ log.error(msg);
+ fail(msg);
+ }
+
+ /**
+ * Performance test.
+ *
+ * @param args
+ */
+ public static void main(String[] args) {
+
+ final Random r = new Random();
+
+ final long start = System.currentTimeMillis();
+
+ for (int i = 0; i < 100000000; i++) {
+
+ // [0:31]
+ final int nbits = r.nextInt(32);
+
+ final int pid = r.nextInt(); // any int value.
+
+ final int ctr = r.nextInt(); // any int value.
+
+ if (pid == 0 && ctr == 0) {
+
+ // 0L is reserved for a NULL.
+ continue;
+
+ }
+
+ final TermIdEncoder encoder = new TermIdEncoder(nbits);
+
+ final long v0 = TermIdEncoder.combine(pid, ctr);
+
+ final long ev = encoder.encode(v0);
+
+ assertTrue(v0 == encoder.decode(ev));
+
}
+ final long split = System.currentTimeMillis();
+
+ for (int i = 0; i < 100000000; i++) {
+
+ // [0:31]
+ final int nbits = r.nextInt(4);
+
+ final int pid = r.nextInt(); // any int value.
+
+ final int ctr = r.nextInt(); // any int value.
+
+ if (pid == 0 && ctr == 0) {
+
+ // 0L is reserved for a NULL.
+ continue;
+
+ }
+
+ final TermIdEncoder encoder = new TermIdEncoder(nbits);
+
+ final long v0 = TermIdEncoder.combine(pid, ctr);
+
+ final long ev = encoder.encode2(v0);
+
+ assertTrue(v0 == encoder.decode2(ev));
+
+ }
+
+ final long end = System.currentTimeMillis();
+
+ System.out.println("Old code " + (split - start) + "ms vs New code "
+ + (end - split) + "ms");
+
}
}
Modified: branches/TERMS_REFACTOR_BRANCH/bigdata/src/java/com/bigdata/btree/BTree.java
===================================================================
--- branches/TERMS_REFACTOR_BRANCH/bigdata/src/java/com/bigdata/btree/BTree.java 2011-07-08 14:46:57 UTC (rev 4862)
+++ branches/TERMS_REFACTOR_BRANCH/bigdata/src/java/com/bigdata/btree/BTree.java 2011-07-08 14:48:19 UTC (rev 4863)
@@ -1827,7 +1827,6 @@
* Mutable counter.
*
* @author <a href="mailto:tho...@us...">Bryan Thompson</a>
- * @version $Id$
*/
public static class Counter implements ICounter {
@@ -1835,7 +1834,8 @@
public Counter(final BTree btree) {
- assert btree != null;
+ if (btree == null)
+ throw new IllegalArgumentException();
this.btree = btree;
@@ -1863,11 +1863,10 @@
}
- if (counter == Long.MAX_VALUE) {
+ if (counter == 0L) {
/*
- * Actually, the counter would overflow on the next call but
- * this eager error makes the test for overflow atomic.
+ * The counter has wrapped back to ZERO.
*/
throw new RuntimeException("Counter overflow");
@@ -1878,7 +1877,7 @@
}
- }
+ } // class Counter
/**
* Places the counter values into a namespace formed by the partition
@@ -1887,12 +1886,13 @@
* int32 word.
*
* @author <a href="mailto:tho...@us...">Bryan Thompson</a>
- * @version $Id$
*/
public static class PartitionedCounter implements ICounter {
private final int partitionId;
private final ICounter src;
+
+ private static final long MAX_LOCAL_COUNTER = 1L << 32;
public PartitionedCounter(final int partitionId, final ICounter src) {
@@ -1904,7 +1904,7 @@
this.src = src;
}
-
+
/**
* Range checks the source counter (it must fit in the lower 32-bit
* word) and then jambs the partition identifier into the high word.
@@ -1916,24 +1916,27 @@
*
* @throws RuntimeException
* if the source counter has overflowed.
+ *
+ * @see TermIdEncoder#combine(pid,ctr), which performs the same
+ * operation and MUST be consistent with this method.
*/
private long wrap(final long tmp) {
- if (tmp > Integer.MAX_VALUE) {
+ if (tmp >= MAX_LOCAL_COUNTER) {
throw new RuntimeException("Counter overflow");
-
+
}
- /*
- * Place the partition identifier into the high int32 word and place
- * the truncated counter value into the low int32 word.
- *
- * Note: You MUST cast [partitionId] to a long or left-shifting
- * 32-bits will always clear it to zero.
- */
+ return combine(partitionId, (int) tmp);
- return (((long)partitionId) << 32) | (int) tmp;
+// /*
+// * Place the partition identifier into the high int32 word and place
+// * the truncated counter value into the low int32 word.
+// */
+//
+//// return (((long)partitionId) << 32) | (int) tmp;
+// return ((long) partitionId) << 32 | (0xFFFFFFFFL & (long) tmp);
}
@@ -1944,13 +1947,59 @@
}
public long incrementAndGet() {
-
- return wrap( src.incrementAndGet() );
+ return wrap(src.incrementAndGet());
+
}
- }
+ /**
+ * Return the partition identifier from the high word of a partitioned
+ * counter.
+ *
+ * @param v
+ * The partitioned counter.
+ *
+ * @return The high word.
+ */
+ public static int getPartitionId(final long v) {
+ return (int) (v >>> 32);
+
+ }
+
+ /**
+ * Return the local counter from the low word of a partitioned counter.
+ *
+ * @param v
+ * The partitioned counter.
+ *
+ * @return The low word.
+ */
+ public static int getLocalCounter(final long v) {
+
+ return (int) v;
+
+ }
+
+ /**
+ * Combines the partition identifier and the local counter using the same
+ * logic as the {@link PartitionedCounter}.
+ *
+ * @param pid
+ * The partition identifier.
+ * @param ctr
+ * The local counter.
+ *
+ * @return The long counter assembled from those values.
+ */
+ public static long combine(final int pid, final int ctr) {
+
+ return ((long) pid) << 32 | (0xFFFFFFFFL & (long) ctr);
+
+ }
+
+ } // class PartitionedCounter
+
/**
* Returns ONE (1).
*/
Modified: branches/TERMS_REFACTOR_BRANCH/bigdata/src/test/com/bigdata/btree/TestIndexCounter.java
===================================================================
--- branches/TERMS_REFACTOR_BRANCH/bigdata/src/test/com/bigdata/btree/TestIndexCounter.java 2011-07-08 14:46:57 UTC (rev 4862)
+++ branches/TERMS_REFACTOR_BRANCH/bigdata/src/test/com/bigdata/btree/TestIndexCounter.java 2011-07-08 14:48:19 UTC (rev 4863)
@@ -27,6 +27,9 @@
package com.bigdata.btree;
+import com.bigdata.btree.BTree.PartitionedCounter;
+import com.bigdata.rdf.lexicon.TermIdEncoder;
+
/**
* Test suite for the {@link IIndex#getCounter()} interface.
*
@@ -48,23 +51,268 @@
super(name);
}
+ /**
+ * Unit test for {@link BTree.Counter} to verify basic increment behavior.
+ */
public void test_counter() {
- BTree btree = getBTree(3);
+ final BTree btree = getBTree(3);
- ICounter counter = btree.getCounter();
-
+ final ICounter counter = btree.getCounter();
+
// initial value is zero for an unpartitioned index
- assertEquals(0,counter.get());
-
+ assertEquals(0, counter.get());
+
// get() does not have a side-effect on the counter.
- assertEquals(0,counter.get());
-
+ assertEquals(0, counter.get());
+
// inc() increments the value and _then_ returns the counter.
- assertEquals(1,counter.incrementAndGet());
- assertEquals(1,counter.get());
- assertEquals(2,counter.incrementAndGet());
+ assertEquals(1, counter.incrementAndGet());
+ assertEquals(1, counter.get());
+ assertEquals(2, counter.incrementAndGet());
}
+
+ /**
+ * Unit test for overflow conditions at the int32 and int64 boundary for
+ * {@link BTree.Counter}.
+ */
+ public void test_counter_overflow() {
+
+ final BTree btree = getBTree(3);
+
+ final ICounter counter = btree.getCounter();
+
+ final long maxSignedInt = (long) Integer.MAX_VALUE;
+ final long minSignedInt = 0xFFFFFFFFL & (long) Integer.MIN_VALUE;
+ final long minusOneInt = 0xFFFFFFFFL & (long) -1;
+ final long int32Overflow = 1L << 32;// bit 33 is on.
+
+ /*
+ * First explore when the counter crosses from max signed int to min
+ * signed int.
+ */
+
+ // Artificially set the counter to max signed int.
+ btree.counter.set(maxSignedInt);
+
+ // Verify current value.
+ assertEquals(maxSignedInt, counter.get());
+
+ // Increment. Should now be min signed int.
+ assertEquals(minSignedInt, counter.incrementAndGet());
+
+ // Increment. Should now be moving towards zero.
+ assertEquals(minSignedInt + 1L, counter.incrementAndGet());
+
+ // Increment. Should now be moving towards zero.
+ assertEquals(minSignedInt + 2L, counter.incrementAndGet());
+
+ /*
+ * Now explore when the counter approaches a value which can only be
+ * expressed in 33 bits (bigger than an unsigned int).
+ */
+
+ btree.counter.set(minusOneInt - 1);
+
+ // Verify current value.
+ assertEquals(minusOneInt - 1, counter.get());
+
+ // Increment. Should now be a long whose lower word is minus one signed
+ // int.
+ assertEquals(minusOneInt, counter.incrementAndGet());
+
+ // Increment. Should now be a long whose lower word is ZERO and whose
+ // upper word as the low bit set.
+ assertEquals(int32Overflow, counter.incrementAndGet());
+
+ /*
+ * Now explore when the counter approaches -1L and 0L.
+ */
+ btree.counter.set(-2L);
+
+ // Verify current value.
+ assertEquals(-2L, counter.get());
+
+ // Increment to -1L.
+ assertEquals(-1L, counter.incrementAndGet());
+
+ // Increment to 0L fails (counter overflow).
+ try {
+ counter.incrementAndGet();
+ fail("Expecting counter overflow");
+ } catch (RuntimeException ex) {
+ if (log.isInfoEnabled())
+ log.info("Ignoring expected exception: " + ex);
+ }
+
+ }
+
+ /**
+ * Unit tests for {@link PartitionedCounter} when the partition identifier
+ * is ZERO (0).
+ */
+ public void test_partitionedCounter_pid0() {
+
+ final BTree btree = getBTree(3);
+
+ final int pid = 0;
+
+ final ICounter counter = new PartitionedCounter(pid, new BTree.Counter(
+ btree));
+
+ final long maxSignedInt = (long) Integer.MAX_VALUE;
+ final long minSignedInt = 0xFFFFFFFFL & (long) Integer.MIN_VALUE;
+ final long minusOneInt = 0xFFFFFFFFL & (long) -1;
+
+ // Verify the initial counter value.
+ assertEquals(0L, counter.get());
+
+ // Increment and get.
+ assertEquals(1L, counter.incrementAndGet());
+
+ // Set the underlying counter to max signed int.
+ btree.counter.set(maxSignedInt);
+
+ // Verify get().
+ assertEquals(maxSignedInt, counter.get());
+
+ // Increment and get (wraps to the long value whose low word is minSignedInt).
+ assertEquals(minSignedInt, counter.incrementAndGet());
+
+ // Increment. Should now be moving towards zero.
+ assertEquals(minSignedInt + 1L, counter.incrementAndGet());
+
+ // Increment. Should now be moving towards zero.
+ assertEquals(minSignedInt + 2L, counter.incrementAndGet());
+
+ /*
+ * Verify behavior as we approach the maximum value which can be
+ * expressed in an int32 local counter.
+ */
+
+ // set the underlying counter.
+ btree.counter.set(minusOneInt - 1);
+
+ // Verify current value.
+ assertEquals(minusOneInt - 1, counter.get());
+
+ // Increment. Should now be a long whose lower word is minus one signed
+ // int.
+ assertEquals(minusOneInt, counter.incrementAndGet());
+
+ // Increment fails (counter overflow).
+ try {
+ counter.incrementAndGet();
+ fail("Expecting counter overflow");
+ } catch (RuntimeException ex) {
+ if (log.isInfoEnabled())
+ log.info("Ignoring expected exception: " + ex);
+ }
+
+ }
+
+ /**
+ * Unit tests for {@link PartitionedCounter} when the partition identifier
+ * is {@link Integer#MAX_VALUE}.
+ */
+ public void test_partitionedCounter_pidMaxSignedInt() {
+
+ doPartitionedCounterTest(Integer.MAX_VALUE);
+
+ }
+
+ /**
+ * Unit tests for {@link PartitionedCounter} when the partition identifier
+ * is {@link Integer#MIN_VALUE}.
+ */
+ public void test_partitionedCounter_pidMinSignedInt() {
+
+ doPartitionedCounterTest(Integer.MIN_VALUE);
+
+ }
+
+ /**
+ * Unit tests for {@link PartitionedCounter} when the partition identifier
+ * is <code>-1</code>.
+ */
+ public void test_partitionedCounter_pidMinusOne() {
+
+ doPartitionedCounterTest(-1);
+
+ }
+
+ private void doPartitionedCounterTest(final int pid) {
+
+ final BTree btree = getBTree(3);
+
+ final ICounter counter = new PartitionedCounter(pid, new BTree.Counter(
+ btree));
+
+ final long maxSignedInt = (long) Integer.MAX_VALUE;
+ final long minusOneInt = 0xFFFFFFFFL & (long) -1;
+
+ // Verify the initial counter value.
+ assertSameCounter(pid, 0/*ctr*/, counter.get());
+
+ // Increment and get.
+ assertSameCounter(pid, 1/*ctr*/, counter.incrementAndGet());
+
+ // Set the underlying counter to max signed int.
+ btree.counter.set(maxSignedInt);
+
+ // Verify get().
+ assertSameCounter(pid, Integer.MAX_VALUE, counter.get());
+
+ // Increment and get (wraps to the long value whose low word is
+ // minSignedInt).
+ assertSameCounter(pid, Integer.MIN_VALUE, counter.incrementAndGet());
+
+ // Increment. Should now be moving towards zero.
+ assertSameCounter(pid, Integer.MIN_VALUE + 1, counter.incrementAndGet());
+
+ // Increment. Should now be moving towards zero.
+ assertSameCounter(pid, Integer.MIN_VALUE + 2, counter.incrementAndGet());
+
+ /*
+ * Verify behavior as we approach the maximum value which can be
+ * expressed in an int32 local counter.
+ */
+
+ // set the underlying counter.
+ btree.counter.set(minusOneInt - 1);
+
+ // Verify current.
+ assertSameCounter(pid, -2, counter.get());
+
+ // Increment. Should now be a long whose lower word is minus one signed
+ // int.
+ assertSameCounter(pid, -1, counter.incrementAndGet());
+
+ // Increment fails (counter overflow).
+ try {
+ counter.incrementAndGet();
+ fail("Expecting counter overflow");
+ } catch (RuntimeException ex) {
+ if (log.isInfoEnabled())
+ log.info("Ignoring expected exception: " + ex);
+ }
+
+ }
+ private static void assertSameCounter(final int pid, final int ctr,
+ final long v0) {
+
+ // sanity check extract of pid.
+ assertEquals("pid", pid, TermIdEncoder.getPartitionId(v0));
+
+ // sanity check extract of ctr.
+ assertEquals("ctr", ctr, TermIdEncoder.getLocalCounter(v0));
+
+ final long v2 = BTree.PartitionedCounter.combine(pid, ctr);
+
+ assertEquals(v0, v2);
+
+ }
+
}
Modified: branches/TERMS_REFACTOR_BRANCH/bigdata-rdf/src/java/com/bigdata/rdf/lexicon/TermIdEncoder.java
===================================================================
--- branches/TERMS_REFACTOR_BRANCH/bigdata-rdf/src/java/com/bigdata/rdf/lexicon/TermIdEncoder.java 2011-07-08 14:46:57 UTC (rev 4862)
+++ branches/TERMS_REFACTOR_BRANCH/bigdata-rdf/src/java/com/bigdata/rdf/lexicon/TermIdEncoder.java 2011-07-08 14:48:19 UTC (rev 4863)
@@ -23,47 +23,42 @@
*/
package com.bigdata.rdf.lexicon;
-import com.bigdata.btree.ICounter;
+import com.bigdata.btree.BTree;
import com.bigdata.btree.BTree.PartitionedCounter;
/**
- * An encoder/decoder for long values formed from a partition identifier in
- * the high word and a local counter in the low word where (1) the sign bit
- * is stolen from both the local counter and the partition identifier; and
- * then (2) the low N bits of the long value are reversed and rotated into
- * the high N bits of the long value. The stolen sign bits are made
- * available for bit flags in the low two-bits of the resulting long value
- * (they will be ZERO(0) and may be overwritten by the caller).
+ * An encoder/decoder for long values formed from a partition identifier in the
+ * high word and a local counter in the low word where the low N bits of the
+ * long value are reversed and rotated into the high N bits of the long value.
* <p>
- * The purpose of this encoding is to cause the N high bits to vary rapidly
- * as the local counter is driven up by writes on the index partition. This
- * has the effect of scattering writes on dependent indices (those using the
- * resulting long value as the sole or leading component of their key).
+ * The purpose of this encoding is to cause the N high bits to vary rapidly as
+ * the local counter is driven up by writes on the index partition. This has the
+ * effect of scattering writes on dependent indices (those using the...
[truncated message content] |
