What's the standard approach to making calculations thread-safe?

Question

What initially seemed like a problem with an easy solution has proven to be quite an interesting challenge.

I have a class which maintains an internally fixed-size, thread-safe collection (by way of using lock on all insertion and removal operations) and provides various statistical values via its properties.

One example:

public double StandardDeviation {
    get {
        return Math.Sqrt((Sum2 - ((Sum * Sum) / Count)) / Count);
    }
}

Now, I've tested this computation thoroughly, running 10,000 values through the collection and checking the standard deviation on each update. It works fine... in a single-threaded scenario.

A problem arises in the multi-threaded context of our development and production environments, however. It seems that this number is somehow sometimes coming back NaN before quickly changing back to a real number. Naturally this must be due to a negative value passed to Math.Sqrt. I can only imagine this happens when, mid-calculation, one of the values used in the calculation is updated by a separate thread.

I could cache the values first:

int C = this.Count;
double S = this.Sum;
double S2 = this.Sum2;

return Math.Sqrt((S2 - (S * S) / C) / C);

But then Sum2 might still be updated, for example, after S = this.Sum has been set, compromising the calculation once again.

I could put a lock around all points in the code where these values are updated:

protected void ItemAdded(double item) {
    // ...

    lock (this.CalculationLock) {
        this.Sum += item;
        this.Sum2 += (item * item);
    }
}

Then if I lock on this same object when calculating StandardDeviation, I thought that would, finally, fix the problem. It didn't. The value is still coming in as NaN on a fleeting, infrequent basis.

Frankly, even if the above solution had worked, it was very messy and did not seem very manageable to me. Is there a standard and/or more straightforward way of achieving thread-safety in calculated values such as this?

---

EDIT: Turns out here we have an example of a problem where it seemed at first like there was only one possible explanation when, after all, the issue was with something else entirely.

I had been meticulous about implementing thread safety in every way I could without making a huge performance sacrifice if at all possible -- locking on reads and writes to shared values (e.g., Sum and Count), caching values locally, and using the same lock object for modifying the collection and updating the shared values... honestly, it all seemed like overkill.

Nothing worked; that nefarious NaN kept popping up. So I decided to print all the values in the collection to the console whenever StandardDeviation returned NaN...

Immediately I noticed that it always seemed to be happening when all the values in the collection were the same.

It's official: I got burned by floating point arithmetic. (All of the values were the same, so the radicand in StandardDeviation -- i.e., the number whose square root is being taken -- was being evaluated to some extremely small negative number.)

Answer 1

You can add a lock in your StandardDeviation method to ensure that values are not changed.

public double StandardDeviation
{
  get
  {
    lock (_lockObject)
    {
       return Math.Sqrt((Sum2 - ((Sum * Sum) / Count)) / Count);
    }
  }
}

Answer 2

You can cache the entire list and then operate with the cached version. Something like this:

var copy = currentList.ToArray();
var sum = Sum(copy)
var sum2 = Sum2(copy)
return sum * sum2... whatever

This way, you only need to hold the lock while the copy (.ToArray, in the sample) is being performed, and you have a consistent set of data to operate with. Of course, depending on the size of your data the memory requirements or the performance penalty can be too much.

Answer 3

Sum and Count are state that is shared across multiple threads. As such, all accesses must be synchronized, unless you (a) have some atomic variable primitive and (b) are very, very careful.

The simplest and most 'standard' approach is to use the same lock you use for synchronizing insertions and removals. As you add or remove, update Sum and Count. Then use that same lock to synchronize access to Sum and Count in the StandardDeviation function.

Answer 4

If, as you've mentioned in comments, performance is a high priority here, you should consider synchronizing all access to the object's underlying data with a ReaderWriterLockSlim (or the older ReaderWriterLock if you're using the 2.0 Framework) instead of a Monitor (via lock statements), so that calculations do not block one another.

You should also consider testing an implementation that caches the data as some have suggested: it may actually be faster than a version that synchronizes access to the variables.

Answer 5

I could put a lock around all points in the code where these values are updated:

protected void ItemAdded(double item) {
    // ...

    lock (this.CalculationLock) {
        this.Sum += item;
        this.Sum2 += (item * item);
    }
}

Then if I lock on this same object when calculating StandardDeviation, I thought that would, finally, fix the problem. It didn't. The value is still coming in as NaN on a fleeting, infrequent basis.

That's exactly what you should do for correctness. If that's not working for you, I'd suggest that either you missed an update scenario - or you have some other issue (like Sum or Sum2 occasionally being NaN or an unexpected value because of some other race condition).