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

Groups > comp.programming.threads > #123

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:iq1ec6$aoo$1@dont-email.me...
[...]
> I think in order to make this solution multi-consumer-friendly, we have
> to play tricks with "ec" and make it a real counter to indicate the
> amount of waiters. I'll think about it over the week-end.
>
> Of course, it could be used as-is with "wake everybody" semantics, but
> then we would get the "thundering herd" problem, which is usually not
> a simple problem to solve either.


Here is some pseudo-code for one of my "very simple" eventcount algorithms, 
membars aside for a moment, that works with the upcoming C++ standard. 
Modulo any bugs/typos, here it is... Typed directly in the newsreader, 
lol...:
_______________________________________________________
struct eventcount
{
    #define EC_WAITBIT 0x1U
    #define EC_INCVAL  0x2U



    std::atomic<unsigned> m_state; // = 0
    unsigned m_waiters;            // = 0
    std::condition_variable m_cond;
    std::mutex m_mutex;



    void prv_signal(unsigned state, bool broadcast)
    {
        if (! (state & EC_WAITBIT)) return;

        m_mutex.lock();

        if (m_waiters)
        {
            unsigned xchg;

            do
            {
                xchg = state + EC_INCVAL;

                if (m_waiters == 1 || broadcast)
                {
                    xchg &= ~EC_WAITBIT;
                }

            } while (! m_state.compare_exchange_weak(
                                   state,
                                   xchg));

            if (broadcast)
            {
                m_cond.notify_all();
            }

            else
            {
                m_cond.notify_one();
            }
        }

        m_mutex.unlock();
    }



    unsigned get()
    {
        return m_state.fetch_or(0x1U);
    }



    void signal()
    {
        unsigned state = m_state.load();

        prv_signal(state, false);
    }



    void broadcast()
    {
        unsigned state = m_state.load();

        prv_signal(state, true);
    }



    void wait(unsigned state1)
    {
        m_mutex.lock();

        unsigned state2 = m_state.load();

        if ((state1 & ~EC_WAITBIT) ==
            (state2 & ~EC_WAITBIT))
        {
            ++m_waiters;

            m_cond.wait(m_mutex);

            --m_waiters;
        }

        m_mutex.unlock();
    }
};
_______________________________________________________




You can use it for a non-blocking queue algorithm like:
_______________________________________________________
static nbqueue g_queue;
static eventcount g_ecount;


void* consume()
{
    void* state;

    while (! (state = g_queue.try_pop()))
    {
        unsigned ecstate = g_ecount.get();
        if ((state = g_queue.try_pop())) break;
        g_ecount.wait(ecstate);
    }

    return state;
}


void produce(void* state)
{
    g_queue.push(state);
    g_ecount.signal();
}
_______________________________________________________




What do you think Andy? 

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