Multithreaded swapping of array's elements

Question

I have to shuffle an array by swapping random index elements in parallel. My question is how to prevent other threads from reading and writing elements that are currently being swapped by another thread. I don't want to lock the entire array while one thread is swapping.

I would like to let couple threads swapping different pairs o elements in the same time.

I tried something like this :

        object[] lockArray = new object[array.Length];
        for (int i = 0; i < array.Length; i++)
            lockArray[i] = new object();

        for (int i = 0; i < thredCount; i++)
        {
            Thread t = new Thread(th => Shuffle.Shuflle(array,lockArray));
            t.Start();
        }

        public class Shuffle
        {
            public static void Shuflle(char[] array,object [] lockArray)
            {
                    for (int count = array.Length - 1; count > 1; count--)
                    {
                        Random rand = new Random();
                        int y = rand.Next(count) + 1;

                        lock (lockArray[count])
                        {
                            lock (lockArray[y])
                            {
                                char temp = array[count];
                                array[count] = array[y];
                                array[y] = temp;
                            }
                        }


                    }
            }
        }

In the array there are digits as chars from 0 to 9, the result is reordered digits. But sometimes I get result with one doubled ex. 138952469. 9 is now doubled in shuffled array and 7 is missing.

Please help me diagnose the problem.

Answer 1

What about not using locks at all:

private void OptimisticalSwap(object[] arr, int i, int j, object sentinel, SpinWait spinWait)
{
  Interlocked.Increment(ref nSwap);
  if(i == j) return;
  var vi = ExchangeWithSentinel(arr, i, sentinel, spinWait);
  var vj = ExchangeWithSentinel(arr, j, sentinel, spinWait);
  Interlocked.Exchange(ref arr[i], vj);
  Interlocked.Exchange(ref arr[j], vi);
}

private object ExchangeWithSentinel(object[] arr, int i, object sentinel, SpinWait spinWait)
{
  spinWait.Reset();
  while(true) {
    var vi = Interlocked.Exchange(ref arr[i], sentinel);
    if(vi != sentinel) return vi;
    spinWait.SpinOnce();
  }
}

the sentinel is just some dummy object that is shared between all the threads doing swapping and used to "reserve" a position for swapping.

var sentinel = new object();

The runs result on my laptop (i7):

Run 0 took 272ms (nSwap=799984, nConflict=300)
Run 1 took 212ms (nSwap=799984, nConflict=706)
Run 2 took 237ms (nSwap=799984, nConflict=211)
Run 3 took 206ms (nSwap=799984, nConflict=633)
Run 4 took 228ms (nSwap=799984, nConflict=350)

The nConflict is the number of times the swap fails to reserve the position. It is rather low compared to the total number of swaps, so I optimized the routine for the case where there is no conflict only calling the SpinUntil when the conflict occurs.

The whole code I tested against:

[TestClass]
  public class ParallelShuffle
  {
    private int nSwap = 0;
    private int nConflict = 0;
    [TestMethod]
    public void Test()
    {
      const int size = 100000;
      const int thCount = 8;
      var sentinel = new object();
      var array = new object[size];

      for(int i = 0; i < array.Length; i++)
        array[i] = i;

      for(var nRun = 0; nRun < 10; ++nRun) {
        nConflict = 0;
        nSwap = 0;
        var sw = Stopwatch.StartNew();
        var tasks = new Task[thCount];
        for(int i = 0; i < thCount; ++i) {
          tasks[i] = Task.Factory.StartNew(() => {
            var rand = new Random();
            var spinWait = new SpinWait();
            for(var count = array.Length - 1; count > 1; count--) {
              var y = rand.Next(count);
              OptimisticalSwap(array, count, y, sentinel, spinWait);
            }
          }, CancellationToken.None, TaskCreationOptions.LongRunning, TaskScheduler.Default);
        }

        Task.WaitAll(tasks);

        //Console.WriteLine(String.Join(", ", array));
        Console.WriteLine("Run {3} took {0}ms (nSwap={1}, nConflict={2})", sw.ElapsedMilliseconds, nSwap, nConflict, nRun);
        // check for doubles:
        var checkArray = new bool[size];
        for(var i = 0; i < array.Length; ++i) {
          var value = (int) array[i];
          Assert.IsFalse(checkArray[value], "A double! (at {0} = {1})", i, value);
          checkArray[value] = true;
        }
      }
    }


   private void OptimisticalSwap(object[] arr, int i, int j, object sentinel, SpinWait spinWait)
    {
      Interlocked.Increment(ref nSwap);
      if(i == j) return;
      var vi = ExchangeWithSentinel(arr, i, sentinel, spinWait);
      var vj = ExchangeWithSentinel(arr, j, sentinel, spinWait);
      Interlocked.Exchange(ref arr[i], vj);
      Interlocked.Exchange(ref arr[j], vi);
    }

    private object ExchangeWithSentinel(object[] arr, int i, object sentinel, SpinWait spinWait)
    {
      spinWait.Reset();
      while(true) {
        var vi = Interlocked.Exchange(ref arr[i], sentinel);
        if(vi != sentinel) return vi;
        spinWait.SpinOnce();
      }
    }

Answer 2

A simple approach would be to use the Fisher-Yates algorithm to create a list of mappings then lock all operations on the source array while you use the mappings to perform the transposition en-mass. However, this would consume additional resources, would take longer over all and would only marginally reduce the volatile time for the array. You may as well just build a new result somthing like this.

public static IEnumerable<T> Shuffle<T>(
    this IEnumerable<T> source,
    Random random = null)
{
    random = random ?? new Random();
    var list = source.ToList();

    for (int i = list.Length; i > 1; i--)
    {
        // Pick random element to swap.
        int j = random.Next(i); // 0 <= j <= i-1;

        // Swap.
        T tmp = list[j];
        list[j] = list[i - 1];
        list[i - 1] = tmp;
    }

    return list;
}

and do

var shuffler = new Task<char[]>(() => return array.Shuffle().ToArray());
array = shuffler.Result;

If you want to shuffle on multiple threads you'll need a different algorithm and a large source to make it worth it.

Answer 3

Just out of curiosity, why do you want to allow multiple threads to swap in parallel? Swapping should not take very long, so locking the whole array for the duration of the swap is likely much faster than any attempt to lock on individual elements.

That said, if you really want to do parallel shuffling, you might be better off doing this:

1. Shuffle each half of an array with separate threads (they can't conflict).
2. Do a 'perfect shuffle' on the array (i.e. interleave the elements from the two sides; see Faro Shuffle for more information.)
3. Shuffle each half of the array again.

You can generalize this to four parts if you want to do four threads worth of shuffling. That said, a 'swap' would have to be a very slow operation in order for there to be any performance benefit from doing this.