Wednesday, January 9, 2013

Multithreading in Windows

The main purpose of my little chess engine project is to grow my computer science skills by doing stuff I haven't done before. Chess programming is great for that because the such a project is small enough to be handled by a single person but complex enough to keep you busy for a long time.

It touches so many areas. You focus on complex high level algorithms and data structures but also on the assembler code that a certain compiler for a certain target platform creates to check whether your programs runs efficiently.    

Between Christmas and New Year I had a bit of time and decided to look into one area that always scared me so far.


Multi-Threading

It is not a completely new concept to iCE because it already dispatches a 2nd thread when started. But the only purpose of this thread is to listen for potential commands sent to the engine to keep the engine responsive even when doing some heavy calculations. The thread is very simple and most of the time just blocked because there is no input. I had to learn some nasty low level API calls to get a thread dispached like

 hThread = CreateThread( NULL, 0, (LPTHREAD_START_ROUTINE) TInputThread::execute, (LPVOID) this, 0, &dwThreadID );

but I got it working.

The real fun starts when multiple threads work on the same data to speed up the overall execution.I don't want to go there for my chess engine yet. It probably requires some significant design changes but for my tuning efforts I though it might be fun to build a multi-threaded tuning framework where different versions of my engine are tested in parallel.

A version of my engine is characterized by a set of evaluation parameter values. Due to my recent efforts those values can be changed anytime without recompiling the code. The tuning process might now build up a work queue of different parameter sets and test the performance of the engine with one of those sets in certain well defined tasks like solving mate puzzles or playing tons of games. This is a real CPU stress test and to fully utilize my new i7 running the whole stuff on a single core doesn't seem the smartest thing to do.  

So I had a reason to have a deeper look into multi-threading. I know how to start and control independent threads but I had no clue how difficult it is to synchronize threads. The usual way of doing  things just don't work. A simple

 if (myQueue.size() > 0) myQueue.pop();    // remove the first element from a queue

doesn't work any longer, because even if queue.size returns a value > 0 there is no guarantee that there is still an item in the queue if the execution reaches queue.pop. Another thread could have just removed the last item between the two calls.

In order to avoid such race conditions the sensitive parts must be protected with something called a critical section for threads or a mutex for process synchronization. There are tons of publications available how to do that and I had a good reading between the years.

One very clever technique I learned is called RAII (Resource Acquisition is Initialization). It basically means to wrap a C++ class around a critical section resource. The critical section is acquired with the construction of the class and freed when the class is destroyed. As in C++ an object is automatically destroyed when it leaves the scope the danger of not freeing a critical section (because of an exception within the code or a forgotten branch) is greatly reduced.

I now feel now a bit more comfortable about writing multi-threaded code. Maybe in a distant future iCE will use more that a 2nd little input handling thread.

We'll see.