tl;dr - in short, this is a question of how to best implement my own version of PostThreadMessage().

More precisely, my target problem right now is communication between the input and render threads in the context of a GUI. I'd like this very same logic to be extensible to communication between the input and game logic threads, and load and render threads. I've kind of settled on a fairly simple counter-based method as I've come along, as it just works.

My assumptions are:

- I don't want to use a locking mechanism

- instead I either use polling in the render thread if running in real-time mode, or signaling via something like a waitable object to force a refresh, if not running in real-time mode. This bit I'm somewhat worried about as I'm not yet sure as to how portable it is.

- I'd like the communication scheme to be extensible to any many-to-one thread model where many threads can send messages to one target thread

With this in mind the best (and so far only, really) way I've managed think of is a FIFO stack with each sender thread having its own dispatch queue and a write marker that points into a circular buffer (eg the stack). The receiving thread then reads everything from its respective read marker up to the write marker at each iteration (or when notified). There is no synchronization between the two threads other than a possible SetEvent() called by the sender if the render thread doesn't already poll in a tight loop.

So far this has been a fairly straightforward and foolproof approach. The primary problem I see here is guesstimating the size of the message buffer and, in particular, what to do when an overflow occurs. Before going about reallocating memory to fit more messages I figured it'd make sense to actually see if there might be more trickery involved in the way Windows does it (yeah, that was a question).

Also, in a way it feels a bit like a hack, even though it works :)

This is totally off the top of my head, so correct me if I'm wrong...

initialise atomic to zero, then:

void ReadWriteFromQueue( bool read )

{

while( atomic_increment != 1 ) // another thread has access already

{

atomic_decrement;

}

if( read == true )

{

// read from queue code here

}

else

{

// write to queue here

// if queue size is too small, resize (possibly during development to best guess max queue size)

}

atomic_decrement;

}

If you have no synchronization code in there, then I can assure you that you likely have a bug ;P

Resizable lock-free structures are even harder to design, so if this is for a game, I would advocate just "knowing your data" and setting a suitable upper limit (and asserting/crashing on overflow).

I haven't gone over the links you provided yet, but I with the SPSC approach I'm using I don't think I need atomics - even for the read/write markers, as it should be safe to assume these can never conflict. Right?

The toughest part of writing a multi-threaded application is comprehending the logic of execution flow and I indeed have rock-walled with strange effects showing up every now and then for apparently no reason. This is why I'm finally setting up a messaging system and aren't really afraid of taking my time with it. Thanks for going into the trouble of posting some reading!

With respect to handling overflow - I'm actually not all that concerned with it. It's just that my initial brute-force addition of GUI refresh messages for in-game windows somewhat surprised me: even though I only had 74 controls hidden and visible that were being created at application start, without filtering, my dispatcher received almost 2000 refresh commands even before the first frame was drawn. I figured I'd done a fairly thorough job of removing redundancy from my code, but cascading the dirty flag can really add up quickly. With simple filtering it wasn't hard to normalize the amount of messages and it helped me identify a simple missing check in the rest of the code, but the cold truth (and a lesson) is that my conservative estimate of queue length of 512 messages overflowed quite quickly. And that made me worried.

I suppose the dispatch queue can in a way be a fairly efficient way of also identifying redundancy that can otherwise be somewhat hard to spot.

In some cases though, it might actually be better to use an array of SPSC queues, because this way there will be no contention between writer-threads!

That's actually what I'm doing right now: each producer thread has its own queue and the consumer iterates through each of them. I don't really see a reason to use an MPSC/MPMC queue in a game as there aren't too many threads to start with. I mentioned this in my own words in the OP .

I guess if my target was a new operating system with an unbounded thread count or some thread-heavy distributed system, I would need a less bloated approach to minimize memory redundancy and centralize messaging, but right now (especially once I've profiled my code a bit and know how may messages are actually flying around) I don't really have a problem with allocating relatively copious amounts of space to accommodate large enough queues. The way I'm thinking right now is along the lines of "simpler is better": a megabyte per thread-thread interaction can hold a fair number of messages and costs almost nothing.

These kinds of deadlocks can happen even more frequently with bounded concurrent queues since you can't push a new event into said queue when it's full but the other thread might _also_ be blocked trying to push into its queue, so you have to be smart about what you do when you need to push a value into a bounded queue. Unbounded queues don't necessarily solve this problem, either; they just change it to be harder to detect and the results to be more serious. You have to think a lot about the synchronization between threads (or processes, or service) even in "lock-free" contexts.

I do appreciate the potential complexity that can arise when the number of threads increases. Since I'm still dabbling with thread-safe messaging I think I'll do what Hodgman said and set up a hard limit to the queue length. Once I hit that during development I'll just analyze the reason and either work backwards to reduce the number of messages or increase the queue size as needed.

Do be aware of a potential dead-lock you can get into with this design. If your render thread is ever stuck waiting for the main thread and the main thread is stuck waiting for the render thread, your game will deadlock.

With an SPSC queue I don't frankly see how a deadlock can occur, especially since none of the threads are waiting for another thread. I'm going for true asynchronous communication here where the render thread just takes pre-calculated input at the start of each frame and applies it all at once to avoid mid-frame updates.

with the SPSC approach I'm using I don't think I need atomics - even for the read/write markers, as it should be safe to assume these can never conflict. Right?

Only if you can assume that your code executes in the order that you've written it in, which you can't. So - Not right

First up, the compiler is totally allowed to reorder your code, as long as the reordered version results in the same visible behavior from a single-threaded point of view.
In a single-threaded program, it doesn't matter whether you write new data and then update the cursor, or whether you do those two writes in the other order... The outcome is the same, so the compiler is free to play with that ordering.
I'm a multi-threaded program though, the wrong ordering can cause the consumer to try and read new data before it has even been written!
So, unless you're using lovingly hand-crafted ASM, you at the very least require a compile-time memory barrier to force the compiler to emit the instructions in the correct order.

Second, CPUs are damn fancy these days - they basically have an optimizer built in!
The CPU is totally allowed to reorder your code, as long as the reordered version results in the same visible behavior from a single-threaded point of view! It can reorder the instruction stream, and can also buffer up and reorder reads and writes to memory!
That means the same situation can occur, where data/cursors are read/written out of order and you end up with corrupt results.
Now, x86 is pretty nice and although it does a lot of reordering, it does create some kinds of implicit fences around certain memory accesses to avoid this problem, but there are many CPUs that don't. To write solid, portable lock-free code, you either have to read the manuals for your target CPUs so you know what assumptions are valid, or you need to insert the appropriate runtime memory fence instructions, which will tell the CPU not to reorder (if necessary).

Point taken, understood and appreciated :).

