[RFC] Atomic Reference Counting - Do you think this would be useful to Boost?
Chris Thomasson
atomic reference counting:
http://groups.google.com/group/comp.programming.threads/msg/7b02ce7b874e6551
I have created an experimental prototype of one of my atomic reference
counting algorithms I posted over in c.p.t:
http://groups.google.com/group/comp.programming.threads/msg/be47a566e4388e0a
Does anybody think that Boost could make use of this level of thread-safety?
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Alberto Ganesh Barbati
> Currently, Boost doesn't provide support for "true" atomically thread-safe
> atomic reference counting:
>
>
http://groups.google.com/group/comp.programming.threads/msg/7b02ce7b874e6551
>
>
> I have created an experimental prototype of one of my atomic reference
> counting algorithms I posted over in c.p.t:
>
>
http://groups.google.com/group/comp.programming.threads/msg/be47a566e4388e0a
>
>
> Does anybody think that Boost could make use of this level of
thread-safety?
>
That might be interesting, but if you want an answer about Boost, you're
in the wrong place, here. Why didn't you post it to one of the Boost
mailing lists?
Ganesh
Earl Purple
Chris Thomasson wrote:
> Currently, Boost doesn't provide support for "true" atomically thread-safe
> atomic reference counting:
>
> http://groups.google.com/group/comp.programming.threads/msg/7b02ce7b874e6551
>
>
> I have created an experimental prototype of one of my atomic reference
> counting algorithms I posted over in c.p.t:
>
> http://groups.google.com/group/comp.programming.threads/msg/be47a566e4388e0a
>
>
> Does anybody think that Boost could make use of this level of thread-safety?
In boost I think there's an option to do so already in
reference-counted pointers. The only problem is that there is no
standard way to do atomic reference counting.
I actually have my own version that has optional atomic counting and it
is used only when necessary. Most of the time it is not. Passing
objects across threads using a producer/consumer queue is one of the
few occasions when they are used. A large collection being manipulated
by a single thread (at a time) is an occasion when they are not.
kanze
> Chris Thomasson wrote:
> > Currently, Boost doesn't provide support for "true"
> > atomically thread-safe atomic reference counting:
> >
http://groups.google.com/group/comp.programming.threads/msg/7b02ce7b874e6551
> > I have created an experimental prototype of one of my atomic reference
> > counting algorithms I posted over in c.p.t:
> >
http://groups.google.com/group/comp.programming.threads/msg/be47a566e4388e0a
> > Does anybody think that Boost could make use of this level of
thread-safety?
> In boost I think there's an option to do so already in
> reference-counted pointers. The only problem is that there is
> no standard way to do atomic reference counting.
Or rather, that the "standard" way (using Boost::mutex) can be
somewhat slow on some platforms.
> I actually have my own version that has optional atomic
> counting and it is used only when necessary. Most of the time
> it is not. Passing objects across threads using a
> producer/consumer queue is one of the few occasions when they
> are used. A large collection being manipulated by a single
> thread (at a time) is an occasion when they are not.
shared_ptr doesn't have the semantics you want when passing
objects accross threads. What you need is auto_ptr.
Regretfully, there's no way of getting an auto_ptr from a
shared_ptr. (On the other hand, I've never had any problem with
auto_ptr's semantics in this case, using raw pointers for
weak_ptr's. Perhaps a weak_ptr for auto_ptr would be the
answer.)
--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
Earl Purple
kanze wrote:
> shared_ptr doesn't have the semantics you want when passing
> objects accross threads. What you need is auto_ptr.
> Regretfully, there's no way of getting an auto_ptr from a
> shared_ptr. (On the other hand, I've never had any problem with
> auto_ptr's semantics in this case, using raw pointers for
> weak_ptr's. Perhaps a weak_ptr for auto_ptr would be the
> answer.)
No, auto_ptr doesn't work in STL collections and prodcon_queue uses
std::deque.
The producer thread is unlikely to want to access the object once
posted to the queue so the only other solution would be to have the
consumer that eventually picks it up make an explicit call (eg call
delete if we're using raw pointers). Of course this explicit call could
be wrapped in a specific smart-pointer.
As far as I'm aware with boost shared_ptr, if you want to use
thread-safety you have to use it all the time, there's no way to
choose. My guess is that tr1 doesn't have any thread-safety feature at
all because it's not standard and tr1 has to be standard.
Jens Theisen
> Currently, Boost doesn't provide support for "true" atomically thread-safe
> atomic reference counting:
>
> http://groups.google.com/group/comp.programming.threads/msg/7b02ce7b874e6551
Just for the record and those who are puzzled by this claim (like me):
shared_ptr _is_ thread safe as documented, and it _does_ use true
atomic reference counting on supported platforms.
The OP is talking about solutions for the problem that a _single_
shared_ptr can't be simultaneously accessed by multiple threads, as
documented.
--
Gruß, Jens
Chris Thomasson
news:1160641223....@m73g2000cwd.googlegroups.com...
> Earl Purple wrote:
>> Chris Thomasson wrote:
>> > Currently, Boost doesn't provide support for "true"
>> > atomically thread-safe atomic reference counting:
[...]
>> > Does anybody think that Boost could make use of this level of
> thread-safety?
[...]
> shared_ptr doesn't have the semantics you want when passing
> objects accross threads.
I also think that shared_ptr<...> does not provide efficient, or any?,
support for strong/atomically thread-safe competing ref-count increments
from multiple threads in parallel; I don't think the following contrived
scenario is valid with shared_ptr<...>. Please correct me if I am wrong:
(pseudo-code)
static shared_ptr<app> g_app(new app(...))
static shared_ptr<foo> g_foo;
void a_number_of_threads() {
for(...) {
// I don't think the following is atomic in current shared_ptr<...>:
shared_ptr<foo> l_foo(g_foo);
if (l_foo) {
if (l_foo->some_predicate(...)) {
shared_ptr<foo> n_foo(new foo(...));
n_foo->local_update(l_foo);
// I don't this cas is even possible in current shared_ptr<...>:
if (! g_foo.cas(l_foo, n_foo)) {
n_foo->local_rollback(l_foo);
g_app->log_rollback(l_foo, n_foo);
}
}
l_foo->some_real_processing(n_foo);
} else { g_app->some_other_processing(...); }
}
return 0;
}
> What you need is auto_ptr.
> Regretfully, there's no way of getting an auto_ptr from a
> shared_ptr. (On the other hand, I've never had any problem with
> auto_ptr's semantics in this case, using raw pointers for
> weak_ptr's. Perhaps a weak_ptr for auto_ptr would be the
> answer.)
Once you have "pure" word-based atomic ref-counts, you can apply normal
word-based atomic operations (e.g., CAS, SWAP; no DWCAS needed) directly to
shared locations that hold a pointer to a ref-count object. So, in order to
get lock-free auto_ptr<...> like semantics with them you could do something
like this contrived scenario:
foo *raw = new foo(...);
atomic_lptr<foo> l_foo(raw);
atomic_sptr<foo> s_new_owner;
// a lock-free transfer-of-ownership from l_foo to s_new_owner
s_new_owner.swap_weak(l_foo, 0);
// l_foo is invalid; if it's non-null we can use it if it does not point to
raw!
if(l_foo && l_foo != raw) {
// we have gained ownership of a new object that we did not create.
}
An example implementation of a lock-free s_new_owner.swap_weak(...)
function, in IA-32 Assembly, can be found here:
http://appcore.home.comcast.net/vzoom/refcount/refcount_ia32_gcc.asm
(in the refcount_ia32_add_swap_weak at the bottom of the file)
It expects the calling thread to own a reference, that why I postfix's the
function name with _weak. If you pass it a count increment of zero (e.g.,
transferring the calling threads reference to the shared location), it just
skips the XADD and does the XCHG. That's virtually equal to auto_ptr<...>
semantics.
I am currently getting a C++ wrapper around my C API's which help implement
a couple of smart pointer classes. Once I release the smart pointers, people
can use them and compare-contrast against shared_ptr<...>. Humm... Could be
interesting...
Any thoughts?
Chris Thomasson
news:ibqdnbGk-uGYvrbY...@comcast.com...
> Currently, Boost doesn't provide support for "true" atomically thread-safe
> atomic reference counting:
[...]
> I have created an experimental prototype of one of my atomic reference
> counting algorithms I posted over in c.p.t:
[...]
> Does anybody think that Boost could make use of this level of
> thread-safety?
Here is an example of what you can do with the C++-based abstraction layer
that I wrapped around my refcount C API; one I release it of course. We can
use it to manage access to a "shared buffer" object of sorts:
(contrived quick pseudo-code!)
#define MYBUFMAXSZ() 4096
#define MYBUFOVERRUNSZ() 0
// quick-and-crude generic buffer
class mybuf {
char *m_base;
char *m_buf;
std::size_t m_sz;
public:
// setup our various smart pointer types...
typedef vzoom::sync::ptr::local<mybuf> ptr_local_t;
typedef vzoom::sync::ptr::weak<mybuf> ptr_weak_t;
typedef vzoom::sync::ptr::strong<mybuf> ptr_strong_t;
private:
static mybuf* myallocator_malloc(std::size_t &sz) {
// crude-and-quick buffer "sanity" check
sz += MYBUFOVERRUNSZ;
if (sz >= MYBUFMAXSZ) { throw; }
mybuf *buf = std::malloc(sz /* adjust for pad and align */);
if (! buf) { assert(buf); throw; }
return buf;
}
static void myallocator_free(mybuf *buf) {
assert(buf); std::free(buf /* adjust for pad and align */);
}
public:
mybuf() throw() : m_base(0), m_buf(0), m_sz(0) {}
mybuf(char const *src)
: m_base(0), m_buf(0), m_sz(0) {
if (! src) { assert(src); throw; }
m_sz = strlen(src) + 1;
m_base = myallocator_malloc(m_sz);
m_buf = std::strcpy(m_base, src);
assert(m_base && m_buf);
}
mybuf(char const *src, char const *concat)
: m_base(0), m_buf(0), m_sz(0) {
if (! src || ! concat) { assert(src && concat); throw; }
m_sz = strlen(src) + strlen(concat) + 2;
m_base = myallocator_malloc(m_sz);
m_buf = std::strcpy(m_base, src);
m_buf = std::strcat(m_buf, concat);
assert(m_base && m_buf);
}
~mybuf() throw() {
try { myallocator_free(m_base); } catch(...) { assert(false);
std::abort(); }
}
public:
// rollback a previous local concatenation
void rollback_local(...) {
// ...
}
// resets a previous concatenation
void reset_local(char const *src, char const *concat) {
// ...
}
public:
char const* c_ptr() const { return m_buf; }
std::size_t bufsize() const { return m_sz; }
};
#include <stdio.h>
#include <string.h>
static mybuf::ptr_strong_t g_shared_buf(new mybuf("InitialValue"));
void threads_a_to_whatever_in_parallel(...) {
for(...) {
// misc. app logic ... {
// read the shared buffer
do {
// read the shared buffer
mybuf::ptr_local_t cmp = g_shared_buf, xchg;
// check for null... :)
if (! cmp) { break; }
if (! xchg) {
// create a local buffer and update it; do this only one time!
xchg.reset(new mybuf(cmp, "ANewAppendedValue"));
} else {
// rollback the previous update; the CAS failed, we need to
locally reset...
xchg->rollback_local(...);
// re-update the local buffer.
xchg->reset_local(cmp, "ANewAppendedValue");
}
// try and update the shared buffer with our local buffer
} while(! g_shared_buf.cas(cmp, xchg));
// some more misc. app logic ...
}
}
You can have atomically thread-safe, mostly lock-free COW-based C++ string
objects with my counting algorithm...
Any thoughts?
kanze
> kanze wrote:
> > shared_ptr doesn't have the semantics you want when passing
> > objects accross threads. What you need is auto_ptr.
> > Regretfully, there's no way of getting an auto_ptr from a
> > shared_ptr. (On the other hand, I've never had any problem with
> > auto_ptr's semantics in this case, using raw pointers for
> > weak_ptr's. Perhaps a weak_ptr for auto_ptr would be the
> > answer.)
> No, auto_ptr doesn't work in STL collections and prodcon_queue
> uses std::deque.
So. You take it out of the auto_ptr, and put it into the queue.
During which time, the queue is the owner, and not the auto_ptr.
That's an implementation detail, of course. The important point
is that the interface to the queue uses an auto_ptr, so that the
thread yielding possession cannot continue accessing the object.
Behind the scenes, you do whatever is necessary for it to work.
(My own MessageQueue also uses deque.)
> The producer thread is unlikely to want to access the object
> once posted to the queue so the only other solution would be
> to have the consumer that eventually picks it up make an
> explicit call (eg call delete if we're using raw pointers).
With a well designed system, the producer thread cannot access
the object once posted to the queue. I don't want the
robustness of my software to depend only on good intentions.
> Of course this explicit call could be wrapped in a specific
> smart-pointer.
> As far as I'm aware with boost shared_ptr, if you want to use
> thread-safety you have to use it all the time, there's no way
> to choose.
As far as I'm aware of with boost shared_ptr, once the object
belongs to a shared_ptr, it always belongs to shared_ptr;
there's no way around that. And that model doesn't work accross
thread boundaries, since shared_ptr doesn't have the desired
semantics for the boundary.
> My guess is that tr1 doesn't have any thread-safety feature at
> all because it's not standard and tr1 has to be standard.
TR1 isn't part of the standard yet. It is in the process of
being adopted. As are threads. Presumably, the version of the
standard which adoptes TR1 will also address thread safety
issues. But I don't think anyone has yet given consideration to
this with regards to shared_ptr.
--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
Chris Thomasson
news:878xjl5...@arcor.de...
> "Chris Thomasson" <cri...@comcast.net> writes:
>
>> Currently, Boost doesn't provide support for "true" atomically
>> thread-safe
>> atomic reference counting:
>>
>>
http://groups.google.com/group/comp.programming.threads/msg/7b02ce7b874e6551
>
> Just for the record and those who are puzzled by this claim (like me):
>
> shared_ptr _is_ thread safe as documented, and it _does_ use true
> atomic reference counting on supported platforms.
I think I have to disagree here, unless, they are now using logic like Joe
Seighs atomic_ptr? Or, something this:
http://groups.google.com/group/comp.programming.threads/browse_frm/thread/f2
c94118046142e8
(hummm, Joes atomic_ptr shows up in a SUN patent... Interesting! :)
AFAICT, shared_ptr uses nothing like that. I think you may be confusing
normal reference counting, with atomically thread-safe reference counting;
there is a BIG difference between the two...
> The OP is talking about solutions for the problem that a _single_
> shared_ptr can't be simultaneously accessed by multiple threads, as
> documented.
That proves that it's not truly atomically thread-safe. IMHO, shared_ptr
should be able to address this...
Jens Theisen
> > shared_ptr _is_ thread safe as documented, and it _does_ use true
> > atomic reference counting on supported platforms.
>
> I think I have to disagree here, unless, they are now using logic like Joe
> Seighs atomic_ptr? Or, something this:
> http://groups.google.com/group/comp.programming.threads/browse_frm/thread/f2
> c94118046142e8
> (hummm, Joes atomic_ptr shows up in a SUN patent... Interesting! :)
Neither of your quotings make it particularly clear what atomic_ptr does
over shared_ptr; I'm sure there is something, but I suspect not that
shared_ptr generally isn't thread safe. What is it?
> AFAICT, shared_ptr uses nothing like that. I think you may be confusing
> normal reference counting, with atomically thread-safe reference counting;
> there is a BIG difference between the two...
>From shared_ptr's source for the x86 platform on gcc:
inline void atomic_increment( int * pw )
{
//atomic_exchange_and_add( pw, 1 );
__asm__
(
"lock\n\t"
"incl %0":
"=m"( *pw ): // output (%0)
"m"( *pw ): // input (%1)
"cc" // clobbers
);
}
That looks fairly atomic to me. I appreciate that this doesn't mean
that every use of shared_ptr is thread safe. However, a good chunk of
them are, if the documentation is correct.
Do you think the documentation is wrong? In what way is it wrong?
--
Gruß, Jens
Joe Seigh
> "Chris Thomasson" <cri...@comcast.net> writes:
....
>
>>http://groups.google.com/group/comp.programming.threads/browse_frm/thread/f2
>>c94118046142e8
>>(hummm, Joes atomic_ptr shows up in a SUN patent... Interesting! :)
>
>
> Neither of your quotings make it particularly clear what atomic_ptr does
> over shared_ptr; I'm sure there is something, but I suspect not that
> shared_ptr generally isn't thread safe. What is it?
>
>
>>AFAICT, shared_ptr uses nothing like that. I think you may be confusing
>>normal reference counting, with atomically thread-safe reference counting;
>>there is a BIG difference between the two...
>
>
>>From shared_ptr's source for the x86 platform on gcc:
>
>
> That looks fairly atomic to me. I appreciate that this doesn't mean
> that every use of shared_ptr is thread safe. However, a good chunk of
> them are, if the documentation is correct.
>
> Do you think the documentation is wrong? In what way is it wrong?
>
The distinction is atomically thread-safe vs. just thread-safe.
atomic_ptr is like Java pointers. You neither have to own the
source nor the target pointer to safely copy them. There's been
prior discussion on this a while back. Unless you're doing some
sort of lock-free programming, atomic-ptr is overkill for normal
stuff.
AFAIK, Sun is patenting the algorithm (Maurice Herlihy is one of the
inventors on the patent). While it may be atomically thread-safe,
it probably won't be lawyer safe. :)
--
Joe Seigh
When you get lemons, you make lemonade.
When you get hardware, you make software.
Chris Thomasson
> #define MYBUFMAXSZ() 4096
> #define MYBUFOVERRUNSZ() 0
[...]
DOH! I forgot treat the macros as function calls!
> sz += MYBUFOVERRUNSZ;
> if (sz >= MYBUFMAXSZ) { throw; }
[...]
sz += MYBUFOVERRUNSZ();
if (sz >= MYBUFMAXSZ()) { throw; }
of course!
Chris Thomasson
Man... One more thing! Every 'mybuf' should be changed to 'char' in the
following piece of code:
> static mybuf* myallocator_malloc(std::size_t &sz) {
> // crude-and-quick buffer "sanity" check
> sz += MYBUFOVERRUNSZ;
> if (sz >= MYBUFMAXSZ) { throw; }
> mybuf *buf = std::malloc(sz /* adjust for pad and align */);
> if (! buf) { assert(buf); throw; }
> return buf;
> }
>
> static void myallocator_free(mybuf *buf) {
> assert(buf); std::free(buf /* adjust for pad and align */);
> }
I think I needed some a couple of more pots of coffee when I was typing that
little buffer thing out in Outlook!
Sorry for any confusion!
Jens Theisen
> The distinction is atomically thread-safe vs. just thread-safe.
> atomic_ptr is like Java pointers. You neither have to own the
> source nor the target pointer to safely copy them. There's been
> prior discussion on this a while back. Unless you're doing some
> sort of lock-free programming, atomic-ptr is overkill for normal
> stuff.
That sounds very much as if the distinction is indeed in the area
where shared_ptr is documented not to be thread safe - namely
concurrent read/write access to the same shared_ptr.
It's true, I'm not only confusing the definitions above, I have no
clue what they are. I'm only aware of shared_ptr's thread safety
guarantees - and to anyone lacking knowledge of the above the OP will
sound like a claim that they don't hold; I just wanted to reassure
other people with this level of expertise that they do, and that this
thread is about something else.
Is there a paper to read up on this?
> AFAIK, Sun is patenting the algorithm (Maurice Herlihy is one of the
> inventors on the patent). While it may be atomically thread-safe,
> it probably won't be lawyer safe. :)
Oh my.
--
Cheers, Jens
--
Chris Thomasson
news:x96dnasfzPPZrK3Y...@comcast.com...[...]
> prior discussion on this a while back. Unless you're doing some
> sort of lock-free programming, atomic-ptr is overkill for normal
> stuff.
Well, atomic_ptr had to use a lot of CAS-Loops; I don't think it had
loopless lock-free code-paths... FWIW, my experimental counting makes no
use
of *CAS, and it only hits a code-path that takes a hashed spinlock when a
thread acquires its first/initial reference, and when the count drops to
zero. Other than that, all of the atomic counter and pointer operations are
100% loop-less and lock-free; no cas, only XCHG and XADD...
> AFAIK, Sun is patenting the algorithm (Maurice Herlihy is one of the
> inventors on the patent). While it may be atomically thread-safe,
> it probably won't be lawyer safe. :)
Luckily, the refcount algorithm I am going to submit to Boost is my prior
art, I don't think it's patent... yet... atomic_ptr is yours, except there
is a patent that claims it; exactly... The single-target synchronization
thing is DWCAS, plain and simple. They describe the DWCAS version of your
atomic_ptr...
;^)
* A newer version, not released yet, makes use of CAS when a user wants to
use the algorithm for lock-free COW operations...
--
Chris Thomasson
> Joe Seigh <jsei...@xemaps.com> writes:
>
>> The distinction is atomically thread-safe vs. just thread-safe.
>> atomic_ptr is like Java pointers. You neither have to own the
>> source nor the target pointer to safely copy them. There's been
>> prior discussion on this a while back. Unless you're doing some
>> sort of lock-free programming, atomic-ptr is overkill for normal
>> stuff.
>
> That sounds very much as if the distinction is indeed in the area
> where shared_ptr is documented not to be thread safe - namely
> concurrent read/write access to the same shared_ptr.
>
> It's true, I'm not only confusing the definitions above, I have no
> clue what they are. I'm only aware of shared_ptr's thread safety
> guarantees - and to anyone lacking knowledge of the above the OP will
> sound like a claim that they don't hold; I just wanted to reassure
> other people with this level of expertise that they do, and that this
> thread is about something else.
>
> Is there a paper to read up on this?
patent application: 20060037026
I read the entire 21-page patent teachings, only to find our that they were
teaching me how to implement Joes algorithm...
:)
Chris Thomasson
> atomic reference counting:
[...]
> Does anybody think that Boost could make use of this level of
> thread-safety?
I should also point out that no part of shared_ptr<...>'s interface should
be utilized within the context of a signal handler; correct? I don't think
any part of shared_ptr<...> is async-signal-safe? If not, you can use my
experimental prototype in a signal handler if you follow a couple of basic
rules... You can apply weak increments in a signal handler. You can
sometimes apply strong decrements if the reference count is guaranteed to
not drop to zero. You don't want to drop to zero in a signal handler unless
you follow a particular usage paradigm... Here is some more information wrt
my refcount algorithm and async-signal-safety:
http://groups.google.com/group/comp.programming.threads/msg/0022ef08ae26e2f3
http://groups.google.com/group/comp.programming.threads/msg/667b1867c19e6288
Here is a tweak/patch that I am currently prototyping in IA-32:
http://groups.google.com/group/comp.programming.threads/msg/9ee468f341a33ee2
After this is properly applied to my algorithm, it can perform weak
increments and decrements the context of a signal handler... The count can
now drop to zero in a signal handler; no problem... One more thing... My
refcount algorithm can work with shared-memory for process-wide refounting
schemes...
I think I am going to go ahead and post my C++ wrappers here, before I
submit anything directly to Boost... There is always the chance that my
submission could be rejected; I will make it an open-source, "mostly"
lock-free atomic reference counting alternative to shared_ptr<...> if that
happens.
Oh yeah, a version for the SPARC-32/64 is also on the way...
I think Boost should benefit from having a smart pointer that exhibits
thread-safety characteristics' that make it able to emulate Java pointer
functionality; any thoughts?
James Kanze
> "kanze" <ka...@gabi-soft.fr> wrote in message
> news:1160641223....@m73g2000cwd.googlegroups.com...
> > Earl Purple wrote:
> >> Chris Thomasson wrote:
> >> > Currently, Boost doesn't provide support for "true"
> >> > atomically thread-safe atomic reference counting:
> [...]
> >> > Does anybody think that Boost could make use of this level of
> >> > thread-safety?
> [...]
> > shared_ptr doesn't have the semantics you want when passing
> > objects accross threads.
> I also think that shared_ptr<...> does not provide efficient,
> or any?, support for strong/atomically thread-safe competing
> ref-count increments from multiple threads in parallel;
It could, if there were any reason for it to. I think there's
an issue of cause and effect here: the semantics of shared_ptr
are inappropriate for objects shared between threads, so there's
no real use in making it "thread safe".
> I don't think the following contrived scenario is valid with
> shared_ptr<...>. Please correct me if I am wrong:
> (pseudo-code)
> static shared_ptr<app> g_app(new app(...))
> static shared_ptr<foo> g_foo;
> void a_number_of_threads() {
> for(...) {
> // I don't think the following is atomic in current shared_ptr<...>:
> shared_ptr<foo> l_foo(g_foo);
I can't see any reason why it should be. I can't imagine any
use where it wouldn't lead to a programming error later.
There might be some vague argument concerning
shared_ptr< foo const >, but I can't think of any realistic
situations where it would be appropriate (just as a I cannot
think of any realistic cases where you would have a shared_ptr
with static lifetime). The fact that I can't think of them
doesn't mean that they don't exist, of course, but it sort of
makes me think that they are at least rare enough that the
committee needed waste too much time on them.
> n_foo->local_update(l_foo);
> return 0;
> }
Again, I'm not really convinced. Most of the time, anyway, you
need to inform the other thread that the object is available,
either putting it in a queue, so the other thread can pick it up
later, if it is busy, or unblocking the other thread, if it was
already waiting. There are probably more exceptions to this
than to the former case, but again, I'd really like to hear
about some non-contrived scenarios.
[...]
> Any thoughts?
For the moment, I have the impression that I'm seeing solutions
looking for a problem. Maybe in some domain I'm less familiar
with?
--
James Kanze (Gabi Software) email: kanze...@neuf.fr
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
Peter Dimov
> I think Boost should benefit from having a smart pointer that exhibits
> thread-safety characteristics' that make it able to emulate Java pointer
> functionality; any thoughts?
Do you hold any patents on it?
Peter Dimov
> AFAIK, Sun is patenting the algorithm (Maurice Herlihy is one of the
> inventors on the patent). While it may be atomically thread-safe,
> it probably won't be lawyer safe. :)
Since your (published) work on atomic_ptr seems to be prior art, will
you do something to oppose the patent? Or is it not worth it? I see
that you even pulled atomic_ptr from the site, why?
--
Peter Dimov
> Chris Thomasson wrote:
> > I don't think the following contrived scenario is valid with
> > shared_ptr<...>. Please correct me if I am wrong:
>
> > (pseudo-code)
>
> > static shared_ptr<app> g_app(new app(...))
> > static shared_ptr<foo> g_foo;
>
> > void a_number_of_threads() {
> > for(...) {
>
> > // I don't think the following is atomic in current shared_ptr<...>:
> > shared_ptr<foo> l_foo(g_foo);
>
> I can't see any reason why it should be. I can't imagine any
> use where it wouldn't lead to a programming error later.
This is the reader-writer problem. One scenario is
void reader()
{
shared_ptr<foo> local( g_foo );
// use local to compute something
}
void writer()
{
shared_ptr<foo> local( g_foo );
shared_ptr<foo> next( new foo( *local ) );
local.reset();
next->update();
g_foo = next; // race here
}
One could put a fast reader-writer lock around g_foo, of course, but it
wouldn't be truly lock-free.
--
Joe Seigh
> Joe Seigh wrote:
>
>
>>AFAIK, Sun is patenting the algorithm (Maurice Herlihy is one of the
>>inventors on the patent). While it may be atomically thread-safe,
>>it probably won't be lawyer safe. :)
>
>
> Since your (published) work on atomic_ptr seems to be prior art, will
> you do something to oppose the patent? Or is it not worth it? I see
> that you even pulled atomic_ptr from the site, why?
>
>
Probably not worth it based on present usage of atomic_ptr. They (Sun)
know about atomic_ptr. Whether they think it's the same as their
stuff is up to them. Even if atomic_ptr is prior art, it would
still be expensive to prove it. The open source as prior art project
is a bit of a joke. It's not for the benefit of open source. It's
for the benefit of corporations who want to use it to keep down the
number of spurious patents being used against them. The process
of deciding what constitues prior art is done by the patent office
and the corporations engaged in the patent process. Open source
developers won't be a party to this process unless they want to
contribute their own time for the benefit of corporations.
Also, I probably shouldn't have told Sun since they usually write
up a paper on the things they do and would do a much better job
on the paper than I would. :)
The big problem for C++ will be if and when C++ does get around
to standarding on multi-threading, what will be available for
the standard to use? If everything is patented, as everything
lately seems to be, you will depend on corporate participants
in the standard to make their technology available. So it's
good to have alternative schemes such as the one Chris proposed.
--
Joe Seigh
When you get lemons, you make lemonade.
When you get hardware, you make software.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
Chris Thomasson
news:1160915500....@i3g2000cwc.googlegroups.com...
> Chris Thomasson wrote:
>
>> I think Boost should benefit from having a smart pointer that exhibits
>> thread-safety characteristics' that make it able to emulate Java pointer
>> functionality; any thoughts?
>
> Do you hold any patents on it?
I hold no patents, and have none pending on my refcount algorithm. I
also do
not think that there are any existing patents that claim my algorithm... I
think this algorithm is, or can be, compatible with Boost. Anyway, I am
planning on submitting my C++ here for an "informal review" of sorts,
sometime within the next couple of days.
I am a little weary of my C++ skills, so I would rather get informal review
here before I shoot it all over to the Boost reviewers; who knows, it might
get accepted...
;)
kanze
> > > (pseudo-code)
> > > void a_number_of_threads() {
> > > for(...) {
Well, the context requires memory synchronization, and something
to ensure the atomicity of the update of g_foo.
But it begs the point. I can easily image abstract, constructed
cases where you'd need some sort of locking or synchronization.
I can't find any practical application for them, however.
Consider, for example, what you might want if g_foo pointed to
configuration data, read from a file. Your writer function
detects that the configuration file has changed (i.e. a newer
time stamp, or there was a signal telling the program to
rereaded it). At this point, however, it is important that any
given transaction see a coherent view of the configuration. And
within a transaction, it's quite possible that there are several
"readers". So you'll probably want to synchronize the writer
with the transaction logic, at a higher level. And this is the
case for every scenario that I can think of. My impression is
that when dealing with global data, shared_ptr is a bit too low
level; you need something higher level (and once you've got it,
shared_ptr becomes caduc).
Also, of course, global variables don't normally hold critical
resources that must be freed in a timely manner. So you can
just use ordinary pointers, and let the Boehm collector do the
cleaning up. No reason to introduce extra complexity.
Where a shared_ptr is useful for managing global data, IMHO, is
where you have a singleton. Calling instance() acquires a lock,
and returns a shared_ptr whose "destructor" frees the lock. It
is, perhaps, somewhat dangerous, in that anyone keeping a
pointer blocks the entire system, but then, anyone keeping a
pointer needs the lock, no matter how you manage it, and so will
block the system anyway.
--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
Peter Dimov
> Also, of course, global variables don't normally hold critical
> resources that must be freed in a timely manner. So you can
> just use ordinary pointers, and let the Boehm collector do the
> cleaning up. No reason to introduce extra complexity.
Yes, of course. The pattern is trivial when you rely on an external
garbage collector; that's why lock-free algorithms are much easier in
Java. atomic_ptr is for cases where you use plain old GCless C++. Very
unfashionable, I know. :-)
--
Chris Thomasson
> atomic reference counting:
[...]
> Does anybody think that Boost could make use of this level of
> thread-safety?
Here is a crude and experimental C++ wrapper that abstracts my refcount
algorithms C API/ABI:
http://appcore.home.comcast.net/vzoom/refcount/
http://appcore.home.comcast.net/vzoom/refcount/refcount.hpp
http://appcore.home.comcast.net/vzoom/refcount/refcount-sys.hpp
http://appcore.home.comcast.net/vzoom/refcount/refcount-ia32-0-0-0-2.zip
It currently has two smart pointer classes vzsync::ptr::global<T> and
vzsync::ptr::local<T>. You use ptr::global for the times when multiple
threads could access it concurrently (e.g., strong competing access). You
use ptr::local for the times when only a single thread will ever access it
(e.g., local on the stack). I am going to add a CAS function to this in the
next couple of days. That way you can implement various atomic COW
techniques with the smart pointer interfaces...
Chris Thomasson
> kanze wrote:
>
>> Also, of course, global variables don't normally hold critical
>> resources that must be freed in a timely manner. So you can
>> just use ordinary pointers, and let the Boehm collector do the
>> cleaning up. No reason to introduce extra complexity.
>
> Yes, of course. The pattern is trivial when you rely on an external
> garbage collector; that's why lock-free algorithms are much easier in
> Java. atomic_ptr is for cases where you use plain old GCless C++. Very
> unfashionable, I know. :-)
You can't do efficient PDR in Java. The Garbage Collector is nice, however
it far from ideal solution... I would prefer that C++ not define a garbage
collection model. A GC seems to "high-level" for C++... IMHO at least...
Every access is either a #LoadStore | #StoreStore, or a #LoadStore |
#LoadLoad... Clearly, PDR only requires #LoadLoad w/ Data-Dependency Hint:
https://coolthreads.dev.java.net/servlets/ProjectForumMessageView?forumID=1797&messageID=11068
I hope C++ memory model is not as strict as Java!
:O
Chris Thomasson
Abstraction C API/ABI. It had to do with the fact that the
g_spinlock_ia32_table_mem, g_spinlock_ia32_table global variables and the
spinlock_ia32_libinit(void) function were declared static. These dosen't
work well with multiple translation units; you can get multiple copies of
the table per-process. I added the 'spinlock-ia32.c' file to the library in
order to keep a global copy of the locking table. Of course, this particular
bug didn't show up before because all of my initial test applications only
consisted of a single translation unit!
I had to add this file:
http://appcore.home.comcast.net/vzoom/refcount/spinlock-ia32.c
And alter this one:
http://appcore.home.comcast.net/vzoom/refcount/spinlock-ia32.h
You should probably re-download:
http://appcore.home.comcast.net/vzoom/refcount/refcount-ia32-0-0-0-2.zip
Thank You!