parallel_for to test whether a property holds for at least one element of an array

parallel_for to test whether a property holds for at least one element of an array

In sequential programming, if I want to test whether a property holds for at least one element in an array, I can do:

for(auto x : container) {
  if (property(x)) return true;
}
return false;

Using a TBB parallel_for, I can iterate over all elements in a container and set a variable (initialized to false) to true if the property is satisfied. Yet this seems sub-optimal: if this variable becomes true, we still examine all remaining elements.

One way would be to test, in the leaf tasks, whether the variable is true and return immediately if it is. Yet this still involves the creation of task subtrees for nothing.

What is the "right way" to implement this?

(One could also use a parallel_reduce, with an "or" associative operation. Is there a way to specify that "true" is an absorbing element for the operation?)

3 posts / 0 new
Last post
For more complete information about compiler optimizations, see our Optimization Notice.

One solution seems to call

 tbb::task::self().cancel_group_execution();

after detecting an element satisfying the property and setting the appropriate flag to true.

Is this the "correct" way?

atomic<bool> ret = false;
for(auto x : container) {
  if (property(x)) ret = true;
  if(ret) break; // even if other threads finds property of interest
}
return ret;

Note, the above does not return the location of the property. I will leave you to write in that detail.

Jim Dempsey

Leave a Comment

Please sign in to add a comment. Not a member? Join today