Thread-safe reference counts.
jason.c...@gmail.com
thread, and then used by multiple threads and freed when they are no
longer needed. I think that reference counting is the most appropriate
way to handle this in my situation.
However, my code currently has a very obvious problem in it. Here is
how I have reference counting implemented for my objects, basically
(sorry about any errors I am typing this here in this message):
=== BEGIN CODE ===
class A {
public:
A ();
void AddRef ();
void Release ();
private:
~A ();
int refs_; // reference count
pthread_mutex_t mtx_; // protects refs_
};
// constructor inits reference count to 1
A::A ()
: refs_(1), mtx_(PTHREAD_MUTEX_INITIALIZER)
{
}
// increment count
void A::AddRef () {
pthread_mutex_lock(&mtx_);
++ refs_;
pthread_mutex_unlock(&mtx_);
}
// decrement count, destroying object at 0.
void A::Release () {
bool deleteme;
pthread_mutex_lock(&mtx_);
-- _refs;
deleteme = (_refs == 0);
pthread_mutex_unlock(&mtx_);
// <--- and here is the problem!
if (deleteme)
delete this;
}
=== END CODE ===
The problem is in Release(). There is a short period of time where the
mutex is unlocked but the object is already doomed for destruction; if
another thread calls AddRef() during that time, that other thread now
has a pointer to garbage and doesn't know it.
I can't delete this before unlocking the mutex. There is also a second
problem, where even if, hypothetically speaking, I could do the delete
inside the mutex lock in release, there's still the problem where
another thread may have called AddRef() in the mean time, and it is
blocking on that mutex, and by the time Release() returns if the
reference count had decreased to 0, the object is deleted, the thread
blocking in AddRef() continues, and operates on the object that's
already been deleted.
So I have two questions:
1) I have no specific reason for implementing this all by hand. I am
not completely familiar with boost, though. Is there some boost thread-
safe reference counting thing that I can use to take care of this all
for me?
2) In any case, how can I fix the above problems in my own code? I
can't quite get my head around it, it seems like it's not possible to
do reference counting from "within" the object; that I need some kind
of external "wrapper" around it instead. Also I am unsure about the
logic that I'd need to use to protect against the case where AddRef
blocks on the mutex, Release destroys the object, then AddRef
continues on a deleted object. Really I guess what I said in #1 was
kind of a lie: I certainly wouldn't *mind* not using boost, as I'm
currently not using boost for anything else in this project, and
installing boost on all the development machines is a *minor* hassle
(nothing I can't overcome, but I don't mind implementing this by hand
at this stage in this particular project, at least).
Thanks,
Jason
jason.c...@gmail.com
<jason.cipri...@gmail.com> wrote:
> Is there some boost thread-
> safe reference counting thing that I can use to take care of this all
> for me?
I see boost::shared_ptr, which appears to do exactly what I want. I'll
just accept the fact that it works by magic and move on with my life.
Jason
Sam
> So I have two questions:
>
> 1) I have no specific reason for implementing this all by hand. I am
> not completely familiar with boost, though. Is there some boost thread-
> safe reference counting thing that I can use to take care of this all
> for me?
Boost's shared_ptr class does this. The flaw in your logic is that you
require explicit action by a thread to register and deregister a reference
to an instance of a class.
The correct approach is to incorporate registration and deregistration into
any instance of a pointer to an instance of the class, so this is handled
automatically by the pointer implementation. Any time the pointer is passed,
the copy constructor registers another reference to the class. ANy time a
pointer goes out of scope, the reference gets deregisters. When the
reference count goes to 0, by definition that means the last pointer to the
class instance just went out of scope, and the object can be safely
destructed.
That's what Boost's shared_ptr does. Although -- much like the rest of
Boost's code -- it is horribly inefficient, and suffers from certain design
flaws -- it is often a good starting point for your own reference-counted
pointers.
> of external "wrapper" around it instead. Also I am unsure about the
> logic that I'd need to use to protect against the case where AddRef
> blocks on the mutex, Release destroys the object, then AddRef
> continues on a deleted object.
You need to wrap your brain around the concept that /every/ time a pointer
to the object gets instantiated, the reference count gets increased, and
/every/ time a pointer to the object goes out of scope, the reference count
gets decreased, so when the reference count goes to 0, by definition, no
more pointers to the object exist and it's safe to delete it.
You don't want to do it manually, by hand, so that's why you want to use an
explicit pointer object class, that handles the reference counting as part
of its constructor, copy constructor, assignment operator, and destructor.
That's the only way to do it reliably.
> Really I guess what I said in #1 was
> kind of a lie: I certainly wouldn't *mind* not using boost, as I'm
> currently not using boost for anything else in this project, and
Then don't. Resist the temptation to use Boost as long as you can. Many
years from now, you'll be thankful for that. Define and implement your own
pointer class, and use this as a learning experience. True, your reference
counting implementation will be much slower than Boost's. Boost does not use
mutexes for this, rather it uses CPU-specific atomic increment/decrement
instructions (and gets it partially wrong, by the way). But this is a good
way to learn some important principles of thread-safe programming.
jason.c...@gmail.com
lot of my suspicions.
On Mar 26, 10:00 pm, Sam <s...@email-scan.com> wrote:
> That's what Boost's shared_ptr does. Although -- much like the rest of
> Boost's code -- it is horribly inefficient, and suffers from certain design
> flaws -- it is often a good starting point for your own reference-counted
> pointers.
I can't comment on shared_ptr's efficiency since I have no experience
with it. Blinding efficiency is not important for this particular
application, however, but as far as "certain design flaws"... is there
anything in particular that I should watch out for? I'm not doing
anything weird, I have STL containers of shared_ptr<Object>'s, I
sometimes return shared_ptr<Object>'s from functions, other than that
it's pretty basic stuff. So far in my shared_ptr experiments it seems
to be well-behaved; although using "ptr.reset(new Object)" is a little
strange when you are used to "ptr = new Object" -- but it makes sense
(similarily, "thelist.push_back(MyPtr(new Object))" as opposed to
"thelist.push_back(new Object)" -- but I'm thankful for the explicit
constructor, it's helping me catch some mistakes).
> You need to wrap your brain around the concept that /every/ time a pointer
> to the object gets instantiated, the reference count gets increased, and
> /every/ time a pointer to the object goes out of scope, the reference count
> gets decreased, so when the reference count goes to 0, by definition, no
> more pointers to the object exist and it's safe to delete it.
Thanks for explaining it this way; I had been thinking about it on a
wider scope, like "when this thread gets a pointer, the reference
count is incremented, and when this thread is done with it, decrement
it" -- which was confusing the heck out of me.
> [snip] Define and implement your own
> pointer class, and use this as a learning experience. True, your reference
> counting implementation will be much slower than Boost's.[snip]
> But this is a good
> way to learn some important principles of thread-safe programming.
Definitely; at least for a learning experience, I was planning on
doing this at the end of this project. I appreciate the shared_ptr's
magic but it's always good to know what's going on under the hood.
Thanks again,
Jason
Chris Thomasson
<jason.c...@gmail.com> wrote in message
news:66accfe0-0a27-4da4...@s13g2000prd.googlegroups.com...
>I have some code where objects are dynamically allocated by some
> thread, and then used by multiple threads and freed when they are no
> longer needed. I think that reference counting is the most appropriate
> way to handle this in my situation.
>
> However, my code currently has a very obvious problem in it. Here is
> how I have reference counting implemented for my objects, basically
> (sorry about any errors I am typing this here in this message):
[...]
Your question about another thread calling AddRef while one is calling
Release and dropping to zero means that you need strong thread-safety which
shared_ptr does not provide. Here are some implementations you can take a
look at:
Joe Seighs work:
http://atomic-ptr-plus.sourceforge.net/
http://groups.google.com/group/comp.programming.threads/browse_frm/thread/3c763698da537d8f
My work:
http://appcore.home.comcast.net/~appcore/vzoom/refcount
http://groups.google.com/group/comp.programming.threads/browse_frm/thread/177609a5eff4a466
(100% portable version (e.g., POSIX Threads)
Here is some information on strong thread-safety:
http://groups.google.com/group/comp.programming.threads/browse_frm/thread/e5167941d32340c6
If you have any questions, please feel free to ask. I know that we can work
out a soultion.
Chris Thomasson
news:E6idnXXztKuPvnba...@comcast.com...
> [comp.programming.threads added]
>
> <jason.c...@gmail.com> wrote in message
> news:66accfe0-0a27-4da4...@s13g2000prd.googlegroups.com...
>>I have some code where objects are dynamically allocated by some
>> thread, and then used by multiple threads and freed when they are no
>> longer needed. I think that reference counting is the most appropriate
>> way to handle this in my situation.
>>
>> However, my code currently has a very obvious problem in it. Here is
>> how I have reference counting implemented for my objects, basically
>> (sorry about any errors I am typing this here in this message):
> [...]
>
> Your question about another thread calling AddRef while one is calling
> Release and dropping to zero means that you need strong thread-safety
> which shared_ptr does not provide. Here are some implementations you can
> take a look at:
Here is context that I accidentally snipped:
<jason.c...@gmail.com> wrote in message
news:66accfe0-0a27-4da4...@s13g2000prd.googlegroups.com...
{
The problem is in Release(). There is a short period of time where the
mutex is unlocked but the object is already doomed for destruction; if
another thread calls AddRef() during that time, that other thread now
has a pointer to garbage and doesn't know it.
I can't delete this before unlocking the mutex. There is also a second
problem, where even if, hypothetically speaking, I could do the delete
inside the mutex lock in release, there's still the problem where
another thread may have called AddRef() in the mean time, and it is
blocking on that mutex, and by the time Release() returns if the
reference count had decreased to 0, the object is deleted, the thread
blocking in AddRef() continues, and operates on the object that's
already been deleted.
}
According to the text above, you need strong thread-safety; period. You not
following the rule of basic thread-safety which says that a thread _cannot_
acquire a reference to an object that it does not already own a reference
to. If your application does not follow that rule, then you need something
like Joe's excellent atomic_ptr.
Chris Thomasson
>
> <jason.c...@gmail.com> wrote in message
> news:66accfe0-0a27-4da4...@s13g2000prd.googlegroups.com...
>>I have some code where objects are dynamically allocated by some
>> thread, and then used by multiple threads and freed when they are no
>> longer needed. I think that reference counting is the most appropriate
>> way to handle this in my situation.
>>
>> However, my code currently has a very obvious problem in it. Here is
>> how I have reference counting implemented for my objects, basically
>> (sorry about any errors I am typing this here in this message):
> [...]
>
> Your question about another thread calling AddRef while one is calling
> Release and dropping to zero means that you need strong thread-safety
> which shared_ptr does not provide. Here are some implementations you can
> take a look at:
Jason, when you get some time, I would advise you to go ahead and read
through the following paper:
This should clear up all of your questions. If not, well,
'comp.programming.threads' is there to help you. IMHO, the traffic in that
group has been sort of sparse lately; we welcome any of your subsequent
queries!
:^)
Gianni Mariani
Alot of libraries do this. I implemented it in Austria C++.
at::PtrTarget_MT provides the definition of the thread safe reference
counted base class.
(defined on line 210)
http://austria.svn.sourceforge.net/viewvc/austria/src/austria/code/at_lifetime_mt.h?view=markup#l_210
It's also portable across Windows and Linux(x86 +amd64).
Torsten Robitzki
> [comp.programming.threads added]
>
> <jason.c...@gmail.com> wrote in message
> news:66accfe0-0a27-4da4...@s13g2000prd.googlegroups.com...
>
>> I have some code where objects are dynamically allocated by some
>> thread, and then used by multiple threads and freed when they are no
>> longer needed. I think that reference counting is the most appropriate
>> way to handle this in my situation.
>>
>> However, my code currently has a very obvious problem in it. Here is
>> how I have reference counting implemented for my objects, basically
>> (sorry about any errors I am typing this here in this message):
>
> [...]
>
> Your question about another thread calling AddRef while one is calling
> Release and dropping to zero means that you need strong thread-safety
> which shared_ptr does not provide. Here are some implementations you can
> take a look at:
This just means, that you are making a copy of an object where the
destructor is in progress. That's simply a bug and should be avoided ;-)
best regards,
Torsten
--
kostenlose Wirtschaftssimulation: http://www.financial-rumors.de
Yannick Tremblay
Sam <s...@email-scan.com> wrote:
>-=-=-=-=-=-
>
>That's what Boost's shared_ptr does. Although -- much like the rest of
>Boost's code -- it is horribly inefficient, and suffers from certain design
>flaws -- it is often a good starting point for your own reference-counted
>pointers.
[...]
>Then don't. Resist the temptation to use Boost as long as you can. Many
>years from now, you'll be thankful for that. Define and implement your own
>pointer class, and use this as a learning experience. True, your reference
>counting implementation will be much slower than Boost's. Boost does not use
>mutexes for this, rather it uses CPU-specific atomic increment/decrement
>instructions (and gets it partially wrong, by the way). But this is a good
>way to learn some important principles of thread-safe programming.
Care to clarify?
And does this also apply to std::tr1::shared_ptr which is based on
boost impelmentation on many platfroms.
Yan
Sam
> In article <cone.1206583245...@commodore.email-scan.com>,
> Sam <s...@email-scan.com> wrote:
>>-=-=-=-=-=-
>>
>>That's what Boost's shared_ptr does. Although -- much like the rest of
>>Boost's code -- it is horribly inefficient, and suffers from certain design
>>flaws -- it is often a good starting point for your own reference-counted
>>pointers.
>
> [...]
>
>>Then don't. Resist the temptation to use Boost as long as you can. Many
>>years from now, you'll be thankful for that. Define and implement your own
>>pointer class, and use this as a learning experience. True, your reference
>>counting implementation will be much slower than Boost's. Boost does not use
>>mutexes for this, rather it uses CPU-specific atomic increment/decrement
>>instructions (and gets it partially wrong, by the way). But this is a good
>>way to learn some important principles of thread-safe programming.
>
> Care to clarify?
The entire design is completely braindead. A separate object, a tiny
object that holds the reference count, gets instantiated for every object
tracked by shared_ptr. This is insane. Heavy use of shared_ptr is just going
to hammer your heap like there's no tomorrow. This is horrible design. The
correct approach is to store the reference count in superclass and derive
from it. You can't then attach shared_ptr to an arbitrary libstdc++ object,
of course, so you just multiply-inherit from it. How hard is that?
Then you have the shared_ptr itself, an object that holds two pointers, one
to the original object, the other to the reference count.
Which means that most compilers won't be able to hold a shared_ptr in CPU
registers, like ordinary pointers. Instead, things are going to get tossed
around in memory.
There are also several other design flaws as well. Like the fact that each
time a reference count gets updated, it involves a call to a library
function. Reference count increment/decrement cannot be inlined, due to a
real first class fookup in the templates. After I read through the class
definition, I just shook my head, laughed, then quickly coded my own
reference-counted object implementation, and ended up benchmarking it 15%
faster than Boost's disgusting implementation.
> And does this also apply to std::tr1::shared_ptr which is based on
> boost impelmentation on many platfroms.
Yes.
Alf P. Steinbach
Have you looketh at boost::intrusive_ptr?
>> And does this also apply to std::tr1::shared_ptr which is based on
>> boost impelmentation on many platfroms.
Cheers,
- Alf
--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?
gpderetta
> Yannick Tremblay writes:
> > Sam <s...@email-scan.com> wrote:
>
> >>That's what Boost's shared_ptr does. Although -- much like the rest of
> >>Boost's code -- it is horribly inefficient, and suffers from certain design
> >>flaws -- it is often a good starting point for your own reference-counted
> >>pointers.
Like the rest of Boost's code? That's not my experience.
>
> > [...]
>
> >>Then don't. Resist the temptation to use Boost as long as you can. Many
> >>years from now, you'll be thankful for that. Define and implement your own
> >>pointer class, and use this as a learning experience. True, your reference
> >>counting implementation will be much slower than Boost's. Boost does not use
> >>mutexes for this, rather it uses CPU-specific atomic increment/decrement
> >>instructions (and gets it partially wrong, by the way). But this is a good
> >>way to learn some important principles of thread-safe programming.
>
> > Care to clarify?
>
> The entire design is completely braindead. A separate object, a tiny
> object that holds the reference count, gets instantiated for every object
> tracked by shared_ptr. This is insane. Heavy use of shared_ptr is just going
> to hammer your heap like there's no tomorrow.
Use a custom allocator. Or use a platform with a better default
allocator.
Also the draft standard (and I think the next boost release) has
make_shared or something like that that will encapsulate 'new' and
will allocate the reference count and your object with a single
allocation; as a plus it will be binary compatible with the default
separate referece counted shared_ptrs.
> This is horrible design. The
> correct approach is to store the reference count in superclass and derive
> from it. You can't then attach shared_ptr to an arbitrary libstdc++ object,
> of course, so you just multiply-inherit from it. How hard is that?
>
If you do not want to pay for a separate heap allocated reference
count, use boost::intrusive_ptr. Which doesn't force you to derive
from some superclass.
Not requiring changes in user classes is good desing, not horrible
design.
Also note that using a separate reference count gives you weak_ptr
(technically you can have it with an intrusive reference counted smart
pointer, but you would have to defer deallocation of the pointed
object untill the last weak pointer dies, which is Not What You Want
(TM) ).
> Then you have the shared_ptr itself, an object that holds two pointers, one
> to the original object, the other to the reference count.
>
> Which means that most compilers won't be able to hold a shared_ptr in CPU
> registers, like ordinary pointers.
Most compilers? Maybe from the last century. I would be surprised if
any half-recent compiler did that.
> Instead, things are going to get tossed
> around in memory.
>
> There are also several other design flaws as well. Like the fact that each
> time a reference count gets updated, it involves a call to a library
> function.
On most plattforms boost shared_ptr uses inline asm or compiler
intrinsics for reference count updates. Calls to platfrom specific
mutex lock/unlock are only a fall back. And you know that, as you said
the same thing in the previous paragraph. Also I would like to know
how it "gets it partially wrong".
> Reference count increment/decrement cannot be inlined, due to a
> real first class fookup in the templates.
What is that supposed to mean?
> After I read through the class
> definition, I just shook my head, laughed, then quickly coded my own
> reference-counted object implementation, and ended up benchmarking it 15%
> faster than Boost's disgusting implementation.
>
15% is hardly impressive. It is unlikely that shared_ptr operations
are responsible of more than 1% of your application run time (if they
are, you are likely doing something wrong). Improving 15% on that
isn't a great accomplishment nor a good use of your time.
With a custom tailored shared ptr you can do much, much better (as,
I'm sure, Chris Thomasson is going to tell you ;) ). But of course you
lose most of the nice properties of shared_ptr: weak_ptr, support for
incomplete types, custom deleter, aliasing constructor etc, etc... and
of course a peer reviewed, widely tested design (even blessed by the
standard committee).
> > And does this also apply to std::tr1::shared_ptr which is based on
> > boost impelmentation on many platfroms.
>
> Yes.
No.
--
gpd
Michael Oswald
>> After I read through the class
>> definition, I just shook my head, laughed, then quickly coded my own
>> reference-counted object implementation, and ended up benchmarking it 15%
>> faster than Boost's disgusting implementation.
>>
>
> 15% is hardly impressive. It is unlikely that shared_ptr operations
> are responsible of more than 1% of your application run time (if they
> are, you are likely doing something wrong). Improving 15% on that
> isn't a great accomplishment nor a good use of your time.
I once made a comparison of boost::shared_ptr and loki::SmartPtr, which uses
a custom allocator (both with non-intrusive reference counting). In debug
mode, loki was slightly slower because of massive policy templates, but
when compiled with -O2 it needed only 50% of the time of boost::shared_ptr.
Of course, their design is rather complementary. Boost::shared_ptr is a more
general and broad approach, while Loki provides possibilities to configure
every tiny bit with policies. Each has it's strength and weaknesses. I have
used both and didn't run into problems so far.
lg,
Michael
David Schwartz
> This just means, that you are making a copy of an object where the
> destructor is in progress. That's simply a bug and should be avoided ;-)
>
> best regards,
> Torsten
I agree. I would put it simply -- you cannot call 'AddRef' unless you
have an explicit or implicit reference to an object. The 'AddRef'
function is not special, it must be called with a reference just like
every other function.
The puzzle is this -- how did you get a pointer to object to call
'AddRef' on anyway?
I've heard a lot of talk about strong thread safety and the like, but
I have to admit, I don't get it. In order to call 'AddRef' on an
object, you need a pointer to it, and how could you possibly have
gotten that pointer without something that already had a reference?
The existence of a pointer should mean the existence of a reference --
otherwise how can you know that pointer remains valid, whether a call
for AddRef or for any other purpose?
DS
co...@mailvault.com
> On Mar 27, 12:13 pm, Sam <s...@email-scan.com> wrote:
>
> > Yannick Tremblay writes:
> > > Sam <s...@email-scan.com> wrote:
>
> > >>Boost'scode -- it is horribly inefficient, and suffers from certain design
> > >>flaws -- it is often a good starting point for your own reference-counted
> > >>pointers.
>
I think some Boost libraries are better than others though.
http://www.webEbenezer.net/comparison.html
Brian
Alexander Terekhov
gpderetta
Use an std::vector (or boost::array) instead of std::deque or
std::list for applications where serialization performance is
critical.
--
gpd
Tim H
The owner calls AddRef before it hands you a pointer.
Sam
> On Mar 27, 12:13 pm, Sam <s...@email-scan.com> wrote:
>> Yannick Tremblay writes:
>> > Care to clarify?
>>
>> The entire design is completely braindead. A separate object, a tiny
>> object that holds the reference count, gets instantiated for every object
>> tracked by shared_ptr. This is insane. Heavy use of shared_ptr is just going
>> to hammer your heap like there's no tomorrow.
>
> Use a custom allocator. Or use a platform with a better default
> allocator.
What a great idea. The implementation is braindead? No problem, just pile on
a heap of workarounds that adds another layer of overhead, that'll fix it!
> Also the draft standard (and I think the next boost release) has
> make_shared or something like that that will encapsulate 'new' and
> will allocate the reference count and your object with a single
> allocation; as a plus it will be binary compatible with the default
> separate referece counted shared_ptrs.
Ditto!
>> This is horrible design. The
>> correct approach is to store the reference count in superclass and derive
>> from it. You can't then attach shared_ptr to an arbitrary libstdc++ object,
>> of course, so you just multiply-inherit from it. How hard is that?
>>
>
> If you do not want to pay for a separate heap allocated reference
> count, use boost::intrusive_ptr. Which doesn't force you to derive
> from some superclass.
I'm almost afraid to look.
> Not requiring changes in user classes is good desing, not horrible
> design.
"User classes" are, by definition, designed by the user. Now that's an
interesting approach: rather than designing a class hierarchy to properly
implement reference-counted objects, nooooooo!!! That makes too much sense.
Instead, forcibly rip out all the reference-counting logic, and use a pile
of duct tape and superglue to attach it to your class hierarchy.
That's a guaranteed recipe for efficiently getting things done, isn't it?
> Also note that using a separate reference count gives you weak_ptr
> (technically you can have it with an intrusive reference counted smart
> pointer, but you would have to defer deallocation of the pointed
> object untill the last weak pointer dies, which is Not What You Want
> (TM) ).
/me looks at my reference-counted class hierarchy, that supports weak
references and virtual inheritance, refrains from any cockamamie logic like
deferred allocation, and benchmarks way ahead of Boost.
I must be imagining things. Hold on while I pop an aspirin, or two, and
reorient myself.
> Most compilers? Maybe from the last century. I would be surprised if
> any half-recent compiler did that.
Try gcc 4.1. CPU registers are at a premium. It's very unlikely that the
compiler will put anything into a register that's not a single, native type.
If there's enough registers for everything, then maybe, but this rarely
occurs in practice. A compiler is more likely to keep a pointer or a native
type, rather than clear out a bunch of registers to hold an entire struct.
Using a reference to a single object that's implemented as a single pointer,
versus two pointers, has a far better chance of resulting in faster code.
That's a no-brainer.
>> There are also several other design flaws as well. Like the fact that each
>> time a reference count gets updated, it involves a call to a library
>> function.
>
> On most plattforms boost shared_ptr uses inline asm or compiler
> intrinsics for reference count updates. Calls to platfrom specific
> mutex lock/unlock are only a fall back. And you know that, as you said
> the same thing in the previous paragraph. Also I would like to know
> how it "gets it partially wrong".
Except that on x86 it uses a wrong builtin, for which there's no
corresponding CPU instruction, resulting in:
x86_64:
movq %rax, %rdi
movl $-1, %esi
call _ZN9__gnu_cxx18__exchange_and_addEPVii
i386:
movl $-1, 4(%esp)
movl %eax, (%esp)
call _ZN9__gnu_cxx18__exchange_and_addEPVii
That's for every reference decrement. Lovely. Ditto for increment.
Seriously, has anyone actually LOOKED at the code that comes out of Boost,
and checked it for sanity?
>> Reference count increment/decrement cannot be inlined, due to a
>> real first class fookup in the templates.
>
> What is that supposed to mean?
Wrong gcc builtin!!!!!!
__exchange_and_add() does not get compiled by gcc to an equivalent CPU
instruction on either i386 or x86_64, for the simple reason that there is no
such CPU instruction, and it has to be emulated by libgcc! shared_ptr forces
a function call to libgcc every time you bounce shared_ptr from place A to
place B. Whoever did this, without verifying that the code gets compiled to
an actual atomic x86 instruction, should wear a paper bag on his head for at
least a month. All they had to do is use the correct builtin, and eliminate
all that overhead of setting up a stack frame, invoking a remote library
function, likely resulting in a trashed cacheline, and replace all of that
useless crap with one or two native CPU instructions!
What a joke.
>> After I read through the class
>> definition, I just shook my head, laughed, then quickly coded my own
>> reference-counted object implementation, and ended up benchmarking it 15%
>> faster than Boost's disgusting implementation.
>>
>
> 15% is hardly impressive. It is unlikely that shared_ptr operations
> are responsible of more than 1% of your application run time (if they
> are, you are likely doing something wrong). Improving 15% on that
> isn't a great accomplishment nor a good use of your time.
You must not be familiar with developing real world applications for the
financial industry, where every nanosecond of latency counts. Even a 1%
improvement translates to a non-trivial competitive advantage. I'll take it
any day.
Furthermore, this was a rather crude benchmark, which probably ended up
hitting the CPU cache most of the time. A more realistic mock-up will likely
show a greater difference due to doubling of heap allocation activity that
shared_ptr demands, not to mention all the unnecessary calls to libgcc.
Especially since, as a result of deferred allocation by shared_ptr, the
extra allocation won't have a 1:1 relationship with heap allocation of the
referenced objects themselves.
> With a custom tailored shared ptr you can do much, much better (as,
I see no need for something heavily customized. Just basic operations,
typical for reference-counted objects, will suffice, as long as you do them
correctly. Really, this is not rocket science.
My impression is that many Boosts classes are what you get in response to a
homework assignment for a junior-level college course on programming
algorithms and concepts, with only a minimum of consideration paid to
practical, real-world scenarios.
> I'm sure, Chris Thomasson is going to tell you ;) ). But of course you
> lose most of the nice properties of shared_ptr: weak_ptr, support for
> incomplete types, custom deleter, aliasing constructor etc, etc... and
> of course a peer reviewed, widely tested design (even blessed by the
> standard committee).
Gee, then I must've imagined knocking off all this, including weak
references, templated default allocators/deallocators, and supporting
multiply-inherited objects, in just a day or two, last year.
If I was on a committee that apparently accepted and blessed Boost's
shared_ptr, without even bothering to check at what code it generates, and
how, I'd probably be embarassed.
>> > And does this also apply to std::tr1::shared_ptr which is based on
>> > boost impelmentation on many platfroms.
>>
>> Yes.
>
> No.
I'm afraid the answer is still yes.
gpderetta
> gpderetta writes:
> > On Mar 27, 12:13 pm, Sam <s...@email-scan.com> wrote:
> >> Yannick Tremblay writes:
> >> > Care to clarify?
>
> >> The entire design is completely braindead. A separate object, a tiny
> >> object that holds the reference count, gets instantiated for every object
> >> tracked by shared_ptr. This is insane. Heavy use of shared_ptr is just going
> >> to hammer your heap like there's no tomorrow.
>
> > Use a custom allocator. Or use a platform with a better default
> > allocator.
>
> What a great idea. The implementation is braindead? No problem, just pile on
> a heap of workarounds that adds another layer of overhead, that'll fix it!
>
If your platform allocator is slow is not shared_ptr fault.
> [...]
> >> This is horrible design. The
> >> correct approach is to store the reference count in superclass and derive
> >> from it. You can't then attach shared_ptr to an arbitrary libstdc++ object,
> >> of course, so you just multiply-inherit from it. How hard is that?
>
> > If you do not want to pay for a separate heap allocated reference
> > count, use boost::intrusive_ptr. Which doesn't force you to derive
> > from some superclass.
>
> I'm almost afraid to look.
Nobody is forcing you to.
>
> > Not requiring changes in user classes is good desing, not horrible
> > design.
>
> "User classes" are, by definition, designed by the user. Now that's an
> interesting approach: rather than designing a class hierarchy to properly
> implement reference-counted objects, nooooooo!!! That makes too much sense.
> Instead, forcibly rip out all the reference-counting logic, and use a pile
> of duct tape and superglue to attach it to your class hierarchy.
No duct tape nor superglue. Just common C++ idioms.
I prefer to adapt non intrusively my classes to use them with third
party
libraries than design for them.
>
> That's a guaranteed recipe for efficiently getting things done, isn't it?
Actually yes.
>
> > Also note that using a separate reference count gives you weak_ptr
> > (technically you can have it with an intrusive reference counted smart
> > pointer, but you would have to defer deallocation of the pointed
> > object untill the last weak pointer dies, which is Not What You Want
> > (TM) ).
>
> /me looks at my reference-counted class hierarchy, that supports weak
> references and virtual inheritance, refrains from any cockamamie logic like
> deferred allocation, and benchmarks way ahead of Boost.
>
15% faster doesn't sound that 'way ahead'.
> I must be imagining things. Hold on while I pop an aspirin, or two, and
> reorient myself.
Certainly not, but I would be curious to see how did you implement
weak pointers.
>
> > Most compilers? Maybe from the last century. I would be surprised if
> > any half-recent compiler did that.
>
> Try gcc 4.1.
That's what I'm using.
> CPU registers are at a premium. It's very unlikely that the
> compiler will put anything into a register that's not a single, native type.
> If there's enough registers for everything, then maybe, but this rarely
> occurs in practice. A compiler is more likely to keep a pointer or a native
> type, rather than clear out a bunch of registers to hold an entire struct.
>
It will reserve registers according to what it is more useful in a
specific place.
Of course small objects means less register spills, but a compiler can
still keep the most used part of an object (in shared pointer case,
the pointer to the held object) and spill the less used part to the
stack (in shared_ptr case, the pointer to the shared count).
> [...]
> >> There are also several other design flaws as well. Like the fact that each
> >> time a reference count gets updated, it involves a call to a library
> >> function.
>
> > On most plattforms boost shared_ptr uses inline asm or compiler
> > intrinsics for reference count updates. Calls to platfrom specific
> > mutex lock/unlock are only a fall back. And you know that, as you said
> > the same thing in the previous paragraph. Also I would like to know
> > how it "gets it partially wrong".
>
> Except that on x86 it uses a wrong builtin, for which there's no
> corresponding CPU instruction, resulting in:
>
> x86_64:
> movq %rax, %rdi
> movl $-1, %esi
> call _ZN9__gnu_cxx18__exchange_and_addEPVii
>
> i386:
> movl $-1, 4(%esp)
> movl %eax, (%esp)
> call _ZN9__gnu_cxx18__exchange_and_addEPVii
>
> That's for every reference decrement. Lovely. Ditto for increment.
>
What I see with gcc-4.1.2 and boost 1.33.1 is:
#APP
lock
xadd %eax, 8(%rbx)
#NO_APP
It doesn't use gcc builtins but custom inline assembler.
Maybe you are using a very old boost version?
>
> >> Reference count increment/decrement cannot be inlined, due to a
> >> real first class fookup in the templates.
>
> > What is that supposed to mean?
>
> Wrong gcc builtin!!!!!!
>
> __exchange_and_add() does not get compiled by gcc to an equivalent CPU
> instruction on either i386 or x86_64, for the simple reason that there is no
> such CPU instruction,
So what? It can be implemented with CAS. It is not unreasonable to
expect that the compiler
would do that for you. Anyways, recent boost releases (at least since
December 2005) do not use the intrinsic.
> and it has to be emulated by libgcc! shared_ptr forces
> a function call to libgcc every time you bounce shared_ptr from place A to
> place B.
Not in the disassembled code I'm looking at.
> [...]
> >> After I read through the class
> >> definition, I just shook my head, laughed, then quickly coded my own
> >> reference-counted object implementation, and ended up benchmarking it 15%
> >> faster than Boost's disgusting implementation.
>
> > 15% is hardly impressive. It is unlikely that shared_ptr operations
> > are responsible of more than 1% of your application run time (if they
> > are, you are likely doing something wrong). Improving 15% on that
> > isn't a great accomplishment nor a good use of your time.
>
> You must not be familiar with developing real world applications for the
> financial industry, where every nanosecond of latency counts. Even a 1%
> improvement translates to a non-trivial competitive advantage. I'll take it
> any day.
I develop applications where latency is important, but 1% is hardly
significative. Anyways in your case is more 15% of 1% ;).
If shared_ptr construction is the bottleneck you are likely going to
get a much bigger speed up by not using reference count at all (use a
real garbage collector or maybe an arena allocator).
>
> Furthermore, this was a rather crude benchmark, which probably ended up
> hitting the CPU cache most of the time. A more realistic mock-up will likely
> show a greater difference due to doubling of heap allocation activity that
> shared_ptr demands,
In a more realistic application you hardly do any shared_ptr
construction at all, at least not in the tightest loop of your
program.
> not to mention all the unnecessary calls to libgcc.
> Especially since, as a result of deferred allocation by shared_ptr, the
> extra allocation won't have a 1:1 relationship with heap allocation of the
> referenced objects themselves.
>
> > With a custom tailored shared ptr you can do much, much better (as,
>
> I see no need for something heavily customized. Just basic operations,
> typical for reference-counted objects, will suffice, as long as you do them
> correctly. Really, this is not rocket science.
>
Then do not complain about performance!
--
gpd
Chris Thomasson
"David Schwartz" <dav...@webmaster.com> wrote in message
news:9ee8ea51-7f0e-4733...@s8g2000prg.googlegroups.com...
>
>> This just means, that you are making a copy of an object where the
>> destructor is in progress. That's simply a bug and should be avoided ;-)
>>
>> best regards,
>> Torsten
>
> I agree. I would put it simply -- you cannot call 'AddRef' unless you
> have an explicit or implicit reference to an object. The 'AddRef'
> function is not special, it must be called with a reference just like
> every other function.
>
> The puzzle is this -- how did you get a pointer to object to call
> 'AddRef' on anyway?
This paper explains the puzzle, and a soultion:
> I've heard a lot of talk about strong thread safety and the like, but
> I have to admit, I don't get it. In order to call 'AddRef' on an
> object, you need a pointer to it, and how could you possibly have
> gotten that pointer without something that already had a reference?
Think of the following scenario:
__________________________________________________
static atomic_ptr<foo> g_foo;
void writers() {
for(;;) {
local_ptr<foo> l_foo(new foo);
g_foo = l_foo;
}
}
void readers() {
for(;;) {
local_ptr<foo> l_foo(g_foo);
if (l_foo) {
l_foo->do_something();
}
}
}
__________________________________________________
Notice how the reader thread can grab a reference from 'g_foo' without
having a previous reference to an object contained within it? You can
download the sourcecode of atomic_ptr from:
http://sourceforge.net/project/showfiles.php?group_id=127837
(atomic-ptr-plus package)
Also, you can take a look at the source code for my proxy garbage collector:
http://appcore.home.comcast.net/misc/pc_sample_h_v1.html
The function that allows any thread to grab a reference to the current
region is 'pc_acquire()':
__________________________________________________
pc_region*
pc_acquire(
pc_master* const _this
) {
pc_sys_anchor cmp = _this->head, xchg;
do {
xchg.refcnt = cmp.refcnt + 2;
xchg.region = cmp.region;
} while (! DWCASPTR(&_this->head, &cmp, &xchg));
return cmp.region;
}
__________________________________________________
Notice how it updates the counter and grabs a pointer to the current region
in a single atomic operation (e.g., DWCAS-loop)? This is another solution to
your puzzle.
> The existence of a pointer should mean the existence of a reference --
> otherwise how can you know that pointer remains valid, whether a call
> for AddRef or for any other purpose?
You need to load a pointer and increment the reference count in a single
atomic operation.
Chris Thomasson
"Alexander Terekhov" <tere...@web.de> wrote in message
news:47EC0773...@web.de...
AFAICT, it seems like they are seriously considering making shared_ptr
strongly thread-safe. Well, IMVHO, that would greatly enhance its
functionality. Nice!
Thanks for pointing this out.
Chris Thomasson
news:9ee8ea51-7f0e-4733...@s8g2000prg.googlegroups.com...
>
Here is some code you can look at which implements strongly thread-safe
reference counting:
http://groups.google.com/group/comp.programming.threads/browse_frm/thread/d30ad3154c08d9dd
The 'foo_obj_acquire/release()' functions is where all the magic take place:
______________________________________________________________________
foo_obj* foo_obj_acquire(foo_obj** psrc) {
foo_obj* _this;
pc_region* const pcr = pc_acquire(&g_pcm);
if (_this = LOADPTR(psrc)) {
atomicword cmp = _this->refcnt;
do {
if (! cmp) {
_this = NULL;
break;
}
} while(! CASWORD(&_this->refcnt, &cmp, cmp + 1));
}
pc_release(pcr);
return _this;
}
void foo_obj_release(foo_obj* _this) {
if (XADDWORD(&_this->refcnt, -1) == 1) {
pc_mutate(&g_pcm, &_this->pcn);
}
}
______________________________________________________________________
Any thread can call 'foo_obj_acquire()' to grab a reference from a pointer
to a 'foo_obj*'. The following setup is perfectly legal:
_____________________________________________________________________
static foo_obj* g_foo = NULL;
void reader_threads(void) {
for (;;) {
foo_obj* const _this = foo_obj_acquire(&g_foo);
if (_this) {
foo_obj_release(_this);
}
}
}
void writer_threads(void) {
for (;;) {
foo_obj* const _this = foo_obj_ctor();
if (_this) {
foo_obj* prev = foo_obj_swap(&g_foo, _this);
if (prev) {
foo_obj_release(prev);
}
}
}
}
_____________________________________________________________________
reader threads can acquire reference's to 'foo_obj' objects on the fly,
without having to own a previous reference to them.
co...@mailvault.com
If it is vector of non POD I think the test results would be
simlar to the list<> results. I can test that if need be.
Both Boost (1.35 if I'm not mistaken) and Ebenezer (since
2006) have optimizations wrt vectors of built-in types like
vector<int>. I disagree with advice that says avoid deques
and lists if they would be used in a serialization context
where performance is important. Serialization is just one
factor that should be considered in choosing the best container for a
given context.
I'm glad you mentioned boost::array. It had slipped off my
radar and I want to investigate the possibility of supporting
it.
Brian
Chris Thomasson
I seems like they are going for something that is analogous to Java
references. Finally, strong thread-safety is being taken seriously.
James Kanze
Certainly. And none of them (no more than any other code
written by human beings) are perfect. In general, though, the
more intensely used the library, the better the chances are that
it is pretty good, or even better. The Boost smart pointers are
amongst the most widely used Boost library, and should certainly
be your first choice if you need smart pointers. (I think that
smart pointers are often overused, but that's a different
issue.) After that, as with any library, you may find that they
don't exactly meet your needs, and you need a custom component.
But writing one yourself until you're sure that it's necessary
is just stupid. (Especially if you're looking for something
very difficult to get right, like a reference counted pointer
which works in a multi-threaded environment.)
--
James Kanze (GABI Software) email:james...@gmail.com
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
co...@mailvault.com
> On Mar 27, 9:42 pm, c...@mailvault.com wrote:
>
> > On Mar 27, 8:12 am, gpderetta <gpdere...@gmail.com> wrote:
> > > Like the rest ofBoost'scode? That's not my experience.
> > I think some Boost libraries are better than others though.
>
> Certainly. And none of them (no more than any other code
> written by human beings) are perfect. In general, though, the
> more intensely used the library, the better the chances are that
> it is pretty good, or even better. The Boost smart pointers are
> amongst the most widely used Boost library, and should certainly
> be your first choice if you need smart pointers.
OK, but auto_ptr should be mentioned and considered before
the Boost options.
> (I think that
> smart pointers are often overused, but that's a different
> issue.)
I agree that they're used too much.
Brian
Jon Harrop
> I have some code where objects are dynamically allocated by some
> thread, and then used by multiple threads and freed when they are no
> longer needed. I think that reference counting is the most appropriate
> way to handle this in my situation.
A concurrent garbage collector is the appropriate way to handle that
situation.
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/products/?u
Ian Collins
> jason.c...@gmail.com wrote:
>> I have some code where objects are dynamically allocated by some
>> thread, and then used by multiple threads and freed when they are no
>> longer needed. I think that reference counting is the most appropriate
>> way to handle this in my situation.
>
> A concurrent garbage collector is the appropriate way to handle that
> situation.
>
--
Ian Collins.
Chris Thomasson
"Jon Harrop" <use...@jdh30.plus.com> wrote in message
news:13uqrk9...@corp.supernews.com...
> jason.c...@gmail.com wrote:
>> I have some code where objects are dynamically allocated by some
>> thread, and then used by multiple threads and freed when they are no
>> longer needed. I think that reference counting is the most appropriate
>> way to handle this in my situation.
>
> A concurrent garbage collector is the appropriate way to handle that
> situation.
Why? There are many different ways to handle lifetime management.
Jon Harrop
They are an order of magnitude slower and leak on cycles.
Ian Collins
> Ian Collins wrote:
>> Jon Harrop wrote:
>>> jason.c...@gmail.com wrote:
>>>> I have some code where objects are dynamically allocated by some
>>>> thread, and then used by multiple threads and freed when they are no
>>>> longer needed. I think that reference counting is the most appropriate
>>>> way to handle this in my situation.
>>> A concurrent garbage collector is the appropriate way to handle that
>>> situation.
>> One possible way, reference counted objects work just as well.
>
> They are an order of magnitude slower and leak on cycles.
>
--
Ian Collins.
Chris Thomasson
> Ian Collins wrote:
>> Jon Harrop wrote:
>>> jason.c...@gmail.com wrote:
>>>> I have some code where objects are dynamically allocated by some
>>>> thread, and then used by multiple threads and freed when they are no
>>>> longer needed. I think that reference counting is the most appropriate
>>>> way to handle this in my situation.
>>>
>>> A concurrent garbage collector is the appropriate way to handle that
>>> situation.
>>
>> One possible way, reference counted objects work just as well.
>
> They are an order of magnitude slower and leak on cycles.
What type of counting algorithm are you talking about? I know a certain type
of distributed reference counting can incur virtually zero-overheads. There
is also deferred counting, weighted counting, ect...
James Kanze
> Jon Harrop wrote:
That's wrong on two counts: first, reference counted objects
fail when cycles are present (which is almost always the case in
my code), and of course reference counting is more expensive in
terms of CPU time, especially in a multithreaded environment.
The latter is, of course, rarely a real problem. The first,
however, pretty much means that there are cases where reference
counting can't be used.
If the problem is freeing memory, especially in a multithreaded
environment, using the Boehm collector with C++ is definitly the
simplest solution. In his case, it sounds like
boost::shared_ptr would also be an effective solution. The
additional runtime will probably not be noticeable, and from his
very general description, it doesn't should like there would be
cycles, or if there were, they should be easy to break. (If
he's currently using neither, it's definitely easier to adopt
boost::shared_ptr---the Boehm collector requires some non
trivial configuration. On the other hand, I find it worthwhile
to invest the effort, since the results are generally useful.)
James Kanze
> Jon Harrop wrote:
> > Ian Collins wrote:
> >> Jon Harrop wrote:
> >>>> I have some code where objects are dynamically allocated by some
> >>>> thread, and then used by multiple threads and freed when they are no
> >>>> longer needed. I think that reference counting is the most appropriate
> >>>> way to handle this in my situation.
> >>> A concurrent garbage collector is the appropriate way to handle that
> >>> situation.
> >> One possible way, reference counted objects work just as well.
> > They are an order of magnitude slower and leak on cycles.
> Nonsense, show us the data.
Well, they obviously leak if cycles are present. And while "an
order of magnitude slower" is obviously false as well, Hans
Boehm has performed a number of benchmarks, and they are slower
in a lot of cases.
A lot depends on how you use dynamic memory. The runtime of a
typical collector depends on the amount of memory actually in
use when the garbage collector runs; the runtime of a typical
manual memory allocator depends on the number of allocations and
frees. An application which uses a lot of small, short lived
objects, and disposes of adequate memory, will run significantly
faster with garbage collection. An application which only
allocates a few, very big object, will run faster with manual
collection or shared pointers.
James Kanze
> "Jon Harrop" <use...@jdh30.plus.com> wrote in message
> news:13uqrk9...@corp.supernews.com...
> > jason.cipri...@gmail.com wrote:
> >> I have some code where objects are dynamically allocated by
> >> some thread, and then used by multiple threads and freed
> >> when they are no longer needed. I think that reference
> >> counting is the most appropriate way to handle this in my
> >> situation.
> > A concurrent garbage collector is the appropriate way to
> > handle that situation.
> Why? There are many different ways to handle lifetime management.
Just to make it clear: the original posting talked about memory
management, not object lifetime management. From the way it was
presented, it more or less sounded like object lifetime had no
significance (often the case). In which case, garbage
collection is fine. But garbage collection has nothing to do
with object lifetime (which, when significant, still must be
managed, garbage collection or not).
The original poster presented a very concrete problem, for which
garbage collection is probably the best solution, but for which
boost::shared_ptr would probably work almost as well. If he's
already using one, but not the other, then the solution is
obvious. If he's using both, I'd go with garbage collection:
less complexity and less actual coding. If he's using neither,
it depends. Boost::shared_ptr is definitly easier to introduce
into a project, but garbage collection is likely to have more
long term benefits.
Jon Harrop
Read Jones and Lins "Garbage Collection" and references therein for a start.
Reference counting is very slow because updating reference counts requires
cache incoherent memory access, which is very slow on modern hardware and
is getting relatively slower every year as CPU speed increases faster than
memory speed. The slowdown is already enormous.
Alexander Terekhov
James Kanze wrote:
[...]
> That's wrong on two counts: first, reference counted objects
> fail when cycles are present (which is almost always the case in
See
http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2007/n2297.html#cycles
regards,
alexander.
Alexander Terekhov
Jon Harrop wrote:
>
> Ian Collins wrote:
> > Jon Harrop wrote:
> >> They are an order of magnitude slower and leak on cycles.
> >
> > Nonsense, show us the data.
>
> Read Jones and Lins "Garbage Collection" and references therein for a start.
>
> Reference counting is very slow because updating reference counts requires
> cache incoherent memory access, which is very slow on modern hardware and
"cache incoherent"? :-)
> is getting relatively slower every year as CPU speed increases faster than
> memory speed. The slowdown is already enormous.
You seem to presume heavy contention while copying and
modifying/destroying shared pointers (maintaining reference counts).
If that is the case, then running transaction in a separate address
space without any managed memory reclamation is surely best. No garbage
collection is needed. ;-)
regards,
alexander.
Jon Harrop
Yes, you can work around it by augmenting reference counting with other
techniques or even replace it wholesale. Persue that idea and a ream of
other improvements for three decades and you end up with a modern GC.
I'm amazed anyone would bother putting a really poor GC in C++ rather than
using a more appropriate language but, IMHO, C++0x is the next Fortran 2003
anyway...
Alexander Terekhov
Jon Harrop wrote:
[...]
> I'm amazed anyone would bother putting a really poor GC in C++ rather than
shared_ptr<> isn't really a GC. And if you view it from the GC angle, it
is indeed really poor.
> using a more appropriate language but, IMHO, C++0x is the next Fortran 2003
> anyway...
Agreed, regarding the Fortran part. :-)
Hey, "The COBOL 2002 standard includes support for object-oriented
programming and other modern language features." ;-)
regards,
alexander.
Chris Thomasson
news:c0da8427-0f37-4505...@59g2000hsb.googlegroups.com...
On 28 mar, 23:56, "Chris Thomasson" <cris...@comcast.net> wrote:
> "Jon Harrop" <use...@jdh30.plus.com> wrote in message
> news:13uqrk9...@corp.supernews.com...
> > > jason.cipri...@gmail.com wrote:
> > >> I have some code where objects are dynamically allocated by
> > >> some thread, and then used by multiple threads and freed
> > >> when they are no longer needed. I think that reference
> > >> counting is the most appropriate way to handle this in my
> > >> situation.
> > > A concurrent garbage collector is the appropriate way to
> > > handle that situation.
> > Why? There are many different ways to handle lifetime management.
> Just to make it clear: the original posting talked about memory
> management, not object lifetime management. From the way it was
> presented, it more or less sounded like object lifetime had no
> significance (often the case). In which case, garbage
> collection is fine. But garbage collection has nothing to do
> with object lifetime (which, when significant, still must be
> managed, garbage collection or not).
GC does indeed detect when an object is not being referenced by anything
(e.g., in a quiescent state). IMHO, this is a _very_ import part of lifetime
management because you cannot terminate an objects life if its being used by
something else.
[...]
Chris Thomasson
> Ian Collins wrote:
>> Jon Harrop wrote:
>>> They are an order of magnitude slower and leak on cycles.
>>
>> Nonsense, show us the data.
>
> Read Jones and Lins "Garbage Collection" and references therein for a
> start.
>
> Reference counting is very slow because updating reference counts requires
> cache incoherent memory access, which is very slow on modern hardware and
> is getting relatively slower every year as CPU speed increases faster than
> memory speed. The slowdown is already enormous.
Let me ask you again: What counting algorithms are you talking about? Did
you know that some algorithms do not need to perform atomic operations or
memory-barriers in order to update a counter?
Jon Harrop
> Jon Harrop wrote:
> [...]
>> I'm amazed anyone would bother putting a really poor GC in C++ rather
>> than
>
> shared_ptr<> isn't really a GC. And if you view it from the GC angle, it
> is indeed really poor.
What does it do apart from collect garbage?
Jon Harrop
> "Jon Harrop" <use...@jdh30.plus.com> wrote in message
> news:13uslj7...@corp.supernews.com...
>> requires cache incoherent memory access, which is very slow on modern
>> hardware and is getting relatively slower every year as CPU speed
>> increases faster than memory speed. The slowdown is already enormous.
>
> Let me ask you again: What counting algorithms are you talking about? Did
> you know that some algorithms do not need to perform atomic operations or
> memory-barriers in order to update a counter?
Anything counting references. Memory barriers simply worsen the situation
even more.
Chris Thomasson
"James Kanze" <james...@gmail.com> wrote in message
news:11306d1e-6d5f-4ad4...@l42g2000hsc.googlegroups.com...
On 29 mar, 02:58, Ian Collins <ian-n...@hotmail.com> wrote:
> > Jon Harrop wrote:
> > > Ian Collins wrote:
> > >> Jon Harrop wrote:
> > >>> jason.cipri...@gmail.com wrote:
> > >>>> I have some code where objects are dynamically allocated by some
> > >>>> thread, and then used by multiple threads and freed when they are
> > >>>> no
> > >>>> longer needed. I think that reference counting is the most
> > >>>> appropriate
> > >>>> way to handle this in my situation.
> > >>> A concurrent garbage collector is the appropriate way to handle that
> > >>> situation.
> > >> One possible way, reference counted objects work just as well.
> > > They are an order of magnitude slower and leak on cycles.
> > Nonsense, show us the data.
> Well, they obviously leak if cycles are present. And while "an
> order of magnitude slower" is obviously false as well, Hans
> Boehm has performed a number of benchmarks, and they are slower
> in a lot of cases.
You can definitely misuse reference counting. For instance, you would NOT
want to use it if you were iterating over a large linked-lists because you
would have to update the counter on each object visited during the
traversal. Take a lock-free reader/writer pattern based on atomic pointers
into account:
<code-sketch>
_____________________________________________________________________
struct object {
atomic_ptr<object> m_next;
void read_only_operation() const;
};
static atomic_ptr<object> g_head;
void writer_push() {
local_ptr<object> l_obj(new object);
local_ptr<object> l_cmp(g_head);
do {
l_obj->m_next = l_cmp;
} while (! g_head.cas(l_cmp, l_obj));
}
void writer_pop() {
local_ptr<object> l_cmp(g_head);
do {
if (! l_cmp) { return; }
} while (! g_head.cas(l_cmp, l_cmp->m_next));
}
void readers() {
local_ptr<object> l_obj(g_head);
while (l_obj) {
l_obj->read_only_operation();
l_obj = l_obj->m_next;
}
}
_____________________________________________________________________
That would give you horrible performance on the readers _and_ the writers.
However, there is a solution. You can use reference counting to manage
so-called proxy collector objects. I can rewrite the code above using a
proxy garbage collector. I will use this implementation for the refactored
code:
http://appcore.home.comcast.net/misc/pc_sample_h_v1.html
Now I can write the above as:
_____________________________________________________________________
struct object {
object* m_next;
pc_node m_pcn;
object() : m_next(NULL) {
pc_node_init(&m_pcn);
}
void read_only_operation() const;
};
static object_dtor(pc_node* pcn) {
delete CONTAINER_OF(pcn, object, m_pcn);
}
static object* g_head = NULL;
static pc_master g_pcm = PC_MASTER_STATICINIT(&g_pcm, object_dtor);
void writer_push() {
object* const l_obj = new object;
object* l_cmp = g_head;
do {
l_obj->m_next = l_cmp;
} while (! CASPTR(&g_head, &l_cmp, l_obj));
}
void writer_pop() {
pc_region* const pcr = pc_acquire(&g_pcm);
object* l_cmp = g_head;
do {
if (! l_cmp) { break; }
} while (! CASPTR(&g_head, &l_cmp, l_cmp->m_next));
pc_release(&g_pcm, pcr);
if (l_cmp) {
pc_mutate(&g_pcm, &l_cmp->m_pcn);
}
}
void readers() {
pc_region* const pcr = pc_acquire(&g_pcm);
object* l_obj = g_head;
while (l_obj) {
l_obj->read_only_operation();
l_obj = l_obj->m_next;
}
pc_release(&g_pcm, pcr);
}
_____________________________________________________________________
This gives excellent performance because I can use raw pointers for the
readers and writers. This basically proves that reference counting can be
used is highly effective manner with hardly any overheads because of the
amortization that going on in the example above. This is just one example of
how flexible atomic reference counting can be...
> A lot depends on how you use dynamic memory. The runtime of a
> typical collector depends on the amount of memory actually in
> use when the garbage collector runs; the runtime of a typical
> manual memory allocator depends on the number of allocations and
> frees. An application which uses a lot of small, short lived
> objects, and disposes of adequate memory, will run significantly
> faster with garbage collection. An application which only
> allocates a few, very big object, will run faster with manual
> collection or shared pointers.
What allocator algorithms are you talking about? There are allocators that
have virtually zero-overheads in that they have fast-paths which don't make
any use of atomic ops and/or memory barriers...
Chris Thomasson
> Chris Thomasson wrote:
>> "Jon Harrop" <use...@jdh30.plus.com> wrote in message
>> news:13uslj7...@corp.supernews.com...
>>> Reference counting is very slow because updating reference counts
>>> requires cache incoherent memory access, which is very slow on modern
>>> hardware and is getting relatively slower every year as CPU speed
>>> increases faster than memory speed. The slowdown is already enormous.
>>
>> Let me ask you again: What counting algorithms are you talking about? Did
>> you know that some algorithms do not need to perform atomic operations or
>> memory-barriers in order to update a counter?
>
> Anything counting references.
non-sense. BTW, this seems to proves that you have little experience with
the more advanced forms of reference counting that have recently been
developed.
> Memory barriers simply worsen the situation even more.
I said that there are counting algorithms that DO NOT use memory barriers
and/or atomic operations.
Okay, we are talking about the same thing in two different threads. Here is
the other post you made that is basically identical to this one:
http://groups.google.com/group/comp.programming.threads/msg/7c04692380331b62
and here is my reply:
http://groups.google.com/group/comp.programming.threads/msg/05a4e3e3a4a75f05
I think we should send follow-ups over there... Agreed?
Jon Harrop
>> Anything counting references.
>
> non-sense. BTW, this seems to proves that you have little experience with
> the more advanced forms of reference counting that have recently been
> developed.
Where have you compared your invention to modern GCs?
>> Memory barriers simply worsen the situation even more.
>
> I said that there are counting algorithms that DO NOT use memory barriers
> and/or atomic operations.
Yes, I know. Reread what I wrote.
> I think we should send follow-ups over there... Agreed?
Why there?
Chris Thomasson
"Jon Harrop" <use...@jdh30.plus.com> wrote in message
news:13uts61...@corp.supernews.com...
> Chris Thomasson wrote:
>> "Jon Harrop" <use...@jdh30.plus.com> wrote in message
>> news:13utp88...@corp.supernews.com...
>>> Anything counting references.
>>
>> non-sense. BTW, this seems to proves that you have little experience with
>> the more advanced forms of reference counting that have recently been
>> developed.
>
> Where have you compared your invention to modern GCs?
It's basically like comparing RCU to GC:
http://lwn.net/Articles/263130/#RCU%20is%20a%20Poor%20Man's%20Garbage%20Collector
It's like comparing apples to oranges because reference counting is not
really analogous to GC. For instance, a traditional reference count usually
destroys an object as soon as the last reference has been released;
basically it collects no garbage at all. This is not true for traditional
GC. BTW, the environments where vZOOM has been licensed to be used in could
not use a GC for various reasons.
Sometimes vZOOM is not the best candidate. If I am consulting for a job that
would greatly benefit from GC, I advise them to use it indeed. It's on a
case-by-case basis. GC is not a silver bullet. It never has been, and it
never will be. The same goes for vZOOM.
>>> Memory barriers simply worsen the situation even more.
>>
>> I said that there are counting algorithms that DO NOT use memory barriers
>> and/or atomic operations.
>
> Yes, I know. Reread what I wrote.
You said that memory barriers make things worse; I agree. That's why I try
to eliminate them wherever I possibly can. Reference counts are a candidate
for this type of low-level optimization.
>> I think we should send follow-ups over there... Agreed?
>
> Why there?
I wanted to coalesce the two basically identical conversations into one.
Chris Thomasson
> Alexander Terekhov wrote:
>> Jon Harrop wrote:
>> [...]
>>> I'm amazed anyone would bother putting a really poor GC in C++ rather
>>> than
>>
>> shared_ptr<> isn't really a GC. And if you view it from the GC angle, it
>> is indeed really poor.
>
> What does it do apart from collect garbage?
shared_ptr<> destroys objects as soon as the reference count drops to one;
its basically 100% accurate. Traditional GC does not work that way at all.
Chris Thomasson
news:66accfe0-0a27-4da4...@s13g2000prd.googlegroups.com...
>I have some code where objects are dynamically allocated by some
> thread, and then used by multiple threads and freed when they are no
> longer needed. I think that reference counting is the most appropriate
> way to handle this in my situation.
>
> how I have reference counting implemented for my objects, basically
> (sorry about any errors I am typing this here in this message):
>
> === BEGIN CODE ===
>
> class A {
> public:
> A ();
> void AddRef ();
> void Release ();
> private:
> ~A ();
> int refs_; // reference count
> pthread_mutex_t mtx_; // protects refs_
> };
>
> // constructor inits reference count to 1
> A::A ()
> : refs_(1), mtx_(PTHREAD_MUTEX_INITIALIZER)
> {
> }
[...]
You cannot use 'PTHREAD_MUTEX_INITIALIZER' that way. A:mtx_ is not an object
with static storage duration. Also, I don't think you can use
static-initalizers in a class constructor initalizers-list.
Jon Harrop
> "Jon Harrop" <use...@jdh30.plus.com> wrote in message
> news:13utp5b...@corp.supernews.com...
>
> shared_ptr<> destroys objects as soon as the reference count drops to one;
That is garbage collection, IMHO.
> its basically 100% accurate. Traditional GC does not work that way at all.
Indeed, traditional GCs can collect values sooner: before they go out of
scope.
Chris Thomasson
> Chris Thomasson wrote:
>> "Jon Harrop" <use...@jdh30.plus.com> wrote in message
>> news:13utp5b...@corp.supernews.com...
>>> What does it do apart from collect garbage?
>>
>> shared_ptr<> destroys objects as soon as the reference count drops to
>> one;
>
> That is garbage collection, IMHO.
>
>> its basically 100% accurate. Traditional GC does not work that way at
>> all.
>
> Indeed, traditional GCs can collect values sooner: before they go out of
> scope.
Traditional GC does not perform a collection every single time an object
quiesces. If you are arguing that a "traditional" GC is more accurate than a
direct reference count, well, alls I can say is that your wrong on multiple
levels.
Chris Thomasson
"Chris Thomasson" <cri...@comcast.net> wrote in message
news:2OWdnUbyCtItkHLa...@comcast.com...
BTW, have you ever considered the following:
ObjectA is being referenced in 3 places throughout a programA... Well, that
means that the number of references is 3. This holds true for traditional
GC, reference counting, or anything else that manages object lifetime.
Again, lets say there are 10 threads and 2 of them hold a single pointer to
an objectA... Well, guess what... The reference count of objectA is 2. I
could go on and on...
How is GC different from reference counting in that respect?
Please explain in detail...
Chris Thomasson
news:11306d1e-6d5f-4ad4...@l42g2000hsc.googlegroups.com...
What about an application that allocates a couple of bug buffers and carves
individual smaller objects out of them?
James Kanze
> "James Kanze" <james.ka...@gmail.com> wrote in message
Garbage collection detects when an object can no longer be
referred to. Obviously, in this case, it's lifetime has ended,
since there is no longer any way to end it otherwise. But
that's about it---garbage collection will not collect the memory
underneath the object that is still alive. Provided, of course,
that there are not errors in the code, and you've lost the last
pointer to the object before its lifetime has ended. But that
has nothing to do with object lifetime per se.
Most objects have indeterminate lifetime, and it doesn't matter.
If an object has determinate lifetime, however, you have to
manage it, garbage collection or no. Garbage collection does
NOT manage object lifetime; it only manages memory.
Jon Harrop
> BTW, have you ever considered the following:
>
>
> ObjectA is being referenced in 3 places throughout a programA... Well,
> that means that the number of references is 3. This holds true for
> traditional GC, reference counting, or anything else that manages object
> lifetime. Again, lets say there are 10 threads and 2 of them hold a single
> pointer to an objectA... Well, guess what... The reference count of
> objectA is 2. I could go on and on...
>
> How is GC different from reference counting in that respect?
>
> Please explain in detail...
It isn't. You are simply citing more irrelevant facts in an attempt to evade
my point.
David Schwartz
> Think of the following scenario:
> __________________________________________________
> static atomic_ptr<foo> g_foo;
>
> void writers() {
> for(;;) {
> local_ptr<foo> l_foo(new foo);
> g_foo = l_foo;
> }
> }
g_foo = l_foo; should map to:
1) Lock g_foo.
2) If g_foo points to an object, release it.
3) Add a reference to l_foo.
4) Make g_foo point to l_foo.
5) Release the lock.
> void readers() {
> for(;;) {
> local_ptr<foo> l_foo(g_foo);
> if (l_foo) {
> l_foo->do_something();
> }
> }}
Well, this can't be safe because there is no assurance l_foo will
continue to point to an object after the 'if' and until the call to
'do_something'. But if the intent was to make that safe, it would have
to be coded to make a copy of l_foo, then test what it points to, then
call a function on it.
> Notice how the reader thread can grab a reference from 'g_foo' without
> having a previous reference to an object contained within it? You can
> download the sourcecode of atomic_ptr from:
Right, but threads aren't the only things that can have references.
Pointers and collections do too. In this case, the pointer has the
reference, which it gives a copy of to the thread. There is always
something that has a reference that gives you your reference.
> Notice how it updates the counter and grabs a pointer to the current
> region
> in a single atomic operation (e.g., DWCAS-loop)? This is another solution
> to
> your puzzle.
> You need to load a pointer and increment the reference count in a single
> atomic operation.
No, you don't. Since you have a pointer, you have a reference. Since
you have a reference, there's no way the pointer can go away.
The solution is much simpler -- never a pointer without a reference.
This seems an awful lot of work to create a problem followed by an
awful lot of work to solve it. Just never allow a pointer to exist
without a reference. It seems illogical to allow this anyway, since
the pointer can't be guaranteed to point anywhere useful anyway.
If you get a pointer from somewhere, that somewhere must have the
pointer. Thus it must have a reference -- otherwise the pointer might
be invalid. Since the pointer is accompanied by a reference, there is
no risk that the pointer can become invalid until you get your
reference. All you have to do is sequence the operations that require
or involve the reference that accompanies that copy of the pointer.
DS
Chris Thomasson
news:48305f1c-6291-498f...@y21g2000hsf.googlegroups.com...
> On Mar 27, 7:04 pm, "Chris Thomasson" <cris...@comcast.net> wrote:
>
>> Think of the following scenario:
>> __________________________________________________
>> static atomic_ptr<foo> g_foo;
>>
>> void writers() {
>> for(;;) {
>> local_ptr<foo> l_foo(new foo);
>> g_foo = l_foo;
>> }
>> }
>
> g_foo = l_foo; should map to:
>
> 1) Lock g_foo.
> 2) If g_foo points to an object, release it.
> 3) Add a reference to l_foo.
> 4) Make g_foo point to l_foo.
> 5) Release the lock.
It does not have to use locks. Have you even looked at the source code to
Joe Seighs atomic pointer?
>> void readers() {
>> for(;;) {
>> local_ptr<foo> l_foo(g_foo);
>> if (l_foo) {
>> l_foo->do_something();
>> }
>> }}
>
> Well, this can't be safe because there is no assurance l_foo will
> continue to point to an object after the 'if' and until the call to
> 'do_something'. But if the intent was to make that safe, it would have
> to be coded to make a copy of l_foo, then test what it points to, then
> call a function on it.
Your incorrect here. This is 100% safe with strongly thread-safe reference
counting such as atomic_ptr.
>> Notice how the reader thread can grab a reference from 'g_foo' without
>> having a previous reference to an object contained within it? You can
>> download the sourcecode of atomic_ptr from:
>
> Right, but threads aren't the only things that can have references.
> Pointers and collections do too. In this case, the pointer has the
> reference, which it gives a copy of to the thread. There is always
> something that has a reference that gives you your reference.
>
>> Notice how it updates the counter and grabs a pointer to the current
>> region
>> in a single atomic operation (e.g., DWCAS-loop)? This is another solution
>> to
>> your puzzle.
>
>> You need to load a pointer and increment the reference count in a single
>> atomic operation.
>
> No, you don't. Since you have a pointer, you have a reference. Since
> you have a reference, there's no way the pointer can go away.
Did you even read the paper I cited?
> The solution is much simpler -- never a pointer without a reference.
>
> This seems an awful lot of work to create a problem followed by an
> awful lot of work to solve it. Just never allow a pointer to exist
> without a reference. It seems illogical to allow this anyway, since
> the pointer can't be guaranteed to point anywhere useful anyway.
>
> If you get a pointer from somewhere, that somewhere must have the
> pointer. Thus it must have a reference -- otherwise the pointer might
> be invalid. Since the pointer is accompanied by a reference, there is
> no risk that the pointer can become invalid until you get your
> reference. All you have to do is sequence the operations that require
> or involve the reference that accompanies that copy of the pointer.
Your thinking in terms of basic thread-safety which is indeed much simpler
to reason about. PLEASE read the cited paper, and then take a look at the
source-code to Joe Seighs excellent atomic_ptr:
http://sourceforge.net/project/showfiles.php?group_id=127837&package_id=139944&release_id=352395
Download it, and look in the 'i686' directory. Then open atomic_ptr.h.
Please!
BTW, did you read where the standard committee is thinking about making
shared_ptr honor strong thread-safety:
http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2007/n2297.html#atomic
?
Chris Thomasson
> Chris Thomasson wrote:
>> BTW, have you ever considered the following:
>>
>>
>> ObjectA is being referenced in 3 places throughout a programA... Well,
>> that means that the number of references is 3. This holds true for
>> traditional GC, reference counting, or anything else that manages object
>> lifetime. Again, lets say there are 10 threads and 2 of them hold a
>> single
>> pointer to an objectA... Well, guess what... The reference count of
>> objectA is 2. I could go on and on...
>>
>> How is GC different from reference counting in that respect?
>>
>> Please explain in detail...
>
> It isn't.
I agree that the essence of GC is not that different from reference counting
within the narrow context listed above.
> You are simply citing more irrelevant facts in an attempt to evade
> my point.
You point is that anything that uses any type of reference counting
whatsoever is slow, outdated, crappy... Either your a troll, or your a GC
religious freak. I never said that GC should never be used. I said I pick
the right tool for the job at hand.
Chris Thomasson
Right. The object is now quiescent.
> But
> that's about it---garbage collection will not collect the memory
> underneath the object that is still alive. Provided, of course,
> that there are not errors in the code, and you've lost the last
> pointer to the object before its lifetime has ended. But that
> has nothing to do with object lifetime per se.
IMHO, the ability to determine when an object is quiescent is a major part
of lifetime management as a whole.
> Most objects have indeterminate lifetime, and it doesn't matter.
> If an object has determinate lifetime, however, you have to
> manage it, garbage collection or no. Garbage collection does
> NOT manage object lifetime; it only manages memory.
Agreed. However, GC is a great tool to use in a lifetime management scheme
for dynamic objects.
Jon Harrop
> You point is that anything that uses any type of reference counting
> whatsoever is slow, outdated, crappy... Either your a troll, or your a GC
> religious freak.
You claimed that reference counting is "100% accurate" and always more
accurate than a GC. I knew that was wrong so I explained why and gave a
worked counter example proving my point.
Chris Thomasson
> Chris Thomasson wrote:
>> You point is that anything that uses any type of reference counting
>> whatsoever is slow, outdated, crappy... Either your a troll, or your a GC
>> religious freak.
>
> You claimed that reference counting is "100% accurate" and always more
> accurate than a GC. I knew that was wrong so I explained why and gave a
> worked counter example proving my point.
Some reference counting algorithms are 100% accurate in that an object is
IMMEDIATELY destroyed when its count drops to zero.. Other algorithms are
not because they use amortizations and deferments much like a traditional GC
does.
struct Bar {
Bar(int refs_) : refs(refs_) {}
void addref() { ++refs; };
void release() { --refs; if (! refs) { delete this; }}
int refs;
};
Here is your scoped example again:
{
0: Bar* bar(new Bar(1));
1: f(bar);
2: bar->release();
3: g();
}
the 'bar' object is immediately destroyed on 'line 2'. In order for a GC to
do this, well, it would have to perform a collection exactly on 'line 2'.
Traditional GC cannot ever be 100% accurate all the time because that would
imply that it runs collections non-stop. AFAICT, you don't understand the
implementation details of reference counting very well because most of your
claims about them are false.
Jon Harrop
> "Jon Harrop" <use...@jdh30.plus.com> wrote in message
> news:13v0jq5...@corp.supernews.com...
>> Chris Thomasson wrote:
>>> You point is that anything that uses any type of reference counting
>>> whatsoever is slow, outdated, crappy... Either your a troll, or your a
>>> GC religious freak.
>>
>> You claimed that reference counting is "100% accurate" and always more
>> accurate than a GC. I knew that was wrong so I explained why and gave a
>> worked counter example proving my point.
>
> Some reference counting algorithms are 100% accurate in that an object is
> IMMEDIATELY destroyed when its count drops to zero.
A 100% accurate collector will collect a value as soon as it is unreachable.
Reference counting does not do that.
> the 'bar' object is immediately destroyed on 'line 2'. In order for a GC
> to do this, well, it would have to perform a collection exactly on 'line
> 2'. Traditional GC cannot ever be 100% accurate all the time because that
> would imply that it runs collections non-stop.
Yes.
> AFAICT, you don't understand the implementation details of reference
> counting very well because most of your claims about them are false.
In the face of a proven counter example your ad-hominem attacks are wearing
thin. Please just swallow it, kiss your fallacy goodbye and move on.
Chris Thomasson
> Chris Thomasson wrote:
>> "Jon Harrop" <use...@jdh30.plus.com> wrote in message
>> news:13v0jq5...@corp.supernews.com...
>>> Chris Thomasson wrote:
>>>> You point is that anything that uses any type of reference counting
>>>> whatsoever is slow, outdated, crappy... Either your a troll, or your a
>>>> GC religious freak.
>>>
>>> You claimed that reference counting is "100% accurate" and always more
>>> accurate than a GC. I knew that was wrong so I explained why and gave a
>>> worked counter example proving my point.
>>
>> Some reference counting algorithms are 100% accurate in that an object is
>> IMMEDIATELY destroyed when its count drops to zero.
>
> A 100% accurate collector will collect a value as soon as it is
> unreachable.
> Reference counting does not do that.
When the reference count is zero, it is unreachable and it is immediately
destroyed. A GC cannot do that unless it is constantly running collection
cycles.
>> the 'bar' object is immediately destroyed on 'line 2'. In order for a GC
>> to do this, well, it would have to perform a collection exactly on 'line
>> 2'. Traditional GC cannot ever be 100% accurate all the time because that
>> would imply that it runs collections non-stop.
>
> Yes.
What GC out there runs collections cycles 100% of the time?
>> AFAICT, you don't understand the implementation details of reference
>> counting very well because most of your claims about them are false.
>
> In the face of a proven counter example your ad-hominem attacks are
> wearing
> thin. Please just swallow it, kiss your fallacy goodbye and move on.
You make false claims about reference counting, I point them out, and you
say I am attacking you? Too funny.
:^D
Chris Thomasson
>
> "Jon Harrop" <use...@jdh30.plus.com> wrote in message
> news:13utp5b...@corp.supernews.com...
>> Alexander Terekhov wrote:
>>> Jon Harrop wrote:
>>> [...]
>>>> I'm amazed anyone would bother putting a really poor GC in C++ rather
>>>> than
>>>
>>> shared_ptr<> isn't really a GC. And if you view it from the GC angle, it
>>> is indeed really poor.
>>
>> What does it do apart from collect garbage?
>
> shared_ptr<> destroys objects as soon as the reference count drops to one;
shared_ptr<> destroys objects as soon as the reference count drops to ZERO!
ARGH!
Alexander Terekhov
Jon Harrop wrote:
>
> Alexander Terekhov wrote:
> > Jon Harrop wrote:
> > [...]
> >> I'm amazed anyone would bother putting a really poor GC in C++ rather
> >> than
> >
> > shared_ptr<> isn't really a GC. And if you view it from the GC angle, it
> > is indeed really poor.
>
> What does it do apart from collect garbage?
It executes deleters (dtors) ending objects lifetime deterministically
and lets allocator collect garbage (which may well be a GC for the later
part, BTW).
regards,
alexander.
Chris Thomasson
Umm... Well, crap! I should have said:
What about an application that allocates a couple of BIG buffers and carves
> individual smaller objects out of them?
Lol! 'bug' buffers is funny! My typos/BUG-mistakes make me crack up
sometimes!
I am surprised that I did not get seriously flames to a point where I needed
to go to the hospital, and get hooked up to some sort of opiate drip.
:^)
James Kanze
I've not heard this term in relationship to object lifetime
management before. Generally speaking, I find that there are
two categories of objects, those with (or which need) a
deterministic lifetime, and those which don't. By "needing" a
deterministic lifetime", I mean that there is significant
(observable, in the sense of the C++ standard) behavior
associated with the end of their lifetime. If you loose all
pointers to the object before that behavior occurs, then you
have a serious error in your program. If you try to use the
object after that behavior has occured, then you also have a
serious error. Conceptually, for such objects, lifetime is
independent of the number of pointers to the object, although in
practice, you need to keep at least one pointer in order to
invoke the termination, and you don't want to keep pointers too
long after the object has been terminated, since any pointer to
the "dead" object is a potential source of errors. For such
objects, garbage collection isn't really that important in a
correct program, because freeing the memory at the point of
termination is always "correct". Garbage collection does help
in assertions against misuse, since it ensures that the memory
will not be used for something else as long as anyone still
holds a pointer to it. What I've often wished for in such cases
is some sort of reverse garbage collection: getting rid of the
pointers to the object because the object should no longer be
referenced. In practice, however, there doesn't seem to be any
effective generic means of "getting rid of the pointers": if the
pointer is in a map, for example, you have to remove the map
entry.
For objects with indeterminate lifetimes, of course, garbage
collection makes for less implementation code, so saves you
programming time.
> > But that's about it---garbage collection will not collect
> > the memory underneath the object that is still alive.
> > Provided, of course, that there are not errors in the code,
> > and you've lost the last pointer to the object before its
> > lifetime has ended. But that has nothing to do with object
> > lifetime per se.
> IMHO, the ability to determine when an object is quiescent is
> a major part of lifetime management as a whole.
Object lifetime is part of the design phase. If the design
specifies a determinate lifetime, you have to program it.
Regardless of the language---in this case, Java and C++ are no
different. If the design determines that it doesn't, *but* you
still need dynamic allocation (a lot of objects which don't have
pure value semantics, and should be copied, and not dynamically
allocated), then garbage collection saves you programming work.
But it never frees you of the responsibility of considering
object lifetime in design---it only intervenes at a much lower
level.
> > Most objects have indeterminate lifetime, and it doesn't
> > matter. If an object has determinate lifetime, however, you
> > have to manage it, garbage collection or no. Garbage
> > collection does NOT manage object lifetime; it only manages
> > memory.
> Agreed. However, GC is a great tool to use in a lifetime
> management scheme for dynamic objects.
Not for lifetime management. For memory management, once you've
determined that the lifetime is indeterminate (or after an
object with a determinate lifetime has been terminated).
Chris Thomasson
> "David Schwartz" <dav...@webmaster.com> wrote in message
> news:48305f1c-6291-498f...@y21g2000hsf.googlegroups.com...
>> On Mar 27, 7:04 pm, "Chris Thomasson" <cris...@comcast.net> wrote:
>>
>>> Think of the following scenario:
>>> __________________________________________________
>>> static atomic_ptr<foo> g_foo;
>>>
>>> void writers() {
>>> for(;;) {
>>> local_ptr<foo> l_foo(new foo);
>>> g_foo = l_foo;
>>> }
>>> }
>>
>> g_foo = l_foo; should map to:
>>
>> 1) Lock g_foo.
>> 2) If g_foo points to an object, release it.
>> 3) Add a reference to l_foo.
>> 4) Make g_foo point to l_foo.
>> 5) Release the lock.
Your referring to a static locking table right? If not, how are you going to
get a reference to an object's lock before you reference an object? If you
want a solution which uses a locking table look here:
Dmitriy V'jukov
> This seems an awful lot of work to create a problem followed by an
> awful lot of work to solve it. Just never allow a pointer to exist
> without a reference. It seems illogical to allow this anyway, since
> the pointer can't be guaranteed to point anywhere useful anyway.
>
> If you get a pointer from somewhere, that somewhere must have the
> pointer. Thus it must have a reference -- otherwise the pointer might
> be invalid. Since the pointer is accompanied by a reference, there is
> no risk that the pointer can become invalid until you get your
> reference. All you have to do is sequence the operations that require
> or involve the reference that accompanies that copy of the pointer.
Consider following example:
class application_settings;
application_settings* g_settings;
// replaces g_settings with new_settings,
// and releases previous value of g_settings
void update_settings(application_settings* new_settings);
// acquires and returns object stored in g_settings
application_settings* acquire_settings();
// releases settings object
void release_settings(application_settings* settings);
void reader_thread()
{
for(;;)
{
application_settings* settings = acquire_settings();
// use settings
release_settings(settings);
}
}
In this example acquire_settings() must act on pointer to object for
which it doesn't have reference yet.
How this pattern must be implemented in the right way (pointer ==
reference)?
Dmitriy V'jukov
David Schwartz
> > g_foo = l_foo; should map to:
>
> > 1) Lock g_foo.
> > 2) If g_foo points to an object, release it.
> > 3) Add a reference to l_foo.
> > 4) Make g_foo point to l_foo.
> > 5) Release the lock.
> It does not have to use locks. Have you even looked at the source code to
> Joe Seighs atomic pointer?
No, it does not have to use a lock, it can work any way it wants to.
I'm talking conceptually here.
DS
David Schwartz
> Consider following example:
>
> class application_settings;
> application_settings* g_settings;
>
> // replaces g_settings with new_settings,
> // and releases previous value of g_settings
> void update_settings(application_settings* new_settings);
>
> // acquires and returns object stored in g_settings
> application_settings* acquire_settings();
>
> // releases settings object
> void release_settings(application_settings* settings);
>
> void reader_thread()
> {
> for(;;)
> {
> application_settings* settings = acquire_settings();
> // use settings
> release_settings(settings);
> }
>
> }
>
> In this example acquire_settings() must act on pointer to object for
> which it doesn't have reference yet.
Huh? Of course it does. You just keep one reference for whatever is
the currently valid settings.
> How this pattern must be implemented in the right way (pointer ==
> reference)?
Wherever 'acquire_settings' keeps a pointer to the current settings,
it also keeps a reference. Like this:
> // replaces g_settings with new_settings,
> // and releases previous value of g_settings
> void update_settings(application_settings* new_settings)
{
new_settings->AddRef();
Lock();
if(g_settings!=NULL) g_settings->UnRef();
g_settings=new_settings;
Unlock();
}
> // acquires and returns object stored in g_settings
> application_settings* acquire_settings()
{
application_settings *ret=NULL;
Lock();
if(g_settings!=NULL)
{
g_settings->AddRef();
ret=g_settings();
}
Unlock();
return ret;
}
> // releases settings object
> void release_settings(application_settings* settings)
{
Lock();
if(g_settings!=NULL)
{
g_settings->UnRef();
g_settings=NULL;
}
Unlock();
}
Note that 'Lock' and 'Unlock' are notional. They can be a global lock
but they can also be atomic operations, a lock specific to the
implementation of g_settings, or anything else you like.
See how threads are not the only thing that can have a reference? The
global 'g_settings' pointer (and its associated lock if it has one)
can also have a reference.
DS
Dilip
> Chris Thomasson wrote:
> > "Jon Harrop" <use...@jdh30.plus.com> wrote in message
> >news:13v0jq5...@corp.supernews.com...
> >> Chris Thomasson wrote:
> >>> You point is that anything that uses any type of reference counting
> >>> whatsoever is slow, outdated, crappy... Either your a troll, or your a
> >>> GC religious freak.
>
> >> You claimed that reference counting is "100% accurate" and always more
> >> accurate than a GC. I knew that was wrong so I explained why and gave a
> >> worked counter example proving my point.
>
> > Some reference counting algorithms are 100% accurate in that an object is
> > IMMEDIATELY destroyed when its count drops to zero.
>
> A 100% accurate collector will collect a value as soon as it is unreachable.
> Reference counting does not do that.
Unreachability is determined only _after_ the GC is triggered.
Exactly _when_ GC is triggered is determined by allocation patterns of
your application and the general memory pressure it causes. In other
words its non-determinsitic -- you have no idea when that object will
be collected. Reference counting on the other hand, barring cycles,
can destroy that object _immediately_ after the count reaches zero.
COM has been doing this for ages.
I am with Chris here. You are making absolutely ridiculous claims.
Dmitriy V'jukov
> Note that 'Lock' and 'Unlock' are notional. They can be a global lock
> but they can also be atomic operations, a lock specific to the
> implementation of g_settings, or anything else you like.
Try to sketch implementation based on atomic operations to feel the
difference between basic and strong thread safety.
> See how threads are not the only thing that can have a reference? The
> global 'g_settings' pointer (and its associated lock if it has one)
> can also have a reference.
You are saying that things are simple, just follow the rule
'pointer==reference'.
Well, if I have pointer to object then things are really simple. But
problem in the example that I don't have pointer to object. I have
pointer to pointer to object. In this situation things are not so
simple. Because I need basically 2 reference counters (or mutexes):
one for object and one for pointer to object.
This is difference between basic thread safety (when you can use
single atomic_inc() for acquire operation) and between strong thread
safety (when you can't).
Both useful in practice.
So I would not say that it's just "an awful lot of work to create a
problem".
Dmitriy V'jukov
David Schwartz
> On Mar 31, 8:37 pm, David Schwartz <dav...@webmaster.com> wrote:
> > Note that 'Lock' and 'Unlock' are notional. They can be a global lock
> > but they can also be atomic operations, a lock specific to the
> > implementation of g_settings, or anything else you like.
> Try to sketch implementation based on atomic operations to feel the
> difference between basic and strong thread safety.
Why would I want to do such a ridiculous thing? I write portable code
to international standards. Why would I want to rewrite my code just
because a new CPU came out or something like that?
> > See how threads are not the only thing that can have a reference? The
> > global 'g_settings' pointer (and its associated lock if it has one)
> > can also have a reference.
> You are saying that things are simple, just follow the rule
> 'pointer==reference'.
Yes, that's what I'm saying.
> Well, if I have pointer to object then things are really simple. But
> problem in the example that I don't have pointer to object. I have
> pointer to pointer to object. In this situation things are not so
> simple. Because I need basically 2 reference counters (or mutexes):
> one for object and one for pointer to object.
If you have a pointer to a pointer to an object, that pointer has a
pointer to an object and you have a pointer to that pointer. You can
do this with two reference counts if you want. You may also be able to
do it with one. It depends on the exact circumstances.
As for having two mutexes, so what?
> This is difference between basic thread safety (when you can use
> single atomic_inc() for acquire operation) and between strong thread
> safety (when you can't).
>
> Both useful in practice.
>
> So I would not say that it's just "an awful lot of work to create a
> problem".
I still don't get it. Why not just always keep a reference with every
pointer? Is the only issue performance? Is this whole thing about
premature optimization?
DS
Chris Thomasson
Using locks makes it work within the scope of the POSIX Standard, which is
very good. Here is an example:
http://groups.google.com/group/comp.programming.threads/browse_frm/thread/177609a5eff4a466
IMHO, it's nice that the PThread standard is flexible enough to support this
narrow type of usage pattern. As you very well know, locks are _very_ useful
indeed.
Chris Thomasson
My only point is that, IMVHO of course, GC can be a wonderful tool for all
sorts of lifetime management schemes. This due to the fact that it can
inform the management protocol when an object is in a quiescent state. IMO,
lifetime management "basically implies" that an object will only be
destroyed when its unreachable; if it never dies, so be it. If it can die,
well, knowing when it's quiescent is a _very_ important piece of information
indeed. You don't really want to terminate an object if it is still able to
be accessed by other entities. Therefore, I conclude that GC and/or
reference counting can be important tools for a lifetime management scheme
to use in general.
Does that make any sense?
Kai-Uwe Bux
Sure. However, often it is the other way around: the object knows when its
job is done and it has to die. Then the object must notify all interested
parties that it is about to self-detonate. In those cases, GC only serves
as a bug-hunting tool flagging a missing notification or a notified party
that did not remove its handle on the object.
The point is that it is not necessarily the objects mistake to
self-destruct. It is often more likely that it is a clients fault to expect
the object to be still alive. If GC keeps an object around that is
semantically supposed to be dead, it can hide a logic bug in the program.
Best
Kai-Uwe Bux
Dmitriy V'jukov
> I still don't get it. Why not just always keep a reference with every
> pointer? Is the only issue performance? Is this whole thing about
> premature optimization?
If you mean difference between implementation of strong thread safety
based on additional persistent mutex and based on atomic operation -
Yes. Implementation based on atomic operations doesn't give any
additional features.
One can easily achieve strong thread safety by combining
boost::shared_ptr and mutex:
boost::shared_ptr<application_settings> g_settings;
mutex_t g_mutex;
All operations involving g_settings (update, acquire) must lock
g_mutex. All operations on acquired object (release) can not lock
g_mutex.
But with atomic operations one can go further and eliminate all atomic
operations and mutation of shared state on fast-path. This way threads
work only with cached data in read-only mode most of the time. This
makes huge performance and scalability difference provided high load.
Basically this means superlinear negative scaling versus linear
positive scaling (I emphasize: provided high load).
Dmitriy V'jukov
James Kanze
> "James Kanze" <james.ka...@gmail.com> wrote in message
> news:1d6f13f6-f217-4609...@s50g2000hsb.googlegroups.com...
> On Mar 31, 4:16 am, "Chris Thomasson" <cris...@comcast.net> wrote:
> [...]
> My only point is that, IMVHO of course, GC can be a wonderful
> tool for all sorts of lifetime management schemes. This due to
> the fact that it can inform the management protocol when an
> object is in a quiescent state.
But you still haven't explained what you mean by "an object in a
quiescent state". All garbage collection can possibly tell you
is whether the object can be (might be) accessed. As far as I
can see, this has nothing to do with the state of the object.
> IMO, lifetime management "basically implies" that an object
> will only be destroyed when its unreachable;
For what meaning of "destroyed". I intentially chose the word
"terminated" in my discussion to avoid any link with the C++
destructors or delete; those are the usual ways of terminating
an object in C++, but the concept of termination is a design
concept, applicable to all languages, and delete (and typically
destructors in the absense of garbage collection) also do memory
management, which is really a separate, unrelated issue.
> if it never dies, so be it.
In the terms I'm using, if an object has a determinate lifetime,
it must be terminated at a specific point in time, in response
to a specific external event, or something similar. Regardless
of who has pointers to it. If an object has an indeterminate
lifetime, then it doesn't matter. In a very real sense, it is
never terminated (never dies); it just disappears. Its
"lifetime" never ends.
> If it can die, well, knowing when it's quiescent is a _very_
> important piece of information indeed.
You still haven't defined quiescent, and what it means with
regards to object lifetime.
> You don't really want to terminate an object if it is still
> able to be accessed by other entities.
You don't really have the choice, if your program is to work.
And it's not really a problem, if the other entities don't
actually access it. On the other hand, if the object doesn't
need termination, then you never terminate it, even when there
are no more pointers to it. It just "disappears"; it's
invisible (since there is no way to "see" it), and presumably,
it's memory will somehow be recycled, but that's it.
> Therefore, I conclude that GC and/or reference counting can be
> important tools for a lifetime management scheme to use in
> general.
> Does that make any sense?
Not yet. I'm still having problems with vocabulary. My
interpretation of "quiescent", for example, implies that an
object will no longer change its state. But that can't be the
meaning your using---most of my dynamically allocated objects
which don't have explicit lifetimes are polymorphic agents
without any state.
David Schwartz
> On Apr 1, 2:56 am, David Schwartz <dav...@webmaster.com> wrote:
> > I still don't get it. Why not just always keep a reference with every
> > pointer? Is the only issue performance? Is this whole thing about
> > premature optimization?
> If you mean difference between implementation of strong thread safety
> based on additional persistent mutex and based on atomic operation -
> Yes. Implementation based on atomic operations doesn't give any
> additional features.
I see. So the whole "problem" you are trying to solve is that an
optimization doesn't work.
> One can easily achieve strong thread safety by combining
> boost::shared_ptr and mutex:
> boost::shared_ptr<application_settings> g_settings;
> mutex_t g_mutex;
> All operations involving g_settings (update, acquire) must lock
> g_mutex. All operations on acquired object (release) can not lock
> g_mutex.
Why would one ever even bother? This whole "strong thread safety"
issue is not an issue. It's a problem you can only run into by
choosing an inappropriate optimization. Just don't do that. Don't
optimize until you have a proven performance issue and then choose the
appropriate (as opposed to inappropriate) optimization.
Strong thread safety (a ridiculous name, IMO) is not something extra
beyond normal thread safety. It's normal thread safety. Whatever is
not strong thread safety (weak thread safety?) is a property of an
optimization that should only be used when it's appropriate.
That is, you have to do something *wrong* to need strong thread
safety.
> But with atomic operations one can go further and eliminate all atomic
> operations and mutation of shared state on fast-path. This way threads
> work only with cached data in read-only mode most of the time. This
> makes huge performance and scalability difference provided high load.
> Basically this means superlinear negative scaling versus linear
> positive scaling (I emphasize: provided high load).
If you can optimize code, great. If it runs better, that's good too.
But it sounds like you are framing this whole issue in completely the
wrong terms. There is no thread safety problem -- use locks
appropriately and there's no reference issue. It's impossible to get
into a situation where the object can become invalid before you can
increment its reference unless you're doing something mind-bogglingly
stupid.
Sane people just don't do such stupid things. That is, this is not
some optimization or extra feature. It's just a stupid bug, like an
off-by-error, that perhaps programmers need to understand so that they
can (trivially) avoid it.
DS
Dmitriy V'jukov
> But it sounds like you are framing this whole issue in completely the
> wrong terms. There is no thread safety problem -- use locks
> appropriately and there's no reference issue. It's impossible to get
> into a situation where the object can become invalid before you can
> increment its reference unless you're doing something mind-bogglingly
> stupid.
Why I must use locks unconditionally by default??? We are living not
in 60's.
You are considering smart pointer with strong thread safety as
application level primitive. It's not application level primitive,
it's low-level basic primitive. Like mutex for lock-based programming.
Implementation of low-level basic primitives is difficult.
Implementation of mutex (which you are proposing to use) is not
straightforward. And it's not portable at all. It's dependent on
compiler, on OS, on hardware.
Why you are not saying to implementor of your threading library "You
are stupid! Not even trying to use those atomic operations! Just don't
do such stupid things!"?
Why you are not saying "Just don't use databases. They are extremely
hard to implement."?
You are mixing up rules for application developers and for
multithreading support library developers.
Dmitriy V'jukov
Chris Thomasson
[...]
How can I do a reader pattern without strong thread-safety? It looks like
the Standard Committee is considering adding this feature to shared_ptr
anyway:
http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2007/n2297.html#atomic
David Schwartz
> On Apr 1, 3:48 pm, David Schwartz <dav...@webmaster.com> wrote:
> > But it sounds like you are framing this whole issue in completely the
> > wrong terms. There is no thread safety problem -- use locks
> > appropriately and there's no reference issue. It's impossible to get
> > into a situation where the object can become invalid before you can
> > increment its reference unless you're doing something mind-bogglingly
> > stupid.
> Why I must use locks unconditionally by default??? We are living not
> in 60's.
You don't have to use locks unconditionally. You have to use locks
where you have no other/better way to meet POSIX memory visibility and
concurrency rules. Otherwise, do whatever you want.
> You are considering smart pointer with strong thread safety as
> application level primitive. It's not application level primitive,
> it's low-level basic primitive. Like mutex for lock-based programming.
I can't follow you here. Are you saying smart pointers are not meant
to be used by applications and only meant as internals of the
implementation of threading libraries? When you say "application level
primitive", do you mean implemented at application level or used at
application level?
> Implementation of low-level basic primitives is difficult.
> Implementation of mutex (which you are proposing to use) is not
> straightforward. And it's not portable at all. It's dependent on
> compiler, on OS, on hardware.
Absolutely. How you implement things like mutexes and smart pointers
is *very* platform specific. How you use them is not.
> Why you are not saying to implementor of your threading library "You
> are stupid! Not even trying to use those atomic operations! Just don't
> do such stupid things!"?
The implementation of a threading-library is going to be very platform-
specific. Because I don't have any special interest in any particular
platform, I talk generally about what they should do *semantically*. I
don't care how they are implemented, I just hope it will be a good
implementation.
> You are mixing up rules for application developers and for
> multithreading support library developers.
Are you saying smart pointers should not be used by applications?
Sorry, I don't understand you. Maybe we are talking past each other.
Are you saying this strong thread safety issue is purely a threading
library internal issue and application developers don't have to worry
about it?
DS
Chris Thomasson
Global locking tables can help a decrementing thread atomically release and
destroy an object when the count has dropped to zero. This is important
because another thread could sneak in and concurrently attempt to increment
the reference count during this time. This is classic race-condition in
atomic reference counting pointers; Java references can solve it, so can
PThreads and C... The important part is that the lifetime of the mutexs
within the global table has static duration and should always outlast the
dynamic objects that which hash indexes...
Chris Thomasson
> On Apr 1, 5:58 am, "Chris Thomasson" <cris...@comcast.net> wrote:
> > "James Kanze" <james.ka...@gmail.com> wrote in message
>
> > news:1d6f13f6-f217-4609...@s50g2000hsb.googlegroups.com...
> > On Mar 31, 4:16 am, "Chris Thomasson" <cris...@comcast.net> wrote:
> > [...]
>
> > My only point is that, IMVHO of course, GC can be a wonderful
> > tool for all sorts of lifetime management schemes. This due to
> > the fact that it can inform the management protocol when an
> > object is in a quiescent state.
> But you still haven't explained what you mean by "an object in a
> quiescent state".
[...]
http://dictionary.reference.com/browse/quiescent%20
An object is at rest and has nothing to do. When an object reaches that
point in its lifetime it can decide to safely destroy itself and/or safely
reuse/cache itself for later resurrection and re-initialization;
whatever.... In RCU speak an object is in a quiescent-state after its
rendered unreachable and has been successfully deferred through the callback
system. All concurrently accessing threads within the epoch will go through
a quiescent-state. The information baking an epoch can be as fine-grain as
an embedded per-object proxy reference count, or it can be coarse-grain,
per-cpu and/or per-thread; whatever. When an epoch goes quiescent, all
objects contained within it have also quiesced.
Dmitriy V'jukov
> On Apr 1, 11:52 am, "Dmitriy V'jukov" <dvyu...@gmail.com> wrote:
>
> > On Apr 1, 3:48 pm, David Schwartz <dav...@webmaster.com> wrote:
> > > But it sounds like you are framing this whole issue in completely the
> > > wrong terms. There is no thread safety problem -- use locks
> > > appropriately and there's no reference issue. It's impossible to get
> > > into a situation where the object can become invalid before you can
> > > increment its reference unless you're doing something mind-bogglingly
> > > stupid.
> > Why I must use locks unconditionally by default??? We are living not
> > in 60's.
>
> You don't have to use locks unconditionally. You have to use locks
> where you have no other/better way to meet POSIX memory visibility and
> concurrency rules. Otherwise, do whatever you want.
Why I must meet POSIX memory visibility and concurrency rules by
default?
Large amount of code is written solely for Windows/x86.
> > You are considering smart pointer with strong thread safety as
> > application level primitive. It's not application level primitive,
> > it's low-level basic primitive. Like mutex for lock-based programming.
>
> I can't follow you here. Are you saying smart pointers are not meant
> to be used by applications and only meant as internals of the
> implementation of threading libraries? When you say "application level
> primitive", do you mean implemented at application level or used at
> application level?
By 'application level primitive' I mean implemented at application
level.
By 'low-level primitive' I mean implemented at 'system' level.
At application level one can *use* low-level primitives w/o the need
to implement them.
> > You are mixing up rules for application developers and for
> > multithreading support library developers.
>
> Are you saying smart pointers should not be used by applications?
They may be used by application developers, but they must not be
implemented by application developers.
> Sorry, I don't understand you. Maybe we are talking past each other.
> Are you saying this strong thread safety issue is purely a threading
> library internal issue and application developers don't have to worry
> about it?
I'm saying that *implementation* of both strong thread safety and
mutex is purely a threading library internal issue. API of both strong
thread safety and mutex can be used by application developer w/o the
need to knowing how it's implemented.
I'm talking from the point of view of threading library developer. You
are talking from the point of view of application developer. You can
even not bother how strong thread safety is implemented (with atomic
operations or with additional mutexes), you just have to know that you
can concurrently mutate single smart pointer w/o any additional
synchronization.
Dmitriy V'jukov
James Kanze
> "James Kanze" <james.ka...@gmail.com> wrote in message
> news:1e8d3d15-c2e1-4968...@m36g2000hse.googlegroups.com...
> > On Apr 1, 5:58 am, "Chris Thomasson" <cris...@comcast.net> wrote:
> > > "James Kanze" <james.ka...@gmail.com> wrote in message
> > >news:1d6f13f6-f217-4609...@s50g2000hsb.googlegroups.com...
> > > On Mar 31, 4:16 am, "Chris Thomasson" <cris...@comcast.net> wrote:
> > > [...]
> > > My only point is that, IMVHO of course, GC can be a wonderful
> > > tool for all sorts of lifetime management schemes. This due to
> > > the fact that it can inform the management protocol when an
> > > object is in a quiescent state.
> > But you still haven't explained what you mean by "an object in a
> > quiescent state".
> [...]
> http://dictionary.reference.com/browse/quiescent%20
> An object is at rest and has nothing to do.
Including being terminated? (I.e. termination is a no-op for
the object.) If termination is not a no-op, then it still has
something to do. Otherwise, the question isn't so much whether
it has something to do or not, but whether it can still be used
by other objects or not. If not, then it probably needs some
sort of explicit termination, in order to inform the other
objects that it is no longer usable (and of course, whatever
event made it unusable should trigger termination, and this
notification). If so, then it lives on forever. Conceptually,
at least---when no other object can reach it, it's memory can be
recycled for other uses.
> When an object reaches that point in its lifetime it can
> decide to safely destroy itself and/or safely reuse/cache
> itself for later resurrection and re-initialization;
> whatever....
Why does the object have to decide?
Or perhaps more to the point: why does the object have nothing
more to do: because it has reached a state from which it can do
nothing more (and so probably requires explicit termination), or
because it normally only has something to do as a result of
requests from another object, and no other object can reach it.
In the later case, of course, that state is irrelevant to the
object; it's exterior to the object, and the object (normally)
has no way of knowing, nor should it.
In the first case, garbage collection will not reap the object
if there are any remaining pointers to it, even if its lifetime
has ended; this allows some additional error checking. In the
second case, garbage collection can be said to play an enabling
role; without garbage collection, somehow, the fact that the
object has become unreachable must be determined manually, so
that the object can be freed. (In many cases, some form of
smart pointer will do the job adequately. In a few, however, it
is more complicated.)
> In RCU speak an object is in a quiescent-state after its
> rendered unreachable and has been successfully deferred
> through the callback system. All concurrently accessing
> threads within the epoch will go through a quiescent-state.
> The information baking an epoch can be as fine-grain as an
> embedded per-object proxy reference count, or it can be
> coarse-grain, per-cpu and/or per-thread; whatever. When an
> epoch goes quiescent, all objects contained within it have
> also quiesced.
I'm not familiar with this vocabulary, so I'll pass on it.
David Schwartz
> Global locking tables can help a decrementing thread atomically release and
> destroy an object when the count has dropped to zero. This is important
> because another thread could sneak in and concurrently attempt to increment
> the reference count during this time.
No, another thread can't sneak in and concurrent attempt to increment
the reference count during that time. The decrementing thread is the
only thread that holds a reference to the object, so no other thread
could even find the object. How could it attempt to increment the
reference count to an object it cannot find?
> This is classic race-condition in
> atomic reference counting pointers; Java references can solve it, so can
> PThreads and C... The important part is that the lifetime of the mutexs
> within the global table has static duration and should always outlast the
> dynamic objects that which hash indexes...
The only way a thread can increment the reference count on an object
is if it has a pointer to the object. When using atomic reference
counting pointers, pointers are *always* accompanied by references.
That is the whole point of such pointers. If you have a pointer, you
have a reference. If you don't have a reference, you don't have a
pointer. You cannot obtain a reference unless something that has a
reference gives you one.
DS
David Schwartz
> I'm saying that *implementation* of both strong thread safety and
> mutex is purely a threading library internal issue. API of both strong
> thread safety and mutex can be used by application developer w/o the
> need to knowing how it's implemented.
>
> I'm talking from the point of view of threading library developer. You
> are talking from the point of view of application developer. You can
> even not bother how strong thread safety is implemented (with atomic
> operations or with additional mutexes), you just have to know that you
> can concurrently mutate single smart pointer w/o any additional
> synchronization.
I completely agree with everything you said, I just don't see what it
has to do with anything. Can you explain why applications have to deal
with this issue if they just make sure that every pointer is
accompanied by a reference? Isn't that the whole point of atomic
reference-counting pointers?
DS
Chris Thomasson
> On Apr 1, 9:27 pm, "Chris Thomasson" <cris...@comcast.net> wrote:
>
>> Global locking tables can help a decrementing thread atomically release
>> and
>> destroy an object when the count has dropped to zero. This is important
>> because another thread could sneak in and concurrently attempt to
>> increment
>> the reference count during this time.
>
> No, another thread can't sneak in and concurrent attempt to increment
> the reference count during that time. The decrementing thread is the
> only thread that holds a reference to the object, so no other thread
> could even find the object. How could it attempt to increment the
> reference count to an object it cannot find?
Lets take some standard code into account... How about a PThread
implmentation for a strongly thread-safe counted pointers which can be found
here, it compiles fine:
http://appcore.home.comcast.net/misc/refcount-c.html
(refcount_copy/swap functions; returns non-zero on failure)
These functions are passed pointers to a shared location that in turn
contains a pointer to a refcount object; you can use them like this:
_____________________________________________________________________
extern "C" void userobj_dtor(void*);
class userobj {
friend void userobj_dtor(void*);
refcount m_refs;
int m_state;
public:
userobj(int state, refcount_refs refs = 1)
: m_state(state) {
refcount_create(&m_refs, refs, userobj_dtor, this);
}
};
void userobj_dtor(void* state) {
delete reinterpret_cast<userobj*>(state);
}
static refcount_shared* g_shared = NULL;
struct userobj_thread {
void readers() {
for (;;) {
refcount_local* local;
if (! refcount_copy(&g_shared, &local)) {
userobj* const uobj = (userobj*)refcount_get_state(local);
printf("(%p/%p/%d)-userobj_thread/userobj/userobj::state",
(void*)this, (void*)uobj, uobj->state);
refcount_release(local);
}
}
}
void writers() {
for (int i = 0 ;; ++i) {
userobj* const obj = new userobj(i);
refcount_local* local = &obj->m_refs;
if (! refcount_swap(&g_shared, &local)) {
refcount_release(local);
}
}
}
};
_____________________________________________________________________
Please check out the 'refcount_copy()/swap()' functions. How would implement
those API's differently? The readers are acquiring pointers to objects that
did not previously own a reference to. IMHO, the locking table is a good
synchronization scheme to use in this scenario.
[...]
David Schwartz
> static refcount_shared* g_shared = NULL;
> if (! refcount_copy(&g_shared, &local)) {
> if (! refcount_swap(&g_shared, &local)) {
> Please check out the 'refcount_copy()/swap()' functions. How would implement
> those API's differently? The readers are acquiring pointers to objects that
> did not previously own a reference to.
Of course the readers are acquiring pointers to object that *THEY* did
not previously have a reference to. But 'g_shared' has a reference to
them, since it has a pointer to them. A pointer should always include
a reference, then this whole "add ref race with dec ref" simply cannot
ever occur.
The whole point of these smart atomic reference counting pointers is
that you always keep a reference count with every pointer. The races
alleged to be possible simply cannot happen unless you deliberately do
something nonsensical.
You cannot add a reference unless you have a pointer. You cannot have
a pointer unless you have a reference. You can only get a reference by
getting the object from something, and that something must have the
object and thus have a reference.
DS
Chris Thomasson
> On Apr 2, 3:25 pm, "Chris Thomasson" <cris...@comcast.net> wrote:
>
>> static refcount_shared* g_shared = NULL;
>
>> if (! refcount_copy(&g_shared, &local)) {
>
>> if (! refcount_swap(&g_shared, &local)) {
>
>> Please check out the 'refcount_copy()/swap()' functions. How would
>> implement
>> those API's differently? The readers are acquiring pointers to objects
>> that
>> did not previously own a reference to.
>
> Of course the readers are acquiring pointers to object that *THEY* did
> not previously have a reference to. But 'g_shared' has a reference to
> them, since it has a pointer to them. A pointer should always include
> a reference, then this whole "add ref race with dec ref" simply cannot
> ever occur.
The locking table allows me to use raw shared pointers to reference counter
objects. There is no need to keep a separate reference count along with the
shared pointer to a counter when I have persistent locks, like the example
code I posted shows. This saves space as well; one word per-shared pointer.
E.g.,
_____________________________________________________
static refcount_shared* g_shared = NULL;
/* instead of something with like: */
struct refcount_shared {
refcount *ptr;
int refs;
};
static refcount_shared g_shared = { NULL, 0 };
_____________________________________________________
Can you modify the implementation of my refcount API here:
http://appcore.home.comcast.net/misc/refcount-c.html
to make it more efficient?
Chris Thomasson
On Apr 2, 6:49 am, "Chris Thomasson" <cris...@comcast.net> wrote:
> > "James Kanze" <james.ka...@gmail.com> wrote in message
> > news:1e8d3d15-c2e1-4968...@m36g2000hse.googlegroups.com...
> > > On Apr 1, 5:58 am, "Chris Thomasson" <cris...@comcast.net> wrote:
> > > > "James Kanze" <james.ka...@gmail.com> wrote in message
> > > >news:1d6f13f6-f217-4609...@s50g2000hsb.googlegroups.com...
> > > > On Mar 31, 4:16 am, "Chris Thomasson" <cris...@comcast.net> wrote:
> > > > [...]
> > > > My only point is that, IMVHO of course, GC can be a wonderful
> > > > tool for all sorts of lifetime management schemes. This due to
> > > > the fact that it can inform the management protocol when an
> > > > object is in a quiescent state.
> > > But you still haven't explained what you mean by "an object in a
> > > quiescent state".
> > [...]
> > http://dictionary.reference.com/browse/quiescent%20
> > An object is at rest and has nothing to do.
> Including being terminated?
Calling the objects destructor is fine in this state.
> (I.e. termination is a no-op for
> the object.) If termination is not a no-op, then it still has
> something to do.
When the counter has dropped to zero, the object can be destroyed, reused,
cached, ect.
> Otherwise, the question isn't so much whether
> it has something to do or not, but whether it can still be used
> by other objects or not.
No dynamic object should be able to acquire a reference to an object whose
reference count is zero. A Proxy GC will call an in-quiescent state callback
function for an object when it determines that said object has quiesced
(e.g., unreachable). This is analogous to a reference counting algorithm
dropping the count to zero and subsequently notifying the application via.
callback. Imagine if shared_ptr did not call dtor, but called a function
that allowed an application to decide what to do. It can call the objects
dtor, or cache it, or immediately reuse it, whatever, the object is
quiescent.
> If not, then it probably needs some
> sort of explicit termination, in order to inform the other
> objects that it is no longer usable (and of course, whatever
> event made it unusable should trigger termination, and this
> notification). If so, then it lives on forever. Conceptually,
> at least---when no other object can reach it, it's memory can be
> recycled for other uses.
It can be reused, cached, the dtor can be called, ect.
> > When an object reaches that point in its lifetime it can
> > decide to safely destroy itself and/or safely reuse/cache
> > itself for later resurrection and re-initialization;
> > whatever....
> Why does the object have to decide?
The programmer who creates the logic can decide. E.g:
void object_quiescent(object* const _this) {
// you can call dtor; delete _this
// you can cache; object_cache_push(_this);
// the object is unreachable indeed.
}
> Or perhaps more to the point: why does the object have nothing
> more to do: because it has reached a state from which it can do
> nothing more (and so probably requires explicit termination), or
> because it normally only has something to do as a result of
> requests from another object, and no other object can reach it.
> In the later case, of course, that state is irrelevant to the
> object; it's exterior to the object, and the object (normally)
> has no way of knowing, nor should it.
The fact that the GC or reference-count can infrom the program logic that an
object is not able to be reached is valuable information to any lifetime
management scheme which deals with dynamic objects.
> In the first case, garbage collection will not reap the object
> if there are any remaining pointers to it, even if its lifetime
> has ended; this allows some additional error checking. In the
> second case, garbage collection can be said to play an enabling
> role; without garbage collection, somehow, the fact that the
> object has become unreachable must be determined manually, so
> that the object can be freed. (In many cases, some form of
> smart pointer will do the job adequately. In a few, however, it
> is more complicated.)
A quiescent-state is like a GC determining that an object can be reaped, but
informing the application and letting it decide what to do. It can call the
dtor, or reuse, ect.
> > In RCU speak an object is in a quiescent-state after its
> > rendered unreachable and has been successfully deferred
> > through the callback system. All concurrently accessing
> > threads within the epoch will go through a quiescent-state.
> > The information baking an epoch can be as fine-grain as an
> > embedded per-object proxy reference count, or it can be
> > coarse-grain, per-cpu and/or per-thread; whatever. When an
> > epoch goes quiescent, all objects contained within it have
> > also quiesced.
> I'm not familiar with this vocabulary, so I'll pass on it.
Check this out:
http://en.wikipedia.org/wiki/Read-copy-update
Dmitriy V'jukov
> Of course the readers are acquiring pointers to object that *THEY* did
> not previously have a reference to. But 'g_shared' has a reference to
> them, since it has a pointer to them. A pointer should always include
> a reference, then this whole "add ref race with dec ref" simply cannot
> ever occur.
This is wrong. This whole race simply cannot ever occur only if (1)
pointer always includes a reference ***AND*** (2) owner of a pointer
makes copy of pointer (and reference increment) BY HIMSELF.
I agree that when condition (1) is violated is just a bad design.
But condition (2) can be violated sometimes, and it's NOT bad design,
it's just given situation. There can be no owner of a pointer (and
reference) at all. Here I mean 'active' owner which can make copy of a
pointer.
Dmitriy V'jukov
Dmitriy V'jukov
> I completely agree with everything you said, I just don't see what it
> has to do with anything. Can you explain why applications have to deal
> with this issue if they just make sure that every pointer is
> accompanied by a reference? Isn't that the whole point of atomic
> reference-counting pointers?
You want example when following simple functions can't cope with the
task? Am I understand you correctly?
void acquire(T* x)
{
atomic_inc(x->rc);
}
void release(T* x)
{
if (0 == atomic_dec(x->rc))
delete x;
}
Dmitriy V'jukov
David Schwartz
> You want example when following simple functions can't cope with the
> task? Am I understand you correctly?
>
> void acquire(T* x)
> {
> atomic_inc(x->rc);
>
> }
>
> void release(T* x)
> {
> if (0 == atomic_dec(x->rc))
> delete x;
>
> }
What is the problem with this supposed to be? This code appears race-
free to me. Of course, you can only call 'acquire' if you hold a
reference (to acquire another reference that you may then give to
something else). But you should never even consider doing anything
with a pointer if you don't have a reference.
DS
David Schwartz
> This is wrong. This whole race simply cannot ever occur only if (1)
> pointer always includes a reference ***AND*** (2) owner of a pointer
> makes copy of pointer (and reference increment) BY HIMSELF.
> I agree that when condition (1) is violated is just a bad design.
> But condition (2) can be violated sometimes, and it's NOT bad design,
> it's just given situation. There can be no owner of a pointer (and
> reference) at all. Here I mean 'active' owner which can make copy of a
> pointer.
I don't understand your requirement 2. It doesn't matter who or what
makes the copy of the pointer, so long as *something* has a reference.
The owner of a reference is notional, not enforced. For example, if a
global variable contains a pointer, it also has a [notional]
reference. Any thread that access that global variable can 'borrow'
the reference.
The only potential problem is if the owner of the 'notional' reference
releases its reference at the same time it is using it. But that race
is in the owner of the reference, not the atomic pointer
implementation or whatever.
A global variable can have a reference. A thread can have a reference.
A collection can have a reference. The owner is just conceptual.
If, for example, I have a hash table that has a bunch of objects in
it, it can also have a reference to each of those objects to ensure
they aren't removed while they're still in the table. But that
reference can be used by any thread that calls into the hash table's
functions.
DS