Mercurial > hg > blitz_condensed
comparison 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 |
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 } |