C# alternative to lock if volatile isn't a good idea

Question

I'm sorry I know this topic has been done to death (I've read I've read this and this and a few more) but there is one issue I have which I am not sure how to do 'correctly'.

Currently my code for a multithreaded Sudoku strategy is the following:

public class MultithreadedStrategy : ISudokuSolverStrategy
{
    private Sudoku Sudoku;
    private List<Thread> ThreadList = new List<Thread>();
    private Object solvedLocker = new Object();
    private bool _solved;
    public bool Solved // This is slow!
    {
        get
        {
            lock (solvedLocker)
            {
                return _solved;
            }
        }
        set
        {
            lock (solvedLocker)
            {
                _solved = value;
            }
        }
    }
    private int threads;
    private ConcurrentQueue<Node> queue = new ConcurrentQueue<Node>();

    public MultithreadedStrategy(int t)
    {
        threads = t;
        Solved = false;
    }
    public Sudoku Solve(Sudoku sudoku)
    {
        // It seems concevable to me that there may not be
        // a starting point where there is only one option.
        // Therefore we may need to search multiple trees.
        Console.WriteLine("WARNING: This may require a large amount of memory.");
        Sudoku = sudoku;

        //Throw nodes on queue
        int firstPos = Sudoku.FindZero();
        foreach (int i in Sudoku.AvailableNumbers(firstPos))
        {
            Sudoku.Values[firstPos] = i;
            queue.Enqueue(new Node(firstPos, i, false, Sudoku));
        }

        //Setup threads
        for (int i = 0; i < threads; i++)
        {
            ThreadList.Add(new Thread(new ThreadStart(ProcessQueue)));
            ThreadList[i].Name = String.Format("Thread {0}", i + 1);
        }

        //Set them running
        foreach (Thread t in ThreadList)
            t.Start();

        //Wait until solution found (conditional timeout?)
        foreach (Thread t in ThreadList)
            t.Join();

        //Return Sudoku
        return Sudoku;
    }

    public void ProcessQueue()
    {
        Console.WriteLine("{0} running...",Thread.CurrentThread.Name);

        Node currentNode;

        while (!Solved) // ACCESSING Solved IS SLOW FIX ME!
        {
            if (queue.TryDequeue(out currentNode))
            {
                currentNode.GenerateChildrenAndRecordSudoku();

                foreach (Node child in currentNode.Children)
                {
                    queue.Enqueue(child);
                }

                // Only 1 thread will have the solution (no?)
                // so no need to be careful about locking
                if (currentNode.CurrentSudoku.Complete())
                {
                    Sudoku = currentNode.CurrentSudoku;
                    Solved = true;
                }
            }
        }
    }
}

(Yes I have done DFS with and without recursion and using a BFS which is what the above strategy modifies)

I was wondering whether I am allowed to change my private bool _solved; to a private volatile solved; and get rid of the accessors. I think this might be a bad thing because my ProcessQueue() method changes the state of _solved Am I correct? I know booleans are atomic but I don't want compiler optimisations to mess up the order of my read/write statements (esp. since the write only happens once).

Basically the lock statement adds tens of seconds to the run time of this strategy. Without the lock it runs an awful lot faster (although is relatively slow compared to a DFS because of the memory allocation within currentNode.GenerateChildrenAndRecordSudoku()

Answer 1

Before getting into alternatives: it is probably safe to go with a low-lock solution here by making access to the boolean volatile. This situation is ideal, as it is unlikely that you have complex observation-ordering requirements. ("volatile" does not guarantee that multiple volatile operations are observed to have consistent ordering from multiple threads, only that reads and writes have acquire and release semantics.)

However, low-lock solutions make me very nervous and I would not use one unless I was sure I had need to.

The first thing I would do is find out why there is so much contention on the lock. An uncontended lock should take 20-80 nanoseconds; you should only get a significant performance decrease if the lock is contended. Why is the lock so heavily contended? Fix that problem and your performance problems will go away.

The second thing I might do if contention cannot be reduced is to use a reader-writer lock. If I understand your scenario correctly, you will have many readers and only one writer, which is ideal for a reader-writer lock.

Leaving the question of volatility aside: as others have pointed out, there are basic mistakes in your threading logic like spinning on a boolean. This stuff is hard to get right. You might consider using the Task Parallel Library here as a higher-level abstraction than rolling your own threading logic. The TPL is ideally suited for problems where significant work must be done on multiple threads. (Note that the TPL does not magically make not-thread-safe code thread-safe. But it does provide a higher level of abstraction, so that you are dealing with Tasks rather than Threads. Let the TPL schedule the threads for you.)

Finally: the idea that a sudoku solver should take tens of seconds indicates to me that the solver is, frankly, not very good. The sudoku problem is, in its theoretically worst possible case, a hard problem to solve quickly no matter how many threads you throw at it. But for "newspaper" quality sudokus you should be able to write a solver that runs in a fraction of a second. There's no need to farm the work out to multiple threads if you can do the whole thing in a few hundred milliseconds.

If you're interested, I have a C# program that quickly finds solutions to sudoku problems here:

http://blogs.msdn.com/b/ericlippert/archive/tags/graph+colouring/

Answer 2

So the first thing, fix you're while loop to just join the threads...

    //Set them running
    foreach (Thread t in ThreadList)
        t.Start();

    //Wait until solution found (conditional timeout?)
    foreach (Thread t in ThreadList)
        t.Join(/* timeout optional here */);

Then there is issue with when to shutdown the threads. My advise is to introduce a wait handle on the class and then in the worker threads just loop on that...

ManualResetEvent mreStop = new ManualResetEvent(false);
//...
while(!mreStop.WaitOne(0))
{
    //...

Now just modify the Solved property to signal all threads that they should quit...

public bool Solved
{
    get
    {
        return _solved;
    }
}

// As Eric suggests, this should be a private method, not a property set.
private void SetCompleted()
{
    _solved = value;
    mreStop.Set();
}

The benefit to this approach is that if a thread fails to quit within a timeout period you can signal the mreStop to stop the workers without setting _solved to true.

Answer 3

volatile IS used to prevent optimizations such as caching and reordering of reads/writes for a single variable. Using it in this case is exactly what it's designed for. I don't see what your concern is.

lock is a slow yet working alternative because it introduces a memory fence implicitly, but in your case you are using a lock just for the memory fence side-effect, which is not really a nice idea.