| 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 |
} |