http://groups.google.com/group/comp.programming.threads?hl=en
comp.programming.threads@googlegroups.com
Today's topics:
* strong atomic reference counting... - 3 messages, 1 author
http://groups.google.com/group/comp.programming.threads/t/1b35d9cff58efb83?hl=en
* amortizing read-access in read/write mutex... - 1 messages, 1 author
http://groups.google.com/group/comp.programming.threads/t/7b92af0a72a360ba?hl=en
==============================================================================
TOPIC: strong atomic reference counting...
http://groups.google.com/group/comp.programming.threads/t/1b35d9cff58efb83?hl=en
==============================================================================
== 1 of 3 ==
Date: Wed, Feb 3 2010 5:52 am
From: "Chris M. Thomasson"
"Chris M. Thomasson" <no@spam.invalid> wrote in message
news:L0g9n.1815$5n.101@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!
:^)
== 2 of 3 ==
Date: Sat, Feb 6 2010 7:47 am
From: "Chris M. Thomasson"
"Marcel Müller" <news.5.maazl@spamgourmet.com> wrote in message
news:4b6c5408$0$6715$9b4e6d93@newsspool2.arcor-online.net...
> Chris M. Thomasson wrote:
>> 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 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!
[...]
== 3 of 3 ==
Date: Sat, Feb 6 2010 8:11 am
From: "Chris M. Thomasson"
Ummm, my bastard news server has been fuc%ing up lately!!! GRRRRR.
Sorry about that.
==============================================================================
TOPIC: amortizing read-access in read/write mutex...
http://groups.google.com/group/comp.programming.threads/t/7b92af0a72a360ba?hl=en
==============================================================================
== 1 of 1 ==
Date: Sat, Feb 6 2010 7:32 am
From: "Chris M. Thomasson"
"David Schwartz" <davids@webmaster.com> wrote in message
news:c8a86bdd-c77f-4d28-809e-1a9dd93eb781@m35g2000prh.googlegroups.com...
On Feb 5, 7:41 am, "Chris M. Thomasson" <n...@spam.invalid> wrote:
> > If I understand this correctly, writers can starve readers right?
> I don't think that's a meaningful statement. It does have absolute
> writer priority, but:
[...]
> > I cannot
> > say if this is a problem or not.
> If it is, the problem is the choice of a reader/writer lock, IMO.
What about a pattern that knows it will be hit with a constant stream of
read requests and may experience periods of rather "rapid" writer activity
that happens to occur on a non-deterministic basis. IMVHO, a read/write
mutex should "allow" readers in during the bursts of writer activity?
[...]
==============================================================================
You received this message because you are subscribed to the Google Groups "comp.programming.threads"
group.
To post to this group, visit http://groups.google.com/group/comp.programming.threads?hl=en
To unsubscribe from this group, send email to comp.programming.threads+unsubscribe@googlegroups.com
To change the way you get mail from this group, visit:
http://groups.google.com/group/comp.programming.threads/subscribe?hl=en
To report abuse, send email explaining the problem to abuse@googlegroups.com
==============================================================================
Google Groups: http://groups.google.com/?hl=en
No comments:
Post a Comment