You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@jena.apache.org by an...@apache.org on 2011/11/07 14:36:34 UTC
svn commit: r1198733 [13/13] - in /incubator/jena/Scratch/AFS/Dev/trunk:
src-archive/riot/comms/ src-archive/riot/comms/client/
src-archive/riot/comms/server0/ src-archive/riot/comms/server1/nio/
src-archive/riot/comms/server1/socket/ src-archive/riot/...
Modified: incubator/jena/Scratch/AFS/Dev/trunk/src/main/java/storage/varrecord/VarRecordBuffer.java
URL: http://svn.apache.org/viewvc/incubator/jena/Scratch/AFS/Dev/trunk/src/main/java/storage/varrecord/VarRecordBuffer.java?rev=1198733&r1=1198732&r2=1198733&view=diff
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src/main/java/storage/varrecord/VarRecordBuffer.java (original)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src/main/java/storage/varrecord/VarRecordBuffer.java Mon Nov 7 13:36:30 2011
@@ -1,4 +1,4 @@
-/**
+/*
* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements. See the NOTICE file
* distributed with this work for additional information
@@ -16,561 +16,561 @@
* limitations under the License.
*/
-package storage.varrecord;
-
-import java.io.PrintStream ;
-import java.nio.ByteBuffer ;
-import java.util.Arrays ;
-
-import migrate.lib.VarInteger ;
-import org.openjena.atlas.lib.ByteBufferLib ;
-import org.openjena.atlas.lib.InternalErrorException ;
-
-import com.hp.hpl.jena.tdb.base.record.Record ;
-import com.hp.hpl.jena.tdb.sys.SystemTDB ;
-
-/** Pack variable length items into a fixed size block */
-public final class VarRecordBuffer
-{
- // Alternative: blocked 8K writes. No write-over boundary (or some kind of continue marker).
- // Less flexible (no delete, no simple extension to replication infrastructure)
-
- // Does this mess up node ids of 64 bits.
- // id : block + idx in file (16 bits = 64K)
- // 64 = 8(type tag) + 40 + 16
- // Better to steal bits from the 8 byte tag.
- // 2^40 ~= 1e12 or 1 trillion
-
- /*
- * Layout:
- * Count
- * (i,j)* Pairs of shorts indexing key and value byte[]
- * unused
- * (varint, bytes)* Each entry is a varint (length of bytes) and the bytes
- *
- * The bytes for entries are added from the top, downwards.
- *
- */
-
- // Layout of variable length things.
- // (?? Currently - no) Block type
- // Block lengh (item count) [integer (or short?)]
- // Ptrs for (K,V) pairs - shorts, byte offsets in the block (max block is 32k) [shorts are signed:-(]
- // Could do ints as 2 bytes unsigned
- // Unused area
- // The keys and values encoded as a VarInt for the length then bytes.
- // The variable length items are added from the top as they arrive
- // They may not in stored in the variable length area in index order
- // because they may have arrived because of an insert in the middle of
- // the indexes at the time.
-
- // Overhead: num elements and the start of the variable length area (it's calculable by scanning?)
- final public static int COUNT = 0 ;
- // Can find the start of variable area.
-// final public static int LINK = 8 ;
- final private static int HEADER_LENGTH = SystemTDB.SizeOfInt ;
-
- final static boolean FILL = true ;
- final static byte FILL_BYTE = (byte)0xAB ;
- final static short FILL_SHORT = (short)0xABAB ;
-
- private static final int SIZE = 100 ;
-
- // Index of byte not-in-use for var size items area.
- // Must initialize
- int numElts ;
- int startVarArea ;
- final ByteBuffer bb ;
-
- public final int LenIdxPtr = Short.SIZE / 8 ;
- public final int LenIdxSlot = 2*LenIdxPtr ;
-
- /**
- * Create a buffer for variable sized records.
- * @param sizeInBytes Total space for records (total includes internal admin space)
- */
-
- public VarRecordBuffer(int sizeInBytes)
- {
- bb = ByteBuffer.allocate(sizeInBytes) ;
- numElts = 0 ;
- setCount(numElts) ;
- startVarArea = bb.capacity() ;
- if ( FILL )
- ByteBufferLib.fill(bb, FILL_BYTE) ;
- }
-
- private VarRecordBuffer(ByteBuffer bb)
- {
- this.bb = bb ;
- numElts = getCount() ;
- // Calc the var start.
- int varLocMin = bb.capacity() ;
- for ( int i = 0 ; i < numElts ; i++ )
- {
- int x1 = keyStartIdx(i) ;
- int x2 = valueStartIdx(i) ;
- varLocMin = Math.min(varLocMin, x1) ;
- varLocMin = Math.min(varLocMin, x2) ;
- }
- this.startVarArea = varLocMin ;
- }
-
- public static VarRecordBuffer wrap(ByteBuffer bb)
- {
- return new VarRecordBuffer(bb) ;
- }
-
- public ByteBuffer getByteBuffer() { return bb ; }
-
- public int size() { return numElts ; }
- public int bytesInUse() { return (HEADER_LENGTH+LenIdxSlot*numElts) + (bb.limit()-startVarArea) ; }
-
- // ---- Internal abstractions
- /** Position of the internal index for the i'th key */
- private int keyIdx(int i)
- { return HEADER_LENGTH+i*LenIdxSlot ; }
-
- /** Position of the internal index for the i'th value */
- private int valueIdx(int i)
- { return HEADER_LENGTH+i*LenIdxSlot+LenIdxPtr ; }
-
- /** Position of the start of the bytes for the i'th key */
- private int keyStartIdx(int i)
- {
- int idx = keyIdx(i) ;
- short start = bb.getShort(idx) ;
- return start ;
- }
-
- /** Position of the start of the bytes for the i'th value */
- private int valueStartIdx(int i)
- {
- int idx = valueIdx(i) ;
- short start = bb.getShort(idx) ;
- return start ;
- }
-
- /** Items */
- private int getCount()
- { return bb.getInt(COUNT) ; }
-
- private void setCount(int count)
- { bb.putInt(COUNT, count) ; }
-
- public Record get(int idx)
- {
- check(idx) ;
-
- int k = keyStartIdx(idx) ;
- int v = valueStartIdx(idx) ;
-
- byte[] key = getBytes(k) ;
- byte[] value = getBytes(v) ;
- return new Record(key,value) ;
- }
-
- /** find by key - linear search - does not assume sorted */
- public byte[] find(byte[] key)
- {
- for ( int i = 0 ; i < numElts ; i++ )
- {
- int k = keyStartIdx(i) ;
- byte[] keyBytes = getBytes(k) ;
- if ( Arrays.equals(keyBytes, key) )
- {
- int v = valueStartIdx(i) ;
- return getBytes(v) ;
- }
- }
- return null ;
- }
-
- public Record getKey(int idx)
- {
- check(idx) ;
-
- int k = keyStartIdx(idx) ;
- int v = valueStartIdx(idx) ;
-
- System.out.printf("Get: %d (x%02X, x%02X)\n", idx, k, v) ;
-
- byte[] key = getBytes(k) ;
- byte[] value = getBytes(v) ;
- return new Record(key,value) ;
- }
-
- private void check(int idx)
- {
- if ( idx < 0 || idx >= numElts )
- throw new IllegalArgumentException("VarRecordBuffer.check failure") ;
- }
-
- public void put(Record r)
- {
- put(numElts, r.getKey(), r.getValue()) ;
- }
-
- public void put(byte[]key, byte[] value)
- {
- put(numElts, key, value) ;
- }
-
- public void put(int idx, Record r)
- {
- put(idx, r.getKey(), r.getValue()) ;
- }
-
- public void put(int idx, byte[]key, byte[] value)
- {
- // Allow put at top end.
- if ( idx < 0 || idx > numElts )
- throw new IllegalArgumentException("VarRecordBuffer.check failure") ;
- //System.out.printf("Put: %d (%d,%d)\n", idx, key.length, value.length) ;
-
- VarInteger keyLen = VarInteger.valueOf(key.length) ;
- VarInteger valLen = VarInteger.valueOf(value.length) ;
-
- // Var bytes + change in fixed area
- int lengthNeeded = bytesNeeded(key, value)+LenIdxSlot ;
-
- // Current gap.
- int currentSpace = startVarArea - (HEADER_LENGTH+LenIdxSlot*numElts) ;
-
-// System.out.printf("put(%d,[%d],[%d]) :: currentSpace=%d , lengthNeeded=%d \n",
-// idx, key.length, value.length, currentSpace, lengthNeeded) ;
-
- if ( lengthNeeded > currentSpace )
- throw new IllegalArgumentException("Insufficient space") ;
-
- // Put variable parts - bytes first, then length (it goes backwards).
- insertVarByteArray(value) ;
- int vIdxVal = insertVarByteArray(valLen.bytes()) ;
- insertVarByteArray(key) ;
- int vIdxKey = insertVarByteArray(keyLen.bytes()) ;
-
- // Put shorts - shuffle up a bit first.
- // Move up 2 places (if needed)
-
- // Shift up 2 offset slots
-// if ( true )
- shiftUp(bb, keyIdx(idx), LenIdxSlot, /*2*LenIdxPtr,*/ (numElts-idx)*LenIdxSlot) ;
-// else
-//// // elt i = elt i-1
-// if ( true )
-// {
-// for ( int i = numElts-1 ; i >= idx ; i-- )
-// {
-// // Better - use a byteblock shuffle.
-// // ith short is
-// // Old key and value internal indexes
-// int x1 = keyStartIdx(i) ;
-// int x2 = valueStartIdx(i) ;
-//
-// // New positions.
-// int j1 = keyIdx(i+1) ;
-// int j2 = valueIdx(i+1) ;
-//
-// System.out.println("j1 = "+j1) ;
-// bb.putShort(j1, (short)x1) ;
-// bb.putShort(j2, (short)x2) ;
-// }
-// }
- // Insert new internal indexes.
- bb.putShort(keyIdx(idx), (short)vIdxKey) ;
- bb.putShort(valueIdx(idx), (short)vIdxVal) ;
-
- numElts++ ;
- setCount(numElts) ;
- }
-
- private static void shiftUp(ByteBuffer bb, int start, int places, int length)
- {
- //System.out.printf("ShiftUp: start=%d places=%d length=%d\n",start, places, length) ;
- if ( length == 0 )
- return ;
- System.arraycopy(bb.array(), start, bb.array(), start+places, length) ;
- if ( FILL )
- ByteBufferLib.fill(bb, start, start+places, FILL_BYTE) ;
- }
-
- /** Delete at idx */
- public void delete(int idx)
- {
- check(idx) ;
- // Shuffles the space now rather than manages
- // non-contiguos free space.
- // Note that all internal indexes are changed
- // from here to the upper end.
-
- // ---- Lengths and setup
- // Assumes bytes for keys or values are not shared.
- int k = keyStartIdx(idx) ;
- VarInteger kLen = VarInteger.make(bb,k) ;
-
- int v = valueStartIdx(idx) ;
- VarInteger vLen = VarInteger.make(bb,v) ;
- //System.out.printf("delete: idx=%d (%d,%d)\n", idx, kLen.length()+kLen.value(), vLen.length()+vLen.value());
-
- // So we have from k to v + length of VarInt + length - k bytes
-
- // v-k is not length of key+varInt
- int delta = (int)kLen.value()+kLen.length()+(int)vLen.value()+vLen.length() ;
- int delta2 = v-k+(int)vLen.value()+vLen.length() ;
- if ( delta != delta2 )
- System.out.printf("*** Deltas: %d/%d\n", delta, delta2) ;
-
- // ---- delta is the size of the byte block, startign at k, to eliminate
- // Move startVarArea to k (exc)
- // remove idx internal index
- // Reset internal indexes (+delta) idx+1 to numElts
-
- //System.out.printf("delete: idx=%d [%d bytes from %d]\n", idx, delta, k) ;
-
- // ByteBufferLib.blockMove(bb,start,finish,length)
- // Move (startVarArea, k[exc]) up deltas places -- it's an overlapping move.
- for ( int j = k-1 ; j >= startVarArea ; j-- )
- {
- //System.out.printf("Move: %d to %d\n", j, j+tByte) ;
- byte b = bb.get(j) ;
- bb.put(j+delta,b) ;
- }
- startVarArea += delta ;
-
- // Move internal indexes to remove idx
- //System.out.printf("Remove index: %d\n", idx) ;
- for ( int i = idx+1 ; i < numElts ; i++ )
- {
- short key = (short)keyStartIdx(i) ;
- short val = (short)valueStartIdx(i) ;
- //System.out.printf("Move index: [%d] <- (%d,%d)(0x%02X,0x%02X)\n", i-1, key, val, key, val) ;
- bb.putShort(keyIdx(i-1), key) ;
- bb.putShort(valueIdx(i-1), val) ;
- }
- // Clear top.
- bb.putShort(keyIdx(numElts-1), FILL_SHORT) ;
- bb.putShort(valueIdx(numElts-1), FILL_SHORT) ;
- numElts -- ;
- setCount(numElts) ;
-
- // Adjust indexes pointing to moved bytes
- for ( int i = 0 ; i < numElts ; i++ )
- {
- int k2 = keyStartIdx(i) ;
- // Don't need look at value
- if ( k2 < k )
- {
- // Fixup.
- int v2 = valueStartIdx(i) ;
- int k3 = k2+delta ;
- int v3 = v2+delta ;
-
- //System.out.printf("Fixup: %d %d->%d, %d->%d\n", i, k2,k3, v2,v3) ;
-
- bb.putShort(keyIdx(i), (short)k3) ;
- bb.putShort(valueIdx(i), (short)v3) ;
- }
- else
- {
- int v2 = valueStartIdx(i) ;
- //System.out.printf("No Fixup: %d (%d,%d)\n", i, k2, v2) ;
- }
- }
-
- //throw new NotImplemented("delete") ;
- }
-
- /** Delete top */
- public void delete()
- {
- delete(numElts-1) ;
- }
-
- private int insertVarByteArray(byte[] bytes)
- {
- int x = startVarArea-bytes.length ;
- for ( int i = 0 ; i < bytes.length ; i++ )
- bb.put(i+x, bytes[i]) ;
- startVarArea -= bytes.length ;
- return startVarArea ;
- }
-
- private static int bytesNeeded(byte[] key, byte[] value )
- {
- return bytesNeeded(key)+bytesNeeded(value) ;
- }
-
- private static int bytesNeeded(byte[] bytes)
- {
- return VarInteger.lengthOf(bytes.length) + bytes.length ;
- }
-
- /** Perform consistence checking */
- public void check()
- {
- if ( getCount() != numElts )
- error("Buffer count does not agree with number of elements (%d,%d)", getCount(), numElts) ;
-
- for ( int i = 0 ; i < numElts ; i++ )
- {
- int k = keyStartIdx(i) ;
- int v = valueStartIdx(i) ;
- }
-
- // Check the unused area is filled with marker bytes.
-
- int lo = valueStartIdx(numElts-1) ;
- int hi = startVarArea ;
-
- if ( lo > hi )
- error("Overlap in internal indexes and variable obects area") ;
-
- if ( FILL )
- {
- for ( int j = lo ; j < hi ; j++ )
- if ( bb.get(j) != FILL_BYTE )
- error("Non-fill byte (0x%02X) unused area", bb.get(j)) ;
- }
- // There are 2*numElts
- int x = startVarArea ;
- for ( int i = 0 ; i < 2*numElts ; i++ )
- {
- if ( x < startVarArea || x >= bb.limit() )
- error("Variable area is corrupt") ;
- VarInteger varInt = VarInteger.make(bb, x) ;
- int len = varInt.length()+(int)varInt.value() ;
- x = x+len ;
- }
-
- }
-
- private void error(String string, Object... args)
- {
- String x = String.format(string, args) ;
- throw new InternalErrorException(x) ;
- }
-
- public void dump()
- {
- print(bb) ;
- StringBuilder sb = new StringBuilder() ;
- sb.append("[size:"+getCount()) ;
-
- for ( int i = 0 ; i < numElts ; i++ )
- {
- sb.append(" ") ;
-
- sb.append("(") ;
- sb.append(keyStartIdx(i)) ;
- sb.append(",") ;
- sb.append(valueStartIdx(i)) ;
- sb.append(")") ;
- }
- sb.append("]") ;
- System.out.println(sb) ;
- }
-
-
- @Override
- public String toString()
- {
- StringBuilder sb = new StringBuilder() ;
- sb.append("[size:"+getCount()) ;
-
- for ( int i = 0 ; i < numElts ; i++ )
- {
- sb.append(" ") ;
-
- sb.append("(") ;
- sb.append(keyStartIdx(i)) ;
- sb.append(",") ;
- sb.append(valueStartIdx(i)) ;
- sb.append(")") ;
-
- Record r = get(i) ;
- sb.append(r) ;
-
- }
- sb.append("]") ;
- return sb.toString() ;
- }
-
-
- private byte[] getBytes(int byteIdx)
- {
- //System.out.println("Get: @"+byteIdx) ;
- VarInteger vInt = getVInt(byteIdx) ; // Length of variable length object
- int v = (int)vInt.value() ;
- int bytesStart = byteIdx+vInt.length() ;
- byte[] b = new byte[v] ;
- // Better ByteBuffer operation?
- for ( int i = 0 ; i < v ; i++ )
- b[i] = bb.get(bytesStart+i) ;
- return b ;
- }
-
- private VarInteger getVInt(int byteIdx)
- {
- return VarInteger.make(bb, byteIdx) ;
- }
-
- // ---- Development
- public static void print(ByteBuffer byteBuffer)
- {
- print(System.out, byteBuffer) ;
- }
-
- public static void print(PrintStream out, ByteBuffer byteBuffer)
- {
- out.printf("ByteBuffer[pos=%d lim=%d cap=%d]",byteBuffer.position(), byteBuffer.limit(), byteBuffer.capacity()) ;
- out.println() ;
- // Print bytes.
- int i = 0 ;
- int maxBytes = SIZE;
- for ( ; i < maxBytes && i < byteBuffer.limit() ; i++ )
- {
- if ( i%20 == 0 && i != 0 )
- out.println() ;
- out.printf(" 0x%02X", byteBuffer.get(i)) ;
- }
- if ( i < maxBytes && i < byteBuffer.limit() )
- out.print(" ...") ;
- // Print as 4-byte ints
-// int maxSlots = 8 ;
-// int i = 0 ;
-// for ( ; i < maxSlots && 4*i < byteBuffer.limit() ; i++ )
-// out.printf(" 0x%04X", byteBuffer.getInt(4*i)) ;
-// if ( i < maxSlots )
-// out.print(" ...") ;
- out.println();
- }
-
- // There's some accessor stuff somewhere - combine.
-
- public static void print(PrintStream out, byte[] bytes)
- {
- out.printf("byte[%d]:", bytes.length) ;
- int i = 0 ;
- int maxBytes = SIZE;
- for ( ; i < maxBytes && i < bytes.length ; i++ )
- {
- if ( i%20 == 0 && i != 0 )
- out.println() ;
- out.printf(" 0x%02X", bytes[i]) ;
- }
- if ( i < maxBytes && i < bytes.length )
- out.print(" ...") ;
- // Print as 4-byte ints
-// int maxSlots = 8 ;
-// int i = 0 ;
-// for ( ; i < maxSlots && 4*i < byteBuffer.limit() ; i++ )
-// out.printf(" 0x%04X", byteBuffer.getInt(4*i)) ;
-// if ( i < maxSlots )
-// out.print(" ...") ;
- out.println();
-
- }
-
-
-
+package storage.varrecord;
+
+import java.io.PrintStream ;
+import java.nio.ByteBuffer ;
+import java.util.Arrays ;
+
+import migrate.lib.VarInteger ;
+import org.openjena.atlas.lib.ByteBufferLib ;
+import org.openjena.atlas.lib.InternalErrorException ;
+
+import com.hp.hpl.jena.tdb.base.record.Record ;
+import com.hp.hpl.jena.tdb.sys.SystemTDB ;
+
+/** Pack variable length items into a fixed size block */
+public final class VarRecordBuffer
+{
+ // Alternative: blocked 8K writes. No write-over boundary (or some kind of continue marker).
+ // Less flexible (no delete, no simple extension to replication infrastructure)
+
+ // Does this mess up node ids of 64 bits.
+ // id : block + idx in file (16 bits = 64K)
+ // 64 = 8(type tag) + 40 + 16
+ // Better to steal bits from the 8 byte tag.
+ // 2^40 ~= 1e12 or 1 trillion
+
+ /*
+ * Layout:
+ * Count
+ * (i,j)* Pairs of shorts indexing key and value byte[]
+ * unused
+ * (varint, bytes)* Each entry is a varint (length of bytes) and the bytes
+ *
+ * The bytes for entries are added from the top, downwards.
+ *
+ */
+
+ // Layout of variable length things.
+ // (?? Currently - no) Block type
+ // Block lengh (item count) [integer (or short?)]
+ // Ptrs for (K,V) pairs - shorts, byte offsets in the block (max block is 32k) [shorts are signed:-(]
+ // Could do ints as 2 bytes unsigned
+ // Unused area
+ // The keys and values encoded as a VarInt for the length then bytes.
+ // The variable length items are added from the top as they arrive
+ // They may not in stored in the variable length area in index order
+ // because they may have arrived because of an insert in the middle of
+ // the indexes at the time.
+
+ // Overhead: num elements and the start of the variable length area (it's calculable by scanning?)
+ final public static int COUNT = 0 ;
+ // Can find the start of variable area.
+// final public static int LINK = 8 ;
+ final private static int HEADER_LENGTH = SystemTDB.SizeOfInt ;
+
+ final static boolean FILL = true ;
+ final static byte FILL_BYTE = (byte)0xAB ;
+ final static short FILL_SHORT = (short)0xABAB ;
+
+ private static final int SIZE = 100 ;
+
+ // Index of byte not-in-use for var size items area.
+ // Must initialize
+ int numElts ;
+ int startVarArea ;
+ final ByteBuffer bb ;
+
+ public final int LenIdxPtr = Short.SIZE / 8 ;
+ public final int LenIdxSlot = 2*LenIdxPtr ;
+
+ /**
+ * Create a buffer for variable sized records.
+ * @param sizeInBytes Total space for records (total includes internal admin space)
+ */
+
+ public VarRecordBuffer(int sizeInBytes)
+ {
+ bb = ByteBuffer.allocate(sizeInBytes) ;
+ numElts = 0 ;
+ setCount(numElts) ;
+ startVarArea = bb.capacity() ;
+ if ( FILL )
+ ByteBufferLib.fill(bb, FILL_BYTE) ;
+ }
+
+ private VarRecordBuffer(ByteBuffer bb)
+ {
+ this.bb = bb ;
+ numElts = getCount() ;
+ // Calc the var start.
+ int varLocMin = bb.capacity() ;
+ for ( int i = 0 ; i < numElts ; i++ )
+ {
+ int x1 = keyStartIdx(i) ;
+ int x2 = valueStartIdx(i) ;
+ varLocMin = Math.min(varLocMin, x1) ;
+ varLocMin = Math.min(varLocMin, x2) ;
+ }
+ this.startVarArea = varLocMin ;
+ }
+
+ public static VarRecordBuffer wrap(ByteBuffer bb)
+ {
+ return new VarRecordBuffer(bb) ;
+ }
+
+ public ByteBuffer getByteBuffer() { return bb ; }
+
+ public int size() { return numElts ; }
+ public int bytesInUse() { return (HEADER_LENGTH+LenIdxSlot*numElts) + (bb.limit()-startVarArea) ; }
+
+ // ---- Internal abstractions
+ /** Position of the internal index for the i'th key */
+ private int keyIdx(int i)
+ { return HEADER_LENGTH+i*LenIdxSlot ; }
+
+ /** Position of the internal index for the i'th value */
+ private int valueIdx(int i)
+ { return HEADER_LENGTH+i*LenIdxSlot+LenIdxPtr ; }
+
+ /** Position of the start of the bytes for the i'th key */
+ private int keyStartIdx(int i)
+ {
+ int idx = keyIdx(i) ;
+ short start = bb.getShort(idx) ;
+ return start ;
+ }
+
+ /** Position of the start of the bytes for the i'th value */
+ private int valueStartIdx(int i)
+ {
+ int idx = valueIdx(i) ;
+ short start = bb.getShort(idx) ;
+ return start ;
+ }
+
+ /** Items */
+ private int getCount()
+ { return bb.getInt(COUNT) ; }
+
+ private void setCount(int count)
+ { bb.putInt(COUNT, count) ; }
+
+ public Record get(int idx)
+ {
+ check(idx) ;
+
+ int k = keyStartIdx(idx) ;
+ int v = valueStartIdx(idx) ;
+
+ byte[] key = getBytes(k) ;
+ byte[] value = getBytes(v) ;
+ return new Record(key,value) ;
+ }
+
+ /** find by key - linear search - does not assume sorted */
+ public byte[] find(byte[] key)
+ {
+ for ( int i = 0 ; i < numElts ; i++ )
+ {
+ int k = keyStartIdx(i) ;
+ byte[] keyBytes = getBytes(k) ;
+ if ( Arrays.equals(keyBytes, key) )
+ {
+ int v = valueStartIdx(i) ;
+ return getBytes(v) ;
+ }
+ }
+ return null ;
+ }
+
+ public Record getKey(int idx)
+ {
+ check(idx) ;
+
+ int k = keyStartIdx(idx) ;
+ int v = valueStartIdx(idx) ;
+
+ System.out.printf("Get: %d (x%02X, x%02X)\n", idx, k, v) ;
+
+ byte[] key = getBytes(k) ;
+ byte[] value = getBytes(v) ;
+ return new Record(key,value) ;
+ }
+
+ private void check(int idx)
+ {
+ if ( idx < 0 || idx >= numElts )
+ throw new IllegalArgumentException("VarRecordBuffer.check failure") ;
+ }
+
+ public void put(Record r)
+ {
+ put(numElts, r.getKey(), r.getValue()) ;
+ }
+
+ public void put(byte[]key, byte[] value)
+ {
+ put(numElts, key, value) ;
+ }
+
+ public void put(int idx, Record r)
+ {
+ put(idx, r.getKey(), r.getValue()) ;
+ }
+
+ public void put(int idx, byte[]key, byte[] value)
+ {
+ // Allow put at top end.
+ if ( idx < 0 || idx > numElts )
+ throw new IllegalArgumentException("VarRecordBuffer.check failure") ;
+ //System.out.printf("Put: %d (%d,%d)\n", idx, key.length, value.length) ;
+
+ VarInteger keyLen = VarInteger.valueOf(key.length) ;
+ VarInteger valLen = VarInteger.valueOf(value.length) ;
+
+ // Var bytes + change in fixed area
+ int lengthNeeded = bytesNeeded(key, value)+LenIdxSlot ;
+
+ // Current gap.
+ int currentSpace = startVarArea - (HEADER_LENGTH+LenIdxSlot*numElts) ;
+
+// System.out.printf("put(%d,[%d],[%d]) :: currentSpace=%d , lengthNeeded=%d \n",
+// idx, key.length, value.length, currentSpace, lengthNeeded) ;
+
+ if ( lengthNeeded > currentSpace )
+ throw new IllegalArgumentException("Insufficient space") ;
+
+ // Put variable parts - bytes first, then length (it goes backwards).
+ insertVarByteArray(value) ;
+ int vIdxVal = insertVarByteArray(valLen.bytes()) ;
+ insertVarByteArray(key) ;
+ int vIdxKey = insertVarByteArray(keyLen.bytes()) ;
+
+ // Put shorts - shuffle up a bit first.
+ // Move up 2 places (if needed)
+
+ // Shift up 2 offset slots
+// if ( true )
+ shiftUp(bb, keyIdx(idx), LenIdxSlot, /*2*LenIdxPtr,*/ (numElts-idx)*LenIdxSlot) ;
+// else
+//// // elt i = elt i-1
+// if ( true )
+// {
+// for ( int i = numElts-1 ; i >= idx ; i-- )
+// {
+// // Better - use a byteblock shuffle.
+// // ith short is
+// // Old key and value internal indexes
+// int x1 = keyStartIdx(i) ;
+// int x2 = valueStartIdx(i) ;
+//
+// // New positions.
+// int j1 = keyIdx(i+1) ;
+// int j2 = valueIdx(i+1) ;
+//
+// System.out.println("j1 = "+j1) ;
+// bb.putShort(j1, (short)x1) ;
+// bb.putShort(j2, (short)x2) ;
+// }
+// }
+ // Insert new internal indexes.
+ bb.putShort(keyIdx(idx), (short)vIdxKey) ;
+ bb.putShort(valueIdx(idx), (short)vIdxVal) ;
+
+ numElts++ ;
+ setCount(numElts) ;
+ }
+
+ private static void shiftUp(ByteBuffer bb, int start, int places, int length)
+ {
+ //System.out.printf("ShiftUp: start=%d places=%d length=%d\n",start, places, length) ;
+ if ( length == 0 )
+ return ;
+ System.arraycopy(bb.array(), start, bb.array(), start+places, length) ;
+ if ( FILL )
+ ByteBufferLib.fill(bb, start, start+places, FILL_BYTE) ;
+ }
+
+ /** Delete at idx */
+ public void delete(int idx)
+ {
+ check(idx) ;
+ // Shuffles the space now rather than manages
+ // non-contiguos free space.
+ // Note that all internal indexes are changed
+ // from here to the upper end.
+
+ // ---- Lengths and setup
+ // Assumes bytes for keys or values are not shared.
+ int k = keyStartIdx(idx) ;
+ VarInteger kLen = VarInteger.make(bb,k) ;
+
+ int v = valueStartIdx(idx) ;
+ VarInteger vLen = VarInteger.make(bb,v) ;
+ //System.out.printf("delete: idx=%d (%d,%d)\n", idx, kLen.length()+kLen.value(), vLen.length()+vLen.value());
+
+ // So we have from k to v + length of VarInt + length - k bytes
+
+ // v-k is not length of key+varInt
+ int delta = (int)kLen.value()+kLen.length()+(int)vLen.value()+vLen.length() ;
+ int delta2 = v-k+(int)vLen.value()+vLen.length() ;
+ if ( delta != delta2 )
+ System.out.printf("*** Deltas: %d/%d\n", delta, delta2) ;
+
+ // ---- delta is the size of the byte block, startign at k, to eliminate
+ // Move startVarArea to k (exc)
+ // remove idx internal index
+ // Reset internal indexes (+delta) idx+1 to numElts
+
+ //System.out.printf("delete: idx=%d [%d bytes from %d]\n", idx, delta, k) ;
+
+ // ByteBufferLib.blockMove(bb,start,finish,length)
+ // Move (startVarArea, k[exc]) up deltas places -- it's an overlapping move.
+ for ( int j = k-1 ; j >= startVarArea ; j-- )
+ {
+ //System.out.printf("Move: %d to %d\n", j, j+tByte) ;
+ byte b = bb.get(j) ;
+ bb.put(j+delta,b) ;
+ }
+ startVarArea += delta ;
+
+ // Move internal indexes to remove idx
+ //System.out.printf("Remove index: %d\n", idx) ;
+ for ( int i = idx+1 ; i < numElts ; i++ )
+ {
+ short key = (short)keyStartIdx(i) ;
+ short val = (short)valueStartIdx(i) ;
+ //System.out.printf("Move index: [%d] <- (%d,%d)(0x%02X,0x%02X)\n", i-1, key, val, key, val) ;
+ bb.putShort(keyIdx(i-1), key) ;
+ bb.putShort(valueIdx(i-1), val) ;
+ }
+ // Clear top.
+ bb.putShort(keyIdx(numElts-1), FILL_SHORT) ;
+ bb.putShort(valueIdx(numElts-1), FILL_SHORT) ;
+ numElts -- ;
+ setCount(numElts) ;
+
+ // Adjust indexes pointing to moved bytes
+ for ( int i = 0 ; i < numElts ; i++ )
+ {
+ int k2 = keyStartIdx(i) ;
+ // Don't need look at value
+ if ( k2 < k )
+ {
+ // Fixup.
+ int v2 = valueStartIdx(i) ;
+ int k3 = k2+delta ;
+ int v3 = v2+delta ;
+
+ //System.out.printf("Fixup: %d %d->%d, %d->%d\n", i, k2,k3, v2,v3) ;
+
+ bb.putShort(keyIdx(i), (short)k3) ;
+ bb.putShort(valueIdx(i), (short)v3) ;
+ }
+ else
+ {
+ int v2 = valueStartIdx(i) ;
+ //System.out.printf("No Fixup: %d (%d,%d)\n", i, k2, v2) ;
+ }
+ }
+
+ //throw new NotImplemented("delete") ;
+ }
+
+ /** Delete top */
+ public void delete()
+ {
+ delete(numElts-1) ;
+ }
+
+ private int insertVarByteArray(byte[] bytes)
+ {
+ int x = startVarArea-bytes.length ;
+ for ( int i = 0 ; i < bytes.length ; i++ )
+ bb.put(i+x, bytes[i]) ;
+ startVarArea -= bytes.length ;
+ return startVarArea ;
+ }
+
+ private static int bytesNeeded(byte[] key, byte[] value )
+ {
+ return bytesNeeded(key)+bytesNeeded(value) ;
+ }
+
+ private static int bytesNeeded(byte[] bytes)
+ {
+ return VarInteger.lengthOf(bytes.length) + bytes.length ;
+ }
+
+ /** Perform consistence checking */
+ public void check()
+ {
+ if ( getCount() != numElts )
+ error("Buffer count does not agree with number of elements (%d,%d)", getCount(), numElts) ;
+
+ for ( int i = 0 ; i < numElts ; i++ )
+ {
+ int k = keyStartIdx(i) ;
+ int v = valueStartIdx(i) ;
+ }
+
+ // Check the unused area is filled with marker bytes.
+
+ int lo = valueStartIdx(numElts-1) ;
+ int hi = startVarArea ;
+
+ if ( lo > hi )
+ error("Overlap in internal indexes and variable obects area") ;
+
+ if ( FILL )
+ {
+ for ( int j = lo ; j < hi ; j++ )
+ if ( bb.get(j) != FILL_BYTE )
+ error("Non-fill byte (0x%02X) unused area", bb.get(j)) ;
+ }
+ // There are 2*numElts
+ int x = startVarArea ;
+ for ( int i = 0 ; i < 2*numElts ; i++ )
+ {
+ if ( x < startVarArea || x >= bb.limit() )
+ error("Variable area is corrupt") ;
+ VarInteger varInt = VarInteger.make(bb, x) ;
+ int len = varInt.length()+(int)varInt.value() ;
+ x = x+len ;
+ }
+
+ }
+
+ private void error(String string, Object... args)
+ {
+ String x = String.format(string, args) ;
+ throw new InternalErrorException(x) ;
+ }
+
+ public void dump()
+ {
+ print(bb) ;
+ StringBuilder sb = new StringBuilder() ;
+ sb.append("[size:"+getCount()) ;
+
+ for ( int i = 0 ; i < numElts ; i++ )
+ {
+ sb.append(" ") ;
+
+ sb.append("(") ;
+ sb.append(keyStartIdx(i)) ;
+ sb.append(",") ;
+ sb.append(valueStartIdx(i)) ;
+ sb.append(")") ;
+ }
+ sb.append("]") ;
+ System.out.println(sb) ;
+ }
+
+
+ @Override
+ public String toString()
+ {
+ StringBuilder sb = new StringBuilder() ;
+ sb.append("[size:"+getCount()) ;
+
+ for ( int i = 0 ; i < numElts ; i++ )
+ {
+ sb.append(" ") ;
+
+ sb.append("(") ;
+ sb.append(keyStartIdx(i)) ;
+ sb.append(",") ;
+ sb.append(valueStartIdx(i)) ;
+ sb.append(")") ;
+
+ Record r = get(i) ;
+ sb.append(r) ;
+
+ }
+ sb.append("]") ;
+ return sb.toString() ;
+ }
+
+
+ private byte[] getBytes(int byteIdx)
+ {
+ //System.out.println("Get: @"+byteIdx) ;
+ VarInteger vInt = getVInt(byteIdx) ; // Length of variable length object
+ int v = (int)vInt.value() ;
+ int bytesStart = byteIdx+vInt.length() ;
+ byte[] b = new byte[v] ;
+ // Better ByteBuffer operation?
+ for ( int i = 0 ; i < v ; i++ )
+ b[i] = bb.get(bytesStart+i) ;
+ return b ;
+ }
+
+ private VarInteger getVInt(int byteIdx)
+ {
+ return VarInteger.make(bb, byteIdx) ;
+ }
+
+ // ---- Development
+ public static void print(ByteBuffer byteBuffer)
+ {
+ print(System.out, byteBuffer) ;
+ }
+
+ public static void print(PrintStream out, ByteBuffer byteBuffer)
+ {
+ out.printf("ByteBuffer[pos=%d lim=%d cap=%d]",byteBuffer.position(), byteBuffer.limit(), byteBuffer.capacity()) ;
+ out.println() ;
+ // Print bytes.
+ int i = 0 ;
+ int maxBytes = SIZE;
+ for ( ; i < maxBytes && i < byteBuffer.limit() ; i++ )
+ {
+ if ( i%20 == 0 && i != 0 )
+ out.println() ;
+ out.printf(" 0x%02X", byteBuffer.get(i)) ;
+ }
+ if ( i < maxBytes && i < byteBuffer.limit() )
+ out.print(" ...") ;
+ // Print as 4-byte ints
+// int maxSlots = 8 ;
+// int i = 0 ;
+// for ( ; i < maxSlots && 4*i < byteBuffer.limit() ; i++ )
+// out.printf(" 0x%04X", byteBuffer.getInt(4*i)) ;
+// if ( i < maxSlots )
+// out.print(" ...") ;
+ out.println();
+ }
+
+ // There's some accessor stuff somewhere - combine.
+
+ public static void print(PrintStream out, byte[] bytes)
+ {
+ out.printf("byte[%d]:", bytes.length) ;
+ int i = 0 ;
+ int maxBytes = SIZE;
+ for ( ; i < maxBytes && i < bytes.length ; i++ )
+ {
+ if ( i%20 == 0 && i != 0 )
+ out.println() ;
+ out.printf(" 0x%02X", bytes[i]) ;
+ }
+ if ( i < maxBytes && i < bytes.length )
+ out.print(" ...") ;
+ // Print as 4-byte ints
+// int maxSlots = 8 ;
+// int i = 0 ;
+// for ( ; i < maxSlots && 4*i < byteBuffer.limit() ; i++ )
+// out.printf(" 0x%04X", byteBuffer.getInt(4*i)) ;
+// if ( i < maxSlots )
+// out.print(" ...") ;
+ out.println();
+
+ }
+
+
+
}
Modified: incubator/jena/Scratch/AFS/Dev/trunk/src/main/java/tools/Memory.java
URL: http://svn.apache.org/viewvc/incubator/jena/Scratch/AFS/Dev/trunk/src/main/java/tools/Memory.java?rev=1198733&r1=1198732&r2=1198733&view=diff
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src/main/java/tools/Memory.java (original)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src/main/java/tools/Memory.java Mon Nov 7 13:36:30 2011
@@ -1,4 +1,4 @@
-/**
+/*
* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements. See the NOTICE file
* distributed with this work for additional information
@@ -16,454 +16,454 @@
* limitations under the License.
*/
-package tools;
-
-import java.util.HashMap;
-import java.util.HashSet;
-
-public class Memory
-{
- // See also:
- // http://www.javaworld.com/javaworld/javatips/jw-javatip130.html (32 bit only)
-
-
- /* 32 bit
-Object => 8
-FakeAvlNode1 => 24
-FakeAvlNode2 => 32
-FakeTTreeNodeNull => 32 -- 2 ints, 4 slots (inc array), null array, parent
-FakeTTreeNode0 => 48 -- 2 ints, 4 slots (inc array), 0 array, parent
-FakeTTreeNode0np => 48 -- 2 ints, 4 slots (inc array), 0 array, no parent
-FakeTTreeNode1 => 48
-FakeTTreeNode1np => 48
-FakeTTreeNode1npSlice => 48
-FakeTTreeNode2 => 56
-FakeTTreeNode2np => 56
-FakeTTreeNode2npSlice => 56
-Struct1 => 16
-Struct1a => 16
-Struct2 => 16
-Struct3 => 24
-Struct4 => 24
-Struct5 => 32
- */
-
- /* 64 bit
-Object => 16
-FakeAvlNode1 => 48
-FakeAvlNode2 => 56
-FakeTTreeNodeNull => 56
-FakeTTreeNode0 => 80
-FakeTTreeNode0np => 72
-FakeTTreeNode0npSlice => 80
-FakeTTreeNode1 => 88
-FakeTTreeNode1np => 80
-FakeTTreeNode1npSlice => 88
-FakeTTreeNode2 => 96
-FakeTTreeNode2np => 88
-FakeTTreeNode2npSlice => 96
-Struct1 => 24
-Struct1a => 32
-Struct2 => 32
-Struct3 => 40
-Struct4 => 48
-Struct5 => 56
- */
-
- static class FakeTTreeNodeNull {
- int height = 99 ;
- FakeTTreeNodeNull parent = null ;
- FakeTTreeNodeNull left = null ;
- FakeTTreeNodeNull right = null ;
- int arrayActiveLen = 0 ;
- Object[] record = null ;
- }
-
- static class FakeTTreeNode0 {
- int height = 99 ;
- FakeTTreeNode0 parent = null ;
- FakeTTreeNode0 left = null ;
- FakeTTreeNode0 right = null ;
- int arrayActiveLen = 0 ;
- Object[] record = new Object[0] ;
- }
-
- static class FakeTTreeNode0np {
- int height = 99 ;
- //*** FakeTTreeNode1 parent = null ;
- FakeTTreeNode0np left = null ;
- FakeTTreeNode0np right = null ;
- int arrayActiveLen = 0 ;
- Object[] record = new Object[0] ;
- }
-
- static class FakeTTreeNode0npSlice {
- int height = 99 ;
- //*** FakeTTreeNode1 parent = null ;
- FakeTTreeNode0npSlice left = null ;
- FakeTTreeNode0npSlice right = null ;
- int arrayActiveLen = 0 ;
- int arrayStart = 0 ;
- Object[] record = new Object[0] ;
- }
-
- static class FakeTTreeNode0Slice {
- int height = 99 ;
- FakeTTreeNode0Slice parent = null ;
- FakeTTreeNode0Slice left = null ;
- FakeTTreeNode0Slice right = null ;
- int arrayActiveLen = 0 ;
- int arrayStart = 0 ;
- Object[] record = new Object[0] ;
- }
-
- static class FakeTTreeNode1 {
- int height = 99 ;
- FakeTTreeNode1 parent = null ;
- FakeTTreeNode1 left = null ;
- FakeTTreeNode1 right = null ;
- int arrayActiveLen = 0 ;
- Object[] record = new Object[1] ;
- }
-
- static class FakeTTreeNode1np {
- int height = 99 ;
- //*** FakeTTreeNode1 parent = null ;
- FakeTTreeNode1np left = null ;
- FakeTTreeNode1np right = null ;
- int arrayActiveLen = 0 ;
- Object[] record = new Object[1] ;
- }
-
- static class FakeTTreeNode1npSlice {
- int height = 99 ;
- //*** FakeTTreeNode1 parent = null ;
- FakeTTreeNode1npSlice left = null ;
- FakeTTreeNode1npSlice right = null ;
- int arrayActiveLen = 0 ;
- int arrayStart = 0 ;
- Object[] record = new Object[1] ;
- }
-
- static class FakeTTreeNode1Slice {
- int height = 99 ;
- FakeTTreeNode1Slice parent = null ;
- FakeTTreeNode1Slice left = null ;
- FakeTTreeNode1Slice right = null ;
- int arrayActiveLen = 0 ;
- int arrayStart = 0 ;
- Object[] record = new Object[1] ;
- }
-
-
- static class FakeTTreeNode2 {
- int height = 99 ;
- FakeTTreeNode2 parent = null ;
- FakeTTreeNode2 left = null ;
- FakeTTreeNode2 right = null ;
- int arrayActiveLen = 0 ;
- Object[] record = new Object[2] ;
- }
-
- static class FakeTTreeNode2np {
- int height = 99 ;
- //*** FakeTTreeNode2 parent = null ;
- FakeTTreeNode2np left = null ;
- FakeTTreeNode2np right = null ;
- int arrayActiveLen = 0 ;
- Object[] record = new Object[2] ;
- }
-
- static class FakeTTreeNode2npSlice {
- int height = 99 ;
- //*** FakeTTreeNode2 parent = null ;
- FakeTTreeNode2npSlice left = null ;
- FakeTTreeNode2npSlice right = null ;
- int arrayActiveLen = 0 ;
- int arrayStart = 0 ;
- Object[] record = new Object[2] ;
- }
-
- static class FakeTTreeNode2Slice {
- int height = 99 ;
- FakeTTreeNode2Slice parent = null ;
- FakeTTreeNode2Slice left = null ;
- FakeTTreeNode2Slice right = null ;
- int arrayActiveLen = 0 ;
- int arrayStart = 0 ;
- Object[] record = new Object[2] ;
- }
-
-
- static class FakeAvlNode1 {
- // No parent
- int height = 99 ;
- FakeAvlNode1 left = null ;
- FakeAvlNode1 right = null ;
- Object record = null ;
- }
-
-
-
- static class FakeAvlNode2 {
- int height = 99 ;
- FakeAvlNode2 parent = null ;
- FakeAvlNode2 left = null ;
- FakeAvlNode2 right = null ;
- Object record = null ;
- }
-
-
- static class Struct1
- {
- Object slot1 = null ;
- }
-
- static class Struct1a
- {
- int x = 0 ;
- Object slot1 = null ;
- }
-
- static class Struct2
- {
- Object slot1 = null ;
- Object slot2 = null ;
- }
-
- static class Struct3
- {
- Object slot1 = null ;
- Object slot2 = null ;
- Object slot3 = null ;
- }
-
- static class Struct4
- {
- Object slot1 = null ;
- Object slot2 = null ;
- Object slot3 = null ;
- Object slot4 = null ;
- }
-
- static class Struct5
- {
- Object slot1 = null ;
- Object slot2 = null ;
- Object slot3 = null ;
- Object slot4 = null ;
- Object slot5 = null ;
- }
-
- /* A Java HashMap is:--
- transient Entry[] table;
- transient int size;
- int threshold;
- final float loadFactor;
- transient volatile int modCount;
- or 4*4 byte values and an array (3+N)
- */
- /* A HashSet is:
- HashMap<E,Object> map;
- and a fixed Object value of "PRESENT" ;
- so +16 bytes (8 object, one slot, round to 8 bytes)
- */
-
- // Trove HashMaps are larger although shoudl grow less as they don't have a Map.Entry overhead.
-
- // HashMap - default size.
- static class StructMap16
- {
- Object slot1 = new HashMap<Object, Object>() ;
- }
-
- static int Size = 100*1000 ;
- public static void main(String...argv)
- {
- // Warm up.
- for ( int i = 0 ; i < 2 ; i++ )
- run(false) ;
- run(true) ;
- System.out.println() ;
- run(true) ;
- }
-
-
-
- private static void run(boolean print)
- {
- Class<?> classes[] =
- {
- HashMap.class,
- HashSet.class ,
- StructMap16.class ,
-// gnu.trove.THashMap.class ,
-// gnu.trove.THashSet.class ,
-
-// HashMap.class, HashSet.class ,
-// StructMap16.class ,
-
-// Object.class,
-// FakeAvlNode1.class, FakeAvlNode2.class,
-// FakeTTreeNodeNull.class,
-//
-// FakeTTreeNode0.class,
-// FakeTTreeNode0Slice.class,
-// FakeTTreeNode0np.class,
-// FakeTTreeNode0npSlice.class,
-//
-// FakeTTreeNode1.class,
-// FakeTTreeNode1Slice.class,
-// FakeTTreeNode1np.class,
-// FakeTTreeNode1npSlice.class,
-//
-// FakeTTreeNode2.class,
-// FakeTTreeNode2Slice.class,
-// FakeTTreeNode2np.class,
-// FakeTTreeNode2npSlice.class,
-//
-// Struct1.class, Struct1a.class, Struct2.class,Struct3.class,Struct4.class,Struct5.class
- } ;
-
- int sizes[] = new int[classes.length] ;
- String names[] = new String[classes.length] ;
- Factory[] factories = new Factory[classes.length] ;
-
- String here = classShortName(Memory.class)+"$" ;
-
- for ( int i = 0 ; i < classes.length ; i++ )
- {
- Class<?> cls = classes[i] ;
- String name = cls.getName() ;
- names[i] = classShortName(cls) ;
- factories[i] = factory(name) ;
-
- int idx = names[i].indexOf(here) ;
- if ( idx == 0 )
- names[i] = names[i].substring(here.length()) ;
- }
-
- boolean missing = false ;
- for ( int i = 0 ; i < classes.length ; i++ )
- {
- Class<?> cls = classes[i] ;
- String name = cls.getName() ;
-// if ( print )
-// System.out.println(name) ;
- int x = -1 ;
- while( x <= 0 )
- x = space(factories[i]) ;
- if ( print )
- System.out.printf("%-25s => %d\n",names[i], x) ;
- if ( x > 0 && x%4 == 0 )
- sizes[i] = x ;
-// else
-// if ( sizes[i] == 0 )
-// missing = true ;
- }
- }
-
-
- interface Factory { Object make() ; }
-
- private static Factory objFactory = new Factory() {
- @Override
- public Object make()
- {
- return new Object() ;
- } } ;
-
- private static Factory mapFactory(final int n)
- {
- return new Factory() {
- @Override
- public Object make()
- {
- return new HashMap<Object, Object>(n) ;
- }
- } ;
- }
-
- private static Factory arrayFactory(final int n)
- {
- return new Factory() {
- @Override
- public Object make()
- {
- return new Object[n] ;
- } } ;
- }
-
- private static Factory factory(String className)
- {
- try
- {
- final Class<?> cls = Class.forName(className) ;
- return new Factory() {
- @Override
- public Object make()
- {
- try
- {
- return cls.newInstance() ;
- } catch (InstantiationException ex) { throw new RuntimeException("Factory", ex) ; }
- catch (IllegalAccessException ex) { throw new RuntimeException("Factory", ex) ; }
- } } ;
- } catch (ClassNotFoundException ex)
- {
- ex.printStackTrace();
- }
- return null ;
- }
-
- static int space(Factory factory)
- {
- Object[] array = new Object[Size] ;
- //System.out.printf("Start...\n") ;
- gcMem() ;
- long bytes1 = usedMemory() ;
-
- for ( int i = 0 ; i < Size ; i++ )
- {
- array[i] = factory.make() ;
- //array[i].hashCode() ;
- //synchronized (array[i]) { array[i].hashCode() ; }
- }
-
- gcMem() ;
- long bytes2 = usedMemory() ;
- //System.out.printf("%,d => %,d bytes (%,d => %,d)\n", Size, bytes2-bytes1, bytes1, bytes2) ;
-
- // Silly thing to stop the compiler guessing we don't use the space again.
- for ( int i = 0 ; i < Size ; i++ )
- if ( array[i].hashCode() < 0 )
- System.out.println(array[i]) ;
-
- // Add 100 for some GC rounding
- return (int)(bytes2-bytes1+100)/Size ;
-
- //System.exit(0) ;
- }
-
- static private void gcMem()
- {
-
- Runtime.getRuntime().gc() ;
- }
-
- static Runtime runtime = Runtime.getRuntime() ;
- private static long usedMemory ()
- {
- return runtime.totalMemory () - runtime.freeMemory ();
- }
-
-
- static public String classShortName(Class<?> cls)
- {
- String tmp = cls.getName() ;
- int i = tmp.lastIndexOf('.') ;
- tmp = tmp.substring(i+1) ;
- return tmp ;
- }
-
+package tools;
+
+import java.util.HashMap;
+import java.util.HashSet;
+
+public class Memory
+{
+ // See also:
+ // http://www.javaworld.com/javaworld/javatips/jw-javatip130.html (32 bit only)
+
+
+ /* 32 bit
+Object => 8
+FakeAvlNode1 => 24
+FakeAvlNode2 => 32
+FakeTTreeNodeNull => 32 -- 2 ints, 4 slots (inc array), null array, parent
+FakeTTreeNode0 => 48 -- 2 ints, 4 slots (inc array), 0 array, parent
+FakeTTreeNode0np => 48 -- 2 ints, 4 slots (inc array), 0 array, no parent
+FakeTTreeNode1 => 48
+FakeTTreeNode1np => 48
+FakeTTreeNode1npSlice => 48
+FakeTTreeNode2 => 56
+FakeTTreeNode2np => 56
+FakeTTreeNode2npSlice => 56
+Struct1 => 16
+Struct1a => 16
+Struct2 => 16
+Struct3 => 24
+Struct4 => 24
+Struct5 => 32
+ */
+
+ /* 64 bit
+Object => 16
+FakeAvlNode1 => 48
+FakeAvlNode2 => 56
+FakeTTreeNodeNull => 56
+FakeTTreeNode0 => 80
+FakeTTreeNode0np => 72
+FakeTTreeNode0npSlice => 80
+FakeTTreeNode1 => 88
+FakeTTreeNode1np => 80
+FakeTTreeNode1npSlice => 88
+FakeTTreeNode2 => 96
+FakeTTreeNode2np => 88
+FakeTTreeNode2npSlice => 96
+Struct1 => 24
+Struct1a => 32
+Struct2 => 32
+Struct3 => 40
+Struct4 => 48
+Struct5 => 56
+ */
+
+ static class FakeTTreeNodeNull {
+ int height = 99 ;
+ FakeTTreeNodeNull parent = null ;
+ FakeTTreeNodeNull left = null ;
+ FakeTTreeNodeNull right = null ;
+ int arrayActiveLen = 0 ;
+ Object[] record = null ;
+ }
+
+ static class FakeTTreeNode0 {
+ int height = 99 ;
+ FakeTTreeNode0 parent = null ;
+ FakeTTreeNode0 left = null ;
+ FakeTTreeNode0 right = null ;
+ int arrayActiveLen = 0 ;
+ Object[] record = new Object[0] ;
+ }
+
+ static class FakeTTreeNode0np {
+ int height = 99 ;
+ //*** FakeTTreeNode1 parent = null ;
+ FakeTTreeNode0np left = null ;
+ FakeTTreeNode0np right = null ;
+ int arrayActiveLen = 0 ;
+ Object[] record = new Object[0] ;
+ }
+
+ static class FakeTTreeNode0npSlice {
+ int height = 99 ;
+ //*** FakeTTreeNode1 parent = null ;
+ FakeTTreeNode0npSlice left = null ;
+ FakeTTreeNode0npSlice right = null ;
+ int arrayActiveLen = 0 ;
+ int arrayStart = 0 ;
+ Object[] record = new Object[0] ;
+ }
+
+ static class FakeTTreeNode0Slice {
+ int height = 99 ;
+ FakeTTreeNode0Slice parent = null ;
+ FakeTTreeNode0Slice left = null ;
+ FakeTTreeNode0Slice right = null ;
+ int arrayActiveLen = 0 ;
+ int arrayStart = 0 ;
+ Object[] record = new Object[0] ;
+ }
+
+ static class FakeTTreeNode1 {
+ int height = 99 ;
+ FakeTTreeNode1 parent = null ;
+ FakeTTreeNode1 left = null ;
+ FakeTTreeNode1 right = null ;
+ int arrayActiveLen = 0 ;
+ Object[] record = new Object[1] ;
+ }
+
+ static class FakeTTreeNode1np {
+ int height = 99 ;
+ //*** FakeTTreeNode1 parent = null ;
+ FakeTTreeNode1np left = null ;
+ FakeTTreeNode1np right = null ;
+ int arrayActiveLen = 0 ;
+ Object[] record = new Object[1] ;
+ }
+
+ static class FakeTTreeNode1npSlice {
+ int height = 99 ;
+ //*** FakeTTreeNode1 parent = null ;
+ FakeTTreeNode1npSlice left = null ;
+ FakeTTreeNode1npSlice right = null ;
+ int arrayActiveLen = 0 ;
+ int arrayStart = 0 ;
+ Object[] record = new Object[1] ;
+ }
+
+ static class FakeTTreeNode1Slice {
+ int height = 99 ;
+ FakeTTreeNode1Slice parent = null ;
+ FakeTTreeNode1Slice left = null ;
+ FakeTTreeNode1Slice right = null ;
+ int arrayActiveLen = 0 ;
+ int arrayStart = 0 ;
+ Object[] record = new Object[1] ;
+ }
+
+
+ static class FakeTTreeNode2 {
+ int height = 99 ;
+ FakeTTreeNode2 parent = null ;
+ FakeTTreeNode2 left = null ;
+ FakeTTreeNode2 right = null ;
+ int arrayActiveLen = 0 ;
+ Object[] record = new Object[2] ;
+ }
+
+ static class FakeTTreeNode2np {
+ int height = 99 ;
+ //*** FakeTTreeNode2 parent = null ;
+ FakeTTreeNode2np left = null ;
+ FakeTTreeNode2np right = null ;
+ int arrayActiveLen = 0 ;
+ Object[] record = new Object[2] ;
+ }
+
+ static class FakeTTreeNode2npSlice {
+ int height = 99 ;
+ //*** FakeTTreeNode2 parent = null ;
+ FakeTTreeNode2npSlice left = null ;
+ FakeTTreeNode2npSlice right = null ;
+ int arrayActiveLen = 0 ;
+ int arrayStart = 0 ;
+ Object[] record = new Object[2] ;
+ }
+
+ static class FakeTTreeNode2Slice {
+ int height = 99 ;
+ FakeTTreeNode2Slice parent = null ;
+ FakeTTreeNode2Slice left = null ;
+ FakeTTreeNode2Slice right = null ;
+ int arrayActiveLen = 0 ;
+ int arrayStart = 0 ;
+ Object[] record = new Object[2] ;
+ }
+
+
+ static class FakeAvlNode1 {
+ // No parent
+ int height = 99 ;
+ FakeAvlNode1 left = null ;
+ FakeAvlNode1 right = null ;
+ Object record = null ;
+ }
+
+
+
+ static class FakeAvlNode2 {
+ int height = 99 ;
+ FakeAvlNode2 parent = null ;
+ FakeAvlNode2 left = null ;
+ FakeAvlNode2 right = null ;
+ Object record = null ;
+ }
+
+
+ static class Struct1
+ {
+ Object slot1 = null ;
+ }
+
+ static class Struct1a
+ {
+ int x = 0 ;
+ Object slot1 = null ;
+ }
+
+ static class Struct2
+ {
+ Object slot1 = null ;
+ Object slot2 = null ;
+ }
+
+ static class Struct3
+ {
+ Object slot1 = null ;
+ Object slot2 = null ;
+ Object slot3 = null ;
+ }
+
+ static class Struct4
+ {
+ Object slot1 = null ;
+ Object slot2 = null ;
+ Object slot3 = null ;
+ Object slot4 = null ;
+ }
+
+ static class Struct5
+ {
+ Object slot1 = null ;
+ Object slot2 = null ;
+ Object slot3 = null ;
+ Object slot4 = null ;
+ Object slot5 = null ;
+ }
+
+ /* A Java HashMap is:--
+ transient Entry[] table;
+ transient int size;
+ int threshold;
+ final float loadFactor;
+ transient volatile int modCount;
+ or 4*4 byte values and an array (3+N)
+ */
+ /* A HashSet is:
+ HashMap<E,Object> map;
+ and a fixed Object value of "PRESENT" ;
+ so +16 bytes (8 object, one slot, round to 8 bytes)
+ */
+
+ // Trove HashMaps are larger although shoudl grow less as they don't have a Map.Entry overhead.
+
+ // HashMap - default size.
+ static class StructMap16
+ {
+ Object slot1 = new HashMap<Object, Object>() ;
+ }
+
+ static int Size = 100*1000 ;
+ public static void main(String...argv)
+ {
+ // Warm up.
+ for ( int i = 0 ; i < 2 ; i++ )
+ run(false) ;
+ run(true) ;
+ System.out.println() ;
+ run(true) ;
+ }
+
+
+
+ private static void run(boolean print)
+ {
+ Class<?> classes[] =
+ {
+ HashMap.class,
+ HashSet.class ,
+ StructMap16.class ,
+// gnu.trove.THashMap.class ,
+// gnu.trove.THashSet.class ,
+
+// HashMap.class, HashSet.class ,
+// StructMap16.class ,
+
+// Object.class,
+// FakeAvlNode1.class, FakeAvlNode2.class,
+// FakeTTreeNodeNull.class,
+//
+// FakeTTreeNode0.class,
+// FakeTTreeNode0Slice.class,
+// FakeTTreeNode0np.class,
+// FakeTTreeNode0npSlice.class,
+//
+// FakeTTreeNode1.class,
+// FakeTTreeNode1Slice.class,
+// FakeTTreeNode1np.class,
+// FakeTTreeNode1npSlice.class,
+//
+// FakeTTreeNode2.class,
+// FakeTTreeNode2Slice.class,
+// FakeTTreeNode2np.class,
+// FakeTTreeNode2npSlice.class,
+//
+// Struct1.class, Struct1a.class, Struct2.class,Struct3.class,Struct4.class,Struct5.class
+ } ;
+
+ int sizes[] = new int[classes.length] ;
+ String names[] = new String[classes.length] ;
+ Factory[] factories = new Factory[classes.length] ;
+
+ String here = classShortName(Memory.class)+"$" ;
+
+ for ( int i = 0 ; i < classes.length ; i++ )
+ {
+ Class<?> cls = classes[i] ;
+ String name = cls.getName() ;
+ names[i] = classShortName(cls) ;
+ factories[i] = factory(name) ;
+
+ int idx = names[i].indexOf(here) ;
+ if ( idx == 0 )
+ names[i] = names[i].substring(here.length()) ;
+ }
+
+ boolean missing = false ;
+ for ( int i = 0 ; i < classes.length ; i++ )
+ {
+ Class<?> cls = classes[i] ;
+ String name = cls.getName() ;
+// if ( print )
+// System.out.println(name) ;
+ int x = -1 ;
+ while( x <= 0 )
+ x = space(factories[i]) ;
+ if ( print )
+ System.out.printf("%-25s => %d\n",names[i], x) ;
+ if ( x > 0 && x%4 == 0 )
+ sizes[i] = x ;
+// else
+// if ( sizes[i] == 0 )
+// missing = true ;
+ }
+ }
+
+
+ interface Factory { Object make() ; }
+
+ private static Factory objFactory = new Factory() {
+ @Override
+ public Object make()
+ {
+ return new Object() ;
+ } } ;
+
+ private static Factory mapFactory(final int n)
+ {
+ return new Factory() {
+ @Override
+ public Object make()
+ {
+ return new HashMap<Object, Object>(n) ;
+ }
+ } ;
+ }
+
+ private static Factory arrayFactory(final int n)
+ {
+ return new Factory() {
+ @Override
+ public Object make()
+ {
+ return new Object[n] ;
+ } } ;
+ }
+
+ private static Factory factory(String className)
+ {
+ try
+ {
+ final Class<?> cls = Class.forName(className) ;
+ return new Factory() {
+ @Override
+ public Object make()
+ {
+ try
+ {
+ return cls.newInstance() ;
+ } catch (InstantiationException ex) { throw new RuntimeException("Factory", ex) ; }
+ catch (IllegalAccessException ex) { throw new RuntimeException("Factory", ex) ; }
+ } } ;
+ } catch (ClassNotFoundException ex)
+ {
+ ex.printStackTrace();
+ }
+ return null ;
+ }
+
+ static int space(Factory factory)
+ {
+ Object[] array = new Object[Size] ;
+ //System.out.printf("Start...\n") ;
+ gcMem() ;
+ long bytes1 = usedMemory() ;
+
+ for ( int i = 0 ; i < Size ; i++ )
+ {
+ array[i] = factory.make() ;
+ //array[i].hashCode() ;
+ //synchronized (array[i]) { array[i].hashCode() ; }
+ }
+
+ gcMem() ;
+ long bytes2 = usedMemory() ;
+ //System.out.printf("%,d => %,d bytes (%,d => %,d)\n", Size, bytes2-bytes1, bytes1, bytes2) ;
+
+ // Silly thing to stop the compiler guessing we don't use the space again.
+ for ( int i = 0 ; i < Size ; i++ )
+ if ( array[i].hashCode() < 0 )
+ System.out.println(array[i]) ;
+
+ // Add 100 for some GC rounding
+ return (int)(bytes2-bytes1+100)/Size ;
+
+ //System.exit(0) ;
+ }
+
+ static private void gcMem()
+ {
+
+ Runtime.getRuntime().gc() ;
+ }
+
+ static Runtime runtime = Runtime.getRuntime() ;
+ private static long usedMemory ()
+ {
+ return runtime.totalMemory () - runtime.freeMemory ();
+ }
+
+
+ static public String classShortName(Class<?> cls)
+ {
+ String tmp = cls.getName() ;
+ int i = tmp.lastIndexOf('.') ;
+ tmp = tmp.substring(i+1) ;
+ return tmp ;
+ }
+
}