I'm in a bit of a hurry, but just for kicks, here's my Q'n'D implementation. It seems to be working at first glance, but it's open for peer review. Note that I don't need to send generic messages (eg the range of message types is restricted to simple pointer/variable updates which are contained in a structure specific to each consumer thread), thus avoiding unnecessary casting.

Producer thread:

msg = disp.QueryFreeMessage();

if(msg)

{ fill in and call disp.Dispatch(); }

Consumer thread:

while(msg = disp.GetMessage()) { HandleMessage(msg); }

#define MAX_PRODUCER_THREADS	64
#define MAX_PRODUCER_MESSAGES	65536

//LINUX:	__sync_add_and_fetch()
//OSX:		OSAtomicAdd32
//WINDOWS:	InterlockedIncrement()
UINT MyAtomicIncrement(	IN volatile UINT * ptr);
void MyAtomicSet(		IN volatile UINT * ptr, IN UINT value);

template<class T>
struct IThreadDispatchQueueSPSC	{
	UINT iThreadID;

	volatile UINT iWriteMarker;
	volatile UINT iReadMarker;

	T queue[MAX_PRODUCER_MESSAGES];

	IThreadDispatchQueueSPSC()
		{
		iWriteMarker = 0;
		iReadMarker = 0;
		}

	T* QueryFreeMessage()
		{ return &queue[iWriteMarker]; }

	T* GetMessage()
		{
		if(iReadMarker == iWriteMarker)
			return 0;

		T* res = &queue[iReadMarker];

		UINT iNext = iReadMarker + 1;

		if(iNext >= MAX_PRODUCER_MESSAGES - 1)
			{ iNext = 0; }

		MyAtomicSet(&iReadMarker, iNext);

		return res;
		}

	void Dispatch()
		{
		UINT iNext = iWriteMarker + 1;

		if(iNext >= MAX_PRODUCER_MESSAGES - 1)
			{ iNext = 0; }

		if(iNext == iReadMarker)
			{ lout << "Warning: dispatch queue full ('" << TStackTrace::getThreadName(iThreadID) << "')" << endl; return; }

		MyAtomicSet(&iWriteMarker, iNext);
		}
	};

template <class T>
struct IThreadMessageQueue_MPSCArray	{
	UINT iConsumerThreadID;

	IThreadDispatchQueueSPSC<T> producerThreads[MAX_PRODUCER_THREADS];

	volatile UINT iNumProducerThreads;

	IThreadMessageQueue_MPSCArray()
		{
		iNumProducerThreads = 0;
		iConsumerThreadID = 0;

		ZeroMemory(producerThreads, sizeof(producerThreads));
		}

	bool RegisterProducerThread(UINT iThreadID)
		{
		if(iNumProducerThreads >= MAX_PRODUCER_THREADS)
			{
			lout << "Error: too many producer threads: " << iNumProducerThreads << endl;
			//THROW("Too many producer threads");
			return false;
			}

		int iIndex = MyAtomicIncrement(&iNumProducerThreads) - 1;
 		lout << "new producer thread: " << iIndex << " " << iThreadID << endl;
		producerThreads[iIndex].iThreadID = iThreadID;

		return true;
		}

	//returns a pointer to the next free message, NULL if the stack overflows.
	T* QueryFreeMessage()
		{
		UINT iThreadID = GetCurrentThreadId();

		for(int i = 0; i < (int)iNumProducerThreads; i++)
			{
			IThreadDispatchQueueSPSC<T>* t = &producerThreads[i];

			if(iThreadID == t->iThreadID)
				{ return t->QueryFreeMessage(); }
			}

		//add this thread
		if(!RegisterProducerThread(iThreadID))
			return NULL;

		//try again
		return QueryFreeMessage();
		}

	//produce a message into the queue
	void Dispatch()
		{
		UINT iThreadID = GetCurrentThreadId();

		for(int i = 0; i < (int)iNumProducerThreads; i++)
			{
			IThreadDispatchQueueSPSC<T>* t = &producerThreads[i];
			if(t->iThreadID == iThreadID)
				{ t->Dispatch(); break; }
			}
		}

	//iterates through unhandled messages sent to this thread. Should only be called by the consumer thread.
	T* GetMessage()
		{
		for(int i = 0; i < (int)iNumProducerThreads; i++)
			{
			IThreadDispatchQueueSPSC<T>* t = &producerThreads[i];

			if(t->iReadMarker != t->iWriteMarker)
				{ return t->GetMessage(); }
			}

		//out of messages
		return NULL;
		}
};