PLINQ AsParallel().ForAll() accessing resource

Question

Suppose I have a number of Particles in X,Y space, and I want to normalise them all such that the average X and Y are 0.

Serial implementation:

public void Normalise()
{
  double avgX = 0.0;
  double avgY = 0.0;

  foreach (Particle p in Particles)
  {
    avgX += p.X;
    avgY += p.Y;
  }

  avgX /= (double)Particles.Count;
  avgY /= (double)Particles.Count;

  foreach (Particle p in Particles)
  {
    p.X -= avgX;
    p.Y -= avgY;
  }
}

This works, and the performance is not bad since it's O(n), but it's "embarrassingly parallel". Take a look at my PLINQ implementation:

public void PNormalise()
{
  double avgX = 0.0;
  double avgY = 0.0;

  Particles.AsParallel().ForAll(p =>
  {
    avgX += p.X;
    avgY += p.Y;
  });

  avgX /= (double)Particles.Count;
  avgY /= (double)Particles.Count;

  Particles.AsParallel().ForAll(p =>
  {
    p.X -= avgX;
    p.Y -= avgY;
  });
}

I'm not sure about the performance here, but I would imagine it's better. The problem is, the particles are all jumping around randomly. I can only assume that the += operations on avgX and avgY are competing against each other, even though they're fairly atomic already.

Is there anything I can do to fix it? I can't lock them because they're not objects, but I'm not sure I'd want to anyway because isn't locking quite expensive?

Answer 1

You can bypass the need for a lock (or atomic operations) via the normal machinery of Parallel LINQ:

var avgX = Particles.AsParallel().Average(p => p.X);
var avgY = Particles.AsParallel().Average(p => p.Y);

Particles.AsParallel().ForAll(p => { p.X -= avgX; p.Y -= avgY });

Since summing the numbers is an O(N) operation, I would be extremely surprised if this part took any significant portion of time.

Answer 2

Use

Particles.AsParallel().ForAll(p =>
{
    Interlocked.Add(avgX, p.X);
    Interlocked.Add(avgY, p.Y);
}

to do a thread-safe atomic addition. For more information see the documentation of the Interlocked Class.

Answer 3

Actually, parallelizing this O(n)-Algorithm won't result in a much better Performance, since you have roughly the same amount of memory accesses as computational instructions.