Mercurial > hg > blitz_condensed

comparison src/org/dancres/struct/BitIndex.java @ 0:3dc0c5604566

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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
comparison
equal deleted inserted replaced
-1:000000000000 0:3dc0c5604566
1 package org.dancres.struct;
2
3 import java.util.ArrayList;
4
5 import java.util.LinkedList;
6
7 import java.util.Random;
8
9 import java.util.HashMap;
10
11 /**
12 <p>An MT-safe BitIndex. Because BitIndex's can never change size and all
13 updates are lock protected, there is no need to clone an index via copy
14 unless one requires a stable copy. i.e. If one can tolerate an out-of-date
15 access that may render misses, the cost of a copy can be avoided. Iteration
16 incurs locking therefore but only to access a snapshot of data bits.</p>
17
18 <p>Be sure to run this with plenty of memory to avoid GC skewing timings
19 during tests.</p>
20 */
21 public class BitIndex {
22 private Object[] theLocks;
23 private long[] theIndex;
24 private int theSize;
25
26 private Object theTotalLock = new Object();
27 private int theTotalSet;
28
29 public BitIndex(int aSize) {
30 theSize = aSize;
31
32 int mySize = aSize / 64;
33
34 if ((aSize % 64) != 0)
35 ++mySize;
36
37 theIndex = new long[mySize];
38 theLocks = new Object[mySize];
39 for (int i = 0; i < theLocks.length; i++) {
40 theLocks[i] = new Object();
41 }
42 }
43
44 public int getSize() {
45 return theSize;
46 }
47
48 public void set(int aPos) {
49 if (aPos >= theSize)
50 throw new IllegalArgumentException("Position larger than size");
51
52 int myIndex = aPos / 64;
53 int myOffset = aPos % 64;
54 long myNewBit = 1L << myOffset;
55
56 synchronized(theLocks[myIndex]) {
57 theIndex[myIndex] |= myNewBit;
58 }
59
60 synchronized(theTotalLock) {
61 ++theTotalSet;
62 }
63 }
64
65 public void clear(int aPos) {
66 if (aPos >= theSize)
67 throw new IllegalArgumentException("Position larger than size");
68
69 int myIndex = aPos / 64;
70 int myOffset = aPos % 64;
71 long myNewBit = 1L << myOffset;
72 myNewBit ^= 0xffffffffffffffffL;
73
74 synchronized(theLocks[myIndex]) {
75 theIndex[myIndex] &= myNewBit;
76 }
77
78 synchronized(theTotalLock) {
79 --theTotalSet;
80 }
81 }
82
83 public int count() {
84 synchronized(theTotalLock) {
85 return theTotalSet;
86 }
87 }
88
89 public BitVisitor getVisitor(boolean forZero) {
90 return new BitVisitorImpl(theIndex, theLocks, forZero);
91 }
92
93 public void iterate(BitListener aListener) {
94 int myBase = 0;
95
96 for (int i = 0; i < theIndex.length; i++) {
97 long myMask = 1L;
98 long myLong;
99
100 synchronized(theLocks[i]) {
101 myLong = theIndex[i];
102 }
103
104 if (myLong != 0) {
105 for (int j = 0; j < 64; j++) {
106 if ((myLong & myMask) != 0)
107 if (aListener.active(myBase + j))
108 return;
109
110 myMask = myMask << 1;
111 }
112 }
113
114 myBase += 64;
115 }
116 }
117
118 public void iterateZero(BitListener aListener) {
119 int myBase = 0;
120
121 for (int i = 0; i < theIndex.length; i++) {
122 long myMask = 1L;
123 long myLong;
124
125 synchronized(theLocks[i]) {
126 myLong = theIndex[i];
127 }
128
129 for (int j = 0; j < 64; j++) {
130 if ((myLong & myMask) == 0)
131 if (aListener.inactive(myBase + j))
132 return;
133
134 myMask = myMask << 1;
135 }
136
137 myBase += 64;
138 }
139 }
140
141 public BitIndex copy() {
142 BitIndex myIndex = new BitIndex(theSize);
143 System.arraycopy(theIndex, 0, myIndex.theIndex, 0, theIndex.length);
144
145 return myIndex;
146 }
147
148 public long[] rawCopy() {
149 long[] myRaw = new long[theIndex.length];
150
151 System.arraycopy(theIndex, 0, myRaw, 0, theIndex.length);
152
153 return myRaw;
154 }
155
156 public static void main(String args[]) {
157 BitIndex myIndex = new BitIndex(512);
158
159 myIndex.set(1);
160
161 System.out.println(Long.toBinaryString(myIndex.theIndex[0]));
162
163 myIndex.set(35);
164
165 System.out.println(Long.toBinaryString(myIndex.theIndex[0]));
166
167 myIndex.set(67);
168
169 System.out.println(Long.toBinaryString(myIndex.theIndex[1]));
170
171 myIndex.clear(35);
172
173 System.out.println(Long.toBinaryString(myIndex.theIndex[0]));
174
175 myIndex.set(35);
176
177 myIndex.iterate(new TestListener());
178
179 myIndex.set(63);
180
181 System.out.println(Long.toBinaryString(myIndex.theIndex[0]));
182
183 BitVisitor myVisitor = myIndex.getVisitor(false);
184
185 int mySlot;
186
187 while ((mySlot = myVisitor.getNext()) != -1) {
188 System.out.print("Bit set at: " + mySlot + " ");
189 }
190 System.out.println();
191
192 myVisitor = myIndex.getVisitor(true);
193
194 while ((mySlot = myVisitor.getNext()) != -1) {
195 System.out.print("Bit clear at: " + mySlot + " ");
196 }
197 System.out.println();
198
199 /*
200 Here we test out how fast we might be able to do add/remove's
201 from a cache indexer based on a HashMap which is
202 secondary indexed via a HashMap of hashcodes containing buckets
203 implemented as ArrayLists vs a combination of array,
204 indexed by HashMap to get offsets and then secondary indexed via a
205 HashMap of hashcodes containing BitMap indexes
206 */
207 ArrayList myList = new ArrayList(512);
208
209 for (int i = 0; i < 512; i++) {
210 myList.add(new Integer(i));
211 }
212
213 HashMap myMap = new HashMap();
214
215 for (int i = 0; i < 512; i++) {
216 myIndex.set(i);
217 myMap.put(new Integer(i), new Integer(i));
218 }
219
220 Random myRandom = new Random();
221
222 long myStart = System.currentTimeMillis();
223
224 for (int i = 0; i < 100000; i++) {
225 Integer myId = new Integer(myRandom.nextInt(512));
226
227 myMap.remove(myId);
228 myList.remove(myId);
229 myList.add(myId);
230 myMap.put(myId, myId);
231 }
232
233 long myEnd = System.currentTimeMillis();
234
235 System.out.println("100000 remove/adds on ArrayList: " +
236 (myEnd - myStart));
237
238 myIndex = new BitIndex(512);
239
240 myStart = System.currentTimeMillis();
241
242 for (int i = 0; i < 100000; i++) {
243 int myId = myRandom.nextInt(512);
244
245 Integer myPos = (Integer) myMap.remove(new Integer(myId));
246 myIndex.clear(myPos.intValue());
247
248 myMap.put(myPos, myPos);
249 myIndex.set(myPos.intValue());
250 }
251
252 myEnd = System.currentTimeMillis();
253
254 System.out.println("100000 remove/adds on Bitmap Indexed Map: " +
255 (myEnd - myStart));
256
257
258 /*
259 Now we test how a search might behave - first case is based on
260 copying the entire contents of a secondary index containing
261 primary keys whilst the second case consists of BitMap indexes
262 which index into one array of primary keys. Thus in the second
263 case we must at least copy the bitmap index and probably ought to
264 copy the keys (note we could copy the keys in chunks same as we
265 lock and copy chunks of the secondary indexes in the first case).
266
267 In fact we don't need to copy the base array in the BitIndex case
268 as an approximation is acceptable. If the entry that would be a
269 partial hit has been replaced, we'll filter it out later. However,
270 in high workload's this might give us a lot of pointless searches.
271 */
272 myStart = System.currentTimeMillis();
273
274 for (int i = 0; i < 100000; i++) {
275 Object[] myArray = new Object[512];
276 myArray = myList.toArray(myArray);
277 }
278
279 myEnd = System.currentTimeMillis();
280
281 System.out.println("100000 copies of array: " + (myEnd - myStart));
282
283 myStart = System.currentTimeMillis();
284
285 for (int i = 0 ; i < 100000; i++) {
286 BitIndex myBits = myIndex.copy();
287 }
288
289 myEnd = System.currentTimeMillis();
290
291 System.out.println("100000 copies of bitset: " +
292 (myEnd - myStart));
293
294 myStart = System.currentTimeMillis();
295
296 for (int i = 0 ; i < 100000; i++) {
297 Object[] myArray = new Object[512];
298 myArray = myList.toArray(myArray);
299 myIndex.copy();
300 }
301
302 myEnd = System.currentTimeMillis();
303
304 System.out.println("100000 copies of array and bitset: " +
305 (myEnd - myStart));
306
307
308 myStart = System.currentTimeMillis();
309
310 }
311
312 private static class TestListener implements BitListener {
313 public boolean active(int aPos) {
314 System.out.println("Slot: " + aPos + " is active");
315 return false;
316 }
317
318 public boolean inactive(int aPos) {
319 throw new org.dancres.util.NotImplementedException();
320 }
321 }
322 }