[FEA] New probing scheme concept

[sleeepyjack]

Part of #110 (Refactor of open address data structures)

Development branch: NVIDIA/cuCollections/refactor

Synopsis

Given a key k, a probing sequence provides a sequence of N potentially non-contiguous locations (or values) [i0, i1, i2, ... iN, EMPTY_SENTINEL] where if k exists it is present in [i0, iN].

TODOs

• Implement classes cuco::probing_schemes::linear_probing and cuco::probing_schemes::double_hashing
• Provide an option for windowed, i.e., vectorized probing via customization point object
• Enable cooperative probing

Backlog

• Use C++20-style ranges with sentinels

References

• https://godbolt.org/z/9bosKoW4v (distinct "ProbingScheme" and "Storage" concepts)
• https://godbolt.org/z/Maxe7j1o4 (probe iterator)
• https://godbolt.org/z/557fjcvvE (equality wrapper)

[PointKernel]

Notes from previous discussions:

• Related blog: https://www.foonathan.net/2020/03/iterator-sentinel/

• iterator sentinel with custom range

for(auto slot_content : custom_range(Probe(key))){
   ...
   if (match(slot_content, key)) return true;
}
return false; // reach end() thus no match

• CG custom range

   for(auto&& slot : cooperative_slot_range(g, k){ // slot is unique on each thread
       if(g.any( equals(slot, k) )){ return true; }

       // The evaluation against `end()` will involve another ballot to see if any thread in the group
       // hit an "EMPTY" slot that indicates the whole group should exit 
   } 
   return false;

• @sleeepyjack's Initial idea of putting all the logic for checking the probing conditions in the iterator: https://godbolt.org/z/E6hKadTxe

[PointKernel]

Distincting probing scheme and storage:

• Probing scheme provides int-type indices
• Storage provides a pointer to the storage
• Probing scheme should be a callable object

https://godbolt.org/z/n8rrxer47

[jrhemstad]

I find it to be a really helpful exercise to write the concept for a type as a way to really force you to think about what it's bare minimum requirements are.

Here's what I came up with for a probing scheme: https://godbolt.org/z/Ka8ehn1j5

This is incomplete. We still need some way to reflect the window size / access.

[PointKernel]

CG, range, and probing iterators: https://godbolt.org/z/a1hqvErfv 🔥 🔥 🔥