Mercurial > hg > blitz_condensed
diff src/org/dancres/struct/BitIndex.java @ 0:3dc0c5604566
Initial checkin of blitz 2.0 fcs - no installer yet.
author | Dan Creswell <dan.creswell@gmail.com> |
---|---|
date | Sat, 21 Mar 2009 11:00:06 +0000 |
parents | |
children |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/org/dancres/struct/BitIndex.java Sat Mar 21 11:00:06 2009 +0000 @@ -0,0 +1,322 @@ +package org.dancres.struct; + +import java.util.ArrayList; + +import java.util.LinkedList; + +import java.util.Random; + +import java.util.HashMap; + +/** + <p>An MT-safe BitIndex. Because BitIndex's can never change size and all + updates are lock protected, there is no need to clone an index via copy + unless one requires a stable copy. i.e. If one can tolerate an out-of-date + access that may render misses, the cost of a copy can be avoided. Iteration + incurs locking therefore but only to access a snapshot of data bits.</p> + + <p>Be sure to run this with plenty of memory to avoid GC skewing timings + during tests.</p> + */ +public class BitIndex { + private Object[] theLocks; + private long[] theIndex; + private int theSize; + + private Object theTotalLock = new Object(); + private int theTotalSet; + + public BitIndex(int aSize) { + theSize = aSize; + + int mySize = aSize / 64; + + if ((aSize % 64) != 0) + ++mySize; + + theIndex = new long[mySize]; + theLocks = new Object[mySize]; + for (int i = 0; i < theLocks.length; i++) { + theLocks[i] = new Object(); + } + } + + public int getSize() { + return theSize; + } + + public void set(int aPos) { + if (aPos >= theSize) + throw new IllegalArgumentException("Position larger than size"); + + int myIndex = aPos / 64; + int myOffset = aPos % 64; + long myNewBit = 1L << myOffset; + + synchronized(theLocks[myIndex]) { + theIndex[myIndex] |= myNewBit; + } + + synchronized(theTotalLock) { + ++theTotalSet; + } + } + + public void clear(int aPos) { + if (aPos >= theSize) + throw new IllegalArgumentException("Position larger than size"); + + int myIndex = aPos / 64; + int myOffset = aPos % 64; + long myNewBit = 1L << myOffset; + myNewBit ^= 0xffffffffffffffffL; + + synchronized(theLocks[myIndex]) { + theIndex[myIndex] &= myNewBit; + } + + synchronized(theTotalLock) { + --theTotalSet; + } + } + + public int count() { + synchronized(theTotalLock) { + return theTotalSet; + } + } + + public BitVisitor getVisitor(boolean forZero) { + return new BitVisitorImpl(theIndex, theLocks, forZero); + } + + public void iterate(BitListener aListener) { + int myBase = 0; + + for (int i = 0; i < theIndex.length; i++) { + long myMask = 1L; + long myLong; + + synchronized(theLocks[i]) { + myLong = theIndex[i]; + } + + if (myLong != 0) { + for (int j = 0; j < 64; j++) { + if ((myLong & myMask) != 0) + if (aListener.active(myBase + j)) + return; + + myMask = myMask << 1; + } + } + + myBase += 64; + } + } + + public void iterateZero(BitListener aListener) { + int myBase = 0; + + for (int i = 0; i < theIndex.length; i++) { + long myMask = 1L; + long myLong; + + synchronized(theLocks[i]) { + myLong = theIndex[i]; + } + + for (int j = 0; j < 64; j++) { + if ((myLong & myMask) == 0) + if (aListener.inactive(myBase + j)) + return; + + myMask = myMask << 1; + } + + myBase += 64; + } + } + + public BitIndex copy() { + BitIndex myIndex = new BitIndex(theSize); + System.arraycopy(theIndex, 0, myIndex.theIndex, 0, theIndex.length); + + return myIndex; + } + + public long[] rawCopy() { + long[] myRaw = new long[theIndex.length]; + + System.arraycopy(theIndex, 0, myRaw, 0, theIndex.length); + + return myRaw; + } + + public static void main(String args[]) { + BitIndex myIndex = new BitIndex(512); + + myIndex.set(1); + + System.out.println(Long.toBinaryString(myIndex.theIndex[0])); + + myIndex.set(35); + + System.out.println(Long.toBinaryString(myIndex.theIndex[0])); + + myIndex.set(67); + + System.out.println(Long.toBinaryString(myIndex.theIndex[1])); + + myIndex.clear(35); + + System.out.println(Long.toBinaryString(myIndex.theIndex[0])); + + myIndex.set(35); + + myIndex.iterate(new TestListener()); + + myIndex.set(63); + + System.out.println(Long.toBinaryString(myIndex.theIndex[0])); + + BitVisitor myVisitor = myIndex.getVisitor(false); + + int mySlot; + + while ((mySlot = myVisitor.getNext()) != -1) { + System.out.print("Bit set at: " + mySlot + " "); + } + System.out.println(); + + myVisitor = myIndex.getVisitor(true); + + while ((mySlot = myVisitor.getNext()) != -1) { + System.out.print("Bit clear at: " + mySlot + " "); + } + System.out.println(); + + /* + Here we test out how fast we might be able to do add/remove's + from a cache indexer based on a HashMap which is + secondary indexed via a HashMap of hashcodes containing buckets + implemented as ArrayLists vs a combination of array, + indexed by HashMap to get offsets and then secondary indexed via a + HashMap of hashcodes containing BitMap indexes + */ + ArrayList myList = new ArrayList(512); + + for (int i = 0; i < 512; i++) { + myList.add(new Integer(i)); + } + + HashMap myMap = new HashMap(); + + for (int i = 0; i < 512; i++) { + myIndex.set(i); + myMap.put(new Integer(i), new Integer(i)); + } + + Random myRandom = new Random(); + + long myStart = System.currentTimeMillis(); + + for (int i = 0; i < 100000; i++) { + Integer myId = new Integer(myRandom.nextInt(512)); + + myMap.remove(myId); + myList.remove(myId); + myList.add(myId); + myMap.put(myId, myId); + } + + long myEnd = System.currentTimeMillis(); + + System.out.println("100000 remove/adds on ArrayList: " + + (myEnd - myStart)); + + myIndex = new BitIndex(512); + + myStart = System.currentTimeMillis(); + + for (int i = 0; i < 100000; i++) { + int myId = myRandom.nextInt(512); + + Integer myPos = (Integer) myMap.remove(new Integer(myId)); + myIndex.clear(myPos.intValue()); + + myMap.put(myPos, myPos); + myIndex.set(myPos.intValue()); + } + + myEnd = System.currentTimeMillis(); + + System.out.println("100000 remove/adds on Bitmap Indexed Map: " + + (myEnd - myStart)); + + + /* + Now we test how a search might behave - first case is based on + copying the entire contents of a secondary index containing + primary keys whilst the second case consists of BitMap indexes + which index into one array of primary keys. Thus in the second + case we must at least copy the bitmap index and probably ought to + copy the keys (note we could copy the keys in chunks same as we + lock and copy chunks of the secondary indexes in the first case). + + In fact we don't need to copy the base array in the BitIndex case + as an approximation is acceptable. If the entry that would be a + partial hit has been replaced, we'll filter it out later. However, + in high workload's this might give us a lot of pointless searches. + */ + myStart = System.currentTimeMillis(); + + for (int i = 0; i < 100000; i++) { + Object[] myArray = new Object[512]; + myArray = myList.toArray(myArray); + } + + myEnd = System.currentTimeMillis(); + + System.out.println("100000 copies of array: " + (myEnd - myStart)); + + myStart = System.currentTimeMillis(); + + for (int i = 0 ; i < 100000; i++) { + BitIndex myBits = myIndex.copy(); + } + + myEnd = System.currentTimeMillis(); + + System.out.println("100000 copies of bitset: " + + (myEnd - myStart)); + + myStart = System.currentTimeMillis(); + + for (int i = 0 ; i < 100000; i++) { + Object[] myArray = new Object[512]; + myArray = myList.toArray(myArray); + myIndex.copy(); + } + + myEnd = System.currentTimeMillis(); + + System.out.println("100000 copies of array and bitset: " + + (myEnd - myStart)); + + + myStart = System.currentTimeMillis(); + + } + + private static class TestListener implements BitListener { + public boolean active(int aPos) { + System.out.println("Slot: " + aPos + " is active"); + return false; + } + + public boolean inactive(int aPos) { + throw new org.dancres.util.NotImplementedException(); + } + } +} \ No newline at end of file