Debian Codegraph @

hppc-examples/src/test/java/com/carrotsearch/hppc/examples/HppcExample_006_HashAndScatterMaps.java

raw
1 package com.carrotsearch.hppc.examples;
2
3 import java.util.Locale;
4 import java.util.concurrent.TimeUnit;
5
6 import org.junit.Test;
7
8 import com.carrotsearch.hppc.HashOrderMixing;
9 import com.carrotsearch.hppc.IntHashSet;
10 import com.carrotsearch.hppc.cursors.IntCursor;
11
12 /**
13 * Explains the difference between scatter and hash containers.
14 */
15 @SuppressWarnings("deprecation")
16 public class HppcExample_006_HashAndScatterMaps {
17 @Test
18 public void scatterVsHashDifference() throws Exception {
19 int key;
20
21 /*
22 * To understand the difference between scatter and hash containers one must first
23 * understand how open addressing with linear conflict resolution works.
24 *
25 * Any associative container has a "key buffer" which is a linear array. When a new
26 * (or existing) key arrives, its "slot" is computed in this linear array (the slot
27 * is an index to the key buffer). The calculation of the slot for a key
28 * can be done in a number of ways, typically it is the hash code of the key modulo
29 * the buffer length.
30 *
31 * In HPPC we can even retrieve the actual "slot" of an existing key. Here is a snippet
32 * that forces the slot (hash) value of a key to become itself, just for demonstration.
33 */
34 IntHashSet set = new IntHashSet() {
35 @Override
36 protected int hashKey(int key) {
37 return key;
38 }
39 };
40
41 key = 0x0002;
42 set.add(key);
43 println("Key 0x%04x is at slot: %d", key, set.indexOf(key));
44
45 /*
46 * Prints:
47 *
48 * Key 0x0002 is at slot: 2
49 *
50 * The problem arises when two keys have the same slot value, the we have to resolve
51 * a conflict; this is typically done by looking for the next available slot (to the right),
52 * again modulo key buffer size. For example this key will conflict with the previous one
53 * because they have the same hash value (modulo buffer size), so it'll be placed at slot
54 * '3', even though it should have been at '2'.
55 */
56 key = 0x1002;
57 set.add(key);
58 println("Key 0x%04x is at slot: %d", key, set.indexOf(key));
59
60 /*
61 * Prints:
62 *
63 * Key 0x1002 is at slot: 3
64 *
65 * This is called open addressing with linear conflict resolution:
66 *
67 * http://en.wikipedia.org/wiki/Open_addressing
68 * http://en.wikipedia.org/wiki/Linear_probing
69 *
70 * This method of building associative containers has some very nice properties: we can
71 * use CPU caches very effectively (since conflicts scan neighboring elements), we can implement
72 * element removals efficiently (it's basically a shift of other conflicting elements).
73 *
74 * But there is also a problem. What happens if we keep adding conflicting elements over
75 * and over? They will create a long chain of "occuppied" slots and every new insertion
76 * (or lookup) will have an increasingly prohibitive cost until a rehash occurs.
77 *
78 * With our toy example this is quite easy to demonstrate.
79 */
80 for (int i = 2; i < 10; i++) {
81 key = (i << 12) + 2;
82 set.add(key);
83 println("Key 0x%04x is at slot: %d", key, set.indexOf(key));
84 }
85
86 /*
87 * Prints:
88 *
89 * Key 0x2002 is at slot: 4
90 * Key 0x3002 is at slot: 5
91 * Key 0x4002 is at slot: 6
92 * Key 0x5002 is at slot: 7
93 * Key 0x6002 is at slot: 8
94 * Key 0x7002 is at slot: 9
95 * Key 0x8002 is at slot: 10
96 * Key 0x9002 is at slot: 11
97 *
98 * We now have a hash map that isn't like a hash map at all -- all keys, instead of being
99 * distributed across the buffer space, are adjacent and grouped. Here is the visualization
100 * of the buffer (a dot is an empty buffer region, numbers indicate progressively
101 * more occupied regions). Let's also expand the buffer a bit to make the point clearer.
102 */
103 set.ensureCapacity(1000);
104 println("Keys buffer: %s", set.visualizeKeyDistribution(30));
105
106 /*
107 * Prints:
108 *
109 * Keys buffer: 1.............................
110 *
111 * which is clearly a nonsensical hash set distribution. A typically deployed trick is to make
112 * some hash function redistribute keys all over the buffer space. Then it's more difficult (but
113 * not impossible) to encounter such bad collision chains. Note how the (linear) keys are
114 * distributed over the buffer space and how the occupancy of the buffer drops upon buffer
115 * expansions. We use a constant hash order mixing strategy here, ignore it for the moment.
116 */
117 println("Adding keys...");
118 set = new IntHashSet(0, 0.75d, HashOrderMixing.constant(0xdeadbeef));
119 key = 0;
120 for (int i = 0; i < 50; i++) {
121 for (int j = 0; j < 1000; j++) {
122 set.add(key++);
123 }
124 println("%5d keys, buffer size: %6d, occupancy: %s", set.size(), set.keys.length, set.visualizeKeyDistribution(30));
125 }
126
127 /*
128 * You should see that, with increasing buffer size and the number of keys, they are nearly
129 * uniformly distributed over the buffer space:
130 *
131 * 1000 keys, buffer size: 2049, occupancy: 544355644445654565654666556565
132 * 2000 keys, buffer size: 4097, occupancy: 545564435485554555744555454565
133 * 3000 keys, buffer size: 4097, occupancy: 879887778698777787987788687888
134 * 4000 keys, buffer size: 8193, occupancy: 555555655554565455555554555445
135 * 5000 keys, buffer size: 8193, occupancy: 667766866675676566666666666666
136 * 6000 keys, buffer size: 8193, occupancy: 888887987786898677888787787777
137 * 7000 keys, buffer size: 16385, occupancy: 445454445444444454545444444444
138 * 8000 keys, buffer size: 16385, occupancy: 555555545554455555655555555455
139 * ...
140 * 49000 keys, buffer size: 65537, occupancy: 888888878888888888887878888888
141 * 50000 keys, buffer size: 131073, occupancy: 444444444444444444444444444444
142 *
143 * The final step causes a rehash so occupancy drops by 50%
144 * (the buffer is doubled). Makes sense.
145 *
146 * There is still a very subtle problem that remains. Consider the following
147 * snippet of code that copies the first 10000 keys from the above container
148 * to another hash container (with the same hashing function). We make the
149 * capacity of "other" identical to the origin set.
150 */
151 println("Copying to 'other'...");
152 IntHashSet other = new IntHashSet(set.size(), 0.75d, HashOrderMixing.constant(0xdeadbeef));
153 int keysToCopy = 10000;
154 for (IntCursor c : set) {
155 if (--keysToCopy < 0) {
156 break;
157 } else {
158 other.add(c.value);
159 }
160 }
161
162 /*
163 * Now lets check out the distribution of keys in "other".
164 */
165 println("%5d keys, buffer size: %6d, occupancy: %s",
166 other.size(),
167 other.keys.length,
168 other.visualizeKeyDistribution(30));
169
170 /*
171 * The above should print:
172 *
173 * 10000 keys, buffer size: 131073, occupancy: 444443........................
174 *
175 * Clearly something went terribly wrong -- our keys are grouped again
176 * (although a bit more sparsely).
177 *
178 * The reason for this behavior is pretty obvious: the keys are assigned to slots that are
179 * distributed according to the result of the hash function. But when one iterates over
180 * the elements of a hash set, the keys are traversed in the nearly-sorted order of
181 * these hash values!
182 *
183 * Let it sink in a bit. If we iterate over a hash set, the keys we retrieve are in the
184 * *worst* possible hash-order.
185 *
186 * This can lead to some very dangerous data-related pathologies, like any lookup operation
187 * requiring a long time to find a free or matching slot.
188 *
189 * This is very easy to demonstrate (in a number of ways). The example below
190 * simply recreates a hash container with a high load factor that is on
191 * the verge of expansion.
192 */
193
194 // 5000 keys from expanding the buffer... (nearly full capacity).
195 double lf = 0.9;
196 int keys = (int) Math.ceil((1 << 19) / lf) - 5000;
197
198 set = new IntHashSet(0, lf, HashOrderMixing.none());
199 for (int i = keys; i-- != 0;) {
200 set.add(i);
201 }
202
203 other = new IntHashSet(0, lf, HashOrderMixing.none());
204 int added = 0;
205 long start = System.currentTimeMillis();
206 long deadline = start + TimeUnit.SECONDS.toMillis(5);
207 for (int v : set.toArray()) {
208 other.add(v);
209
210 // Print some diagnostics every 10k elements.
211 if ((++added % 10000) == 0) {
212 long round = -(start - (start = System.currentTimeMillis()));
213 println("%6d keys, round: %5d ms, buffer: %s", added, round, other.visualizeKeyDistribution(40));
214
215 if (start > deadline) {
216 println("Breaking out forcibly, it'll take forever.");
217 break; // Don't run for too long.
218 }
219 }
220 }
221
222 /*
223 * Note how add(), that should be a very simple and cheap operation, becomes an
224 * expensive, nearly blocking call. The reason is of course the fully-occupied
225 * front of the hash table; every slot lookup become more and more expensive.
226 *
227 * ...
228 * 340000 keys, round: 1 ms, buffer: 7777777777777777777777777777777777777771
229 * 345000 keys, round: 1 ms, buffer: 7777777777777777777777777777777777777775
230 * 350000 keys, round: 4 ms, buffer: 9777777777777777777777777777777777777777
231 * 355000 keys, round: 29 ms, buffer: X977777777777777777777777777777777777777
232 * 360000 keys, round: 57 ms, buffer: XXX7777777777777777777777777777777777777
233 * 365000 keys, round: 85 ms, buffer: XXXX777777777777777777777777777777777777
234 * 370000 keys, round: 112 ms, buffer: XXXXX77777777777777777777777777777777777
235 * 375000 keys, round: 141 ms, buffer: XXXXXX8777777777777777777777777777777777
236 * 380000 keys, round: 169 ms, buffer: XXXXXXX877777777777777777777777777777777
237 * 385000 keys, round: 196 ms, buffer: XXXXXXXX97777777777777777777777777777777
238 * 390000 keys, round: 223 ms, buffer: XXXXXXXXX9777777777777777777777777777777
239 * 395000 keys, round: 250 ms, buffer: XXXXXXXXXXX77777777777777777777777777777
240 * 400000 keys, round: 278 ms, buffer: XXXXXXXXXXXX7777777777777777777777777777
241 * 405000 keys, round: 306 ms, buffer: XXXXXXXXXXXXX777777777777777777777777777
242 * 410000 keys, round: 333 ms, buffer: XXXXXXXXXXXXXX77777777777777777777777777
243 * 415000 keys, round: 362 ms, buffer: XXXXXXXXXXXXXXX8777777777777777777777777
244 * 420000 keys, round: 390 ms, buffer: XXXXXXXXXXXXXXXX877777777777777777777777
245 * 425000 keys, round: 418 ms, buffer: XXXXXXXXXXXXXXXXX97777777777777777777777
246 * 430000 keys, round: 447 ms, buffer: XXXXXXXXXXXXXXXXXX9777777777777777777777
247 * 435000 keys, round: 473 ms, buffer: XXXXXXXXXXXXXXXXXXXX77777777777777777777
248 * 440000 keys, round: 502 ms, buffer: XXXXXXXXXXXXXXXXXXXXX7777777777777777777
249 * ...
250 *
251 * The examples leading to the above scenario can be multiplied and are not always
252 * easy to predict. There is no perfect way to solve it either, it's an inherent
253 * feature of linear conflict resolution. There are some workarounds that could
254 * be applied to putAll and similar operations (Koloboke and Fastutil implement
255 * them), but there is no way to solve the issue systematically... unless each and
256 * every hash container has a different key distribution.
257 *
258 * Which is exactly what HPPC implements. The two different "flavors" of associative
259 * containers are meant to distinguish between "safe" and "fast" ones.
260 *
261 * Any hash container will, by default, use a fairly unique internal
262 * mixing seed that ensures no two objects have the same distribution of keys.
263 *
264 * Compare the running time (and distributions) from the code below with the one
265 * executed before.
266 */
267
268 other = new IntHashSet(0, 0.9d);
269 added = 0;
270 start = System.currentTimeMillis();
271 for (int v : set.toArray()) {
272 if ((++added % 50000) == 0) {
273 long round = -(start - (start = System.currentTimeMillis()));
274 println("%6d keys, round: %5d ms, buffer: %s", added, round, other.visualizeKeyDistribution(40));
275 }
276 other.add(v);
277 }
278
279 /*
280 * Prints:
281 *
282 * 50000 keys, round: 7 ms, buffer: 8888888888888878888888888888888888888888
283 * 100000 keys, round: 3 ms, buffer: 8888888888888888888888888888888888888888
284 * 150000 keys, round: 3 ms, buffer: 6666666666666666666666666666666666666666
285 * 200000 keys, round: 2 ms, buffer: 8888888888888888888888888888888888888888
286 * 250000 keys, round: 5 ms, buffer: 5555555555555555555555555555555555555555
287 * 300000 keys, round: 1 ms, buffer: 6666666666666666666666666666666666666666
288 * 350000 keys, round: 2 ms, buffer: 7777777777777777777777777777777777777777
289 * 400000 keys, round: 2 ms, buffer: 8888888888888888888888888888888888888888
290 * 450000 keys, round: 2 ms, buffer: 9999999999999999999999999999999999999999
291 * 500000 keys, round: 9 ms, buffer: 5555555555555555555555555555555555555555
292 * 550000 keys, round: 2 ms, buffer: 5555555555555555555555555555555555555555
293 * 600000 keys, round: 2 ms, buffer: 6666666666666666666666666666666666666666
294 * 650000 keys, round: 2 ms, buffer: 6666666666666666666666666666666666666666
295 *
296 * Nothing is free though. There is a small performance penalty (and it
297 * really is very small unless you're dealing with huge collections) associated with
298 * an additional memory read (the mixing seed) and a XOR with the key hash.
299 *
300 * To conclude this example: contrary to hash containers, the "scatter"
301 * variants of maps and sets do *not* implement key remixing; they also implement
302 * a simpler hashing heuristic to speed up slot lookups.
303 *
304 * Scatter containers are still useful (they're faster!) and can be used to implement lookup tables
305 * or counting tables. It is important to remember though to *never* copy the keys of a hash map
306 * or a hash set to a scatter map or set. You can do it the other way around though:
307 * copy keys from a scatter set to a hash set, for instance, because the hash set's mixing
308 * function will make sure they are uniquely redistributed across the buffer space.
309 *
310 * That's it, simple.
311 */
312 }
313
314 private void println(String msg, Object... args) {
315 System.out.println(String.format(Locale.ROOT, msg, args));
316 }
317 }