how to use openmp with a break in a while-loop

Question

I want to use openmp to accelerate the code like below.

The code is just to explain the operations, not real.

Iterator iterator(records);
while(iterator.next())
{
    int current_id = iterator.current_row_index();
    bool result = index.find(records[current_id])
    if (result == false)
        if (index.insert(records[current_id]) == false)
            break;
}
return iterator.current_row_index();

The index is shared by all the threads.

Here are some thoughts from me:

using omp parallel directive, ensure the threads run in order.
using omp critical directive to operate iterator.
using omp critical directive to find in index and insert into index.

but I really doubt the speedup since almost all the operation are in critical.

Is there some advice to speedup the code using openmp?

Thanks!

is the Iterator only a forward iterator? Can it be used as random-access iterator? — Anton
@Anton it's only a forward iterator now, but i could modified it to support backward. but it can not be random-access. And i prefer not to modify the iterator code. — b8flowerfire
Do you want to stop at the first index that a serial while loop would have found or at any index? — Walter
@Walter I want to stop at the first time. Because we need the breaking index to return. — b8flowerfire

Anton Anton · Accepted Answer · 2014-09-12T11:35:49

Answering the title of the question and assuming there were no other problems (discussed below), a general while-loop with a break over a forward iterator can be translated like this:

Iterator iterator(records);
#pragma omp parallel
{
    #pragma omp single nowait
    {
        while(iterator.next())
        {
            int current_id = iterator.current_row_index();
            #pragma omp task firstprivate(current_id)
            {
                if ( should_stop(current_id)) ) {
                    // below requires OpenMP 4.0
                    #pragma omp cancel parallel
                }
            }
        }
    }
}

However, there are more complex problems in your question which would actually deserve separate questions.

usage of the index table suggests that it is not thread-safe. So, you cannot safely access it and insert concurrently. And since it is the only work for the while-loop, there is no sense making it parallel unless you switch to concurrent hash table like concurrent_unordered_map provided in e.g. tbb, ppl, boost
It is not clear when insert can return false and why you need the index of the row when it happens. Probably, after switching to another table implementation, it would be unnecessary at all. Otherwise generally, several threads can have an 'answer' to your condition simultaneously and you have to synchronize them and reduce to a single result. The simplest OMP-ish way is to use a critical section in order to select and store the result, otherwise, there is a danger of introducing a race-condition to the program.

how to use openmp with a break in a while-loop

1 Answers