Intel® oneAPI Threading Building Blocks
Ask questions and share information about adding parallelism to your applications when using this threading library.

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

David_M_6
Beginner
272 Views

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?)

0 Kudos
2 Replies
David_M_6
Beginner
272 Views

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?

0 Kudos
jimdempseyatthecove
Honored Contributor III
272 Views
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

0 Kudos
Reply