Topic: Lockless Ring Buffer Queue
Author: Robin Rowe <robinsrowe@gmail.com>
Date: Tue, 13 Jan 2015 20:26:26 -0800 (PST)
Raw View
------=_Part_247_1737416481.1421209586153
Content-Type: multipart/alternative;
boundary="----=_Part_248_1423647908.1421209586153"
------=_Part_248_1423647908.1421209586153
Content-Type: text/plain; charset=UTF-8
I've written a ring buffer queue using atomic that never locks. Two threads
accessing it simultaneously will not collide on push() or pop(). Used for a
communications queue. Is there already a std container like this? Does
anyone else need this?
Robin
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/.
------=_Part_248_1423647908.1421209586153
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">I've written a ring buffer queue using atomic that never l=
ocks. Two threads accessing it simultaneously will not collide on push() or=
pop(). Used for a communications queue. Is there already a std container l=
ike this? Does anyone else need this?<br><br>Robin<br> </div>
<p></p>
-- <br />
<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/">http://groups.google.com/a/isocpp.org/group/std-proposals/<=
/a>.<br />
------=_Part_248_1423647908.1421209586153--
------=_Part_247_1737416481.1421209586153--
.
Author: David Krauss <potswa@gmail.com>
Date: Wed, 14 Jan 2015 13:31:06 +0800
Raw View
> On 2015=E2=80=9301=E2=80=9314, at 12:26 PM, Robin Rowe <robinsrowe@gmail.=
com> wrote:
>=20
> I've written a ring buffer queue using atomic that never locks. Two threa=
ds accessing it simultaneously will not collide on push() or pop(). Used fo=
r a communications queue.
Is the source code available?
> Is there already a std container like this?
Nope.
> Does anyone else need this?
Yup.
A write-up would be appreciated!
--=20
---=20
You received this message because you are subscribed to the Google Groups "=
ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposa=
ls/.
.
Author: David Krauss <potswa@gmail.com>
Date: Wed, 14 Jan 2015 13:40:12 +0800
Raw View
--Apple-Mail=_ED81D0FD-9E98-44E1-A689-FA7E12E5CE68
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain; charset=UTF-8
> On 2015=E2=80=9301=E2=80=9314, at 12:26 PM, Robin Rowe <robinsrowe@gmail.=
com> wrote:
>=20
> I've written a ring buffer queue using atomic that never locks.
=E2=80=A6 To be sure, I hope it (b)locks when it=E2=80=99s empty. Also, in =
my experience, it=E2=80=99s a good idea to block when some maximum capacity=
is reached.
A more sophisticated version can automatically set the maximum capacity by =
detecting how many items tend to be added and removed in a typical timeslic=
e. It would be good to have an interface for =E2=80=9Cautomatic capacity;=
=E2=80=9D naive implementations can just use an arbitrary default.
--=20
---=20
You received this message because you are subscribed to the Google Groups "=
ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposa=
ls/.
--Apple-Mail=_ED81D0FD-9E98-44E1-A689-FA7E12E5CE68
Content-Transfer-Encoding: quoted-printable
Content-Type: text/html; charset=UTF-8
<html><head><meta http-equiv=3D"Content-Type" content=3D"text/html charset=
=3Dutf-8"></head><body style=3D"word-wrap: break-word; -webkit-nbsp-mode: s=
pace; -webkit-line-break: after-white-space;" class=3D""><br class=3D""><di=
v><blockquote type=3D"cite" class=3D""><div class=3D"">On 2015=E2=80=9301=
=E2=80=9314, at 12:26 PM, Robin Rowe <<a href=3D"mailto:robinsrowe@gmail=
..com" class=3D"">robinsrowe@gmail.com</a>> wrote:</div><br class=3D"Appl=
e-interchange-newline"><div class=3D""><span style=3D"font-family: Helvetic=
a; font-size: 12px; font-style: normal; font-variant: normal; font-weight: =
normal; letter-spacing: normal; line-height: normal; orphans: auto; text-al=
ign: start; text-indent: 0px; text-transform: none; white-space: normal; wi=
dows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none;=
display: inline !important;" class=3D"">I've written a ring buffer queue u=
sing atomic that never locks.</span></div></blockquote></div><br class=3D""=
><div class=3D"">=E2=80=A6 To be sure, I hope it (b)locks when it=E2=80=99s=
empty. Also, in my experience, it=E2=80=99s a good idea to block when some=
maximum capacity is reached.</div><div class=3D""><br class=3D""></div><di=
v class=3D"">A more sophisticated version can automatically set the maximum=
capacity by detecting how many items tend to be added and removed in a typ=
ical timeslice. It would be good to have an interface for =E2=80=9Cautomati=
c capacity;=E2=80=9D naive implementations can just use an arbitrary defaul=
t.</div></body></html>
<p></p>
-- <br />
<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/">http://groups.google.com/a/isocpp.org/group/std-proposals/<=
/a>.<br />
--Apple-Mail=_ED81D0FD-9E98-44E1-A689-FA7E12E5CE68--
.
Author: Ville Voutilainen <ville.voutilainen@gmail.com>
Date: Wed, 14 Jan 2015 07:47:43 +0200
Raw View
On 14 January 2015 at 06:26, Robin Rowe <robinsrowe@gmail.com> wrote:
> I've written a ring buffer queue using atomic that never locks. Two threads
> accessing it simultaneously will not collide on push() or pop(). Used for a
> communications queue. Is there already a std container like this? Does
> anyone else need this?
See
http://open-std.org/JTC1/SC22/WG21/docs/papers/2013/n3533.html
That seems to be work-in-progress.
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/.
.
Author: Robin Rowe <robinsrowe@gmail.com>
Date: Tue, 13 Jan 2015 22:19:18 -0800 (PST)
Raw View
------=_Part_767_2013834558.1421216358450
Content-Type: multipart/alternative;
boundary="----=_Part_768_27655939.1421216358450"
------=_Part_768_27655939.1421216358450
Content-Type: text/plain; charset=UTF-8
Here's my source code. I cut it down to eliminate code that may not be
generally useful. Please pardon any mistakes.
// AtomicRingQueue.h - A lockless non-blocking ring buffer
// 2015/1/13 Copyright Robin.Rowe@CinePaint.org
// License open source MIT
#ifndef AtomicRingQueue_h
#define AtomicRingQueue_h
#include <atomic>
#include <memory>
#include "String.h" // a std::string-like class with operator+
template <typename T>
class AtomicRingQueue
{ unique_ptr<T []> buffer;
std::atomic<unsigned> front;
std::atomic<unsigned> back;
std::atomic<int> counter;
unsigned size;
unsigned peakSize;//useful for logging
const char* queueName;//useful for logging
public:
~AtomicRingQueue()
{ Clear();
}
AtomicRingQueue()
{ Clear();
}
AtomicRingQueue(unsigned size,const char* queueName=0)
{ Open(size,queueName);
}
void Open(unsigned size,const char* queueName=0)
{ Clear();
this->queueName=queueName;
buffer=unique_ptr<T []>(new T[size]);
this->size=size;
}
bool IsEmpty() const
{ const int count=counter;
const bool isEmpty=(count<=0);
return isEmpty;
}
void Clear()
{ front=0;
back=0;
counter=0;
peakSize=0;
size=0;
queueName=0;
}
bool Push(T t)
{ int count=counter.fetch_add(1,std::memory_order_relaxed);
if(count>int(GetMaxSize()))
{ counter.fetch_sub(1,std::memory_order_relaxed);
LogError(String("Queue full ")+toString());
return false;
}
unsigned i=front.fetch_add(1,std::memory_order_relaxed);
if(i>=size)
{ if(i==size)
{ front.fetch_sub(size,std::memory_order_relaxed);
}
i-=size;
}
buffer[i]=t;
return true;
}
bool Pop(T& t)
{ const int count=counter.fetch_sub(1,std::memory_order_relaxed);
if(count<=0)
{ counter.fetch_add(1,std::memory_order_relaxed);
LogDebug(String("Empty queue pop ")+queueName);
return false;
}
if(count>peakSize)
{ peakSize=count;
}
unsigned i=back.fetch_add(1,std::memory_order_relaxed);
if(i>=size)
{ if(i==size) //only once, the thread that went off end first
{ back.fetch_sub(size,std::memory_order_relaxed);
}
i-=size;
}
t=buffer[i];
buffer[i]=0;
return true;
}
unsigned GetSize() const
{ const int count=counter;
return count<0 ? 0:unsigned(count);
}
unsigned GetFreeSize() const
{ return GetMaxSize()-GetSize();
}
bool IsFull() const
{ return GetMaxSize()==GetSize();
}
unsigned GetMaxSize() const
{ return size;
}
unsigned GetPeakSize() const
{ return peakSize;
}
virtual String toString() const
{ return String(queueName)+" count="+GetSize()+"
peakSize="+GetPeakSize()+" maxSize="+GetMaxSize();
}
};
#endif
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/.
------=_Part_768_27655939.1421216358450
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">Here's my source code. I cut it down to eliminate code tha=
t may not be generally useful. Please pardon any mistakes.<br><br>// Atomic=
RingQueue.h - A lockless non-blocking ring buffer<br>// 2015/1/13 Copyright=
Robin.Rowe@CinePaint.org<br>// License open source MIT<br><br>#ifndef Atom=
icRingQueue_h<br>#define AtomicRingQueue_h<br><br>#include <atomic><b=
r>#include <memory><br>#include "String.h" // a std::string-like clas=
s with operator+<br><br>template <typename T><br>class AtomicRingQueu=
e<br>{ unique_ptr<T []> buffer;<br> &nbs=
p; std::atomic<unsigned> front;<br> std::atomic<=
unsigned> back;<br> std::atomic<int> counter;<br=
> unsigned size;<br> unsigned peakSize;=
//useful for logging<br> const char* queueName;//useful f=
or logging<br>public:<br> ~AtomicRingQueue()<br> &nb=
sp; { Clear();<br> }<br> &nb=
sp; AtomicRingQueue()<br> { Clear=
();<br> }<br> AtomicRingQueue(unsigned =
size,const char* queueName=3D0)<br> { O=
pen(size,queueName);<br> }<br> void Ope=
n(unsigned size,const char* queueName=3D0)<br> { &nb=
sp; Clear();<br> this->queueN=
ame=3DqueueName;<br> buffer=3Dunique_p=
tr<T []>(new T[size]);<br> this-=
>size=3Dsize;<br> }<br> bool IsEmpty=
() const<br> { const int count=3Dcounte=
r;<br> const bool isEmpty=3D(count<=
=3D0);<br> return isEmpty;<br> &n=
bsp; }<br> void Clear() <br> {&nb=
sp; front=3D0;<br> back=3D=
0;<br> counter=3D0;<br> &nb=
sp; peakSize=3D0;<br> &nbs=
p; size=3D0;<br> queueName=3D0;<br>&nb=
sp; }<br> bool Push(T t)<br>  =
; { int count=3Dcounter.fetch_add(1,std::memory_order_rel=
axed);<br> if(count>int(GetMaxSize(=
)))<br> { counter.fe=
tch_sub(1,std::memory_order_relaxed);<br> &nb=
sp; LogError(String("Queue full ")+toString());<br> =
; return false;<br> =
}<br> =
unsigned i=3Dfront.fetch_add(1,std::memory_order_relaxed);<br> &=
nbsp; if(i>=3Dsize)<br>  =
; { if(i=3D=3Dsize)<br> &nb=
sp; { front.fetch_sub(size,std::=
memory_order_relaxed);<br>  =
; }<br> i-=3D=
size;<br> }<br> &nbs=
p; buffer[i]=3Dt;<br> retu=
rn true;<br> }<br> bool Pop(T& t)<b=
r> { const int count=3Dcounter.fetch_su=
b(1,std::memory_order_relaxed);<br> if=
(count<=3D0)<br> {  =
; counter.fetch_add(1,std::memory_order_relaxed);<br> &nb=
sp; LogDebug(String("Empty queue pop ")+queu=
eName);<br> return =
false;<br> }<br> &nb=
sp; if(count>peakSize)<br> &nb=
sp; { peakSize=3Dcount;<br>  =
; }<br> unsigned i=3Dback.fetch_=
add(1,std::memory_order_relaxed);<br> =
if(i>=3Dsize)<br> { &nbs=
p; if(i=3D=3Dsize) //only once, the thread that went off end first<br> =
; { bac=
k.fetch_sub(size,std::memory_order_relaxed);<br> &n=
bsp; }<br> &n=
bsp; i-=3Dsize;<br> }<br>&=
nbsp; t=3Dbuffer[i];<br> &=
nbsp; buffer[i]=3D0;<br> r=
eturn true;<br> }<br> unsigned GetSize(=
) const<br> { const int count=3Dcounter=
;<br> return count<0 ? 0:unsigned(c=
ount);<br> }<br> unsigned GetFreeSize()=
const<br> { return GetMaxSize()-GetSiz=
e();<br> }<br> bool IsFull() const<br>&=
nbsp; { return GetMaxSize()=3D=3DGetSize();<b=
r> }<br> unsigned GetMaxSize() const<br=
> { return size;<br> =
}<br> unsigned GetPeakSize() const<br> =
{ return peakSize;<br> }<br>  =
; virtual String toString() const<br> { =
return String(queueName)+" count=3D"+GetSize()+" peakSize=3D"+GetPea=
kSize()+" maxSize=3D"+GetMaxSize();<br> }<br>};<br><br>#e=
ndif<br><br><br></div>
<p></p>
-- <br />
<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/">http://groups.google.com/a/isocpp.org/group/std-proposals/<=
/a>.<br />
------=_Part_768_27655939.1421216358450--
------=_Part_767_2013834558.1421216358450--
.
Author: Robin Rowe <robinsrowe@gmail.com>
Date: Tue, 13 Jan 2015 22:34:06 -0800 (PST)
Raw View
------=_Part_1384_848608391.1421217246442
Content-Type: multipart/alternative;
boundary="----=_Part_1385_1122327810.1421217246442"
------=_Part_1385_1122327810.1421217246442
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
> I hope it (b)locks when it=E2=80=99s empty.
It never blocks. Returns false if a push or pop fails.
Robin
--=20
---=20
You received this message because you are subscribed to the Google Groups "=
ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposa=
ls/.
------=_Part_1385_1122327810.1421217246442
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">> I hope it (b)locks when it=E2=80=99s empty.<br><br>It=
never blocks. Returns false if a push or pop fails.<br><br>Robin<br></div>
<p></p>
-- <br />
<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/">http://groups.google.com/a/isocpp.org/group/std-proposals/<=
/a>.<br />
------=_Part_1385_1122327810.1421217246442--
------=_Part_1384_848608391.1421217246442--
.
Author: Thiago Macieira <thiago@macieira.org>
Date: Tue, 13 Jan 2015 22:59:17 -0800
Raw View
Hmm... sorry, but this doesn't look very atomic to me.
Was the synchronisation supposed to be external to this class? If it's
external, then this isn't lockless since the lock is present, just elsewhere.
On Tuesday 13 January 2015 22:19:18 Robin Rowe wrote:
> bool Push(T t)
> { int count=counter.fetch_add(1,std::memory_order_relaxed);
> if(count>int(GetMaxSize()))
> { counter.fetch_sub(1,std::memory_order_relaxed);
> LogError(String("Queue full ")+toString());
> return false;
> }
> unsigned i=front.fetch_add(1,std::memory_order_relaxed);
> if(i>=size)
> { if(i==size)
> { front.fetch_sub(size,std::memory_order_relaxed);
> }
> i-=size;
> }
What happens if another thread gets to run Pop right here? Let's say this was
the first element added and the queue was created with size = 2, so state is:
count == 0
counter == 1
i == 0
front == 1
buffer[0] = unset yet
So Pop runs:
> bool Pop(T& t)
> { const int count=counter.fetch_sub(1,std::memory_order_relaxed);
count == 1
counter == 0
> if(count<=0)
> { counter.fetch_add(1,std::memory_order_relaxed);
> LogDebug(String("Empty queue pop ")+queueName);
> return false;
> }
> if(count>peakSize)
> { peakSize=count;
> }
> unsigned i=back.fetch_add(1,std::memory_order_relaxed);
i == 0
back == 1
> if(i>=size)
> { if(i==size) //only once, the thread that went off end first
> { back.fetch_sub(size,std::memory_order_relaxed);
> }
> i-=size;
> }
> t=buffer[i];
read of unset item
Note that an acquire barrier is missing here on the reading of buffer[i], along
with the missing release barrier in the Push() function.
Let's make it worse: what happens if a third thread does Push right here?
> bool Push(T t)
> { int count=counter.fetch_add(1,std::memory_order_relaxed);
count = 0
counter == 1
> if(count>int(GetMaxSize()))
> { counter.fetch_sub(1,std::memory_order_relaxed);
> LogError(String("Queue full ")+toString());
> return false;
> }
> unsigned i=front.fetch_add(1,std::memory_order_relaxed);
i == 2
> if(i>=size)
> { if(i==size)
> { front.fetch_sub(size,std::memory_order_relaxed);
front == 0
> }
> i-=size;
i == 0
> }
> buffer[i]=t;
Writing of buffer[0].
Then the first thread resumes and overwrites buffer[0].
--
Thiago Macieira - thiago (AT) macieira.info - thiago (AT) kde.org
Software Architect - Intel Open Source Technology Center
PGP/GPG: 0x6EF45358; fingerprint:
E067 918B B660 DBD1 105C 966C 33F5 F005 6EF4 5358
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/.
.
Author: Robin Rowe <robinsrowe@gmail.com>
Date: Wed, 14 Jan 2015 01:09:15 -0800 (PST)
Raw View
------=_Part_3730_1397385180.1421226555233
Content-Type: multipart/alternative;
boundary="----=_Part_3731_971556668.1421226555233"
------=_Part_3731_971556668.1421226555233
Content-Type: text/plain; charset=UTF-8
Thiago,
You're right that Push isn't atomic on data write, and it's a flaw. Thanks
for catching that. Only the queue index is atomic. That does no harm on
Push because it will write to the right slot eventually. However, there's a
moment where the index has incremented and the data isn't written yet. On
Pop, as you point out, it could read a slot that hasn't been written yet.
In practice this doesn't seem to happen. Just lucky, I guess.
Maybe I can fix this without adding a lock. Thinking about it.
Any other issues?
Robin
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/.
------=_Part_3731_971556668.1421226555233
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">Thiago,<br><br>You're right that Push isn't atomic on data=
write, and it's a flaw. Thanks for catching that. Only the queue index is =
atomic. That does no harm on Push because it will write to the right slot e=
ventually. However, there's a moment where the index has incremented and th=
e data isn't written yet. On Pop, as you point out, it could read a slot th=
at hasn't been written yet. In practice this doesn't seem to happen. Just l=
ucky, I guess.<br><br>Maybe I can fix this without adding a lock. Thinking =
about it.<br><br>Any other issues?<br><br>Robin<br></div>
<p></p>
-- <br />
<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/">http://groups.google.com/a/isocpp.org/group/std-proposals/<=
/a>.<br />
------=_Part_3731_971556668.1421226555233--
------=_Part_3730_1397385180.1421226555233--
.
Author: Thiago Macieira <thiago@macieira.org>
Date: Wed, 14 Jan 2015 08:53:12 -0800
Raw View
On Wednesday 14 January 2015 01:09:15 Robin Rowe wrote:
> Thiago,
>
> You're right that Push isn't atomic on data write, and it's a flaw. Thanks
> for catching that. Only the queue index is atomic. That does no harm on
> Push because it will write to the right slot eventually. However, there's a
> moment where the index has incremented and the data isn't written yet. On
> Pop, as you point out, it could read a slot that hasn't been written yet.
> In practice this doesn't seem to happen. Just lucky, I guess.
>
> Maybe I can fix this without adding a lock. Thinking about it.
>
> Any other issues?
The memory ordering issue that I pointed out is one.
Depending on how you fix the push/pop, be careful of the ABA problem.
--
Thiago Macieira - thiago (AT) macieira.info - thiago (AT) kde.org
Software Architect - Intel Open Source Technology Center
PGP/GPG: 0x6EF45358; fingerprint:
E067 918B B660 DBD1 105C 966C 33F5 F005 6EF4 5358
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/.
.
Author: Tony V E <tvaneerd@gmail.com>
Date: Wed, 14 Jan 2015 13:02:24 -0500
Raw View
--001a11c3c348b50db2050ca08a4f
Content-Type: text/plain; charset=UTF-8
On Wed, Jan 14, 2015 at 4:09 AM, Robin Rowe <robinsrowe@gmail.com> wrote:
> Thiago,
>
> You're right that Push isn't atomic on data write, and it's a flaw. Thanks
> for catching that. Only the queue index is atomic. That does no harm on
> Push because it will write to the right slot eventually. However, there's a
> moment where the index has incremented and the data isn't written yet. On
> Pop, as you point out, it could read a slot that hasn't been written yet.
> In practice this doesn't seem to happen. Just lucky, I guess.
>
> Maybe I can fix this without adding a lock. Thinking about it.
>
yes, it is doable, just may not be easy.
>
> Any other issues?
>
Probably :-)
It is very hard to get lock-free right the first (or second, third, ...)
time.
Other things to consider:
- do you support single consumer, single producer? or multiple? (you can
use different techniques based on what you want to support)
- counter can go arbitrarily negative (if multi-consumer), which probably
makes Push unhappy
- peakCount can decrease (also, why is it set in Pop instead of push?)
- buffer[i] = t is probably not atomic (depends on T's assignment
operator, but unlikely), so even if the rest was correct, a reader could
read a "partial T".
- buffer[i] = t might throw - then what?!
- Open() is obviously not safe to call while Push/Pop is being called
(maybe should be constructor-only?)
- in general, I don't like the idea of a size() function, since by the time
it returns it may no longer be correct. "recentSize()" maybe OK :-)
- etc
I talked about a similar buffer-based lock-free queue at CppCon (
https://www.youtube.com/watch?v=Xf35TLFKiO8) and will hopefully continue
the discussion at C++Now (cppnow.org)
In general, testing doesn't catch all threading bugs - although things like
thread-sanitizer helps a great deal. For a particularly scary story see
"the Problems with Threads"
http://ptolemy.eecs.berkeley.edu/publications/papers/06/problemwithThreads/
where it took 4 years of running before a deadlock bug occurred!
So "in practice" doesn't mean much. You also need "in theory" such as "in
theory, I have proven its correctness, see appendix...".
(of course, for standardization, you only need to specify that it is
correct, and make the implementation someone else's problem, but it would
be nice to know that an implementation was possible :-)
>
> Robin
>
You might also want to look into contributing to Boost - which does have a
(small) library of lock-free containers. Currently only node-based
containers, no buffer based ones.
Tony
--
>
> ---
> You received this message because you are subscribed to the Google Groups
> "ISO C++ Standard - Future Proposals" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to std-proposals+unsubscribe@isocpp.org.
> To post to this group, send email to std-proposals@isocpp.org.
> Visit this group at
> http://groups.google.com/a/isocpp.org/group/std-proposals/.
>
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/.
--001a11c3c348b50db2050ca08a4f
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><br><div class=3D"gmail_extra"><br><div class=3D"gmail_quo=
te">On Wed, Jan 14, 2015 at 4:09 AM, Robin Rowe <span dir=3D"ltr"><<a hr=
ef=3D"mailto:robinsrowe@gmail.com" target=3D"_blank">robinsrowe@gmail.com</=
a>></span> wrote:<br><blockquote class=3D"gmail_quote" style=3D"margin:0=
px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><=
div dir=3D"ltr">Thiago,<br><br>You're right that Push isn't atomic =
on data write, and it's a flaw. Thanks for catching that. Only the queu=
e index is atomic. That does no harm on Push because it will write to the r=
ight slot eventually. However, there's a moment where the index has inc=
remented and the data isn't written yet. On Pop, as you point out, it c=
ould read a slot that hasn't been written yet. In practice this doesn&#=
39;t seem to happen. Just lucky, I guess.<br><br>Maybe I can fix this witho=
ut adding a lock. Thinking about it.<br></div></blockquote><div><br></div><=
div>yes, it is doable, just may not be easy.<br>=C2=A0<br></div><blockquote=
class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px so=
lid rgb(204,204,204);padding-left:1ex"><div dir=3D"ltr"><br>Any other issue=
s?<span class=3D""><font color=3D"#888888"><br></font></span></div></blockq=
uote><div><br></div><div>Probably :-)<br></div><div>It is very hard to get =
lock-free right the first (or second, third, ...) time.<br><br></div><div>O=
ther things to consider:<br></div><div><div>- do you support single consume=
r, single producer? or multiple?=20
(you can use different techniques based on what you want to support)<br></d=
iv>- counter can go arbitrarily negative (if multi-consumer), which probabl=
y makes Push unhappy<br></div><div>- peakCount can decrease (also, why is i=
t set in Pop instead of push?)<br></div>- buffer[i] =3D t=C2=A0 is probably=
not atomic (depends on T's assignment operator, but unlikely), so even=
if the rest was correct, a reader could read a "partial T".<br><=
div>- buffer[i] =3D t=C2=A0 might throw - then what?!<br></div>- Open() is =
obviously not safe to call while Push/Pop is being called (maybe should be =
constructor-only?)<br></div><div class=3D"gmail_quote">- in general, I don&=
#39;t like the idea of a size() function, since by the time it returns it m=
ay no longer be correct. "recentSize()" maybe OK :-)<br></div><di=
v class=3D"gmail_quote"><div>- etc<br></div><div><br></div><div>I talked ab=
out a similar buffer-based lock-free queue at CppCon (<a href=3D"https://ww=
w.youtube.com/watch?v=3DXf35TLFKiO8">https://www.youtube.com/watch?v=3DXf35=
TLFKiO8</a>) and will hopefully continue the discussion at C++Now (<a href=
=3D"http://cppnow.org">cppnow.org</a>)<br><br></div><div>In general, testin=
g doesn't catch all threading bugs - although things like thread-saniti=
zer helps a great deal.=C2=A0 For a particularly scary story see "the =
Problems with Threads" <a href=3D"http://ptolemy.eecs.berkeley.edu/pub=
lications/papers/06/problemwithThreads/">http://ptolemy.eecs.berkeley.edu/p=
ublications/papers/06/problemwithThreads/</a> where it took 4 years of runn=
ing before a deadlock bug occurred!<br><br></div><div>So "in practice&=
quot; doesn't mean much.=C2=A0 You also need "in theory" such=
as "in theory, I have proven its correctness, see appendix...".<=
br></div><div>(of course, for standardization, you only need to specify tha=
t it is correct, and make the implementation someone else's problem, bu=
t it would be nice to know that an implementation was possible :-)<br></div=
><div>=C2=A0<br></div><blockquote class=3D"gmail_quote" style=3D"margin:0px=
0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><di=
v dir=3D"ltr"><span class=3D""><font color=3D"#888888"><br>Robin<br></font>=
</span></div></blockquote><div><br><br></div><div>You might also want to lo=
ok into contributing to Boost - which does have a (small) library of lock-f=
ree containers.=C2=A0 Currently only node-based containers, no buffer based=
ones.<br><br>Tony<br><br><br></div><blockquote class=3D"gmail_quote" style=
=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding=
-left:1ex"><div dir=3D"ltr"><span class=3D""><font color=3D"#888888"></font=
></span></div><div class=3D""><div class=3D"h5">
<p></p>
-- <br>
<br>
--- <br>
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br>
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org" target=3D"_=
blank">std-proposals+unsubscribe@isocpp.org</a>.<br>
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org" target=3D"_blank">std-proposals@isocpp.org</a>.<br>
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/" target=3D"_blank">http://groups.google.com/a/isocpp.org/gro=
up/std-proposals/</a>.<br>
</div></div></blockquote></div><br></div></div>
<p></p>
-- <br />
<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/">http://groups.google.com/a/isocpp.org/group/std-proposals/<=
/a>.<br />
--001a11c3c348b50db2050ca08a4f--
.