Thread-safe reference counts.

On Mar 28, 12:17 am, Sam <s...@email-scan.com> wrote:
> gpderetta writes: 
> 
> 
>
> 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.

> [...] 
> 
>
> I'm almost afraid to look.

Nobody is forcing you to.

> 
>
> "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.

> 
>
> /me looks at my reference-counted class hierarchy, that supports weak
> references and virtual inheritance, refrains from any cockamamie logic lik
e
> 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.

> 
>
> 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 typ
e.
> 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 nativ
e
> 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).

> [...] 
> 
>
> 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?

> 
> 
>
> 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.

> [...] 
> 
>
> 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 i
t
> 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 like
ly
> 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.
> 
>
> I see no need for something heavily customized. Just basic operations,
> typical for reference-counted objects, will suffice, as long as you do the
m
> correctly. Really, this is not rocket science.
>

Then do not complain about performance!

--
gpd

"David Schwartz" <davids@webmaster.com> wrote in message
news:9ee8ea51-7f0e-4733-801e-e798d086d177@s8g2000prg.googlegroups.com...
> 
>
> 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:

http://citeseer.ist.psu.edu/cache/p...s01lockfree.pdf




> 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/show...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/mis...ample_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.

"Alexander Terekhov" <terekhov@web.de> wrote in message
news:47EC0773.6754B949@web.de...
>
> David Schwartz wrote: 
>
> See
>
> http://www.open-std.org/JTC1/SC22/W...297.html#atomic

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.

"David Schwartz" <davids@webmaster.com> wrote in message
news:9ee8ea51-7f0e-4733-801e-e798d086d177@s8g2000prg.googlegroups.com...
> 
>
> 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?

Here is some code you can look at which implements strongly thread-safe
reference counting:


http://groups.google.com/group/comp...br />
4c08d9dd


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.

On Mar 27, 3:14=A0pm, gpderetta <gpdere...@gmail.com> wrote:
> On Mar 27, 9:42 pm, c...@mailvault.com wrote:
 
bEbenezer.net/comparison.html
>
> Use an std::vector (or boost::array) instead of std::deque or
> std::list for applications where serialization performance is
> critical.
>

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" <cristom@comcast.net> wrote in message
 news:jtidnfmYi5kOz3HanZ2dnUVZ_gydnZ2d@co
mcast.com...
>
> "Alexander Terekhov" <terekhov@web.de> wrote in message
> news:47EC0773.6754B949@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.

I seems like they are going for something that is analogous to Java
references. Finally, strong thread-safety is being taken seriously.

On Mar 27, 9:42 pm, c...@mailvault.com wrote:
> On Mar 27, 8:12 am, gpderetta <gpdere...@gmail.com> wrote:
 
 
 
 

> 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.  (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.kanze@gmail.com
Conseils en informatique orient=E9e objet/
Beratung in objektorientierter Datenverarbeitung
9 place S=E9mard, 78210 St.-Cyr-l'=C9cole, France, +33 (0)1 30 23 00 34

On Mar 28, 5:19=A0am, James Kanze <james.ka...@gmail.com> wrote:
> On Mar 27, 9:42 pm, c...@mailvault.com wrote:
> 
>
> Certainly. =A0And none of them (no more than any other code
> written by human beings) are perfect. =A0In general, though, the
> more intensely used the library, the better the chances are that
> it is pretty good, or even better. =A0The Boost smart pointers are
> amongst the most widely used Boost library, and should certainly
> be your first choice if you need smart pointers. =A0

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

jason.cipriani@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.

--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/products/?u

Jon Harrop wrote:
> jason.cipriani@gmail.com wrote: 
>
> A concurrent garbage collector is the appropriate way to handle that
> situation.
>
One possible way, reference counted objects work just as well.

--
Ian Collins.