Subj : Re: really simple portable eventcount...
To   : comp.programming.threads
From : Joe Seigh
Date : Sun Mar 06 2005 08:27 am

On Sat, 5 Mar 2005 22:54:59 -0800, SenderX <xxx@xxx.com> wrote:

> This is real fast in the signals without waiters case:

I was working on something somewhat similar but used a different
technique that turned out not to work.  But anyway I know what
the issues are here.  Some of the membars you need aren't so
nice.

>
>
> // pseudo-code
> class ec
> {
>
>   pthread_mutex_t m_mutex;
>   pthread_cond_t m_cond;
>   int m_waiters;
>   int m_ec;
>
>
> public:
>
>   ec() : m_waiters( 0 ), m_ec( 0 )
>   {
>     // init mutex and cond
>   }
>
>
> public:
>
>   int get()
>   {
>     int local = m_ec;
>     atomic_bitset( &m_ec, 0x80000000 );

You need a store/load + load/load  rather than just a load/load that you normally
use when just reading an eventcount.

>     return local & 0x7FFFFFFF;
>   }
>
>
>   int signal()
>   {

You probably need a store/load here.  The lock-free collection
you're signaling about probably has a release memory barrier but
it's in the wrong place.  The more conventional method would be
a store/store before incrementing the count with a store/load
before checking for waiters so it's probably not a real hit
relatively speaking.

>     int local = m_ec;
>
>     if ( local & 0x80000000 )
>     {
>       pthread_mutex_lock( &m_mutex );
>
>       while ( ! cas( &m_ec,
>                      local,
>                      ( local + 1 ) & 0x7FFFFFFF )
>       {
>         local = m_ec
>       }
>
>       local = m_waiters
>       m_waiters = 0;
>
>       pthread_mutex_unlock( &m_mutex );
>
>       if ( local )
>       {
>         pthread_cond_broadcast( &m_cond );
>       }
>     }
>   }
>
>
>   int wait( int cmp )
>   {

load/load here of course.

>     int local = m_ec & 0x7FFFFFFF;
>
>     if ( local == cmp )
>     {
>       pthread_mutex_lock( &m_mutex );
>
>       local = m_ec & 0x7FFFFFFF;
>
>       if ( local == cmp )
>       {
>         ++m_waiters;
>
>         pthread_cond_wait( &m_cond, &m_mutex );
>       }
>
>       pthread_mutex_unlock( &m_mutex );
>     }
>   }
>
> };
>
>
> Can be used as a simple signal for lock-free algorithms.
>
>
>

How you structure everything depends on what the relative frequency
of the functions that you expect to used.  You can shift the burden
on either the signaling or the waiting depending on which you think
will be more frequent.  In this case you are trying to make the
signaling almost free while waiting has a cost with setting the
waiters bit.  So you want to reduce that with a particular usage
paradigm.  That was that double checked waiting thing I mentioned
previously.  For example if you had a lock free queue, you use the
following logic

	while ((item = queue_pop()) == NULL) {
		wc = get();		// get current waitcount
		if ((item = queue_pop()) != NULL)
			break;
		wait(wc);		// wait for signal
	}

If you go this way then the likelyhood that if you set the waiters bit
that you are going to wait is extremely high and you can dispense
with the waitcount as nearly redundant and just wasting cycles.



-- 
Joe Seigh

.