File BucketCuckooTable.h

↰ Parent directory (ADS/dictionary)

The cuckoo hashing with buckets of 4 places and a search in breadth of Li, Andersen, Kaminsky and Freedman (the table of MemC3 and libcuckoo), beyond the book: the engineered cuckoo table of Namespace ADS [see File CuckooHashing.h for the cuckoo hashing of Pagh and Rodler, one key per place].

Definition (ADS/dictionary/BucketCuckooTable.h)

Detailed Description

A key with the hash h may be in any of the 4 places of two buckets, so that a search looks at 8 places in the worst case, and the table reaches a load of 95 % and more before an insertion fails, against less than 50 % with one key per place.

Each place has a tag of 8 bits, 0 when empty and otherwise 8 bits of the hash of its key (1 in place of 0); the 4 tags of a bucket are a word of 32 bits, compared with the tag of a key all at once by broadword operations, so that a key is compared only in the places whose tag matches. The first bucket of a key is given by the top bits of h, the second by the first and the tag, :math:` b_2 = b_1 oplus ( g( t ) wedge ( B - 1 ) vee 1 ) ` for B buckets (a power of 2) and a mixing g of the tag (the partial-key cuckoo hashing of MemC3), an involution, so that a key moves to its other bucket with no need to hash it again.

An insertion puts a new key in a free place of its two buckets if any; otherwise it searches in breadth, from the places of its buckets, a path of at most 5 moves that ends in a bucket with a free place (each key of a bucket of the path moving to its other bucket), and moves the keys along it from the end, so that the new key takes the first place of the path. The search in breadth finds a shorter path than the random walk of the cuckoo hashing, and moves fewer keys. When no path is found within 5 moves and 1024 buckets (or past the load of 98 %), the table doubles and every key is placed again, which costs O( 1 ) amortized per insertion; when the hash of a key reads memory that the key points to, as for the strings, the doubling hashes all the keys first, prefetching the memory of the key 8 places ahead, and then places them, prefetching the first bucket of the key 8 places ahead, so that the misses of the keys overlap. A removal clears the tag of the place.

The iterators visit the pairs in the order of the places, as constant pairs of references ( key , value ); find() gives a value to change in place. An insertion of a new key may move other keys and invalidates the iterators; a removal keeps them valid but the one on the removed pair.

The hash of a key is h( k ), taken as it is if H declares is_avalanching [see File FastHash.h] and mixed by hashWord() otherwise. The keys and the values must be default constructible and movable.

The contracts [see File Contract.h]: after insert() the key is in the table and after remove() it is not; the invariant is that each key is in one of its two buckets with its tag, and that the tags count the pairs, checked on the buckets of the key of the operation only past 1024 places. The operations are defined in BucketCuckooTable.tpp.

  1. Li, D. G. Andersen, M. Kaminsky, M. J. Freedman, Algorithmic improvements for fast concurrent cuckoo hashing, Proceedings of EuroSys 2014, 27, 2014, doi:10.1145/2592798.2592820

  1. Fan, D. G. Andersen, M. Kaminsky, MemC3: compact and concurrent MemCache with dumber caching and smarter hashing, Proceedings of NSDI 2013, 371-384, 2013 (the partial-key cuckoo hashing)

  1. Dietzfelbinger, C. Weidling, Balanced allocation and dictionaries with tightly packed constant size bins, Theoretical Computer Science 380(1-2), 47-68, 2007 (the buckets of several places)

  1. Chen, A. Ailamaki, P. B. Gibbons, T. C. Mowry, Improving hash join performance through prefetching, Proceedings of ICDE 2004, 116-127, 2004, doi:10.1109/ICDE.2004.1319989 (the prefetch of the memory of the keys some keys ahead, in the doubling)

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Classes