[Mulgara-svn] r793 - in projects/xa2/object-pool: bulk src
andrae at mulgara.org
andrae at mulgara.org
Wed Apr 16 09:58:02 UTC 2008
Author: andrae
Date: 2008-04-16 02:58:01 -0700 (Wed, 16 Apr 2008)
New Revision: 793
Added:
projects/xa2/object-pool/bulk/random70M
Modified:
projects/xa2/object-pool/src/ByteMap.java
projects/xa2/object-pool/src/ByteMapTest.java
projects/xa2/object-pool/src/CompMemTrie.java
projects/xa2/object-pool/src/CompMemTrieTest.java
projects/xa2/object-pool/src/MemoryTrie.java
Log:
Implements a Memory Based Trie using the 256-ary ByteMap.
Note: When we come to serialise this, if the map overhead is greater than 4+N bytes we should consider
converting to an implicit double array as this has either 3+N(odd) or 4+N(even) constant overhead.
Added: projects/xa2/object-pool/bulk/random70M
===================================================================
(Binary files differ)
Property changes on: projects/xa2/object-pool/bulk/random70M
___________________________________________________________________
Name: svn:mime-type
+ application/octet-stream
Modified: projects/xa2/object-pool/src/ByteMap.java
===================================================================
--- projects/xa2/object-pool/src/ByteMap.java 2008-04-16 09:21:48 UTC (rev 792)
+++ projects/xa2/object-pool/src/ByteMap.java 2008-04-16 09:58:01 UTC (rev 793)
@@ -70,6 +70,11 @@
* @return Value corresponding to key; or null if not found.
*/
public T lookup(byte key) {
+ if ((high & hiNibbleAsBitInShort(key)) == 0) {
+ // We didn't find the high nibble in this map.
+ return null;
+ }
+
// the low-nibble index is the ones left of the key's high-nibble bit in high.
int lowOffset = ones(HIGH, high, key);
@@ -78,6 +83,11 @@
if (lowOffset >= low.length) {
return null;
}
+ if ((low[lowOffset] & lowNibbleAsBitInShort(key)) == 0) {
+ // The high nibble matched, but the low nibble didn't.
+ return null;
+ }
+
int dataOffset = 0;
for (int i = 0; i < lowOffset; i++) {
dataOffset += ones(low[i]);
Modified: projects/xa2/object-pool/src/ByteMapTest.java
===================================================================
--- projects/xa2/object-pool/src/ByteMapTest.java 2008-04-16 09:21:48 UTC (rev 792)
+++ projects/xa2/object-pool/src/ByteMapTest.java 2008-04-16 09:58:01 UTC (rev 793)
@@ -13,6 +13,8 @@
testAlternate();
testAlternateLowNibbleImmediate();
testLookupNonExistentLow();
+ testLookupMissedHighMatchedLow();
+ testLookupMatchedHighMissedLow();
}
public static void testEmpty() throws Exception {
@@ -124,6 +126,36 @@
System.out.println("testLookupNonExistentLow Successful");
}
+ public static void testLookupMissedHighMatchedLow() throws Exception {
+ System.out.println("running testLookupMissedHighMatchedLow...");
+ ByteMap<Long> byteMap = new ByteMap<Long>();
+
+ int i = 0x017;
+ 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 = 0x007;
+ assertNull("Found entry for uninserted key i = " + i, byteMap.lookup((byte)i));
+
+ System.out.println("testLookupMissedHighMatchedLow Successful");
+ }
+
+ public static void testLookupMatchedHighMissedLow() throws Exception {
+ System.out.println("running testLookupMatchedHighMissedLow...");
+ ByteMap<Long> byteMap = new ByteMap<Long>();
+
+ int i = 0x007;
+ 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 = 0x006;
+ assertNull("Found entry for uninserted key i = " + i, byteMap.lookup((byte)i));
+
+ System.out.println("testLookupMatchedHighMissedLow Successful");
+ }
+
public static void assertNull(String str, Object obj) throws Exception {
if (obj != null) {
throw new IllegalStateException(str);
Modified: projects/xa2/object-pool/src/CompMemTrie.java
===================================================================
--- projects/xa2/object-pool/src/CompMemTrie.java 2008-04-16 09:21:48 UTC (rev 792)
+++ projects/xa2/object-pool/src/CompMemTrie.java 2008-04-16 09:58:01 UTC (rev 793)
@@ -13,7 +13,7 @@
@SuppressWarnings("serial")
public static class NotFound extends Exception {};
- private TrieBranch root;
+ private TrieNode root;
public CompMemTrie() {
this.root = null;
@@ -21,7 +21,7 @@
public void insert(byte[] key, long value) {
if (root == null) {
- root = new TrieBranch(key, value);
+ root = new TrieLeaf(key, value);
} else {
try {
root.insert(key, value);
@@ -46,6 +46,14 @@
protected TrieLeaf least;
+ public void insert(byte[] key, long value) throws InsertAbove {
+ insert(new TrieLeaf(key, value), 0);
+ }
+
+ public long lookup(byte[] key) throws NotFound {
+ return lookup(key, 0);
+ }
+
protected abstract void insert(TrieLeaf node, int parentLcd) throws InsertAbove;
protected abstract long lookup(byte[] key, int parentLcd) throws NotFound;
@@ -77,7 +85,7 @@
this.least = this.term;
}
- public TrieBranch(TrieBranch oldRoot, byte[] key, long value) {
+ public TrieBranch(TrieNode oldRoot, byte[] key, long value) {
this(oldRoot, new TrieLeaf(key, value));
}
@@ -127,14 +135,6 @@
}
}
- public void insert(byte[] key, long value) throws InsertAbove {
- insert(new TrieLeaf(key, value), 0);
- }
-
- public long lookup(byte[] key) throws NotFound {
- return lookup(key, 0);
- }
-
protected void insert(TrieLeaf node, int parentLcp) throws InsertAbove {
if (!regionMatches(least.key, parentLcp, node.key, parentLcp, offset - parentLcp)) {
throw cont;
Modified: projects/xa2/object-pool/src/CompMemTrieTest.java
===================================================================
--- projects/xa2/object-pool/src/CompMemTrieTest.java 2008-04-16 09:21:48 UTC (rev 792)
+++ projects/xa2/object-pool/src/CompMemTrieTest.java 2008-04-16 09:58:01 UTC (rev 793)
@@ -23,6 +23,9 @@
testWithFile(new File("../scratch/connectives.uniq"));
testWithFile(new File("../scratch/web2a.uniq"));
testWithFile(new File("../scratch/web2.uniq"));
+ testWithRandomFileTuned(new File("../bulk/random70M"), 12, 10);
+ testWithRandomFileTuned(new File("../bulk/random70M"), 250, 10);
+ testWithRandomFileTuned(new File("../bulk/random70M"), 5000, 10);
testWithRandomFile(new File("/dev/urandom"));
// testLoadWithRandomFile(new File("/dev/urandom"));
}
@@ -67,9 +70,7 @@
}
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;
@@ -78,11 +79,10 @@
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();
@@ -114,7 +114,7 @@
Bytes keyBytes = new Bytes(key);
if (namesMap.containsKey(keyBytes)) {
- namesTrie.insert(key, namesMap.get(keyBytes));
+// namesTrie.insert(key, namesMap.get(keyBytes));
} else {
n++;
namesMap.put(keyBytes, n);
@@ -123,6 +123,10 @@
_aggregateL += System.currentTimeMillis() - _si;
_avlL += key.length;
nL++;
+
+ if (namesTrie.lookup(key) != n) {
+ throw new IllegalStateException("lookup failed key: " + Arrays.toString(key) + " value: " + n);
+ }
}
for (int i = 0; i < 10; i++) {
@@ -130,7 +134,7 @@
buffer.get(key);
keyBytes = new Bytes(key);
if (namesMap.containsKey(keyBytes)) {
- namesTrie.insert(key, namesMap.get(keyBytes));
+// namesTrie.insert(key, namesMap.get(keyBytes));
} else {
n++;
namesMap.put(keyBytes, n);
@@ -139,6 +143,10 @@
_aggregateS += System.currentTimeMillis() - _ss;
_avlS += key.length;
nS++;
+
+ if (namesTrie.lookup(key) != n) {
+ throw new IllegalStateException("lookup failed key: " + Arrays.toString(key) + " value: " + n);
+ }
}
}
}
@@ -146,14 +154,17 @@
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");
+ System.out.println(chan.position() + " bytes read from /dev/urandom");
chan.close();
long _startLookup = System.currentTimeMillis();
System.out.println("Checking random bytes from " + file);
for (Bytes k : namesMap.keySet()) {
+ int i = 0;
if (namesTrie.lookup(k.bytes) != namesMap.get(k)) {
- throw new IllegalStateException("Trie doesn't match Map");
+ throw new IllegalStateException("Trie doesn't match Map on entry: " + i + " key:" + Arrays.toString(k.bytes) + " value: " + namesTrie.lookup(k.bytes) + " value': " + namesMap.get(k));
}
+ i++;
}
long _endLookup = System.currentTimeMillis();
@@ -161,6 +172,95 @@
" insert:" + (_endInsert - _startInsert) + " lookup:" + (_endLookup - _startLookup));
}
+ public static void testWithRandomFileTuned(File file, int max, int small) throws Exception {
+ Map<Bytes, Long> namesMap = new HashMap<Bytes, Long>();
+ CompMemTrie namesTrie = new CompMemTrie();
+
+ System.out.println("Inserting random bytes from " + file + " to max records " + max + " with small " + small);
+ 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 < max) {
+ 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++;
+
+ if (namesTrie.lookup(key) != n) {
+ throw new IllegalStateException("lookup failed key: " + Arrays.toString(key) + " value: " + n);
+ }
+ }
+
+ for (int i = 0; i < small; 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++;
+
+ if (namesTrie.lookup(key) != n) {
+ throw new IllegalStateException("lookup failed key: " + Arrays.toString(key) + " value: " + n);
+ }
+ }
+ }
+ }
+ 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");
+ System.out.println(chan.position() + " bytes read from /dev/urandom");
+ chan.close();
+
+ long _startLookup = System.currentTimeMillis();
+ System.out.println("Checking random bytes from " + file);
+ for (Bytes k : namesMap.keySet()) {
+ int i = 0;
+ if (namesTrie.lookup(k.bytes) != namesMap.get(k)) {
+ throw new IllegalStateException("Trie doesn't match Map on entry: " + i + " key:" + Arrays.toString(k.bytes) + " value: " + namesTrie.lookup(k.bytes) + " value': " + namesMap.get(k));
+ }
+ i++;
+ }
+ 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();
@@ -207,6 +307,10 @@
_aggregateLL += System.currentTimeMillis() - _sll;
_avlLL += key.length;
nLL++;
+
+ if (namesTrie.lookup(key) != n) {
+ throw new IllegalStateException("lookup failed key: " + Arrays.toString(key) + " value: " + n);
+ }
}
for (int j = 0; j < 10; j++) {
@@ -223,6 +327,10 @@
_aggregateL += System.currentTimeMillis() - _sl;
_avlL += key.length;
nL++;
+
+ if (namesTrie.lookup(key) != n) {
+ throw new IllegalStateException("lookup failed key: " + Arrays.toString(key) + " value: " + n);
+ }
}
for (int k = 0; k < 10; k++) {
@@ -239,6 +347,10 @@
_aggregateS += System.currentTimeMillis() - _ss;
_avlS += key.length;
nS++;
+
+ if (namesTrie.lookup(key) != n) {
+ throw new IllegalStateException("lookup failed key: " + Arrays.toString(key) + " value: " + n);
+ }
}
for (int ii = 0; ii < 1000; ii++) {
@@ -255,6 +367,10 @@
_aggregateS += System.currentTimeMillis() - _sss;
_avlSS += key.length;
nSS++;
+
+ if (namesTrie.lookup(key) != n) {
+ throw new IllegalStateException("lookup failed key: " + Arrays.toString(key) + " value: " + n);
+ }
}
}
}
@@ -271,9 +387,11 @@
long _startLookup = System.currentTimeMillis();
System.out.println("Checking random bytes from " + file);
for (Bytes k : namesMap.keySet()) {
+ int i = 0;
if (namesTrie.lookup(k.bytes) != namesMap.get(k)) {
- throw new IllegalStateException("Trie doesn't match Map");
+ throw new IllegalStateException("Trie doesn't match Map on entry: " + i + " key:" + Arrays.toString(k.bytes) + " value: " + namesTrie.lookup(k.bytes) + " value': " + namesMap.get(k));
}
+ i++;
}
long _endLookup = System.currentTimeMillis();
Modified: projects/xa2/object-pool/src/MemoryTrie.java
===================================================================
--- projects/xa2/object-pool/src/MemoryTrie.java 2008-04-16 09:21:48 UTC (rev 792)
+++ projects/xa2/object-pool/src/MemoryTrie.java 2008-04-16 09:58:01 UTC (rev 793)
@@ -15,7 +15,7 @@
@SuppressWarnings("serial")
public static class NotFound extends Exception {};
- private TrieBranch root;
+ private TrieNode root;
public MemoryTrie() {
this.root = null;
@@ -24,7 +24,7 @@
public void insert(byte[] key, long value) {
// System.err.println("MemoryTrie # Inserting: " + Arrays.hashCode(key) + " :: " + value);
if (root == null) {
- root = new TrieBranch(key, value);
+ root = new TrieLeaf(key, value);
} else {
try {
root.insert(key, value);
@@ -50,9 +50,17 @@
protected TrieLeaf least;
+ public void insert(byte[] key, long value) throws InsertAbove {
+ insert(new TrieLeaf(key, value), 0);
+ }
+
+ public long lookup(byte[] key) throws NotFound {
+ return lookup(key, 0);
+ }
+
protected abstract void insert(TrieLeaf node, int parentLcd) throws InsertAbove;
protected abstract long lookup(byte[] key, int parentLcd) throws NotFound;
-
+
protected static boolean regionMatches(byte[] lhs, int lhsOff, byte[] rhs, int rhsOff, int len) {
if (lhsOff < 0 || rhsOff < 0) {
return false;
@@ -81,7 +89,7 @@
this.least = this.term;
}
- public TrieBranch(TrieBranch oldRoot, byte[] key, long value) {
+ public TrieBranch(TrieNode oldRoot, byte[] key, long value) {
this(oldRoot, new TrieLeaf(key, value));
}
@@ -131,14 +139,6 @@
}
}
- public void insert(byte[] key, long value) throws InsertAbove {
- insert(new TrieLeaf(key, value), 0);
- }
-
- public long lookup(byte[] key) throws NotFound {
- return lookup(key, 0);
- }
-
protected void insert(TrieLeaf node, int parentLcp) throws InsertAbove {
if (!regionMatches(least.key, parentLcp, node.key, parentLcp, offset - parentLcp)) {
throw cont;
More information about the Mulgara-svn
mailing list