OpenMP parallelization and deleting from a vector of lists

Question

Hi, gang. First, a high-level description of the problem & approach.

I have a list containing images and pixel locations in each image - a list of lists. I want to pick n items at random from that list of images and for each image I want to iterate over k random pixel locations. I want to do this in parallel. For each processed pixel, I wish to delete it from the list.

My approach is to distribute the images and pixel lists among all threads - so each thread has its own list of images and lists of pixel locations, but no two threads will be processing the same image at the same time. I store these into a vector.

So let's say the code looks something like this:

struct MyObject
{
  // Image index on disk
  int imageIndex_;
  // List of x,y locations
  std::list< Point > pixels_;
};

std::vector< std::list < MyObject > > mainList(NUM_THREADS);

Then, mainList[0] would contain the images to be processed by thread with id 0. I launch threads the following way: #pragma omp parallel num_threads(numThreads_) and then they all run the same piece of code which samples images randomly from the thread's list of images.

The problem is, when a pixel is processed and a thread erases it from the pixel list, such as mainList[0].begin()->pixels_.erase(someIter), I sometimes get a assertion; it traces to the delete operator.

I know that writing to std::list is not thread-safe, but I was pretty sure that it is safe for a list of lists, where each list in the main list is accessed by one thread only. I know that I provided limited code, but the problem boils down to deleting from a list of lists (or vector of lists) in parallel, when each thread has access to only one list at a time and the lists are not shared between threads.

What am I missing here? Can I not delete from a vector of lists of lists in parallel?

Answer 1

You provided too little info for me to guess the real problem, here are some thoughts:

You seem to access invalidated iterators (i. e. delete one element twice). This can be caused by a race condition OR by a bug in your code that really tries to delete an item more than once. For example - are you sure that the random numbers you generated are unique? Do you apply the modulo operator to the generated random numbers after each element is removed to assure the index is valid?

What I would check first is running the program with OpenMP disabled. Then you can decide if the assertion fails due to a race condition or due to another bug.

On an unrelated note - you might want to use std::vector instead of std::list. You are accessing random elements in the container and std::vector is optimized for random access.