parallel-for over concurrent hash map

[jacopol]

Hi, I want to do a parallel-for-loop (with OpenMP), iterating over the contents of a (concurrent) hash map. In std::unordered_set one cannot write the following, since parallel-for needs a random-access iterator.

    #pragma omp parallel for
    for (auto m : current) { ... }

Instead, one can write the following, which is good enough:

    #pragma omp parallel for
    for (size_t b=0; b<current.bucket_count(); b++)
    for (auto m=current.begin(b); m!=current.end(b); m++) { ... }

Here the outer parallel-loop iterates over all buckets (random access), while the inner, sequential loop iterates over all elements in a given bucket.

Problem: it seems I cannot do the same in libcuckoo. I can get a sequential iterator over a locked_table, but this wouldn't have random access. I couldn't find a way to get access to and iterate over the elements in a particular given bucket b; (i.e., current.begin(b) doesn't work, even not if current is locked_table). Is there a way to achieve this? Or is it easy to extend the libcuckoo API with this functionality?

[manugoyal]

Hi @jacopol, good question! This should be fairly easy to support in the existing libcuckoo API. The locked table iterator state is basically (bucket_index, bucket_slot_index) (https://github.com/efficient/libcuckoo/blob/88bb6e2ca1b68572f66e3e2bea071829652afeb2/libcuckoo/cuckoohash_map.hh#L2263), so it should be straightforward to support a locked_table.begin/end which accepts a bucket index.

If you're willing to submit a PR yourself, that'd be great. Otherwise I can probably get around to it in the next few weekends. Probably most of the work would go into supporting a clean interface (iterator can't go beyond the range of the bucket) and writing some unit tests.