Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming.threads > #254

Re: What's the latest state-of-the art for EventCounts?

Show all headers | View raw

"Andy Venikov" <swojchelowek@gmail.com> wrote in message
news:iqf632$69h$1@dont-email.me...
> On 05/09/2011 07:28 PM, Chris M. Thomasson wrote:
>
> <snip>
>
>
>> ARGHGHGH! I totally fuc%ed up the code. It should read as:
>> _______________________________________________________
[....]
>> _______________________________________________________
>>
>>
>> Thank you VERY much for finding that nasty race-condition!
>>
>> :^o
[...]
>> Thanks!  ;^/
>>
>
> Yeah, this looks much better.

Hell yeah it does!  ;^)




> There's some confusing bit manipulation code in your wait function.
> Am I correct in assuming that if we change get() to:
>
> return m_state.fetch_or(EC_WAITBIT) | EC_WAITBIT;
>
> then in the wait() function there's no need for bit manipulation and it
> could be written as:
>
> void wait(unsigned state1)
> {
>   m_mutex.lock();
>   unsigned state2 = m_state.load();
>   if (state1 == state2)
>   { ... same here ... }
>   m_mutex.unlock();
> }
> ?

Sure; however it might cause some false wakeups. I just wanted to mask the
waitbit off before I compared anything.




> I should probably also mention a possible (although highly
> improbable) race-condition when m_state wraps-around.
> (Effectively there's just 31 bits in m_state to use as a
> generation-count).

[...]

Hell yeah. The algorithm will deadlock and totally bit the dust if this
condition rears it's ugly head! Yikes!

:^o




> - 2 items
> in the queue by now.
> I think it's a similar problem to how big a generation count for
> ABA is big enough?

It's a bit worse because the version  count ABA solutions for CAS usually
compare the node pointer value as well. So the counter has to wrap AND the
node pointer value has to be exactly the same in order to trip the
race-condition. Here, in this eventcount there is no node pointer to
compare, just the version counter value. So, it's a bit worse than ABA wrt
lock-based collections (e.g., non-blocking stack)...




> Although nowadays, I must admit, 2 billion doesn't sound like a very
> safe number. I think if you use long long or some such then you're
> all set. Although it's an interesting problem to ponder on.

I think I have solved the problem using a very simple algorithm that I will
post at the end of this message. I don't use a eventcount, but rather a
single waiter bit and the predicate of the user algorithm itself. The
algorithm is pretty nice... Well, IMVHO of course!

:^)




> I also thought more about the original code I posted (the one that
> worked only for single consumer). I think that the event count variable
> could be safely used to indicate the number of waiters.
> I.e.:

[...]

Humm... Interesting. It should work. I need to take a closer look at it.


Anyway, here is what I am "thinking" about using now:
______________________________________________________________
class waitset
{
    std::mutex m_mutex;
    std::condition_variable m_cond;
    std::atomic<bool> m_waitbit;
    VAR_T(unsigned) m_waiters;



public:
    waitset()
    :   m_waitbit(false),
        m_waiters(0)
    {

    }


    ~waitset()
    {
        bool waitbit = m_waitbit.load(std::memory_order_relaxed);

        unsigned waiters = VAR(m_waiters);

        RL_ASSERT(! waitbit && ! waiters);
    }



private:
    void prv_signal(bool waitbit, bool broadcast)
    {
        if (! waitbit) return;

        m_mutex.lock($);

        unsigned waiters = VAR(m_waiters);

        if (waiters < 2 || broadcast)
        {
            m_waitbit.store(false, std::memory_order_relaxed);
        }

        m_mutex.unlock($);

        if (waiters)
        {
            if (! broadcast)
            {
                m_cond.notify_one($);
            }

            else
            {
                m_cond.notify_all($);
            }
        }
    }



public:
    void wait_begin()
    {
        m_mutex.lock($);

        m_waitbit.store(true, std::memory_order_relaxed);

        MEMBAR_SEQ_CST();
    }


    bool wait_try_begin()
    {
        if (! m_mutex.try_lock($)) return false;

        m_waitbit.store(true, std::memory_order_relaxed);

        MEMBAR_SEQ_CST();

        return true;
    }


    void wait_cancel()
    {
        unsigned waiters = VAR(m_waiters);

        if (! waiters)
        {
            m_waitbit.store(false, std::memory_order_relaxed);
        }

        m_mutex.unlock($);
    }


    void wait_commit()
    {
        MEMBAR_SEQ_CST();

        ++VAR(m_waiters);

        m_cond.wait(m_mutex, $);

        if (! --VAR(m_waiters))
        {
            m_waitbit.store(false, std::memory_order_relaxed);
        }

        m_mutex.unlock($);
    }



public:
    void signal()
    {
        MEMBAR_SEQ_CST();

        bool waitbit = m_waitbit.load(std::memory_order_relaxed);

        prv_signal(waitbit, false);
    }


    void broadcast()
    {
        MEMBAR_SEQ_CST();

        bool waitbit = m_waitbit.load(std::memory_order_relaxed);

        prv_signal(waitbit, true);
    }
};
______________________________________________________________




I have coded up a simple test for it in Relacy Race Detector. Here is the
working code:

http://pastebin.com/q9R0sqT7




You can use it like:
______________________________________________________________
static nbqueue g_nbqueue;
static waitset g_waitset;


void* consumers()
{
    void* state;

    while (! (state = g_nbqueue.try_pop()))
    {
        g_waitset.wait_begin();

        if ((state = g_nbqueue.try_pop()))
        {
            g_waitset.wait_cancel();

            break;
        }

        g_waitset.wait_commit();
    }

    return state;
}


void producers(void* state)
{
    g_nbqueue.push(state);
    g_waitset.signal();
}
______________________________________________________________



Pretty simple. What do you think of it Andy?


Thanks!

:^)

Back to comp.programming.threads | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

What's the latest state-of-the art for EventCounts? Andy Venikov <swojchelowek@gmail.com> - 2011-04-29 18:53 -0400
  Re: What's the latest state-of-the art for EventCounts? Andy Venikov <swojchelowek@gmail.com> - 2011-05-02 10:47 -0400
    Re: What's the latest state-of-the art for EventCounts? Andy Venikov <swojchelowek@gmail.com> - 2011-05-05 12:01 -0400
      Re: What's the latest state-of-the art for EventCounts? "Chris M. Thomasson" <cristom@charter.net> - 2011-05-05 19:29 -0700
        Re: What's the latest state-of-the art for EventCounts? Andy Venikov <swojchelowek@gmail.com> - 2011-05-06 14:24 -0400
          Re: What's the latest state-of-the art for EventCounts? "Chris M. Thomasson" <cristom@charter.net> - 2011-05-07 16:49 -0700
            Re: What's the latest state-of-the art for EventCounts? Andy Venikov <swojchelowek@gmail.com> - 2011-05-09 19:05 -0400
              Re: What's the latest state-of-the art for EventCounts? "Chris M. Thomasson" <cristom@charter.net> - 2011-05-09 16:28 -0700
                Re: What's the latest state-of-the art for EventCounts? Andy Venikov <swojchelowek@gmail.com> - 2011-05-11 19:28 -0400
                Re: What's the latest state-of-the art for EventCounts? "Chris M. Thomasson" <cristom@charter.net> - 2011-06-09 19:09 -0700
                Re: What's the latest state-of-the art for EventCounts? Keith H Duggar <duggar@alum.mit.edu> - 2011-07-30 19:15 -0700

csiph-web