[Mulgara-svn] r789 - projects/xa2/object-pool/src
andrae at mulgara.org
andrae at mulgara.org
Tue Apr 15 10:27:31 UTC 2008
Author: andrae
Date: 2008-04-15 03:27:30 -0700 (Tue, 15 Apr 2008)
New Revision: 789
Added:
projects/xa2/object-pool/src/CompMemTrieTest.java
Modified:
projects/xa2/object-pool/src/ByteMap.java
projects/xa2/object-pool/src/ByteMapTest.java
projects/xa2/object-pool/src/MemoryTrieTest.java
Log:
The Compressed Memory Trie now mostly works.
There is a failure with the binary data test that needs to be tracked down.
Note this commit includes a fix to the ByteMap (with associated test) where we failed to check the dataOffset
on lookup to see if it exceeded the data array (which can happen on lookup failure).
Modified: projects/xa2/object-pool/src/ByteMap.java
===================================================================
--- projects/xa2/object-pool/src/ByteMap.java 2008-04-15 06:17:45 UTC (rev 788)
+++ projects/xa2/object-pool/src/ByteMap.java 2008-04-15 10:27:30 UTC (rev 789)
@@ -23,10 +23,9 @@
/**
* @param datum Value to be associated with key. Note: Must not be null.
- * @return true if map now contains key->datum; false if entry for key already exists and
- * !datum.equals(existing_value).
+ * @return the old value associated with key, or null if this is a new mapping.
*/
- public boolean insert(byte key, T datum) {
+ public T insert(byte key, T datum) {
if (datum == null) {
throw new IllegalArgumentException("Attempted to insert null into ByteMap");
}
@@ -44,17 +43,12 @@
int l = lowNibbleAsBitInShort(key);
if ((low[lowOffset] & l) != 0) {
// We already have a data entry for this byte.
- if (data.get(dataOffset).equals(datum)) {
- // Pre-existing data matches datum;
- return true;
- } else {
- return false;
- }
+ return data.set(dataOffset, datum);
} else {
// We need to insert a data entry for this byte.
low[lowOffset] = (short)(low[lowOffset] | l);
data.add(dataOffset, datum);
- return true;
+ return null;
}
} else {
// We need to insert a new low entry for this hi-nibble.
@@ -90,8 +84,12 @@
}
dataOffset += ones(LOW, low[lowOffset], key);
- // the resulting index is a direct index into the forwarding-pointer array.
- return data.get(dataOffset);
+ if (dataOffset >= data.size()) {
+ return null;
+ } else {
+ // the resulting index is a direct index into the forwarding-pointer array.
+ return data.get(dataOffset);
+ }
}
private static int ones(short index) {
Modified: projects/xa2/object-pool/src/ByteMapTest.java
===================================================================
--- projects/xa2/object-pool/src/ByteMapTest.java 2008-04-15 06:17:45 UTC (rev 788)
+++ projects/xa2/object-pool/src/ByteMapTest.java 2008-04-15 10:27:30 UTC (rev 789)
@@ -11,6 +11,8 @@
testSequential();
testAlternateImmediate();
testAlternate();
+ testAlternateLowNibbleImmediate();
+ testLookupNonExistentLow();
}
public static void testEmpty() throws Exception {
@@ -28,7 +30,7 @@
ByteMap<Long> byteMap = new ByteMap<Long>();
for (int i = 0; i < 0x00000100; i++) {
- assertTrue("Found double entry for i = " + i + " in sequential map", byteMap.insert((byte)i, new Long(i)));
+ assertNull("Found double entry for i = " + i + " in sequential map", byteMap.insert((byte)i, new Long(i)));
Long l = byteMap.lookup((byte)i);
assertEquals("Found mismatching entry for i = " + i + " in sequential map: Received " + l, new Long(i), l);
}
@@ -40,7 +42,7 @@
ByteMap<Long> byteMap = new ByteMap<Long>();
for (int i = 0; i < 0x00000100; i++) {
- assertTrue("Found double entry for i = " + i + " in sequential map", byteMap.insert((byte)i, new Long(i)));
+ assertNull("Found double entry for i = " + i + " in sequential map", byteMap.insert((byte)i, new Long(i)));
}
for (int i = 0; i < 0x00000100; i++) {
@@ -55,12 +57,12 @@
ByteMap<Long> byteMap = new ByteMap<Long>();
for (int i = 0; i < 128; i++) {
- assertTrue("Found double entry for i = " + i + " in alternate map", byteMap.insert((byte)i, new Long(i)));
+ assertNull("Found double entry for i = " + i + " in alternate map", byteMap.insert((byte)i, new Long(i)));
Long l = byteMap.lookup((byte)i);
assertEquals("Found mismatching entry for i = " + i + " in alternate map: Received " + l, new Long(i), l);
int ii = 255 - i;
- assertTrue("Found double entry for i' = " + ii + " in alternate map", byteMap.insert((byte)ii, new Long(ii)));
+ assertNull("Found double entry for i' = " + ii + " in alternate map", byteMap.insert((byte)ii, new Long(ii)));
Long ll = byteMap.lookup((byte)ii);
assertEquals("Found mismatching entry for i' = " + ii + " in alternate map: Received " + ll, new Long(ii), ll);
}
@@ -72,10 +74,10 @@
ByteMap<Long> byteMap = new ByteMap<Long>();
for (int i = 0; i < 128; i++) {
- assertTrue("Found double entry for i = " + i + " in alternate map", byteMap.insert((byte)i, new Long(i)));
+ assertNull("Found double entry for i = " + i + " in alternate map", byteMap.insert((byte)i, new Long(i)));
int ii = 255 - i;
- assertTrue("Found double entry for i' = " + ii + " in alternate map", byteMap.insert((byte)ii, new Long(ii)));
+ assertNull("Found double entry for i' = " + ii + " in alternate map", byteMap.insert((byte)ii, new Long(ii)));
}
for (int i = 0; i < 128; i++) {
@@ -89,13 +91,51 @@
System.out.println("testAlternateImmediate Successful");
}
+
+ public static void testAlternateLowNibbleImmediate() throws Exception {
+ System.out.println("running testAlternateLowNibbleImmediate...");
+ ByteMap<Long> byteMap = new ByteMap<Long>();
+
+ for (int i = 0; i < 64; i++) {
+ assertNull("Found double entry for i = " + i + " in alternate map", byteMap.insert((byte)i, new Long(i)));
+ Long l = byteMap.lookup((byte)i);
+ assertEquals("Found mismatching entry for i = " + i + " in alternate map: Received " + l, new Long(i), l);
+
+ int ii = 127 - i;
+ assertNull("Found double entry for i' = " + ii + " in alternate map", byteMap.insert((byte)ii, new Long(ii)));
+ Long ll = byteMap.lookup((byte)ii);
+ assertEquals("Found mismatching entry for i' = " + ii + " in alternate map: Received " + ll, new Long(ii), ll);
+ }
+ System.out.println("testAlternateLowNibbleImmediate Successful");
+ }
+ public static void testLookupNonExistentLow() throws Exception {
+ System.out.println("running testLookupNonExistentLow...");
+ ByteMap<Long> byteMap = new ByteMap<Long>();
+
+ int i = 0x061;
+ assertNull("Found double entry for i = " + i, byteMap.insert((byte)i, new Long(i)));
+ Long l = byteMap.lookup((byte)i);
+ assertEquals("Found mismatching entry for i = " + i + " Received " + l, new Long(i), l);
+
+ i = 0x067;
+ assertNull("Found entry for uninserted key i = " + i, byteMap.lookup((byte)i));
+
+ System.out.println("testLookupNonExistentLow Successful");
+ }
+
public static void assertNull(String str, Object obj) throws Exception {
if (obj != null) {
throw new IllegalStateException(str);
}
}
+ public static void assertNotNull(String str, Object obj) throws Exception {
+ if (obj == null) {
+ throw new IllegalStateException(str);
+ }
+ }
+
public static void assertTrue(String str, boolean b) throws Exception {
if (!b) {
throw new IllegalStateException(str);
Copied: projects/xa2/object-pool/src/CompMemTrieTest.java (from rev 785, projects/xa2/object-pool/src/MemoryTrieTest.java)
===================================================================
--- projects/xa2/object-pool/src/CompMemTrieTest.java (rev 0)
+++ projects/xa2/object-pool/src/CompMemTrieTest.java 2008-04-15 10:27:30 UTC (rev 789)
@@ -0,0 +1,283 @@
+/*
+ * Copyright Topaz Foundation 2008
+ * Author Andrae Muys
+ * Date 9th April 2008
+ */
+
+import java.util.Arrays;
+import java.util.HashMap;
+import java.util.Map;
+import java.io.BufferedReader;
+import java.io.File;
+import java.io.FileInputStream;
+import java.io.FileReader;
+import java.nio.ByteBuffer;
+import java.nio.channels.FileChannel;
+
+/**
+ * Basic tests of the CompMemTrie.
+ */
+public class CompMemTrieTest {
+ public static void main(String[] args) throws Exception {
+ testWithFile(new File("../scratch/propernames.uniq"));
+ testWithFile(new File("../scratch/connectives.uniq"));
+ testWithFile(new File("../scratch/web2a.uniq"));
+ testWithFile(new File("../scratch/web2.uniq"));
+ testWithRandomFile(new File("/dev/urandom"));
+// testLoadWithRandomFile(new File("/dev/urandom"));
+ }
+
+ public static void testWithFile(File file) throws Exception {
+ Map<byte[], Long> namesMap = new HashMap<byte[], Long>();
+ CompMemTrie namesTrie = new CompMemTrie();
+
+ System.out.println("Inserting lines from " + file);
+ BufferedReader names = new BufferedReader(new FileReader(file));
+ long n = 0;
+ String name = names.readLine();
+ long _startInsert = System.currentTimeMillis();
+ while (name != null) {
+ namesMap.put(name.getBytes(), n);
+ namesTrie.insert(name.getBytes(), n);
+ name = names.readLine();
+ n++;
+ }
+ long _endInsert = System.currentTimeMillis();
+ names.close();
+
+ System.out.println("Checking lines from " + file);
+ long _startLookup = System.currentTimeMillis();
+ for (byte[] key : namesMap.keySet()) {
+ if (namesTrie.lookup(key) != namesMap.get(key)) {
+ throw new IllegalStateException("Trie doesn't match Map");
+ }
+ }
+ long _endLookup = System.currentTimeMillis();
+
+ System.out.println("Test Succeeded with " + file +
+ " insert:" + (_endInsert - _startInsert) + " lookup:" + (_endLookup - _startLookup));
+ }
+
+ public static class Bytes {
+ public final byte[] bytes;
+
+ public Bytes(byte[] bytes) {
+ this.bytes = new byte[bytes.length];
+ System.arraycopy(bytes, 0, this.bytes, 0, bytes.length);
+ }
+
+ public boolean equals(Object o) {
+// System.err.print("Bytes::equals() # ");
+ if (o instanceof Bytes) {
+// System.err.println("Comparing " + Arrays.hashCode(bytes) + " with " + Arrays.hashCode(((Bytes)o).bytes));
+ return Arrays.equals(bytes, ((Bytes)o).bytes);
+ } else {
+ return false;
+ }
+ }
+
+ public int hashCode() {
+ int hc = Arrays.hashCode(bytes);
+// System.err.println("Bytes # Calculated hashcode for: " + hc);
+ return hc;
+ }
+ }
+
+ public static void testWithRandomFile(File file) throws Exception {
+ Map<Bytes, Long> namesMap = new HashMap<Bytes, Long>();
+ CompMemTrie namesTrie = new CompMemTrie();
+
+ System.out.println("Inserting random bytes from " + file);
+ FileChannel chan = new FileInputStream(file).getChannel();
+ ByteBuffer buffer = ByteBuffer.allocate(134*1024);
+
+ long n = 0;
+ byte[] key;
+ // Set limit to 0 so initial compact works correctly.
+ buffer.clear().limit(0);
+ long _startInsert = System.currentTimeMillis();
+ long _aggregateL = 0;
+ long _avlL = 0;
+ long _aggregateS = 0;
+ long _avlS = 0;
+ int nL = 0;
+ int nS = 0;
+
+ while (n < 5000) {
+ if (buffer.remaining() < 67*1024 && chan.read(buffer.compact()) == -1) {
+ break;
+ }
+ buffer.flip();
+
+ key = new byte[((int)buffer.getShort()) & 0x0000FFFF];
+ buffer.get(key);
+ Bytes keyBytes = new Bytes(key);
+
+ if (namesMap.containsKey(keyBytes)) {
+ namesTrie.insert(key, namesMap.get(keyBytes));
+ } else {
+ n++;
+ namesMap.put(keyBytes, n);
+ long _si = System.currentTimeMillis();
+ namesTrie.insert(key, n);
+ _aggregateL += System.currentTimeMillis() - _si;
+ _avlL += key.length;
+ nL++;
+ }
+
+ for (int i = 0; i < 10; i++) {
+ key = new byte[((int)buffer.get()) & 0x000000FF];
+ buffer.get(key);
+ keyBytes = new Bytes(key);
+ if (namesMap.containsKey(keyBytes)) {
+ namesTrie.insert(key, namesMap.get(keyBytes));
+ } else {
+ n++;
+ namesMap.put(keyBytes, n);
+ long _ss = System.currentTimeMillis();
+ namesTrie.insert(key, n);
+ _aggregateS += System.currentTimeMillis() - _ss;
+ _avlS += key.length;
+ nS++;
+ }
+ }
+ }
+ long _endInsert = System.currentTimeMillis();
+ System.out.println("Input " + namesMap.size() + " entries");
+ System.out.println(" " + nL + " long entries ave: " + (_avlL / nL) + " in: " + _aggregateL + "ms");
+ System.out.println(" " + nS + " short entries ave: " + (_avlS / nS) + " in: " + _aggregateS + "ms");
+ chan.close();
+
+ long _startLookup = System.currentTimeMillis();
+ System.out.println("Checking random bytes from " + file);
+ for (Bytes k : namesMap.keySet()) {
+ if (namesTrie.lookup(k.bytes) != namesMap.get(k)) {
+ throw new IllegalStateException("Trie doesn't match Map");
+ }
+ }
+ long _endLookup = System.currentTimeMillis();
+
+ System.out.println("Test Succeeded with " + file +
+ " insert:" + (_endInsert - _startInsert) + " lookup:" + (_endLookup - _startLookup));
+ }
+
+ public static void testLoadWithRandomFile(File file) throws Exception {
+ Map<Bytes, Long> namesMap = new HashMap<Bytes, Long>();
+ CompMemTrie namesTrie = new CompMemTrie();
+
+ System.out.println("Inserting random bytes from " + file);
+ FileChannel chan = new FileInputStream(file).getChannel();
+ ByteBuffer buffer = ByteBuffer.allocate(8*1024*1024);
+
+ long n = 0;
+ byte[] key;
+ // Set limit to 0 so initial compact works correctly.
+ buffer.clear().limit(0);
+ long _startInsert = System.currentTimeMillis();
+ long _aggregateL = 0;
+ long _avlL = 0;
+ int nL = 0;
+ long _aggregateLL = 0;
+ long _avlLL = 0;
+ int nLL = 0;
+ long _aggregateS = 0;
+ long _avlS = 0;
+ int nS = 0;
+ long _aggregateSS = 0;
+ long _avlSS = 0;
+ int nSS = 0;
+
+ for (int i = 0; i < 100; i++) {
+ if (buffer.remaining() < 2*1024*1024 && chan.read(buffer.compact()) == -1) {
+ break;
+ }
+ buffer.flip();
+
+ key = new byte[buffer.getInt() & 0x0007FFFF];
+ buffer.get(key);
+ Bytes keyBytes = new Bytes(key);
+
+ if (namesMap.containsKey(keyBytes)) {
+ namesTrie.insert(key, namesMap.get(keyBytes));
+ } else {
+ n++;
+ namesMap.put(keyBytes, n);
+ long _sll = System.currentTimeMillis();
+ namesTrie.insert(key, n);
+ _aggregateLL += System.currentTimeMillis() - _sll;
+ _avlLL += key.length;
+ nLL++;
+ }
+
+ for (int j = 0; j < 10; j++) {
+ key = new byte[((int)buffer.getShort()) & 0x0000FFFF];
+ buffer.get(key);
+ keyBytes = new Bytes(key);
+ if (namesMap.containsKey(keyBytes)) {
+ namesTrie.insert(key, namesMap.get(keyBytes));
+ } else {
+ n++;
+ namesMap.put(keyBytes, n);
+ long _sl = System.currentTimeMillis();
+ namesTrie.insert(key, n);
+ _aggregateL += System.currentTimeMillis() - _sl;
+ _avlL += key.length;
+ nL++;
+ }
+
+ for (int k = 0; k < 10; k++) {
+ key = new byte[((int)buffer.get()) & 0x000000FF];
+ buffer.get(key);
+ keyBytes = new Bytes(key);
+ if (namesMap.containsKey(keyBytes)) {
+ namesTrie.insert(key, namesMap.get(keyBytes));
+ } else {
+ n++;
+ namesMap.put(keyBytes, n);
+ long _ss = System.currentTimeMillis();
+ namesTrie.insert(key, n);
+ _aggregateS += System.currentTimeMillis() - _ss;
+ _avlS += key.length;
+ nS++;
+ }
+
+ for (int ii = 0; ii < 1000; ii++) {
+ key = new byte[((int)buffer.get()) & 0x0000001F];
+ buffer.get(key);
+ keyBytes = new Bytes(key);
+ if (namesMap.containsKey(keyBytes)) {
+ namesTrie.insert(key, namesMap.get(keyBytes));
+ } else {
+ n++;
+ namesMap.put(keyBytes, n);
+ long _sss = System.currentTimeMillis();
+ namesTrie.insert(key, n);
+ _aggregateS += System.currentTimeMillis() - _sss;
+ _avlSS += key.length;
+ nSS++;
+ }
+ }
+ }
+ }
+ }
+ long _endInsert = System.currentTimeMillis();
+ System.out.println("Input " + namesMap.size() + " entries");
+ System.out.println(" " + nLL + " very long entries ave: " + (_avlLL / nLL) + " in: " + _aggregateLL + "ms");
+ System.out.println(" " + nL + " long entries ave: " + (_avlL / nL) + " in: " + _aggregateL + "ms");
+ System.out.println(" " + nS + " short entries ave: " + (_avlS / nS) + " in: " + _aggregateS + "ms");
+ System.out.println(" " + nSS + " very short entries ave: " + (_avlSS / nSS) + " in: " + _aggregateSS + "ms");
+ chan.close();
+
+ long _startLookup = System.currentTimeMillis();
+ System.out.println("Checking random bytes from " + file);
+ for (Bytes k : namesMap.keySet()) {
+ if (namesTrie.lookup(k.bytes) != namesMap.get(k)) {
+ throw new IllegalStateException("Trie doesn't match Map");
+ }
+ }
+ long _endLookup = System.currentTimeMillis();
+
+ System.out.println("Test Succeeded with " + file +
+ " insert:" + (_endInsert - _startInsert) + " lookup:" + (_endLookup - _startLookup));
+ }
+}
Modified: projects/xa2/object-pool/src/MemoryTrieTest.java
===================================================================
--- projects/xa2/object-pool/src/MemoryTrieTest.java 2008-04-15 06:17:45 UTC (rev 788)
+++ projects/xa2/object-pool/src/MemoryTrieTest.java 2008-04-15 10:27:30 UTC (rev 789)
@@ -19,12 +19,12 @@
*/
public class MemoryTrieTest {
public static void main(String[] args) throws Exception {
-// testWithFile(new File("../scratch/propernames.uniq"));
-// testWithFile(new File("../scratch/connectives.uniq"));
-// testWithFile(new File("../scratch/web2a.uniq"));
-// testWithFile(new File("../scratch/web2.uniq"));
-// testWithRandomFile(new File("/dev/urandom"));
- testLoadWithRandomFile(new File("/dev/urandom"));
+ testWithFile(new File("../scratch/propernames.uniq"));
+ testWithFile(new File("../scratch/connectives.uniq"));
+ testWithFile(new File("../scratch/web2a.uniq"));
+ testWithFile(new File("../scratch/web2.uniq"));
+ testWithRandomFile(new File("/dev/urandom"));
+// testLoadWithRandomFile(new File("/dev/urandom"));
}
public static void testWithFile(File file) throws Exception {
More information about the Mulgara-svn
mailing list