Spin-Wait vs. Condition Variable

Recently at work, I ran into an interesting threading problem.

I have two threads – A and B, running concurrently. Thread A needs a piece of data from Thread B. Normally, Thread B would just pass a message to Thread A. But in this scenario, every millisecond counts. Thread A needs the data A.S.A.P!

In theory, Thread B should have the result within couple milliseconds. Since the wait is so short, the synchronous approach is feasible. I would block Thread A until Thread B gets the data. But should I use a condition varialbe, or should I just spin-wait (assuming that I have a multi-core processor)?

This is very much a real life threading problem that even expert programmer encounters. (And I am no expert. :???:)

Speed Comparison

I expect spin-wait to have lower latency than condition variable. But by how much?

It has been awhile since I ran any performance test. So I cooked up some test code to get a sense of the latency.

Here’s the spin-wait code.

long global_spin_var = 0;
void spin_thread()
{
	while(1)
	{
		// memory barrier for visibility semantics
		_ReadWriteBarrier();

		// spin wait
		if(global_spin_var == 1){ break; }
	}
}
void time_spin_thread()
{
	// ... set up timing code here

	// update the global variable with cmpxchg
	InterlockedExchange(&global_spin_var,0);

	thread t1(bind(&spin_thread));
	// wait for a second for thread start, sloppy but good enough
	Sleep(1000);
	t1.join();
}

Here’s the condition variable code.

long global_condition_wait_var = 0;
condition_variable global_condition;
mutex global_mutex;

void condition_wait_thread()
{
	mutex::scoped_lock lock(m_mutex);
	while(global_condition_wait_var == 0)
		global_condition.wait(lock);
}

void time_condition_wait_thread()
{
	// ... set up timing code here

	// update the global variable with cmpxchg
	InterlockedExchange(&global_condition_wait_var,0);

	thread t2(bind(&condition_wait_thread));

	// wait for a second for thread start, sloppy but good enough
	Sleep(1000);

	global_condition.notify_all();
	t2.join();
}

It turns out that latency of condition variable is higher, but not absurdly high.

Spin-wait’s latency is about half of condition variable. This is a reasonable trade-off for spending a bunch of CPU cycles spinning.

Latency comparison between spin-wait and condition variable

Final Thoughts

So which approach did I end up using? Neither.

Apparently Thread A doesn’t really need the “right” answer from Thread B. It just needs “some” answer to make things look good.

Another lesson from the real world – it doesn’t matter if it works, as long as it looks good. 🙄

Source

The source and the data sheet can be downloaded here.

Tools: Visual Studio 2008, Boost 1.41, Window 7, Intel I5-750 (quad core)

3 thoughts on “Spin-Wait vs. Condition Variable

  1. Bill says:

    I would like to point out a possible error in your condition_variable code.

    You must be sure to hold the lock “m_mutex” when setting your “global_condition_wait_var” to 1 in your notification code.
    (InterlockedExchange would no longer be needed.)

    By leaving out the lock, the following situation is possible:

    global_condition_wait_var initialized to 0

    waiting thread:
    m_lock is acquired,
    while loop condition is checked (global_condition_wait_var == 0) (it is true)

    notification thread:
    global_condition_wait_var is atomically set to 1
    .notify_all() is called (before waiting thread begins waiting)

    waiting thread:
    m_lock is atomically released and thread waits on the condvar (after being notified) (it waits until the next spurious wakeup (who knows when))

    Holding the lock when changing the possible outcome of your “condition” ensures this is not possible.
    It is the reason for the atomic release/wait within condition_variable::wait.

  2. Bill,

    You are absolutely right. Looking back at this test code, it is completely wrongly. I don’t know how I came to believe that InterlockedExchange can replace locking the actual mutex.

    There is clearly a potential for lost-wakeup.

    I will rewrite it and redo the test.

    Thanks for pointing it out.

    … Alan

Leave a Reply

Your email address will not be published. Required fields are marked *