Threads operating on the one instance of a method

Question

I'm creating an app, where I have 50x50 map. On this map I can add dots, which are new instances of the class "dot". Every dot has it's own thread, and every thread connected with a specific dot operates on the method "explore" of the class, and in this method there is another method "check_place(x,y)" which is responsible for checking if some place on the map was already discovered. If not, the static variable of the class "num_discovered" should be incremented. This single instance of the method "check_place(x,y)" should be accessed in the real-time by every thread started in the app.

Constructor:

public dot(Form1 F)
{    
    /...
    thread = new System.Threading.Thread(new System.Threading.ThreadStart(explore)); //wątek wykonujący metodę explore klasy robot
    thread.Start();
}

check_place(x,y) method:

static void check_place(int x, int y)
{
    lock (ob)
    {
        if (discovered[x, y] == false)
        {
            discovered[x, y] = true;
            num_discovered += 1;
        }
    }
}

In the explore method I'm invoking method "check_place(x,y)" like this:

dot.check_place(x, y);

Is it enough to achieve a situation where in the single time only one dot can check if place was already discovered?

Answer 1

Your performance on this could potentially be pretty bad - I recommend using Task.Run here to increase efficiency when you need to run your explore method on multiple threads in parallel.

As far as locking and thread safety, if the lock in check_place is the only place you're setting bools in the discovered variable and setting the num_discovered variable, the existing code will work. If you start setting them from somewhere else in the code, you will need to use locks there as well.

Also, when reading from these variables, you should read these values into local variables inside other locks using the same lock object to maintain thread safety here as well.

I have other suggestions but those are the two most basic things you need here.

Answer 2

Is it enough to achieve a situation where in the single time only one dot can check if place was already discovered?

Yes. But what's the point?

If threads are spending all of their time waiting on other threads, what have you gained from being multi-threaded?

There are three (sometimes overlapping) reasons to spawn more threads:

1. To make use of more than one core at the same time: overall throughput increases.
2. To have work done while another thread is waiting on something else (typically I/O from file, DB or network): overall throughput increases.
3. To respond to user interaction while work is being done: overall throughput decreases, but it feels faster to the user as they are separately being reacted to.

Here the last doesn't apply.

If your "checking" involved I/O then the second might apply, and this strategy might make sense.

The first could well apply, but because all the threads are spending most of their time waiting on other threads, you don't gain an improvement in throughput.

Indeed, because there is overhead involved in setting up threads and switching between them, this code will be slower than just having one thread do everything: If only one thread can work at a time, then only have one thread!

So your use of a lock here is correct in that it prevents corruption and errors, but pointless in that it makes everything too slow.

What to do about this:

If your real case involves I/O or other reasons why the threads in fact spend most of their time out of each others' way, then what you have is fine.

Otherwise you've got two options.

Easy: Just use one thread. Hard: Have finer locking.

One way to have finer locking would be to do double-checking:

static void check_place(int x, int y)
{
  if (!discovered[x, y])
    lock (ob)
      if (!discovered[x, y])
      {
        discovered[x, y] = true;
        num_discovered += 1;
      }
}

Now at the very least some threads will skip past some cases where discovered[x, y] is true without holding up the other threads.

This is useful when a thread is going to get a result at the end of the locked period. Its still not good enough here though, because it's just going to move on quickly to a case were it fights for the lock again.

If our lookup of discovered were itself thread-safe and that thread-safety was finely grained, then we could make some progress:

static void check_place(int x, int y)
{
  if (discovered.SetIfFalse(x, y))
    Interlocked.Increment(ref num_discovered)
}

So far though we've just moved the problem around; how do we make SetIfFalse thread-safe without using a single lock and causing the same problem?

There are a few approaches. We could use striped locks, or low-locking concurrent collections.

It seem that you have a fixed-size structure of 50×50, in which case this isn't too hard:

private class DotMap
{
  //ints because we can't use interlocked with bools
  private int[][] _map = new int[50][];
  public DotMap()
  {
    for(var i = 0; i != 50; ++i)
      _map[i] = new int[50];
  }
  public bool SetIfFalse(int x, int y)
  {
    return Interlocked.CompareExchange(ref _map[x][y], 1, 0) == 0;
  }
}

Now our advantages are:

1. All of our locking is much lower-level (but note that Interlocked operations will still slow down in the face of contention, albeit not as much as lock).
2. Much of our locking is out of the way of other locking. Specifically, that in SetIfFalse can allow for separate areas to be checked without being in each others way at all.

This is neither a panacea though (such approaches still suffer in the face of contention, and also bring their own costs) nor easy to generalise to other cases (changing SetIfFalse to something that does anything more than check and change that single value is not easy). It's still quite likely that even on a machine with a lot of cores this would be slower than the single-threaded approach.

Another possibility is to not have SetIfFalse thread-safe at all, but to ensure that the threads where each partitioned from each other so that they were never going to hit the same values and that the structure is safe in the case of such multi-threaded access (fixed arrays of elements above machine word-size are thread-safe when threads only ever hit different indices, must mutable structures where one can Add and/or Remove are not).

In all, you've got the right idea about how to use lock to keep threads from causing errors, and that is the approach to use 98% of the time when something lends itself well to multithreading because it involves threads waiting on something else. Your example though hits that lock too much to benefit from multiple cores, and creating code that does is not trivial.