]>
git.proxmox.com Git - rustc.git/blob - src/jemalloc/src/ckh.c
2 *******************************************************************************
3 * Implementation of (2^1+,2) cuckoo hashing, where 2^1+ indicates that each
4 * hash bucket contains 2^n cells, for n >= 1, and 2 indicates that two hash
5 * functions are employed. The original cuckoo hashing algorithm was described
8 * Pagh, R., F.F. Rodler (2004) Cuckoo Hashing. Journal of Algorithms
11 * Generalization of cuckoo hashing was discussed in:
13 * Erlingsson, U., M. Manasse, F. McSherry (2006) A cool and practical
14 * alternative to traditional hash tables. In Proceedings of the 7th
15 * Workshop on Distributed Data and Structures (WDAS'06), Santa Clara, CA,
18 * This implementation uses precisely two hash functions because that is the
19 * fewest that can work, and supporting multiple hashes is an implementation
20 * burden. Here is a reproduction of Figure 1 from Erlingsson et al. (2006)
21 * that shows approximate expected maximum load factors for various
25 * #hashes | 1 | 2 | 4 | 8 |
26 * --------+-------+-------+-------+-------+
27 * 1 | 0.006 | 0.006 | 0.03 | 0.12 |
28 * 2 | 0.49 | 0.86 |>0.93< |>0.96< |
29 * 3 | 0.91 | 0.97 | 0.98 | 0.999 |
30 * 4 | 0.97 | 0.99 | 0.999 | |
32 * The number of cells per bucket is chosen such that a bucket fits in one cache
33 * line. So, on 32- and 64-bit systems, we use (8,2) and (4,2) cuckoo hashing,
36 ******************************************************************************/
37 #define JEMALLOC_CKH_C_
38 #include "jemalloc/internal/jemalloc_internal.h"
40 /******************************************************************************/
41 /* Function prototypes for non-inline static functions. */
43 static bool ckh_grow(tsd_t
*tsd
, ckh_t
*ckh
);
44 static void ckh_shrink(tsd_t
*tsd
, ckh_t
*ckh
);
46 /******************************************************************************/
49 * Search bucket for key and return the cell number if found; SIZE_T_MAX
52 JEMALLOC_INLINE_C
size_t
53 ckh_bucket_search(ckh_t
*ckh
, size_t bucket
, const void *key
)
58 for (i
= 0; i
< (ZU(1) << LG_CKH_BUCKET_CELLS
); i
++) {
59 cell
= &ckh
->tab
[(bucket
<< LG_CKH_BUCKET_CELLS
) + i
];
60 if (cell
->key
!= NULL
&& ckh
->keycomp(key
, cell
->key
))
61 return ((bucket
<< LG_CKH_BUCKET_CELLS
) + i
);
68 * Search table for key and return cell number if found; SIZE_T_MAX otherwise.
70 JEMALLOC_INLINE_C
size_t
71 ckh_isearch(ckh_t
*ckh
, const void *key
)
73 size_t hashes
[2], bucket
, cell
;
77 ckh
->hash(key
, hashes
);
79 /* Search primary bucket. */
80 bucket
= hashes
[0] & ((ZU(1) << ckh
->lg_curbuckets
) - 1);
81 cell
= ckh_bucket_search(ckh
, bucket
, key
);
82 if (cell
!= SIZE_T_MAX
)
85 /* Search secondary bucket. */
86 bucket
= hashes
[1] & ((ZU(1) << ckh
->lg_curbuckets
) - 1);
87 cell
= ckh_bucket_search(ckh
, bucket
, key
);
91 JEMALLOC_INLINE_C
bool
92 ckh_try_bucket_insert(ckh_t
*ckh
, size_t bucket
, const void *key
,
99 * Cycle through the cells in the bucket, starting at a random position.
100 * The randomness avoids worst-case search overhead as buckets fill up.
102 offset
= (unsigned)prng_lg_range(&ckh
->prng_state
, LG_CKH_BUCKET_CELLS
);
103 for (i
= 0; i
< (ZU(1) << LG_CKH_BUCKET_CELLS
); i
++) {
104 cell
= &ckh
->tab
[(bucket
<< LG_CKH_BUCKET_CELLS
) +
105 ((i
+ offset
) & ((ZU(1) << LG_CKH_BUCKET_CELLS
) - 1))];
106 if (cell
->key
== NULL
) {
118 * No space is available in bucket. Randomly evict an item, then try to find an
119 * alternate location for that item. Iteratively repeat this
120 * eviction/relocation procedure until either success or detection of an
121 * eviction/relocation bucket cycle.
123 JEMALLOC_INLINE_C
bool
124 ckh_evict_reloc_insert(ckh_t
*ckh
, size_t argbucket
, void const **argkey
,
125 void const **argdata
)
127 const void *key
, *data
, *tkey
, *tdata
;
129 size_t hashes
[2], bucket
, tbucket
;
137 * Choose a random item within the bucket to evict. This is
138 * critical to correct function, because without (eventually)
139 * evicting all items within a bucket during iteration, it
140 * would be possible to get stuck in an infinite loop if there
141 * were an item for which both hashes indicated the same
144 i
= (unsigned)prng_lg_range(&ckh
->prng_state
,
145 LG_CKH_BUCKET_CELLS
);
146 cell
= &ckh
->tab
[(bucket
<< LG_CKH_BUCKET_CELLS
) + i
];
147 assert(cell
->key
!= NULL
);
149 /* Swap cell->{key,data} and {key,data} (evict). */
150 tkey
= cell
->key
; tdata
= cell
->data
;
151 cell
->key
= key
; cell
->data
= data
;
152 key
= tkey
; data
= tdata
;
158 /* Find the alternate bucket for the evicted item. */
159 ckh
->hash(key
, hashes
);
160 tbucket
= hashes
[1] & ((ZU(1) << ckh
->lg_curbuckets
) - 1);
161 if (tbucket
== bucket
) {
162 tbucket
= hashes
[0] & ((ZU(1) << ckh
->lg_curbuckets
)
165 * It may be that (tbucket == bucket) still, if the
166 * item's hashes both indicate this bucket. However,
167 * we are guaranteed to eventually escape this bucket
168 * during iteration, assuming pseudo-random item
169 * selection (true randomness would make infinite
170 * looping a remote possibility). The reason we can
171 * never get trapped forever is that there are two
174 * 1) This bucket == argbucket, so we will quickly
175 * detect an eviction cycle and terminate.
176 * 2) An item was evicted to this bucket from another,
177 * which means that at least one item in this bucket
178 * has hashes that indicate distinct buckets.
181 /* Check for a cycle. */
182 if (tbucket
== argbucket
) {
189 if (!ckh_try_bucket_insert(ckh
, bucket
, key
, data
))
194 JEMALLOC_INLINE_C
bool
195 ckh_try_insert(ckh_t
*ckh
, void const**argkey
, void const**argdata
)
197 size_t hashes
[2], bucket
;
198 const void *key
= *argkey
;
199 const void *data
= *argdata
;
201 ckh
->hash(key
, hashes
);
203 /* Try to insert in primary bucket. */
204 bucket
= hashes
[0] & ((ZU(1) << ckh
->lg_curbuckets
) - 1);
205 if (!ckh_try_bucket_insert(ckh
, bucket
, key
, data
))
208 /* Try to insert in secondary bucket. */
209 bucket
= hashes
[1] & ((ZU(1) << ckh
->lg_curbuckets
) - 1);
210 if (!ckh_try_bucket_insert(ckh
, bucket
, key
, data
))
214 * Try to find a place for this item via iterative eviction/relocation.
216 return (ckh_evict_reloc_insert(ckh
, bucket
, argkey
, argdata
));
220 * Try to rebuild the hash table from scratch by inserting all items from the
221 * old table into the new.
223 JEMALLOC_INLINE_C
bool
224 ckh_rebuild(ckh_t
*ckh
, ckhc_t
*aTab
)
226 size_t count
, i
, nins
;
227 const void *key
, *data
;
231 for (i
= nins
= 0; nins
< count
; i
++) {
232 if (aTab
[i
].key
!= NULL
) {
235 if (ckh_try_insert(ckh
, &key
, &data
)) {
247 ckh_grow(tsd_t
*tsd
, ckh_t
*ckh
)
251 unsigned lg_prevbuckets
, lg_curcells
;
258 * It is possible (though unlikely, given well behaved hashes) that the
259 * table will have to be doubled more than once in order to create a
262 lg_prevbuckets
= ckh
->lg_curbuckets
;
263 lg_curcells
= ckh
->lg_curbuckets
+ LG_CKH_BUCKET_CELLS
;
268 usize
= sa2u(sizeof(ckhc_t
) << lg_curcells
, CACHELINE
);
269 if (unlikely(usize
== 0 || usize
> HUGE_MAXCLASS
)) {
273 tab
= (ckhc_t
*)ipallocztm(tsd
, usize
, CACHELINE
, true, NULL
,
279 /* Swap in new table. */
283 ckh
->lg_curbuckets
= lg_curcells
- LG_CKH_BUCKET_CELLS
;
285 if (!ckh_rebuild(ckh
, tab
)) {
286 idalloctm(tsd
, tab
, tcache_get(tsd
, false), true, true);
290 /* Rebuilding failed, so back out partially rebuilt table. */
291 idalloctm(tsd
, ckh
->tab
, tcache_get(tsd
, false), true, true);
293 ckh
->lg_curbuckets
= lg_prevbuckets
;
302 ckh_shrink(tsd_t
*tsd
, ckh_t
*ckh
)
306 unsigned lg_prevbuckets
, lg_curcells
;
309 * It is possible (though unlikely, given well behaved hashes) that the
310 * table rebuild will fail.
312 lg_prevbuckets
= ckh
->lg_curbuckets
;
313 lg_curcells
= ckh
->lg_curbuckets
+ LG_CKH_BUCKET_CELLS
- 1;
314 usize
= sa2u(sizeof(ckhc_t
) << lg_curcells
, CACHELINE
);
315 if (unlikely(usize
== 0 || usize
> HUGE_MAXCLASS
))
317 tab
= (ckhc_t
*)ipallocztm(tsd
, usize
, CACHELINE
, true, NULL
, true,
321 * An OOM error isn't worth propagating, since it doesn't
322 * prevent this or future operations from proceeding.
326 /* Swap in new table. */
330 ckh
->lg_curbuckets
= lg_curcells
- LG_CKH_BUCKET_CELLS
;
332 if (!ckh_rebuild(ckh
, tab
)) {
333 idalloctm(tsd
, tab
, tcache_get(tsd
, false), true, true);
340 /* Rebuilding failed, so back out partially rebuilt table. */
341 idalloctm(tsd
, ckh
->tab
, tcache_get(tsd
, false), true, true);
343 ckh
->lg_curbuckets
= lg_prevbuckets
;
350 ckh_new(tsd_t
*tsd
, ckh_t
*ckh
, size_t minitems
, ckh_hash_t
*hash
,
351 ckh_keycomp_t
*keycomp
)
354 size_t mincells
, usize
;
355 unsigned lg_mincells
;
357 assert(minitems
> 0);
358 assert(hash
!= NULL
);
359 assert(keycomp
!= NULL
);
364 ckh
->nshrinkfails
= 0;
368 ckh
->prng_state
= 42; /* Value doesn't really matter. */
372 * Find the minimum power of 2 that is large enough to fit minitems
373 * entries. We are using (2+,2) cuckoo hashing, which has an expected
374 * maximum load factor of at least ~0.86, so 0.75 is a conservative load
375 * factor that will typically allow mincells items to fit without ever
378 assert(LG_CKH_BUCKET_CELLS
> 0);
379 mincells
= ((minitems
+ (3 - (minitems
% 3))) / 3) << 2;
380 for (lg_mincells
= LG_CKH_BUCKET_CELLS
;
381 (ZU(1) << lg_mincells
) < mincells
;
384 ckh
->lg_minbuckets
= lg_mincells
- LG_CKH_BUCKET_CELLS
;
385 ckh
->lg_curbuckets
= lg_mincells
- LG_CKH_BUCKET_CELLS
;
387 ckh
->keycomp
= keycomp
;
389 usize
= sa2u(sizeof(ckhc_t
) << lg_mincells
, CACHELINE
);
390 if (unlikely(usize
== 0 || usize
> HUGE_MAXCLASS
)) {
394 ckh
->tab
= (ckhc_t
*)ipallocztm(tsd
, usize
, CACHELINE
, true, NULL
, true,
396 if (ckh
->tab
== NULL
) {
407 ckh_delete(tsd_t
*tsd
, ckh_t
*ckh
)
414 "%s(%p): ngrows: %"FMTu64
", nshrinks: %"FMTu64
","
415 " nshrinkfails: %"FMTu64
", ninserts: %"FMTu64
","
416 " nrelocs: %"FMTu64
"\n", __func__
, ckh
,
417 (unsigned long long)ckh
->ngrows
,
418 (unsigned long long)ckh
->nshrinks
,
419 (unsigned long long)ckh
->nshrinkfails
,
420 (unsigned long long)ckh
->ninserts
,
421 (unsigned long long)ckh
->nrelocs
);
424 idalloctm(tsd
, ckh
->tab
, tcache_get(tsd
, false), true, true);
426 memset(ckh
, 0x5a, sizeof(ckh_t
));
430 ckh_count(ckh_t
*ckh
)
439 ckh_iter(ckh_t
*ckh
, size_t *tabind
, void **key
, void **data
)
443 for (i
= *tabind
, ncells
= (ZU(1) << (ckh
->lg_curbuckets
+
444 LG_CKH_BUCKET_CELLS
)); i
< ncells
; i
++) {
445 if (ckh
->tab
[i
].key
!= NULL
) {
447 *key
= (void *)ckh
->tab
[i
].key
;
449 *data
= (void *)ckh
->tab
[i
].data
;
459 ckh_insert(tsd_t
*tsd
, ckh_t
*ckh
, const void *key
, const void *data
)
464 assert(ckh_search(ckh
, key
, NULL
, NULL
));
470 while (ckh_try_insert(ckh
, &key
, &data
)) {
471 if (ckh_grow(tsd
, ckh
)) {
483 ckh_remove(tsd_t
*tsd
, ckh_t
*ckh
, const void *searchkey
, void **key
,
490 cell
= ckh_isearch(ckh
, searchkey
);
491 if (cell
!= SIZE_T_MAX
) {
493 *key
= (void *)ckh
->tab
[cell
].key
;
495 *data
= (void *)ckh
->tab
[cell
].data
;
496 ckh
->tab
[cell
].key
= NULL
;
497 ckh
->tab
[cell
].data
= NULL
; /* Not necessary. */
500 /* Try to halve the table if it is less than 1/4 full. */
501 if (ckh
->count
< (ZU(1) << (ckh
->lg_curbuckets
502 + LG_CKH_BUCKET_CELLS
- 2)) && ckh
->lg_curbuckets
503 > ckh
->lg_minbuckets
) {
504 /* Ignore error due to OOM. */
505 ckh_shrink(tsd
, ckh
);
515 ckh_search(ckh_t
*ckh
, const void *searchkey
, void **key
, void **data
)
521 cell
= ckh_isearch(ckh
, searchkey
);
522 if (cell
!= SIZE_T_MAX
) {
524 *key
= (void *)ckh
->tab
[cell
].key
;
526 *data
= (void *)ckh
->tab
[cell
].data
;
534 ckh_string_hash(const void *key
, size_t r_hash
[2])
537 hash(key
, strlen((const char *)key
), 0x94122f33U
, r_hash
);
541 ckh_string_keycomp(const void *k1
, const void *k2
)
547 return (strcmp((char *)k1
, (char *)k2
) ? false : true);
551 ckh_pointer_hash(const void *key
, size_t r_hash
[2])
558 assert(sizeof(u
.v
) == sizeof(u
.i
));
560 hash(&u
.i
, sizeof(u
.i
), 0xd983396eU
, r_hash
);
564 ckh_pointer_keycomp(const void *k1
, const void *k2
)
567 return ((k1
== k2
) ? true : false);