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

Groups > comp.programming.threads > #653

Re: Why lock-free implementations are faster than traditional using synchronization? Are they?

Show all headers | View raw

"Michael Podolsky" <michael.podolsky.69@gmail.com> wrote in message 
news:af80f87d-ea93-4cb4-88f4-be456f45037a@a7g2000yqd.googlegroups.com...

[...]

> Let me make myself clear.

> I did not mean a scenario without a progress, i.e. spinning without a
> progress.

[...]

> Then, I asked, how spinning on a cmpxchg in lock-free is better then
> spinning on such a spinlock?

Spinning is pretty bad period. However, wrt strong CAS (e.g., no spurious 
failures) and lock-free algorithms in general, a failure condition usually 
means that actual shared data was updated by another thread. Contrast this 
with a spinlock in which a failure condition merely means that the spinlock 
state was updated. Take the following into account:

lock-free
________________________________________________
struct counter
{
    atomic<unsigned> m_count; // = 0

    unsigned
    inc_or_relaxed(unsigned  incv, unsigned orv)
    {
        unsigned cmp = m_count.load(mb_relaxed);

        while (! m_count.compare_exchange_strong(
                                      cmp,
                                      (cmp + incv) | orv,
                                      mb_relaxed));

        return cmp;
    }
};
________________________________________________

Each failure of the while loop means that `counter::m_count' was updated. 
The "winning" thread is completely finished with the whole operation.


simple spin-lock
________________________________________________
struct counter
{
    atomic<unsigned> m_splock; // = 0
    unsigned m_count; // = 0

    unsigned
    inc_or_relaxed(unsigned  incv, unsigned orv)
    {
        while (m_splock.exchange(1, mb_relaxed)) backoff();
        atomic_thread_fence(mb_acquire);

        unsigned count = m_count;
        m_count = (count + incv) | orv;

        atomic_thread_fence(mb_release);
        m_splock.store(0, mb_relaxed);

        return count;
    }
};
________________________________________________

Each failure of the while loop means that `counter::m_splock' was updated... 
If the spinlock is swung into a "locked" state, then all failing threads 
need to wait for that one "winning" thread to update the actual shared state 
_and_ put the spinlock back into an "unlocked" state. Also, notice the 
memory barriers? 

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

Thread

Why lock-free implementations are faster than traditional using synchronization? Are they? Michael Podolsky <michael.podolsky.69@gmail.com> - 2011-10-08 18:08 -0700
  Re: Why lock-free implementations are faster than traditional using synchronization? Are they? Casper H.S. Dik <Casper.Dik@OrSPaMcle.COM> - 2011-10-09 10:45 +0000
  Re: Why lock-free implementations are faster than traditional using synchronization? Are they? Marcel Müller <news.5.maazl@spamgourmet.org> - 2011-10-10 13:22 +0200
  Re: Why lock-free implementations are faster than traditional using synchronization? Are they? David Schwartz <davids@webmaster.com> - 2011-10-12 16:57 -0700
    Re: Why lock-free implementations are faster than traditional using synchronization? Are they? "Chris M. Thomasson" <cristom@charter.net> - 2011-10-14 16:54 -0700
    Re: Why lock-free implementations are faster than traditional using synchronization? Are they? Michael Podolsky <michael.podolsky.69@gmail.com> - 2011-10-26 08:37 -0700
      Re: Why lock-free implementations are faster than traditional using synchronization? Are they? "Chris M. Thomasson" <cristom@charter.net> - 2011-10-26 14:19 -0700
      Re: Why lock-free implementations are faster than traditional using synchronization? Are they? David Schwartz <davids@webmaster.com> - 2011-10-27 01:00 -0700
  Re: Why lock-free implementations are faster than traditional using synchronization? Are they? "Chris M. Thomasson" <cristom@charter.net> - 2011-10-14 17:57 -0700

csiph-web