strong atomic reference counting...
Chris M. Thomasson
reference counting using a PDR algorithm. The basic overall pattern is as
follows:
____________________________________________________________________
template<typename T>
struct refcount
{
uword32 m_count; // = 1
T* m_object; // = new T()
static refcount* acquire_strong(refcount** pref)
{
pdr_acquire();
refcount* ref = ATOMIC_LOAD(pref);
if (ref)
{
uword32 count = ref->m_count;
do
{
if (! count)
{
ref = NULL;
break;
}
}
while (! ATOMIC_CAS(&ref->m_count, count, count + 1));
}
pdr_release();
return ref;
}
void release()
{
if (! ATOMIC_DEC(&m_count))
{
delete m_object;
pdr_defer(this);
}
}
};
____________________________________________________________________
I wanted to try and eliminate that nasty CAS-loop in `acquire_strong()'
which implements the "increment if not zero" logic. So, here is what I came
up with:
____________________________________________________________________
template<typename T>
struct refcount
{
uword32 m_count; // = 2
T* m_object; // = new T()
static refcount* acquire_strong(refcount** pref)
{
pdr_acquire();
refcount* ref = ATOMIC_LOAD(pref);
if (ref && ATOMIC_FAA(&ref->m_count, 2) & 0x1U)
{
ref = NULL;
}
pdr_release();
return ref;
}
void release()
{
if (ATOMIC_FAA(&m_count, -2) == 2)
{
uword32 cmp = 0;
if (ATOMIC_CAS(&m_count, cmp, 1))
{
delete m_object;
pdr_defer(this);
}
}
}
};
____________________________________________________________________
Instead of forcing the `acquire_strong()' function to never even try to
increment a reference count that is zero, I simply inc/dec the count by 2,
and when that goes to zero I _attempt_ to set it to 1. Therefore, the
`acquire_strong()' function can "easily" detect reference counted objects
that have already been deferred by checking to see if the count has the 0x1
bit set. I think I will model this in Relacy 2.2 using the following PDR
implementation:
http://cpt.pastebin.com/f71480694
So far, I think that algorithm should work out fine.
Chris M. Thomasson
news:L0g9n.1815$5n....@newsfe23.iad...
> As you may already know, you can implement strongly thread-safe atomic
> reference counting using a PDR algorithm. The basic overall pattern is as
> follows:
> ____________________________________________________________________
> ____________________________________________________________________
>
>
>
>
> I wanted to try and eliminate that nasty CAS-loop in `acquire_strong()'
> which implements the "increment if not zero" logic. So, here is what I
> came up with:
> ____________________________________________________________________
> ____________________________________________________________________
>
> Instead of forcing the `acquire_strong()' function to never even try to
> increment a reference count that is zero, I simply inc/dec the count by 2,
> and when that goes to zero I _attempt_ to set it to 1. Therefore, the
> `acquire_strong()' function can "easily" detect reference counted objects
> that have already been deferred by checking to see if the count has the
> 0x1 bit set. I think I will model this in Relacy 2.2 using the following
> PDR implementation:
>
>
> http://cpt.pastebin.com/f71480694
>
>
> So far, I think that algorithm should work out fine.
Here is a model of my experimental reference counting algorithm in Relacy:
http://cpt.pastebin.com/f63893cd9
IMVHO, it's nice to be able to remove the CAS-loop from in the function that
acquires strong references. Anyway, what do you think of the technique?
Thanks!
:^)
Marcel Müller
> IMVHO, it's nice to be able to remove the CAS-loop from in the function
> that acquires strong references. Anyway, what do you think of the
> technique?
Once I completed to move my home I will have a look at this.
But I currently already have an implementation without a CAS loop and
with only one machine size word memory footprint. (The stolen bits
trick, but without the restriction in the number of active references.)
Unfortunately not very well tested so far.
Maybe I can improve this solution further with the ideas from your post.
Once it has successfully run for some time, I will post the code here.
Marcel
Chris M. Thomasson
news:4b69ad47$0$7626$9b4e...@newsspool1.arcor-online.net...
> Chris M. Thomasson wrote:
>> IMVHO, it's nice to be able to remove the CAS-loop from in the function
>> that acquires strong references. Anyway, what do you think of the
>> technique?
>
> Once I completed to move my home I will have a look at this.
>
> But I currently already have an implementation without a CAS loop and with
> only one machine size word memory footprint. (The stolen bits trick, but
> without the restriction in the number of active references.) Unfortunately
> not very well tested so far.
Now that's pretty interesting because the "stolen bits" are typically used
to actually represent the reference count itself. Therefore, I would very
much like to examine your algorithm Marcel.
> Maybe I can improve this solution further with the ideas from your post.
> Once it has successfully run for some time, I will post the code here.
I am looking forward to it; thanks.
BTW, have you ever played around with Dmitriy Vyukov's Relacy Race Detector?
http://groups.google.com/group/relacy
IMVHO, it's an essential tool to have!
Marcel Müller
> "Marcel M�ller" <news.5...@spamgourmet.com> wrote in message
> news:4b69ad47$0$7626$9b4e...@newsspool1.arcor-online.net...
>> Chris M. Thomasson wrote:
>>> IMVHO, it's nice to be able to remove the CAS-loop from in the
>>> function that acquires strong references. Anyway, what do you think
>>> of the technique?
>>
>> Once I completed to move my home I will have a look at this.
>>
>> But I currently already have an implementation without a CAS loop and
>> with only one machine size word memory footprint. (The stolen bits
>> trick, but without the restriction in the number of active
>> references.) Unfortunately not very well tested so far.
>
> Now that's pretty interesting because the "stolen bits" are typically
> used to actually represent the reference count itself. Therefore, I
> would very much like to examine your algorithm Marcel.
The primary reference counter is intrusive in my case. (Implemented by
deriving from a base class.) However, that does not make any difference.
But the additional counter for strong thread safety works with stolen
bits. The basic idea is that this counter value is moved to the primary
reference counter immediately after the local reference is acquired from
the shared pointer. This creates a frequency distribution of values that
drops exponentially with increasing value. In fact I never was able to
increment the counter with the stolen bits above 2 in test applications
with some dozen threads. Even this is non-trivial. Since most platforms
provide at least 32 bit alignment, the two superfluous bits are usually
sufficient and no special allocator is required.
> BTW, have you ever played around with Dmitriy Vyukov's Relacy Race
> Detector?
I had a look at it when I developed the above algo. But I stopped at the
point when I realized that porting to my platform is required. On
eComStation I am restricted to gcc 3.3 (no std::atomic) and have no
posix compatibility.
Marcel
Dmitriy Vyukov
> > BTW, have you ever played around with Dmitriy Vyukov's Relacy Race
> > Detector?
>
> I had a look at it when I developed the above algo. But I stopped at the
> point when I realized that porting to my platform is required. On
> eComStation I am restricted to gcc 3.3 (no std::atomic) and have no
> posix compatibility.
Do I get you right, that you do not have access to any single Windows/
Linux box?
--
Dmitriy V'jukov
Chris M. Thomasson
> Chris M. Thomasson wrote:
>> "Marcel M�ller" <news.5...@spamgourmet.com> wrote in message
>> news:4b69ad47$0$7626$9b4e...@newsspool1.arcor-online.net...
>>> Chris M. Thomasson wrote:
>>>> IMVHO, it's nice to be able to remove the CAS-loop from in the function
>>>> that acquires strong references. Anyway, what do you think of the
>>>> technique?
>>>
>>> Once I completed to move my home I will have a look at this.
>>>
>>> But I currently already have an implementation without a CAS loop and
>>> with only one machine size word memory footprint. (The stolen bits
>>> trick, but without the restriction in the number of active references.)
>>> Unfortunately not very well tested so far.
>>
>> Now that's pretty interesting because the "stolen bits" are typically
>> used to actually represent the reference count itself. Therefore, I would
>> very much like to examine your algorithm Marcel.
>
> The primary reference counter is intrusive in my case. (Implemented by
> deriving from a base class.) However, that does not make any difference.
> But the additional counter for strong thread safety works with stolen
> bits. The basic idea is that this counter value is moved to the primary
> reference counter immediately after the local reference is acquired from
> the shared pointer. This creates a frequency distribution of values that
> drops exponentially with increasing value. In fact I never was able to
> increment the counter with the stolen bits above 2 in test applications
> with some dozen threads.
Could you please provide just some very brief pseudo-code? It sounds like
bad things could happen if the counter on the shared pointer overflows;
right? Is this what you were getting at by saying that you could not
increment the counter with the stolen bits above 2?
Humm... Well, it kind of sounds like you are doing something like:
_________________________________________________
// increment outer count.
uword32 outer = ATOMIC_FAA(&g_outer, 1) + 1;
uword32 count = GET_COUNT(outer);
object* obj = GET_OBJECT(outer);
// transfer outer to inner count.
ATOMIC_FAA(&obj->count, count);
// try and reset the outer count.
ATOMIC_CAS(&g_outer, outer, (uword32)obj);
_________________________________________________
I am most likely totally misunderstanding your algorithm and the pseudo-code
above is just way off target. What am I missing here Marcel? If I am close,
then I can definitely see the shi% hitting the fan if the outer count just
happens to overflow.
> Even this is non-trivial. Since most platforms provide at least 32 bit
> alignment, the two superfluous bits are usually sufficient and no special
> allocator is required.
>> BTW, have you ever played around with Dmitriy Vyukov's Relacy Race
>> Detector?
>
> I had a look at it when I developed the above algo. But I stopped at the
> point when I realized that porting to my platform is required. On
> eComStation I am restricted to gcc 3.3 (no std::atomic) and have no posix
> compatibility.
If I understand you correctly, then in this case you would need to try and
port your algorithm over to Relacy. IMVHO, it would be a worthwhile use of
your time. However, keep in mind that Relacy will blast the shi% out of the
algorithm and probably get it into a scenario in which the counter
overflows.
Dmitriy Vyukov
> Could you please provide just some very brief pseudo-code? It sounds like
> bad things could happen if the counter on the shared pointer overflows;
> right? Is this what you were getting at by saying that you could not
> increment the counter with the stolen bits above 2?
I suspect it's this:
http://groups.google.com/group/comp.programming.threads/msg/ce852a32d7994a06
--
Dmitriy V'jukov
Marcel Müller
>> I had a look at it when I developed the above algo. But I stopped at the
>> point when I realized that porting to my platform is required. On
>> eComStation I am restricted to gcc 3.3 (no std::atomic) and have no
>> posix compatibility.
>
> Do I get you right, that you do not have access to any single Windows/
> Linux box?
Yes. Win-Notebook without any development environment and my Linux
Server, Debian Lenny but 300MHz, only ssh and no X.
Both are no serious options.
However, I am planning a new Linux VirtualBox-Server late this year.
There I can install VMs wich match the requirements.
Marcel
Marcel Müller
> Could you please provide just some very brief pseudo-code?
Not immediately. The eCS machine is still down.
> It sounds
> like bad things could happen if the counter on the shared pointer
> overflows; right?
Yes. Very bad. The application will terminate.
> Is this what you were getting at by saying that you
> could not increment the counter with the stolen bits above 2?
No. The workaround for the above problem worked. Although in theory it
only decreases the demand from the number of acquired local copies to
the number of threads, in practice the probability for a crash is
/extremely/ low. I was definitely not able to force a crash with some
dozen threads.
> Humm... Well, it kind of sounds like you are doing something like:
> _________________________________________________
> // increment outer count.
> uword32 outer = ATOMIC_FAA(&g_outer, 1) + 1;
>
> uword32 count = GET_COUNT(outer);
>
> object* obj = GET_OBJECT(outer);
>
>
> // transfer outer to inner count.
> ATOMIC_FAA(&obj->count, count);
>
> // try and reset the outer count.
> ATOMIC_CAS(&g_outer, outer, (uword32)obj);
> _________________________________________________
I do not exactly remember the code, but basically this is true. The only
difference I remember is, that I have to undo the FAA to obj->count if
the last CAS failed, because another thread has already transfered the
outer count in this case.
> I am most likely totally misunderstanding your algorithm and the
> pseudo-code above is just way off target. What am I missing here Marcel?
> If I am close, then I can definitely see the shi% hitting the fan if the
> outer count just happens to overflow.
Absolutely. But the CAS to the outer count is only a few assembler
instructions away from the FAA. It is nearly impossible to get more than
two threads exactly to this location at the same time as long there is
no blocking instruction in between. In fact I was no even able to reach
a counter value of 2 without a synchronized debug output in between.
>> Even this is non-trivial. Since most platforms provide at least 32 bit
>> alignment, the two superfluous bits are usually sufficient and no
>> special allocator is required.
>
>>> BTW, have you ever played around with Dmitriy Vyukov's Relacy Race
>>> Detector?
>>
>> I had a look at it when I developed the above algo. But I stopped at
>> the point when I realized that porting to my platform is required. On
>> eComStation I am restricted to gcc 3.3 (no std::atomic) and have no
>> posix compatibility.
>
> If I understand you correctly, then in this case you would need to try
> and port your algorithm over to Relacy. IMVHO, it would be a worthwhile
> use of your time. However, keep in mind that Relacy will blast the shi%
> out of the algorithm and probably get it into a scenario in which the
> counter overflows.
Yes. If n threads try to acquire a pointer from the same shared location
in theory the counter could reach n. In practice the probability to
reach n is approximately the probability of one thread being in this
code lines to the power of n. This decays extremely fast in practice.
Of course, if you run several hundreds of threads in parallel the
probability increases. But this is no typical application case and most
operating systems (or administrators) will block this kind of behavior.
In fact on 32 bit platforms the counter could safely grow to 3. On a 64
bit platform it could typically grow to 7. The latter is really very
hard to reach. I think most real world applications have much more
critical errors.
In fact I prefer to know that the code is bad and the risk is
admissible rather than not to know about the quality, which is quite
more often the case.
And if you don't trust, also larger numbers are supported. (Compile time
option.) But this causes additional overhead for memory alignment,
especially for small objects.
The base class that implements the inner count automatically overloads
the new and delete operators in this case. Of course, you must not
allocate arrays of your type. But this applies to reference counted
objects anyway.
Amongst others I use the above pointer in a thread safe string class
with shared storage. Volatile instances provide strong thread safety.
The string has a custom allocator that stores the inner count and the
length at negative offsets, so the conversion of local (non-volatile)
strings to const char* is a no-op. Even the conversion from string[] to
const char*[] is a no-op. This makes wrappers to C libraries very
efficient. The direct access to shared instances other than copy
construction or assignment (lhs & rhs) is rejected by the compiler.
In this string implementation with stolen bits it is very essential that
the maximum outer count does not scale with the number of local copies
of the shared object. This can grow very large, since a single thread
may create almost any number of them over time. It only scales with the
number of threads. And even this only in the worst case. Typically it is
significantly less than the number of threads.
Back to the topic.
I have no CAS loop in my implementation, but I needed some work arounds
to things that can happen to the inner count in certain cases. At this
point your increment by two trick may help. Actually the implementation
might be currently buggy with respect to the inner count.
Marcel
Chris M. Thomasson
news:L0g9n.1815$5n....@newsfe23.iad...
> As you may already know, you can implement strongly thread-safe atomic
> reference counting using a PDR algorithm. The basic overall pattern is as
> follows:
> ____________________________________________________________________
> ____________________________________________________________________
>
>
>
>
> I wanted to try and eliminate that nasty CAS-loop in `acquire_strong()'
> which implements the "increment if not zero" logic. So, here is what I
> came up with:
> ____________________________________________________________________
> ____________________________________________________________________
>
> Instead of forcing the `acquire_strong()' function to never even try to
> increment a reference count that is zero, I simply inc/dec the count by 2,
> and when that goes to zero I _attempt_ to set it to 1. Therefore, the
> `acquire_strong()' function can "easily" detect reference counted objects
> that have already been deferred by checking to see if the count has the
> 0x1 bit set. I think I will model this in Relacy 2.2 using the following
> PDR implementation:
>
>
> http://cpt.pastebin.com/f71480694
>
>
> So far, I think that algorithm should work out fine.
Here is a model of my experimental reference counting algorithm in Relacy:
http://cpt.pastebin.com/f63893cd9
IMVHO, it's nice to be able to remove the CAS-loop from in the function that
acquires strong references. Anyway, what do you think of the technique?
Thanks!
:^)
Chris M. Thomasson
news:L0g9n.1815$5n....@newsfe23.iad...
> reference counting using a PDR algorithm. The basic overall pattern is as
> follows:
> ____________________________________________________________________
> ____________________________________________________________________
>
>
>
>
> I wanted to try and eliminate that nasty CAS-loop in `acquire_strong()'
> which implements the "increment if not zero" logic. So, here is what I
> came up with:
> ____________________________________________________________________
> ____________________________________________________________________
>
> Instead of forcing the `acquire_strong()' function to never even try to
> increment a reference count that is zero, I simply inc/dec the count by 2,
> and when that goes to zero I _attempt_ to set it to 1. Therefore, the
> `acquire_strong()' function can "easily" detect reference counted objects
> that have already been deferred by checking to see if the count has the
> 0x1 bit set. I think I will model this in Relacy 2.2 using the following
> PDR implementation:
>
>
> http://cpt.pastebin.com/f71480694
>
>
> So far, I think that algorithm should work out fine.
Chris M. Thomasson
news:L0g9n.1815$5n....@newsfe23.iad...
> reference counting using a PDR algorithm. The basic overall pattern is as
> follows:
> ____________________________________________________________________
> ____________________________________________________________________
>
>
>
>
> I wanted to try and eliminate that nasty CAS-loop in `acquire_strong()'
> which implements the "increment if not zero" logic. So, here is what I
> came up with:
> ____________________________________________________________________
> ____________________________________________________________________
>
> Instead of forcing the `acquire_strong()' function to never even try to
> increment a reference count that is zero, I simply inc/dec the count by 2,
> and when that goes to zero I _attempt_ to set it to 1. Therefore, the
> `acquire_strong()' function can "easily" detect reference counted objects
> that have already been deferred by checking to see if the count has the
> 0x1 bit set. I think I will model this in Relacy 2.2 using the following
> PDR implementation:
>
>
> http://cpt.pastebin.com/f71480694
>
>
> So far, I think that algorithm should work out fine.
Chris M. Thomasson
news:L0g9n.1815$5n....@newsfe23.iad...
> reference counting using a PDR algorithm. The basic overall pattern is as
> follows:
> ____________________________________________________________________
> ____________________________________________________________________
>
>
>
>
> I wanted to try and eliminate that nasty CAS-loop in `acquire_strong()'
> which implements the "increment if not zero" logic. So, here is what I
> came up with:
> ____________________________________________________________________
> ____________________________________________________________________
>
> Instead of forcing the `acquire_strong()' function to never even try to
> increment a reference count that is zero, I simply inc/dec the count by 2,
> and when that goes to zero I _attempt_ to set it to 1. Therefore, the
> `acquire_strong()' function can "easily" detect reference counted objects
> that have already been deferred by checking to see if the count has the
> 0x1 bit set. I think I will model this in Relacy 2.2 using the following
> PDR implementation:
>
>
> http://cpt.pastebin.com/f71480694
>
>
> So far, I think that algorithm should work out fine.
Chris M. Thomasson
news:L0g9n.1815$5n....@newsfe23.iad...
> reference counting using a PDR algorithm. The basic overall pattern is as
> follows:
> ____________________________________________________________________
> ____________________________________________________________________
>
>
>
>
> I wanted to try and eliminate that nasty CAS-loop in `acquire_strong()'
> which implements the "increment if not zero" logic. So, here is what I
> came up with:
> ____________________________________________________________________
> ____________________________________________________________________
>
> Instead of forcing the `acquire_strong()' function to never even try to
> increment a reference count that is zero, I simply inc/dec the count by 2,
> and when that goes to zero I _attempt_ to set it to 1. Therefore, the
> `acquire_strong()' function can "easily" detect reference counted objects
> that have already been deferred by checking to see if the count has the
> 0x1 bit set. I think I will model this in Relacy 2.2 using the following
> PDR implementation:
>
>
> http://cpt.pastebin.com/f71480694
>
>
> So far, I think that algorithm should work out fine.
Chris M. Thomasson
news:L0g9n.1815$5n....@newsfe23.iad...
> reference counting using a PDR algorithm. The basic overall pattern is as
> follows:
> ____________________________________________________________________
> ____________________________________________________________________
>
>
>
>
> I wanted to try and eliminate that nasty CAS-loop in `acquire_strong()'
> which implements the "increment if not zero" logic. So, here is what I
> came up with:
> ____________________________________________________________________
> ____________________________________________________________________
>
> Instead of forcing the `acquire_strong()' function to never even try to
> increment a reference count that is zero, I simply inc/dec the count by 2,
> and when that goes to zero I _attempt_ to set it to 1. Therefore, the
> `acquire_strong()' function can "easily" detect reference counted objects
> that have already been deferred by checking to see if the count has the
> 0x1 bit set. I think I will model this in Relacy 2.2 using the following
> PDR implementation:
>
>
> http://cpt.pastebin.com/f71480694
>
>
> So far, I think that algorithm should work out fine.
Chris M. Thomasson
I hope I don't come across as to harsh, but I think I would rather work with
the odds that an ABA solution provides (e.g., 64-bit aba counter NOT rolling
and false comparing within the right place of a threads critical section)
means the chance that bad things will happen is "fairly" few and far
between. The chance that 16 cores can rapidly blast the shit out of the
`g_outer' counter and just might overflow that 2-bit counter while doing so
is not that hard to imagine. IMHO, it's basically like basing the
correctness of your algorithms on "volatile" timing conditions. If I am
going to do that, I want that monotonic counter to be fairly wide!
[...]
Chris M. Thomasson
Sorry about that.