Array of structs, multithreading, can I write at the same time to different indexes?

Question

Hi

I have an huge array which contains a struct "Tile". The program im writing is a 2D game, and I don't want different players (handled by different threads) to write their position to the same tile at the same time, and I wondered two things. Can two threads write to two different places in the array at the same time safely, and is there some effective way to lock only one index of this array?

Answer 1

Yes, you can write to different positions simultaneously from different threads.

To do the locking, you should create an array of locks, and use some simple hashing technique to choose a lock, based on the position being written. For instance:

class TileArray
{
    private static readonly int numLocks = 16;
    private object[] locks = (from i in Range(0, numLocks) select new object()).ToArray();
    private Tile[] tiles = hugeTileArray();

    ...

    public Tile this[int i]
    {
        get { return tiles[i]; }
        set
        {
            lock (locks[i % numLocks])
                tiles[i] = value;
        }
    }
}

This avoids the need to create zillions of locks, but still keeps lock-contention to a minimum. You can set numLocks up or down, based on profiling. Keep it a power of two, though, for an efficient modulo computation.

One final minutiae: beware of aliasing effects. For instance, multiple-of-16 positions might happen to be very popular with your threads for some odd reason, in which case, contention will go through the roof. If this is the case, you'll need a stronger hash. Perhaps (uint)i.GetHashCode() % numLocks will do, but I'm not sure what Int32.GetHashCode does; it might just return the number itself. Failing this, you can steal one from Bob Jenkins.

Answer 2

There is no built-in support for what you want to do. Multiple threads can access the same array at the same time, but you'd need to take care of data consistency yourself by means of synchronization or so. Therefore, while it is possible to implement per-index locking (which is similar to what a database does in a transaction), I'm not sure that this is the right approach for what you're trying to do. Why are you using an array to start with?

Answer 3

I believe you can use the lock statement to make the code thread safe which is accessing the array and is shared between the threads.

Answer 4

You can use the Interlocked.CompareExchange function to do the read and write safely without the explicit use of locks.

public class Example
{
  private Tile[] m_Array;

  public Tile this[int index]
  {
    get { return Interlocked.CompareExchange(ref m_Array[i], null, null); }
    set { Interlocked.CompareExchange(ref m_Array[i], value, m_Array[i]); }
  }
}

Of course you will have to convert your Tile struct to a class to be able to do this.