In my application, i currently make many (parallel) calculations based on a time parameter. The calculation is a parametric function of time, so, each time value renders a unique solution. Currently, I have many threads that are calling the same calculation function, and the time parameters are often the same. The calculations can take some considerable amount of time.

I want to optimize by adding a hash-table like structure. So, instead of calculating and recalculating for identical times across many threads, I would prefer storing the calculation results in a hash-table keyed by the time. My application currently uses the STL for its containers, so I would like to use the map container.

Now, I know this container is not thread safe, so I am trying to devise a system to wrap the map object to ensure thread safety. I am considering two alternative methods to achieve this. Here is the (untested, uncompiled, just conceptual so far) code for the two methods:

double method0( double t, double (*calculate)(double) ){
    double result;
    omp_set_lock( &mapLock );
    if( calcMap.count(t) == 0 ){
        result = calculate(t);
        calcMap.insert( pair<double,double>( t, result ) );
    }
    else
        result = calcMap[t];
    omp_unset_lock( &mapLock );
    return result;
}

double method1( double t, double (*calculate)(double) ){
    double result;
    if( calcMap.count(t) == 0 ){
        omp_set_lock( &mapLock );
        if( calcMap.count(t) == 0 )
            calcMap.insert( pair<double,double>( t, calculate(t) ) );
        omp_unset_lock( &mapLock );
    }
    return calcMap[t];
}

Now, I think the first method should always work, because all access to the map is guarded by a lock. This is not preferable, though, because it introduces a huge serial bottle-neck that might not be necessary. Parallel reads shouldn't block each other. Also, there should be no reason that the map can't fetch calculations for times 0, 1, 2, and 3 if only 4 is being calculated and then inserted.

The second method would work, but only if the map adds an element as its last step of insert. Namely, as long as the element is allocated and set before it is added to the map, this method should be thread safe.

Does anyone know if I can make any assumptions about thread safety in the std::map class? If not, do you know of a method that is thread-safe and would perform better than my first method?

Thanks

I have decided that instead of doing these calculations on the fly, I will do a pre-processing step first that will do all my calculations for all objects at all time positions. This should relieve any need for thread-safety in these maps.

This question has already been answered. Start a new discussion instead.