3 ms·

I am aware that using buckets the way you have described works fine for the cuckoo hashing collision resolution technique. But it would not help to ensure the s

I am aware that using buckets the way you have described works fine for the cuckoo hashing collision resolution technique. But it would not help to ensure the same kind of locality of memory references as you would get using the linear probing. I do not know what exactly the commenter meant by suggesting to use buckets. I assumed (as the conversation is predominantly about the locality of memory references) that they suggested to use buckets in order to avoid two (or more) cache misses. And I just pointed out that it would be a bad trade-off, because then the cuckoo algorithm would only operate within a bucket and the expected load factors would be low.

nkurz 10y ago
And I just pointed out that it would be a bad trade-off, because then the cuckoo algorithm would only operate within a bucket and the expected load factors would be low. Like 'cmurphycode', I think you might be misinterpreting something about how the buckets would be used. The buckets are in addition to the multiple hashes (which I think some authors call 'ways'). A good number of buckets would those sufficient to fill 1 or 2 cachelines, since these are going to already be fetched from memory as a unit. The idea is that you fetch the full buckets from 2 (or more) independent hashes, and then sift through them linearly without further memory accesses. The terminology for cuckoo hashes is poor, but I think "buckets", "bins", and "slots" are all synonyms depending on whose description you are using. By "using buckets", the idea is to have (at least) two regions in consecutive memory where the item will be if it exists. I think this paper offers a reasonable terminology: http://www.cs.princeton.edu/~xl/Publications_files/cuckoo-eurosys14.pdf http://www.cs.princeton.edu/~xl/Publications_files/cuckoo-eu.... They use a "num_hashes, num_buckets" pair to describe variations. The classic version is a "2,1-cuckoo": you create two hashes from the key, and look in one bucket in each location. Li et al. suggest that a "2,4-cuckoo" works allows much easier insertions at high density.
- pbasista 10y ago
  > The idea is that you fetch the full buckets from 2 (or more) independent hashes, and then sift through them linearly without further memory accesses Maybe. How do you know what the commenter (erichocean) meant? If they say that using "buckets" can mean the same locality of memory references as linear probing, their interpretation of what "buckets" mean must deal with that problem in some way.
  - nkurz 10y ago
    > How do you know what the commenter (erichocean) meant? Because "bucket" is a well-defined term-of-the-art with regard to cuckoo hashes, because Erich has demonstrated deep knowledge of similar algorithms in the past, because I've been thinking about improving the memory locality of cuckoo hashes for years, and because I would have used approximately the same phrasing as Erich did to describe the memory locality advantages of "buckets". If they say that using "buckets" can mean the same locality of memory references as linear probing, their interpretation of what "buckets" mean must deal with that problem in some way. Not only do buckets "deal" with locality, because of the granular nature of cachelines and parallel abilities of memory controllers, searching two compact small regions turns out to be just as searching one region of twice the size. Vectorized linear probing and SIMD cuckoo hashes are so similar that your question very likely indicates that you are not using the same terminology as others are. Here's paper that offers a good comparison: Rethinking SIMD Vectorization for In-Memory Databases Polychroniou, Roghaven, and Ross (2015) http://www.cs.columbia.edu/~orestis/sigmod15.pdf http://www.cs.columbia.edu/~orestis/sigmod15.pdf

nkurz 10y ago

And I just pointed out that it would be a bad trade-off, because then the cuckoo algorithm would only operate within a bucket and the expected load factors would be low. Like 'cmurphycode', I think you might be misinterpreting something about how the buckets would be used. The buckets are in addition to the multiple hashes (which I think some authors call 'ways'). A good number of buckets would those sufficient to fill 1 or 2 cachelines, since these are going to already be fetched from memory as a unit. The idea is that you fetch the full buckets from 2 (or more) independent hashes, and then sift through them linearly without further memory accesses. The terminology for cuckoo hashes is poor, but I think "buckets", "bins", and "slots" are all synonyms depending on whose description you are using. By "using buckets", the idea is to have (at least) two regions in consecutive memory where the item will be if it exists. I think this paper offers a reasonable terminology: http://www.cs.princeton.edu/~xl/Publications_files/cuckoo-eurosys14.pdf http://www.cs.princeton.edu/~xl/Publications_files/cuckoo-eu.... They use a "num_hashes, num_buckets" pair to describe variations. The classic version is a "2,1-cuckoo": you create two hashes from the key, and look in one bucket in each location. Li et al. suggest that a "2,4-cuckoo" works allows much easier insertions at high density.

pbasista 10y ago
> The idea is that you fetch the full buckets from 2 (or more) independent hashes, and then sift through them linearly without further memory accesses Maybe. How do you know what the commenter (erichocean) meant? If they say that using "buckets" can mean the same locality of memory references as linear probing, their interpretation of what "buckets" mean must deal with that problem in some way.
- nkurz 10y ago
  > How do you know what the commenter (erichocean) meant? Because "bucket" is a well-defined term-of-the-art with regard to cuckoo hashes, because Erich has demonstrated deep knowledge of similar algorithms in the past, because I've been thinking about improving the memory locality of cuckoo hashes for years, and because I would have used approximately the same phrasing as Erich did to describe the memory locality advantages of "buckets". If they say that using "buckets" can mean the same locality of memory references as linear probing, their interpretation of what "buckets" mean must deal with that problem in some way. Not only do buckets "deal" with locality, because of the granular nature of cachelines and parallel abilities of memory controllers, searching two compact small regions turns out to be just as searching one region of twice the size. Vectorized linear probing and SIMD cuckoo hashes are so similar that your question very likely indicates that you are not using the same terminology as others are. Here's paper that offers a good comparison: Rethinking SIMD Vectorization for In-Memory Databases Polychroniou, Roghaven, and Ross (2015) http://www.cs.columbia.edu/~orestis/sigmod15.pdf http://www.cs.columbia.edu/~orestis/sigmod15.pdf