2 * This software is part of the SBCL system. See the README file for
5 * This software is derived from the CMU CL system, which was
6 * written at Carnegie Mellon University and released into the
7 * public domain. The software is in the public domain and is
8 * provided with absolutely no warranty. See the COPYING and CREDITS
9 * files for more information.
13 * Our implementation of the hopscotch algorithm described in
14 * http://people.csail.mit.edu/shanir/publications/disc2008_submission_98.pdf
15 * which is extremely simple variation on linear probing
16 * that provides a guaranteed bound on number of probes.
19 #include <pthread.h> // only because of our dang non-self-contained .h files
20 #ifdef COLLECT_STATISTICS
24 #include "genesis/constants.h"
26 #include "gc-internal.h" // for os_validate()
27 #include "hopscotch.h"
29 typedef struct hopscotch_table
* tableptr
;
30 void hopscotch_integrity_check(tableptr
,char*,int);
32 #define table_size(table) (1+(table).mask)
34 #define INTEGRITY_CHECK(when) {}
36 /// Set a single bit in the hop mask for logical cell at 'index'
37 static inline void set_hop_bit(tableptr ht
, unsigned index
, int bit
)
39 unsigned mask
= 1<<bit
;
40 ht
->hops
[index
] |= mask
;
42 /// Set all the bits in the hop mask for logical cell at 'index'
43 static inline void set_hop_mask(tableptr ht
, unsigned index
, unsigned bits
)
45 ht
->hops
[index
] = bits
;
47 static inline unsigned get_hop_mask(tableptr ht
, unsigned index
)
49 return ht
->hops
[index
];
52 /// Hopscotch storage allocation granularity.
53 /// Our usual value of "page size" is the GC page size, which is
54 /// coarser than necessary (cf {target}/backend-parms.lisp).
55 static int hh_allocation_granularity
= 4096;
56 #define ALLOCATION_OVERHEAD (2*sizeof(unsigned int))
57 /// Return the number of usable bytes (excluding the header) in an allocation
58 #define usable_size(x) ((unsigned int*)x)[-1]
60 /// Sizing up a table can't be done in-place, so reserve a few blocks
61 /// of memory for when resize has to happen during GC. We don't return
62 /// these blocks to the OS. If even more is required, it will be allocated
63 /// as needed, but we'll only keep on reserve at most two blocks.
64 #define N_CACHED_ALLOCS 2
65 char* cached_alloc
[N_CACHED_ALLOCS
];
66 void hopscotch_init() // Called once on runtime startup, from gc_init().
68 // Get 16KB from the OS and evenly divide it into two pieces.
69 int n_bytes_per_slice
= 8 * 1024;
70 int n_bytes_total
= N_CACHED_ALLOCS
* n_bytes_per_slice
;
71 char* mem
= (char*)os_validate(0, n_bytes_total
);
73 cached_alloc
[0] = mem
+ ALLOCATION_OVERHEAD
;
74 cached_alloc
[1] = cached_alloc
[0] + n_bytes_per_slice
;
75 // Write the user-visible size of each allocation into the block header
76 usable_size(cached_alloc
[0]) = n_bytes_per_slice
- ALLOCATION_OVERHEAD
;
77 usable_size(cached_alloc
[1]) = n_bytes_per_slice
- ALLOCATION_OVERHEAD
;
80 /* Return the address of at least 'nbytes' of storage.
81 * This is not a general-purpose thing - it's only intended to keep
82 * one or perhaps two hopscotch hash tables around during GC,
83 * for pinned objects, and maybe something else.
84 * As such, no attempt is made to minimize storage use,
85 * and if used more generally, would badly suffer from fragmentation.
87 static char* cached_allocate(os_vm_size_t nbytes
)
89 // See if either cached allocation is large enough.
90 if (cached_alloc
[0] && usable_size(cached_alloc
[0]) >= nbytes
) {
91 // Yup, just give the consumer the whole thing.
92 char* result
= cached_alloc
[0];
93 cached_alloc
[0] = 0; // Remove from the pool
96 if (cached_alloc
[1] && usable_size(cached_alloc
[1]) >= nbytes
) { // Ditto.
97 char* result
= cached_alloc
[1];
101 // Request more memory, not using malloc().
102 // Round up, since the OS will give more than asked if the request is
103 // not a multiple of the mmap granularity, which we'll assume is 4K.
104 // (It doesn't actually matter.)
105 nbytes
= CEILING(nbytes
, hh_allocation_granularity
);
106 char* result
= os_validate(0, nbytes
);
108 result
+= ALLOCATION_OVERHEAD
;
109 usable_size(result
) = nbytes
- ALLOCATION_OVERHEAD
;
113 /* Return 'mem' to the cache, first zero-filling to the specified length.
114 * Though the memory size is recorded in the header of the memory block,
115 * the allocator doesn't know how many bytes were touched by the requestor,
116 * which is why the length is specified again.
117 * If returning it to the OS and not the cache, then don't bother 0-filling.
119 static void cached_deallocate(char* mem
, int zero_fill_length
)
122 if (!cached_alloc
[0]) {
123 } else if (!cached_alloc
[1])
126 // Try to retain whichever 2 blocks are largest (the given one and
127 // cached ones) in the hope of fulfilling future requests from cache.
128 int this_size
= usable_size(mem
);
129 int cached_size0
= usable_size(cached_alloc
[0]);
130 int cached_size1
= usable_size(cached_alloc
[1]);
131 if (!(this_size
> cached_size0
|| this_size
> cached_size1
)) {
132 // mem is not strictly larger than either cached block. Release it.
133 os_deallocate(mem
- ALLOCATION_OVERHEAD
,
134 usable_size(mem
) + ALLOCATION_OVERHEAD
);
137 // Evict and replace the smaller of the two cache entries.
138 if (cached_size1
< cached_size0
)
140 os_deallocate(cached_alloc
[line
] - ALLOCATION_OVERHEAD
,
141 usable_size(cached_alloc
[line
]) + ALLOCATION_OVERHEAD
);
143 bzero(mem
, zero_fill_length
);
144 cached_alloc
[line
] = mem
;
147 /* Initialize 'ht' for 'size' logical bins with a max hop of 'hop_range'.
148 * 'valuesp' makes a hash-map if true; a hash-set if false.
149 * Hop range will be selected automatically if specified as 0.
151 static void hopscotch_realloc(tableptr ht
, boolean valuesp
, int size
, char hop_range
)
153 // Somewhat arbitrary criteria that improve the worst-case probes for
154 // small hashtables. The reference algorithm uses a fixed max hop of 32,
155 // but fewer is better, and our pinned object table tends to be very small.
156 if (hop_range
== 0) { // Let us pick.
157 if (size
<= 1024) hop_range
= 8;
158 else if (size
<= 16384) hop_range
= 16;
162 // The key/value arrays are *not* circular.
163 // The last few logical cells in the key array can use physical cells
164 // at indices greater than 'size'; there's no wrapping back to index 0.
165 int n_keys
= size
+ (hop_range
- 1);
166 unsigned storage_size
= sizeof (uword_t
) * n_keys
167 + sizeof (int) * size
// hop bitmasks
168 + (valuesp
? (sizeof (int) * n_keys
) : 0); // values
171 gc_assert(usable_size(ht
->keys
) >= storage_size
);
173 ht
->keys
= (uword_t
*)cached_allocate(storage_size
);
175 ht
->mem_size
= storage_size
;
177 ht
->hop_range
= hop_range
;
178 ht
->hops
= (unsigned*)((char*)ht
->keys
+ sizeof (uword_t
) * n_keys
);
179 ht
->values
= !valuesp
? 0 :
180 (unsigned*)((char*)ht
->hops
+ sizeof (int) * size
);
183 /* Initialize 'ht' for first use, which entails zeroing the counters
184 * and allocating storage.
186 void hopscotch_create(tableptr ht
, boolean valuesp
, int size
, char hop_range
)
188 gc_assert((size
& (size
-1)) == 0); // ensure power-of-2
192 // Ensure that the first reset() doesn't do something screwy.
193 ht
->prev_size
= size
;
194 // Clear these even if not collecting statistics,
195 // because it looks ugly if we don't.
196 ht
->hit
.n_seeks
= ht
->hit
.n_probes
= 0;
197 ht
->miss
.n_seeks
= ht
->miss
.n_probes
= 0;
199 ht
->keys
= 0; // Forces allocation of backing storage.
200 hopscotch_realloc(ht
, valuesp
, size
, hop_range
);
203 /* Delete the storage associated with 'ht' */
204 void hopscotch_delete(tableptr ht
)
206 if (ht
->mem_size
) { // Free it, zero-filling if ever used.
207 cached_deallocate((char*)ht
->keys
, ht
->count
? ht
->mem_size
: 0);
214 /* Prepare 'ht' for re-use. Same as CLRHASH */
215 void hopscotch_reset(tableptr ht
)
218 bzero(ht
->keys
, ht
->mem_size
);
221 // If the size exceeds twice the final size from the prior run,
222 // or is the same size and was not enlarged, then downsize,
223 // but don't go below a certain minimal size.
224 int size
= table_size(*ht
);
226 fprintf(stderr
, "hh reset: size=%d prev=%d upsized=%d\n",
227 size
, ht
->prev_size
, ht
->resized
);
229 if (size
> (ht
->prev_size
<< 1)
230 || (size
== ht
->prev_size
&& !ht
->resized
&& size
> 8))
231 // Halve the size for the next GC cycle
232 hopscotch_realloc(ht
, ht
->values
!= 0, size
>> 1, 0);
233 ht
->prev_size
= size
;
235 INTEGRITY_CHECK("after reset");
238 /* Double the size of 'ht'. Called when an insertion overflows the table */
239 tableptr
hopscotch_resize_up(tableptr ht
)
241 int size
= ht
->mask
+ 1; // Logical bin count
242 int old_max_index
= hopscotch_max_key_index(*ht
);
243 struct hopscotch_table copy
;
246 fprintf(stderr
, "resize up: ct=%d cap=%d hop=%d LF=%f\n",
247 ht
->count
, 1+old_max_index
, ht
->hop_range
,
248 (float)ht
->count
/(1+old_max_index
));
250 INTEGRITY_CHECK("before resize");
251 // Copy the keys or key/value pairs.
253 // It's conceivable, however improbable, that there is a hash function
254 // which causes more collisions at the new size than the old size.
255 // Due to the fixed hop range, failure to insert while rehashing
256 // must be caught so that we can try again with a larger size.
257 // But usually this loop will execute exactly once.
261 hopscotch_create(©
, ht
->values
!= 0, size
, 0);
262 copy
.rehashing
= 1; // Causes put() to return 0 on failure
264 for(i
=old_max_index
; i
>= 0 ; --i
)
266 if (!hopscotch_put(©
, ht
->keys
[i
], ht
->values
[i
]))
269 for(i
=old_max_index
; i
>= 0 ; --i
)
271 if (!hopscotch_put(©
, ht
->keys
[i
], 1)) {
273 fprintf(stderr
, "resize failed with new size %d, hop_range %d\n",
274 size
, copy
.hop_range
);
279 } while (i
>= 0 && (hopscotch_delete(©
), 1));
281 // Zero-fill and release the old storage.
282 cached_deallocate((char*)ht
->keys
, ht
->mem_size
);
284 // Move all of the data pointers from 'copy' into ht.
285 // mem_size is passed to bzero() when resetting the table,
286 // so definitely be sure to use the new, not the old.
287 // And of course _don't_ hopscotch_delete() copy when done.
288 ht
->mem_size
= copy
.mem_size
;
289 ht
->mask
= copy
.mask
;
290 ht
->hop_range
= copy
.hop_range
;
291 ht
->keys
= copy
.keys
;
292 ht
->hops
= copy
.hops
;
293 ht
->values
= copy
.values
;
295 INTEGRITY_CHECK("after resize");
299 void hopscotch_log_stats(tableptr ht
)
301 #ifdef COLLECT_STATISTICS
302 static FILE *hh_logfile
;
304 hh_logfile
= fopen("hash-stats.txt","a");
306 "hopscotch: ct=%5d cap=%5d LF=%f seek=%5d+%5d probe/seek=%f+%f (hit+miss)\n",
308 (ht
->mask
+ ht
->hop_range
),
309 (float)ht
->count
/ (ht
->mask
+ ht
->hop_range
),
310 ht
->hit
.n_seeks
, ht
->miss
.n_seeks
,
311 ht
->hit
.n_seeks
>0 ? (float)ht
->hit
.n_probes
/ ht
->hit
.n_seeks
: 0.0,
312 ht
->miss
.n_seeks
>0 ? (float)ht
->miss
.n_probes
/ ht
->miss
.n_seeks
: 0.0);
314 ht
->hit
.n_seeks
= ht
->hit
.n_probes
= 0;
315 ht
->miss
.n_seeks
= ht
->miss
.n_probes
= 0;
319 /* Return an integer with 'n' low-order 1 bits.
320 * This does not do the right thing for n = 0, but that's fine!
321 * (Shifting an unsigned 32-bit integer rightward by 32 is not defined.
322 * 32-bit x86 masks the shift amount to 5 bits, so you get 0 shift)
324 static inline unsigned int bitmask_of_width(int n
) {
325 return (0xFFFFFFFFU
>> (32 - n
));
328 #define put_pair(i,k,v) ht->keys[i] = k; if(ht->values) ht->values[i] = v
330 /* Add key/val to 'ht'. 'val' is ignored for a hash-set */
331 int hopscotch_put(tableptr ht
, uword_t key
, unsigned int val
)
333 // 'desired_index' is where 'key' logically belongs, but it
334 // may physically go in any cell to the right up to (range-1) away.
335 int desired_index
= hash(key
) & ht
->mask
;
336 if (ht
->keys
[desired_index
] == 0) { // Instant win
337 put_pair(desired_index
, key
, val
);
338 set_hop_bit(ht
, desired_index
, 0);
341 // 'limit' is the inclusive bound on cell indices.
342 int limit
= hopscotch_max_key_index(*ht
);
343 int free_index
= desired_index
;
345 while (ht
->keys
[++free_index
] != 0) // While cell is occupied
346 if (free_index
== limit
)
347 return ht
->rehashing
? 0 : // fail if rehash table is too small
348 hopscotch_put(hopscotch_resize_up(ht
), key
, val
);
350 // 'free_index' is where *some* item could go,
351 // but it might be too far away for this key.
353 if ((displacement
= free_index
- desired_index
) < ht
->hop_range
) {
354 put_pair(free_index
, key
, val
);
355 set_hop_bit(ht
, desired_index
, displacement
);
358 // Find the empty cell furthest away from and to the left of free_index,
359 // within the hop_range, that contains an item that can be moved.
360 int logical_bin
= free_index
- (ht
->hop_range
- 1);
361 // limit is the max index (inclusive) of the available free cells
362 // up to but excluding 'free_index'
363 limit
= free_index
- 1;
364 // In case free_index currently points to a physical bin "off the end"
365 // of the logical bins, confine to the highest logical bin,
366 // which is just the table mask.
367 if (limit
>= (int)ht
->mask
)
369 // Now 'free_index' is fixed, and 'logical_bin' is what we search
370 // over to find something to displace into the free_index.
371 // Example: v----- free index
372 // | | X | X | O | | [X = filled. O = filled + owned]
373 // ^--- logical bin (displacement = 3)
374 // Look at the low 3 bits of the hop bits for 'logical_bin'.
375 // Those indicate the physical cells "owned" by the logical cell
376 // and within the needed distance to the free cell.
377 // If any are set, the leftmost bit is robbed to make room.
378 // In the above example, bit index 2 (0-based index) would be claimed.
379 for ( ; logical_bin
<= limit
; ++logical_bin
) {
380 displacement
= free_index
- logical_bin
;
381 unsigned bits
= get_hop_mask(ht
, logical_bin
);
382 unsigned masked_bits
= bits
& bitmask_of_width(displacement
);
384 int victim
= ffs(masked_bits
) - 1; // ffs() is 1-based
385 int physical_elt
= logical_bin
+ victim
;
386 // Relocate the contents of 'physical_elt' to 'free_index'
387 put_pair(free_index
, ht
->keys
[physical_elt
], ht
->values
[physical_elt
]);
388 put_pair(physical_elt
, 0, 0);
389 // This logical bin no longer owns the index where the victim was,
390 // but does own the index where it got moved to.
391 set_hop_mask(ht
, logical_bin
, bits
^ (1<<displacement
| 1<<victim
));
392 // Now free_index gets smaller, and we try again from the top.
393 free_index
= physical_elt
;
397 // Too many collisions and not enough room to move things around.
398 return ht
->rehashing
? 0 : hopscotch_put(hopscotch_resize_up(ht
), key
, val
);
402 /// When probing on lookup, while we could use the mask bits in the
403 /// desired logical bin to restrict the number of key comparisons made,
404 /// this turns out to be worse. Though slightly counter-intuitive,
405 /// it is likely due to one fewer conditional branch when we hit the
406 /// first choice physical cell. The probe() macro will decide whether
407 /// to use the mask bits and/or record the number of key comparisons.
408 /// Statistics gathering also slows us down a lot, so only do it when
409 /// making comparative benchmarks, not in real-world use.
410 #ifdef COLLECT_STATISTICS
411 #define probe(mask,i,retval) ++probes; if (ht->keys[i] == key) { \
412 ++ht->hit.n_seeks; ht->hit.n_probes += probes; \
415 #define probe(mask,i,retval) if (ht->keys[i] == key) return retval
418 /* Test for membership in a hashset. Return 1 or 0. */
419 int hopscotch_containsp(tableptr ht
, uword_t key
)
421 // index needn't be 'long' but the code generated is better with it.
422 unsigned long index
= hash(key
) & ht
->mask
;
423 unsigned bits
= get_hop_mask(ht
, index
);
424 #ifdef COLLECT_STATISTICS
427 // *** Use care when modifying this code, and benchmark it thoroughly! ***
428 // TODO: use XMM register to test 2 keys at once if properly aligned.
430 probe((1<<0), index
+0, 1);
431 probe((1<<1), index
+1, 1);
432 probe((1<<2), index
+2, 1);
433 probe((1<<3), index
+3, 1);
434 probe((1<<4), index
+4, 1);
435 probe((1<<5), index
+5, 1);
436 probe((1<<6), index
+6, 1);
437 probe((1<<7), index
+7, 1);
439 // There's a trade-off to be made: checking for fewer bits at a time
440 // (such as by "bits & 0x0f") would give finer grain to the set of
441 // physical cells tested, but would mean more iterations.
442 // It seems like 8 bits at a time is a good number, especially if the
443 // hop range is 8, because this general case need never execute.
444 while ((bits
>>= 8) != 0) {
447 probe((1<<0), index
+0, 1);
448 probe((1<<1), index
+1, 1);
449 probe((1<<2), index
+2, 1);
450 probe((1<<3), index
+3, 1);
451 probe((1<<4), index
+4, 1);
452 probe((1<<5), index
+5, 1);
453 probe((1<<6), index
+6, 1);
454 probe((1<<7), index
+7, 1);
457 #ifdef COLLECT_STATISTICS
459 ht
->miss
.n_probes
+= probes
;
464 /* Return the value associated with 'key', or -1 if not found */
465 int hopscotch_get(tableptr ht
, uword_t key
)
467 int index
= hash(key
) & ht
->mask
;
468 unsigned bits
= get_hop_mask(ht
, index
);
469 #ifdef COLLECT_STATISTICS
472 // This is not as blazingly fast as the hand-unrolled loop
473 // in containsp(), but the GC does not need it, so ...
476 probe(1, index
+0, ht
->values
[index
+0]);
477 probe(2, index
+1, ht
->values
[index
+1]);
478 probe(4, index
+2, ht
->values
[index
+2]);
479 probe(8, index
+3, ht
->values
[index
+3]);
484 #ifdef COLLECT_STATISTICS
486 ht
->miss
.n_probes
+= probes
;
494 int popcount(unsigned x
)
497 for ( ; x
!= 0 ; x
>>= 1 )
502 /* Perform a bunch of sanity checks on 'ht' */
503 void hopscotch_integrity_check(tableptr ht
, char*when
, int verbose
)
505 int n_items
= 0, tot_bits_set
= 0, i
;
506 int size
= table_size(*ht
);
507 int n_kv_pairs
= size
+ ht
->hop_range
-1;
511 for(i
=n_kv_pairs
-1 ; i
>= 0 ; --i
) if (ht
->keys
[i
]) ++n_items
;
512 for(i
=ht
->mask
; i
>= 0; --i
) tot_bits_set
+= popcount(get_hop_mask(ht
,i
));
514 fprintf(s
, "(%s) Verifying table @ %p. count=%d actual=%d bits=%d\n",
515 when
, ht
, ht
->count
, n_items
, tot_bits_set
);
516 for (i
=0;i
<n_kv_pairs
;++i
) {
517 uword_t key
= ht
->keys
[i
];
519 if (key
!= 0 || (i
<=ht
->mask
&& get_hop_mask(ht
,i
) != 0)) {
520 // Compute the logical cell that owns this physical cell.
521 int start_index
= i
- (ht
->hop_range
-1);
522 if (start_index
< 0) start_index
= 0;
524 if (end_index
> ht
->mask
) end_index
= ht
->mask
;
527 for (logical_cell
= start_index
; logical_cell
<= end_index
; ++logical_cell
) {
528 unsigned hop_bits
= get_hop_mask(ht
, logical_cell
);
529 if (hop_bits
& (1<<(i
- logical_cell
))) {
531 claimed
= logical_cell
;
534 "physical cell %d duplicately claimed: %d and %d",
535 i
, claimed
, logical_cell
);
541 if (claimed
==i
|| (claimed
==-1 && !key
))
543 else if (claimed
!=-1) {
544 fprintf(s
, "[%4d]", claimed
);
545 if ((int)(ht
->mask
& hash(key
)) != claimed
)
546 lose("key hashes to wrong logical cell?");
547 } else { // should have been claimed
548 fprintf(s
, " **** ");
551 fprintf(s
, " %4d: %04x", i
, i
<= ht
->mask
? get_hop_mask(ht
,i
) : 0);
553 fprintf(s
, " %12p -> %d",
554 (void*)(key
<<(1+WORD_SHIFT
)),
555 (int)(ht
->mask
& hash(key
)));
560 if (ht
->count
!= n_items
|| tot_bits_set
!= n_items
|| fail
)
561 lose("integrity check on hashtable %p failed", ht
);