http://groups.google.com/group/comp.programming.threads?hl=en
comp.programming.threads@googlegroups.com
Today's topics:
* memory_order_acquire/release in terms of LoadStore/LoadLoad/... - 1 messages,
1 author
http://groups.google.com/group/comp.programming.threads/t/c65d8b1eb19fcc31?hl=en
* amortizing read-access in read/write mutex... - 7 messages, 3 authors
http://groups.google.com/group/comp.programming.threads/t/7b92af0a72a360ba?hl=en
* strong atomic reference counting... - 1 messages, 1 author
http://groups.google.com/group/comp.programming.threads/t/1b35d9cff58efb83?hl=en
* ftok - 3 messages, 1 author
http://groups.google.com/group/comp.programming.threads/t/4080bc1e3e027ae0?hl=en
* Indicating truncation to the calling process - 3 messages, 2 authors
http://groups.google.com/group/comp.programming.threads/t/6c6effa342f41ce6?hl=en
* FREE Animations you can e-mail - 1 messages, 1 author
http://groups.google.com/group/comp.programming.threads/t/d8c814d2fcc9957d?hl=en
==============================================================================
TOPIC: memory_order_acquire/release in terms of LoadStore/LoadLoad/...
http://groups.google.com/group/comp.programming.threads/t/c65d8b1eb19fcc31?hl=en
==============================================================================
== 1 of 1 ==
Date: Thurs, Jan 28 2010 11:26 pm
From: frege
On Jan 25, 11:41 am, frege <gottlobfr...@gmail.com> wrote:
> For C++0x (and for 'acquire' and 'release' terminology in general),
>
> acquire == LoadLoad + LoadStore
> release == StoreStore + LoadStore
>
It looks like this is the conclusion. I've posted some of my research/
references and conclusions at http://blog.forecode.com/2010/01/29/barriers-to-understanding-memory-barriers/
. I'll probably add some more references there as I find them.
Tony
==============================================================================
TOPIC: amortizing read-access in read/write mutex...
http://groups.google.com/group/comp.programming.threads/t/7b92af0a72a360ba?hl=en
==============================================================================
== 1 of 7 ==
Date: Sun, Jan 31 2010 2:53 am
From: "Chris M. Thomasson"
You can amortize read access on a read/write mutex by using the following
fairly simple pattern:
______________________________________________________________
static uword32 g_pending = 0;
static rw_mutex g_rw_mutex;
void readers()
{
g_rw_mutex.read_lock();
for (;;)
{
request_type* r = try_to_get_a_read_request();
if (! r)
{
g_rw_mutex.read_unlock();
r = wait_for_a_read_request();
g_rw_mutex.read_lock();
}
process_read_request(r);
if (ATOMIC_LOAD(g_pending))
{
g_rw_mutex.read_unlock();
// perhaps uncomment for "unfair" read/write mutex impls.
// SwitchToThread() or sched_yield(); // Humm...
g_rw_mutex.read_lock();
}
}
g_rw_mutex.read_unlock();
}
void writers()
{
for (;;)
{
request_type* r = wait_for_a_write_request();
ATOMIC_INC(&g_pending);
g_rw_mutex.write_lock();
ATOMIC_DEC(&g_pending);
process_write_request(r);
g_rw_mutex.write_unlock();
}
}
______________________________________________________________
As you can see, I am reducing the number of times I actually "need" to gain
read access by only releasing and reacquiring read access when the
`g_pending' variable is non-zero. To show this off, I believe that the
"normal" way to code the above would be something like:
______________________________________________________________
static rw_mutex g_rw_mutex;
void readers()
{
for (;;)
{
request_type* r = wait_for_a_read_request();
g_rw_mutex.read_lock();
process_read_request(r);
g_rw_mutex.read_unlock();
}
}
void writers()
{
for (;;)
{
request_type* r = wait_for_a_write_request();
g_rw_mutex.write_lock();
process_write_request(r);
g_rw_mutex.write_unlock();
}
}
______________________________________________________________
Yes, it's a heck of a lot simpler, but it will be acquiring and releasing
read access for every darn read request! This should perform much worse than
the amortized version because generally acquiring and releasing read access
is fairly expensive in general purpose read/write mutex implementations. The
ability to skip "unnecessary" atomic RMW's and membars is key aspect in
writing scaleable software. So, AFAICT this amortization pattern might be
worth while for some applications.
Any thoughts on this particular technique?
:^)
== 2 of 7 ==
Date: Sun, Jan 31 2010 2:58 am
From: David Schwartz
On Jan 31, 2:53 am, "Chris M. Thomasson" <n...@spam.invalid> wrote:
> Any thoughts on this particular technique?
I think probably the best way to do it is a function that's a no-op if
there's no pending writer and releases the read lock, waits until the
writer is finished, and the re-acquires the read lock if there is one.
It's good for cases where you have a number of independent things you
need to do while holding a read lock and neither holding the read lock
through the whole list nor releasing it and reacquiring it on each
item makes sense.
DS
== 3 of 7 ==
Date: Sun, Jan 31 2010 3:39 am
From: Dmitriy Vyukov
On Jan 31, 1:58 pm, David Schwartz <dav...@webmaster.com> wrote:
> On Jan 31, 2:53 am, "Chris M. Thomasson" <n...@spam.invalid> wrote:
>
> > Any thoughts on this particular technique?
>
> I think probably the best way to do it is a function that's a no-op if
> there's no pending writer and releases the read lock, waits until the
> writer is finished, and the re-acquires the read lock if there is one.
> It's good for cases where you have a number of independent things you
> need to do while holding a read lock and neither holding the read lock
> through the whole list nor releasing it and reacquiring it on each
> item makes sense.
Agree. Something along the lines of:
g_rw_mutex.lock();
while (...)
{
do_something_useful();
g_rw_mutex.i_am_quiescent();
}
g_rw_mutex.unlock();
Perhaps, i_am_quiescent() must return a flag indicating whether lock
was released and reacquired or not, reader thread can do some
recaching if the mutex was reacquired.
As for the technique, I think it's very nice IF it's applicable. It
solves the problem with a little added complexity. However it requires
cooperation from the rest of the code and from a programmer.
If you can count on periodic activity from all user threads, life
indeed becomes much easier in a multi-threaded environment (wrt lock
management, memory management, object life-time management, etc). Then
you can amortize basically everything and move all the overheads to
that periodic function.
--
Dmitriy V'jukov
== 4 of 7 ==
Date: Sun, Jan 31 2010 3:45 am
From: "Chris M. Thomasson"
"David Schwartz" <davids@webmaster.com> wrote in message
news:801a06d8-80e6-4325-8118-2d306c880cf7@f17g2000prh.googlegroups.com...
On Jan 31, 2:53 am, "Chris M. Thomasson" <n...@spam.invalid> wrote:
> > Any thoughts on this particular technique?
> I think probably the best way to do it is a function that's a no-op if
> there's no pending writer and releases the read lock, waits until the
> writer is finished, and the re-acquires the read lock if there is one.
Agreed. I believe I can add such a function to my read/write mutex
implementation:
http://software.intel.com/en-us/forums/showthread.php?t=65822
which could look something like this:
_____________________________________________________________________
void rdsync() throw()
{
LONG count = *((LONG volatile*)&m_count);
assert(count < LONG_MAX);
if (count < 0)
{
// a writer is pending which means that we need to
// release and reacquire our read access.
rdunlock();
rdlock();
// since this is a 100% fair rw_mutex, we are now guaranteed
// that the writer has fully completed all of it's actions.
}
}
_____________________________________________________________________
That should work fine and I think I will probably model it in Relacy 2.2.
> It's good for cases where you have a number of independent things you
> need to do while holding a read lock and neither holding the read lock
> through the whole list nor releasing it and reacquiring it on each
> item makes sense.
Agreed. I do think it should be able to improve performance in usage
patterns like the one you described...
== 5 of 7 ==
Date: Sun, Jan 31 2010 4:01 am
From: "Chris M. Thomasson"
"Dmitriy Vyukov" <dvyukov@gmail.com> wrote in message
news:f8fb9dbe-ad42-4efa-b263-fcffab0961f4@z26g2000yqm.googlegroups.com...
On Jan 31, 1:58 pm, David Schwartz <dav...@webmaster.com> wrote:
> > On Jan 31, 2:53 am, "Chris M. Thomasson" <n...@spam.invalid> wrote:
> >
> > > Any thoughts on this particular technique?
> >
> > I think probably the best way to do it is a function that's a no-op if
> > there's no pending writer and releases the read lock, waits until the
> > writer is finished, and the re-acquires the read lock if there is one.
> > It's good for cases where you have a number of independent things you
> > need to do while holding a read lock and neither holding the read lock
> > through the whole list nor releasing it and reacquiring it on each
> > item makes sense.
> Agree. Something along the lines of:
> g_rw_mutex.lock();
> while (...)
> {
> do_something_useful();
> g_rw_mutex.i_am_quiescent();
> }
> g_rw_mutex.unlock();
> Perhaps, i_am_quiescent() must return a flag indicating whether lock
> was released and reacquired or not, reader thread can do some
> recaching if the mutex was reacquired.
YES! That return value would be providing "essential" information to the
readers. Here, let me modify the function I am thinking about adding to my
rw_mutex impl:
_____________________________________________________________________
bool rdsync() throw()
{
LONG count = *((LONG volatile*)&m_count);
assert(count < LONG_MAX);
if (count < 0)
{
// a writer is pending which means that we need to
// release and reacquire our read access.
rdunlock();
rdlock();
// since this is a 100% fair rw_mutex, we are now guaranteed
// that the writer has fully completed all of it's actions.
return true;
}
return false;
}
_____________________________________________________________________
Now one can do:
_____________________________________________________________________
g_rw_mutex.rdlock();
for (;;)
{
do_something_useful();
if (g_rw_mutex.rdsync())
{
// refresh cached data...
}
}
g_rw_mutex.rdunlock();
_____________________________________________________________________
;^)
> As for the technique, I think it's very nice IF it's applicable. It
> solves the problem with a little added complexity. However it requires
> cooperation from the rest of the code and from a programmer.
Yes, this is absolutely correct. I am thinking that it should work out
fairly well in areas where it is applicable. Therefore, in those specific
cases, it actually might be worth the extra complexity and programming
effort...
> If you can count on periodic activity from all user threads, life
> indeed becomes much easier in a multi-threaded environment (wrt lock
> management, memory management, object life-time management, etc). Then
> you can amortize basically everything and move all the overheads to
> that periodic function.
Amen Brother!!!!
:^D
== 6 of 7 ==
Date: Sun, Jan 31 2010 4:09 am
From: "Chris M. Thomasson"
"Chris M. Thomasson" <no@spam.invalid> wrote in message
news:nie9n.31934$BV.29228@newsfe07.iad...
> "Dmitriy Vyukov" <dvyukov@gmail.com> wrote in message
> news:f8fb9dbe-ad42-4efa-b263-fcffab0961f4@z26g2000yqm.googlegroups.com...
[...]
>> Perhaps, i_am_quiescent() must return a flag indicating whether lock
>> was released and reacquired or not, reader thread can do some
>> recaching if the mutex was reacquired.
>
> YES! That return value would be providing "essential" information to the
> readers. Here, let me modify the function I am thinking about adding to my
> rw_mutex impl:
> _____________________________________________________________________
> bool rdsync() throw()
> {
> LONG count = *((LONG volatile*)&m_count);
>
> assert(count < LONG_MAX);
>
> if (count < 0)
> {
> // a writer is pending which means that we need to
> // release and reacquire our read access.
>
> rdunlock();
>
> rdlock();
>
> // since this is a 100% fair rw_mutex, we are now guaranteed
> // that the writer has fully completed all of it's actions.
>
> return true;
> }
>
> return false;
> }
> _____________________________________________________________________
FWIW, the function above is very similar to the `proxy<...>::sync()'
function in my proxy collector:
http://cpt.pastebin.com/f71480694
_________________________________________________________________
collector& sync(collector& c)
{
// check if the `c' is in the middle of a quiescence process.
if (c.m_count.load(std::memory_order_relaxed) & 0x10U)
{
// drop `c' and get the next collector.
release(c);
return acquire();
}
return c;
}
_________________________________________________________________
This allows for basically the exact same pattern to be applied to proxy
garbage collectors:
_________________________________________________________________
void readers()
{
proxy_type::collector* c = &g_proxy.acquire();
for (;;)
{
do_something_useful();
c = &g_proxy.sync(*c);
}
g_proxy.release(*c);
}
_________________________________________________________________
The model of the algorithm in Relacy 2.2 shows the pattern in action in the
form of reader threads iterating over all the nodes contained within a
lock-free stack.
== 7 of 7 ==
Date: Sun, Jan 31 2010 5:31 am
From: David Schwartz
On Jan 31, 3:39 am, Dmitriy Vyukov <dvyu...@gmail.com> wrote:
> Perhaps, i_am_quiescent() must return a flag indicating whether lock
> was released and reacquired or not, reader thread can do some
> recaching if the mutex was reacquired.
I agree. It should be effectively free to add and might help the
caller decide whether it needs to do some extra processing.
I don't think the cases where this is useful are that many, but it
does have genuine use cases. Most reader/writer lock implementations
could add it with very little difficulty. Typical read/write locks
refuse new readers when a writer is pending, so they should be able to
tell if they would refuse a read lock or not without much trouble.
DS
==============================================================================
TOPIC: strong atomic reference counting...
http://groups.google.com/group/comp.programming.threads/t/1b35d9cff58efb83?hl=en
==============================================================================
== 1 of 1 ==
Date: Sun, Jan 31 2010 5:56 am
From: "Chris M. Thomasson"
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:
____________________________________________________________________
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.
==============================================================================
TOPIC: ftok
http://groups.google.com/group/comp.programming.threads/t/4080bc1e3e027ae0?hl=en
==============================================================================
== 1 of 3 ==
Date: Sun, Jan 31 2010 6:54 am
From: karthikbalaguru
Hi,
I understand that ftok shall return
a key that can be used in IPC.
But, what is the expansion for
ftok ?
Thx in advans,
Karthik Balaguru
== 2 of 3 ==
Date: Sun, Jan 31 2010 7:39 am
From: karthikbalaguru
On Jan 31, 7:54 pm, karthikbalaguru <karthikbalagur...@gmail.com>
wrote:
> Hi,
> I understand that ftok shall return
> a key that can be used in IPC.
> But, what is the expansion for
> ftok ?
>
To be clear -
What does each letter 'f' , 't' , 'o' ,'k'
refer to ? Any ideas ?
Thx in advans,
Karthik Balaguru
== 3 of 3 ==
Date: Sun, Jan 31 2010 9:31 am
From: karthikbalaguru
On Jan 31, 9:00 pm, Nicolas George <nicolas$geo...@salle-s.org> wrote:
> karthikbalaguru wrote in message
>
> <5c52fff4-2d0d-4757-99bf-8e27c9530...@b36g2000pri.googlegroups.com>:
>
> > What does each letter 'f' , 't' , 'o' ,'k'
> > refer to ? Any ideas ?
>
> File TO Key?
Hey Nicolas,
That sounds reasonable.
Is it File TOken ?
Karthik Balaguru
==============================================================================
TOPIC: Indicating truncation to the calling process
http://groups.google.com/group/comp.programming.threads/t/6c6effa342f41ce6?hl=en
==============================================================================
== 1 of 3 ==
Date: Sun, Jan 31 2010 9:28 am
From: karthikbalaguru
Hi,
I understand that the msgrcv()
function would read a message from
the queue associated with the
message queue id and place it
in the buffer(userdefined).
Further, it has an argument of type
size_t that indicates the maximum
size(in bytes) of the message that can
be received or truncated incase of larger
message.
Incase of large messages, the
truncated part of the message shall
be lost . But is there a mechanism
to indicate the calling process about
truncation ? Or is there an alternate
API that has an feature of indicating
the calling thread of the truncation ?
Any ideas ?
Thx in advans,
Karthik Balaguru
== 2 of 3 ==
Date: Sun, Jan 31 2010 5:36 pm
From: David Schwartz
On Jan 31, 9:28 am, karthikbalaguru <karthikbalagur...@gmail.com>
wrote:
> Hi,
>
> I understand that the msgrcv()
> function would read a message from
> the queue associated with the
> message queue id and place it
> in the buffer(userdefined).
>
> Further, it has an argument of type
> size_t that indicates the maximum
> size(in bytes) of the message that can
> be received or truncated incase of larger
> message.
>
> Incase of large messages, the
> truncated part of the message shall
> be lost . But is there a mechanism
> to indicate the calling process about
> truncation ? Or is there an alternate
> API that has an feature of indicating
> the calling thread of the truncation ?
> Any ideas ?
Just pass one extra byte of buffer space.
Suppose you were going to pass, say, 1,024 bytes to 'msgrcv'. Instead,
pass 1,025. If you get 1,025 bytes, then your 1,024 byte received
would have truncated.
DS
== 3 of 3 ==
Date: Sun, Jan 31 2010 7:15 pm
From: karthikbalaguru
On Feb 1, 6:36 am, David Schwartz <dav...@webmaster.com> wrote:
> On Jan 31, 9:28 am, karthikbalaguru <karthikbalagur...@gmail.com>
> wrote:
>
>
>
>
>
> > Hi,
>
> > I understand that the msgrcv()
> > function would read a message from
> > the queue associated with the
> > message queue id and place it
> > in the buffer(userdefined).
>
> > Further, it has an argument of type
> > size_t that indicates the maximum
> > size(in bytes) of the message that can
> > be received or truncated incase of larger
> > message.
>
> > Incase of large messages, the
> > truncated part of the message shall
> > be lost . But is there a mechanism
> > to indicate the calling process about
> > truncation ? Or is there an alternate
> > API that has an feature of indicating
> > the calling thread of the truncation ?
> > Any ideas ?
>
> Just pass one extra byte of buffer space.
>
> Suppose you were going to pass, say, 1,024 bytes to 'msgrcv'. Instead,
> pass 1,025. If you get 1,025 bytes, then your 1,024 byte received
> would have truncated.
>
Hey David, Thx for your reply.
Okay, if we pass even a single
extra byte, it gets truncated.
The name 'MSG_NOERROR'
to truncate the message text if longer
than msgsz bytes is misleading :-(
Considering MSG_NOERROR
is specified, how will the calling
process know that the truncation
has happened as only few of the
messages are larger in my scenario ?
Thx in advans,
Karthik Balaguru
==============================================================================
TOPIC: FREE Animations you can e-mail
http://groups.google.com/group/comp.programming.threads/t/d8c814d2fcc9957d?hl=en
==============================================================================
== 1 of 1 ==
Date: Sun, Jan 31 2010 11:46 am
From: fitz
FREE Animations you can e-mail
(click link):
http://www.amperefitz.com/contact.html
THOUSANDS of FREE Animations
Enjoy,
Fitz
==============================================================================
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