How to support local random sampling from containers?

[bwpriest]

We have discussed two container sampling primitives:

1. global random sampling (a prototype of which Roger has already implemented as a part of another workflow), and
2. local random sampling.

The purpose of this thread is to discuss 2. I believe that we landed upon the consensus that we should organize this and related workflows with adapter classes that wrap the for_all method of the container from which we are sampling, allowing us to pass in a function that is only executed on a randomly sampled set of locally-held elements. This would result in an interface like

...
ygm::default_random_engine<> rng(my_container.comm(), seed);
ygm::local_sample_adapter sampler(my_container, rng);
// Do that function execution on 500 samples
sampler.for_all(
  500, [](key_type key, value_type &val) { \* do something *\}
);

Is this the desired interface? If so, we need to be able to loop over local containers outside of the container classes in order to apply the function to only sampled objects. The same issue applies to any filtering adapter that we might create in the future, and in fact we can probably cast local_sample_adapter as a special type of filtering adapter.

My initial approach here is to add some methods to the relevant containers that return their local begin and end iterators. However, doing so is dangerous and so they should probably be protected and adapter classes declared as friends, or something similar. This would allow for_all adapters to get begin and end iterators and then do whatever with them, without requiring the adapter to actually know the contents of the objects. Does this make sense? Is there a better or more general approach that we should take?

[rogerpearce]

My first thought is do we really need to randomly sample from all containers generically? The performance will vary greatly between them, and efficient implementation may also need to be data structure specific. For example:

• ygm::bag should be able to local sample in O( # samples ) time
• ygm::map and ygm::set will be O( N ), assuming # samples < N

I'm not a fan of local_begin() and local_end(), because that forces future designed data structures to support iterators. But, I agree that this would be necessary for a generic sampler.for_all() approach.

[bwpriest]

I concur with this assessment. I was operating under the assumption that we wanted a fully generic adapter implementation, but such an approach will be suboptimal compared to independently implemented member functions for some containers.

[rogerpearce]

If we do want to be able to do this with all containers, what if we added the following interfaces to all containers:

• for_random( k, rng, lambda) where k are sampled globally
• for_random_local( k, rng, lambda) where k are sampled locally and each rank generates their own random samples.

I am skeptical that the "local" version is better in any way because the setup for global sampling (prefix_sum) is basically the same cost as a barrier which would need to be done anyways.

These could be wrapped in a for_all adapter if needed for a workflow.

[bwpriest]

ok sounds good. I'll work on supporting member functions rather than a generic for_all adapter.