Parallel.ForEach search doesn't find the correct value-CodePudding

This is my first attempt at parallel programming.

I'm writing a test console app before using this in my real app and I can't seem to get it right. When I run this, the parallel search is always faster than the sequential one, but the parallel search never finds the correct value. What am I doing wrong?

I tried it without using a partitioner (just Parallel.For); it was slower than the sequential loop and gave the wrong number. I saw a Microsoft doc that said for simple computations, using Partitioner.Create can speed things up. So I tried that but still got the wrong values. Then I saw Interlocked, but I think I'm using it wrong.

Any help would be greatly appreciated

Random r = new Random();
Stopwatch timer = new Stopwatch();

do {
    // Make and populate a list
    List<short> test = new List<short>();
    for (int x = 0; x <= 10000000; x  )
    {
        test.Add((short)(r.Next(short.MaxValue) * r.NextDouble()));
    }

    // Initialize result variables
    short rMin = short.MaxValue;
    short rMax = 0;

    // Do min/max normal search
    timer.Start();
    foreach (var amp in test)
    {
        rMin = Math.Min(rMin, amp);
        rMax = Math.Max(rMax, amp);
    }
    timer.Stop();

    // Display results
    Console.WriteLine($"rMin: {rMin}  rMax: {rMax}  Time: {timer.ElapsedMilliseconds}");

    // Initialize parallel result variables
    short pMin = short.MaxValue;
    short pMax = 0;

    // Create list partioner
    var rangePortioner = Partitioner.Create(0, test.Count);

    // Do min/max parallel search
    timer.Restart();
    Parallel.ForEach(rangePortioner, (range, loop) =>
    {
        short min = short.MaxValue;
        short max = 0;

        for (int i = range.Item1; i < range.Item2; i  )
        {
            min = Math.Min(min, test[i]);
            max = Math.Max(max, test[i]);
        }
        _ = Interlocked.Exchange(ref Unsafe.As<short, int>(ref pMin), Math.Min(pMin, min));
        _ = Interlocked.Exchange(ref Unsafe.As<short, int>(ref pMax), Math.Max(pMax, max));

    });
    timer.Stop();

    // Display results
    Console.WriteLine($"pMin: {pMin}  pMax: {pMax}  Time: {timer.ElapsedMilliseconds}");


    Console.WriteLine("Press enter to run again; any other key to quit");
} while (Console.ReadKey().Key == ConsoleKey.Enter);

Sample output:

rMin: 0  rMax: 32746  Time: 106
pMin: 0  pMax: 32679  Time: 66
Press enter to run again; any other key to quit

CodePudding user response：

The correct way to do a parallel search like this is to compute local values for each thread used, and then merge the values at the end. This ensures that synchronization is only needed at the final phase:

var items = Enumerable.Range(0, 10000).ToList();

int globalMin = int.MaxValue;
int globalMax = int.MinValue;
Parallel.ForEach<int, (int Min, int Max)>(
    items, 
    () => (int.MaxValue, int.MinValue), // Create new min/max values for each thread used
    (item, state, localMinMax) =>
{
    var localMin = Math.Min(item, localMinMax.Min);
    var localMax = Math.Max(item, localMinMax.Max);
    return (localMin, localMax); // return the new min/max values for this thread
},
localMinMax => // called one last time for each thread used
{
    lock(items) // Since this may run concurrently, synchronization is needed
    {
        globalMin = Math.Min(globalMin, localMinMax.Min);
        globalMax = Math.Max(globalMax, localMinMax.Max);
    }
});

As you can see this is quite a bit more complex than a regular loop, and this is not even doing anything fancy like partitioning.

Be aware that multi threaded programming is difficult. While it is a great idea to try out such techniques in a playground rather than a real program, I would still suggest that you should start by studying the potential dangers of thread safety, there is fairly easy to find good resources about this.

Not all problems will be as obviously wrong like this, and it is quite easy to cause issues that breaks once in a million, or only when the cpu load is high, or only on single CPU systems, or issues that are only detected long after the code is put into production. It is a good practice to be paranoid whenever multiple threads may read and write the same memory concurrently.

I would also recommend learning about immutable data types, and pure functions, since these are much safer and easier to reason about once multiple threads are involved.

CodePudding user response：

Interlocked.Exchange is thread safe only for Exchange, every Math.Min and Math.Max can be with race condition. You should compute min/max for every batch separately and then join results.

CodePudding user response：

Using low-lock techniques like the Interlocked class is tricky and advanced. Taking into consideration that your experience in multithreading is not excessive, I would say go with a simple and trusty lock:

object locker = new object();

//...

lock (locker)
{
    pMin = Math.Min(pMin, min);
    pMax = Math.Max(pMax, max);
}