http://groups.google.com/group/comp.programming.threads?hl=en
comp.programming.threads@googlegroups.com
Today's topics:
* removing store/load in Peterson's algorithm? - 3 messages, 2 authors
http://groups.google.com/group/comp.programming.threads/t/6a7e7620b0cd85eb?hl=en
* Nike NBA swingman Jersey www.jersey-2009.com - 1 messages, 1 author
http://groups.google.com/group/comp.programming.threads/t/5b8b418216a99bca?hl=en
* jerseys,official MLB jerseys,(www.jersey-2009.com) - 1 messages, 1 author
http://groups.google.com/group/comp.programming.threads/t/f2220f1b85837a72?hl=en
* patients / licensing issues - 1 messages, 1 author
http://groups.google.com/group/comp.programming.threads/t/930fd13376fd2ba9?hl=en
* a lock-based proxy collector? - 3 messages, 1 author
http://groups.google.com/group/comp.programming.threads/t/3b70d0ead8e62e15?hl=en
==============================================================================
TOPIC: removing store/load in Peterson's algorithm?
http://groups.google.com/group/comp.programming.threads/t/6a7e7620b0cd85eb?hl=en
==============================================================================
== 1 of 3 ==
Date: Wed, Dec 23 2009 11:32 am
From: "James"
"Dmitriy Vyukov" <dvyukov@gmail.com> wrote in message
news:ad5c3755-23c5-42b8-b7b3-3ecfb3f29b53@c3g2000yqd.googlegroups.com...
On Dec 21, 10:23 pm, "James" <n...@spam.invalid> wrote:
[...]
> > For the MFENCE version I am performing a 32-bit store to location a, an
> > MFENCE then a 32-bit load from location b.
> >
> > For the collocation version I am performing a 16-bit store to location a
> > then a 32-bit load from location a.
> >
> > That should be fair?
> Yes.
> > > I think that if collocation is observably faster than MFENCE then that
> > > means that it just does not work.
> >
> > The MFENCE version of the test is much slower than the collocation
> > version.
> > So, does the collocation trick not work on an x86?
> The first question I would answer is: does Peterson algorithm with
> collocation actually provide mutual exclusion on x86 (is it guaranteed
> or just seems to work on some processors)? If the answer is No then
> performance of collocation is irrelevant for me.
I simply don't know if it works on x86. I don't know who to ask in order to
verify this. I could create a test which does not prove anything even if it
passes a hundred trillion times. Can you think of a way to verify that
collocation works on x86?
== 2 of 3 ==
Date: Thurs, Dec 24 2009 2:50 am
From: Dmitriy Vyukov
On Dec 23, 10:29 pm, "James" <n...@spam.invalid> wrote:
> > "Dmitriy Vyukov" <dvyu...@gmail.com> wrote in message
> >news:756561b8-810a-40ef-99e1-ff7138e13661@g7g2000yqa.googlegroups.com...
>
> On Dec 21, 8:32 pm, "James" <n...@spam.invalid> wrote:
> [...]
>
>
>
> > > > > STORE16(&state1, 1);
> > > > > LOAD32(&state1);
> > > > > LOAD32(&state2);
>
> > > > > Can the load from state2 rise above the 16-bit store? It seems like
> > > > > it
> > > > > should be able to. Where am I going wrong?
>
> > > > > [...]
> > > > Yes, it can. But there is no such code in Peterson algorithm, there is
> > > > only 1 load.
>
> > > I was referring to a load that occurred within the critical section. Can
> > > loads from the critical section rise above the 16-bit store? Can that
> > > cause
> > > any problems?
> > I can only cite myself:
> > I think one need only #LoadLoad | #LoadStore:
> > STORE16(&state, 1);
> > LOAD32(&state);
> > if (...) ...
> > membar #LoadLoad | #LoadStore; //no-op for SPARC TSO and x86
> > // nothing from here can hoist above mutex acquisition
>
> But the:
>
> STORE16(&state, 1);
> LOAD32(&state);
>
> will not prevent a store from within the critical section from rising above
> it. This would mess things up right?
It depends on hardware.
On IA-32, Intel64, SPARC TSO it won't mess.
On IA-64, SPARC RMO it can.
--
Dmitriy V'jukov
== 3 of 3 ==
Date: Thurs, Dec 24 2009 2:52 am
From: Dmitriy Vyukov
On Dec 23, 10:32 pm, "James" <n...@spam.invalid> wrote:
> > > For the MFENCE version I am performing a 32-bit store to location a, an
> > > MFENCE then a 32-bit load from location b.
>
> > > For the collocation version I am performing a 16-bit store to location a
> > > then a 32-bit load from location a.
>
> > > That should be fair?
> > Yes.
> > > > I think that if collocation is observably faster than MFENCE then that
> > > > means that it just does not work.
>
> > > The MFENCE version of the test is much slower than the collocation
> > > version.
> > > So, does the collocation trick not work on an x86?
> > The first question I would answer is: does Peterson algorithm with
> > collocation actually provide mutual exclusion on x86 (is it guaranteed
> > or just seems to work on some processors)? If the answer is No then
> > performance of collocation is irrelevant for me.
>
> I simply don't know if it works on x86. I don't know who to ask in order to
> verify this. I could create a test which does not prove anything even if it
> passes a hundred trillion times. Can you think of a way to verify that
> collocation works on x86?
Well, what about consulting those fine x86 manuals?
--
Dmitriy V'jukov
==============================================================================
TOPIC: Nike NBA swingman Jersey www.jersey-2009.com
http://groups.google.com/group/comp.programming.threads/t/5b8b418216a99bca?hl=en
==============================================================================
== 1 of 1 ==
Date: Thurs, Dec 24 2009 6:02 am
From: jersey-2009
For more information, please contact Sophie,
our MSN: niketrade08@hotmail.com
Minimum order is one,factory price also! Paypal payment free
shipping,ship time will take 4-7 working days.
cheap wholesale Reebok super bowl NFL Jersey
wholesale NFL pro bowl jersey,Browl NFL Jersey www.jersey-2009.com
NBA Jersey for woman www.jersey-2009.com
classic NBA Jersey NFL Jersey korea supplier
mitchell and ness NBA Jersey www.jersey-2009.com
2009 game Jersey NBA star www.jersey-2009.com
alternate Jersey NBA www.jersey-2009.com
best selling NBA Jersey www.jersey-2009.com
NBA Jersey card
authenic NBA Jersey www.jersey-2009.com
discount NBA Jersey www.jersey-2009.com
classic customized Jersey NBA www.jersey-2009.com
Nike NBA swingman Jersey www.jersey-2009.com
custom NBA basketball Jersey www.jersey-2009.com
retired NBA Jersey
adidas Jersey NBA swingman www.jersey-2009.com
infant NBA Jersey www.jersey-2009.com
adidas authentic Jersey NBA www.jersey-2009.com
NBA new Jersey net www.jersey-2009.com
NBA practice Jersey
NBA rewind Jersey www.jersey-2009.com
big kid NBA Jersey www.jersey-2009.com
youth NBA basketball Jersey www.jersey-2009.com
womens NBA Jersey dress www.jersey-2009.com
spalding NBA player Jersey basketball Jersey NBA
NBA Jersey size www.jersey-2009.com
NBA soul Jersey www.jersey-2009.com
black Jersey NBA www.jersey-2009.com
buy NBA Jersey www.jersey-2009.com
NBA pro cut Jersey www.jersey-2009.com
NBA and NFL Jersey www.jersey-2009.com
adidas alternate Jersey man www.jersey-2009.com
==============================================================================
TOPIC: jerseys,official MLB jerseys,(www.jersey-2009.com)
http://groups.google.com/group/comp.programming.threads/t/f2220f1b85837a72?hl=en
==============================================================================
== 1 of 1 ==
Date: Thurs, Dec 24 2009 6:02 am
From: jersey-2009
AAA quality clothes cheap wholesale from china. (www.jersey-2009.com)
NFL jersey wholesale (www.jersey-2009.com)
NFL NBA MLB NHL soccer soccer jerseys (www.jersey-2009.com)
nike brand,MLB jerseys china supplier (www.jersey-2009.com)
MLB jerseys china wholesaler.(www.jersey-2009.com)
wholesale MLB jerseys.(www.jersey-2009.com)
NFL shop,,NFL NBA MLB NHL jerser wholesale,NFL NBA MLB NHL
(www.jersey-2009.com)
jersey supplier(www.jersey-2009.com)
NFL NBA MLB NHL jersey korea supplier (www.jersey-2009.com)
NFL NBA jersey stock (www.jersey-2009.com)
alibaba,wholesale NFL NBA MLB NHL jerseys.(www.jersey-2009.com)
soccer jersey china supplier (www.jersey-2009.com)
soccer jerseys china wholesale.(www.jersey-2009.com)
wholesale soccer jersey,supply soccer jerseys (www.jersey-2009.com)
NFL NBA MLB NHL copy jersey (www.jersey-2009.com)
copy www.jersey-2009.com paypal paymentjerseys from china
(www.jersey-2009.com)
NFL jerseys from china.(www.jersey-2009.com)
NBA www.jersey-2009.com paypal payment shop (www.jersey-2009.com)
NFL jersey wholesale womens NBA jersey (www.jersey-2009.com)
NBA jersey sale (www.jersey-2009.com)
cheap authentic NBA jersey (www.jersey-2009.com)
07 jersey NBA star (www.jersey-2009.com)
NBA jersey numbers (www.jersey-2009.com)
NBA vintage jersey NBA throw back jersey (www.jersey-2009.com)
NBA jersey dress for woman (www.jersey-2009.com)
reebok NBA jersey (www.jersey-2009.com)
NBA jersey for toddler (www.jersey-2009.com)
old NBA jersey (www.jersey-2009.com)
youth NBA swingman jersey (www.jersey-2009.com)
NBA authentic basketball jersey (www.jersey-2009.com)
basketball jersey NBA new style (www.jersey-2009.com)
NBA all star game jersey (www.jersey-2009.com)
NBA new jersey (www.jersey-2009.com)
adidas NBA jersey (www.jersey-2009.com)
official NBA jersey (www.jersey-2009.com)
classics hardwood jersey NBA (www.jersey-2009.com)
old school NBA jersey (www.jersey-2009.com)
NBA jersey for woman (www.jersey-2009.com)
classic NBA jersey (www.jersey-2009.com)
NFL jersey korea supplier(www.jersey-2009.com)
mitchell and ness NBA jersey (www.jersey-2009.com)
2009 game jersey NBA star (www.jersey-2009.com)
alternate jersey NBA (www.jersey-2009.com)
best selling NBA jersey (www.jersey-2009.com)
NBA jersey card (www.jersey-2009.com)
authenic NBA jersey (www.jersey-2009.com)
discount NBA jersey (www.jersey-2009.com)
Wholesale MLB jerseys,paypal,cheap MLB jersey(www.jersey-2009.com)
wholesale football jerseys,(www.jersey-2009.com)
reebok MLB player jerseys,(www.jersey-2009.com)
authentic MLB jerseys,discount MLB
jerseys,mitchell ness jerseys,throwback (www.jersey-2009.com)
Nice jerseys,replica MLB jerseys,(www.jersey-2009.com)
women MLB jerseys,youth MLB (www.jersey-2009.com)
pro Bowl jerseys,super bowl jerseys,(www.jersey-2009.com)
nhljerseys,hockey jerseys,nba jerseys,(www.jersey-2009.com)
all star jersey,mlb baseball jerseys (www.jersey-2009.com)
(www.jersey-2009.com) paypal payment
==============================================================================
TOPIC: patients / licensing issues
http://groups.google.com/group/comp.programming.threads/t/930fd13376fd2ba9?hl=en
==============================================================================
== 1 of 1 ==
Date: Thurs, Dec 24 2009 9:08 am
From: Toby Douglass
I'm trying to find out if there are patient/licensing issues involved in
using Treiber's stack or Michael and Scott's queue.
I understand the Boost library is using M&S's queue, so I'm guessing
it's generally available.
I can't find any info on T's stack.
I'm also interesting in finding out about Harris' singly linked-list; I
found the patent for that and I'll contact him directly, but while I'm
here...anyone know?
==============================================================================
TOPIC: a lock-based proxy collector?
http://groups.google.com/group/comp.programming.threads/t/3b70d0ead8e62e15?hl=en
==============================================================================
== 1 of 3 ==
Date: Thurs, Dec 24 2009 5:50 pm
From: "Chris M. Thomasson"
"Dmitriy Vyukov" <dvyukov@gmail.com> wrote in message
news:c085d068-f533-4ab7-9c1c-4d8fc3aec9eb@j14g2000yqm.googlegroups.com...
On Dec 20, 9:54 pm, "Chris M. Thomasson" <n...@spam.invalid> wrote:
> > "Dmitriy Vyukov" <dvyu...@gmail.com> wrote in message
> >
> > news:0ed72eb1-1132-4a8f-a001-67b9087d74e1@d20g2000yqh.googlegroups.com...
> > On Dec 20, 8:39 pm, "Chris M. Thomasson" <n...@spam.invalid> wrote:
> > [...]
> >
> > > > I am in the process of re-running the test with RL_FORCE_SEQ_CST
> > > > defined.
> >
> > It passes, but I feel that there is still a problem.
> >
> > > > Anyway, I believe I have found the error. Imagine there are 4
> > > > collectors
> > > > [C1..C4]. The tail has collected from [C1..C2], now the head wraps
> > > > to
> > > > C2.
> > > > The tail detects this and frees nodes collected from [C1..C2]
> > > > without
> > > > collecting from [C3..C4]. This can cause a race-condition in which
> > > > the
> > > > freed
> > > > nodes are being accessed from [C3..C4].
> >
> > > > Does that make sense to you?
> > > I can't say right now.
> > > But I know that wrapping represents a problem for such algorithms. One
> > > may have old writer step on new writer, old writer step on new reader,
> > > old reader step on new writer. All these cases must be correctly
> > > handled. Monotonic head/tail index may solve some of these problems
> > > (because it effectively becomes IBM ABA counter).
> >
> > Humm... You could not allow the head to acquire a collector that the
> > tail
> > was collecting from. I am not sure how to handle this. Need to think
> > some
> > more.
> Just a thought. Maybe introduce explicit state for each collector:
> busy, collection pending, collecting, free. Then readers will be able
> to detect collisions.
I "think" I have made an observation that "should" detect grace periods
sufficient to safely destroy nodes within this scheme. Take the case with an
array of 3 collector objects. And the index points to collector 1. A mutator
advances the index to collector 2; takes write lock on previous collector 1;
defers object A in current defer list; releases write lock on collector 1.
Now, assume current readers in collector 2 have raced in have a reference to
object A, which is entirely possible. Then the mutator performs the same
action and defers node B; the current collector is now 3. AFAICT, it is
completely impossible for any readers in collector 3 to have visibility to
node A, therefore node A is quiescent because write locks were acquired and
released for collector 1 and 2.
Okay, this tells me that two mutations have to occur in order for a node in
the first mutation to become quiescent. I am To handle collection index
wrapping, the per collector defer list would be a FIFO. Popping an item
would remove the oldest node which would be the quiescent one.
A simple way to do this would be to use a single collector thread that would
have a FIFO defer list. As soon as it detects that it has made two
mutations, it can pop a node from the FIFO and destroy it. I really need to
draw all of this on paper; well, it seems to work out here:
http://relacy.pastebin.com/f571d4312
(passes 10,000,000 iterations without `RL_FORCE_SEQ_CST' defined)
Now, if this observation turns out to be true, then I believe I can apply it
to any "array-based" proxy collector scheme. Also, I don't even think I need
acquire/release semantics on the current collector index variable because
the collector objects provide proper synchronization in and of themselves.
The key elements are objects are deferred in FIFO order. After two mutations
occur, one can pop a node off the FIFO and destroy it because it's
quiescent. I believe there are many improvements I can make to this
lock-based collector as well as non-blocking collectors based on the same
basic logic. I will do further testing with Relacy...
What do you think about this Dmitriy?
BTW, Merry Christmas Everybody!
:^D
== 2 of 3 ==
Date: Thurs, Dec 24 2009 5:56 pm
From: "Chris M. Thomasson"
"Chris M. Thomasson" <no@spam.invalid> wrote in message
news:URUYm.2918$8e4.2821@newsfe03.iad...
[...]
> Also, I don't even think I need
> acquire/release semantics on the current collector index variable because
> the collector objects provide proper synchronization in and of themselves.
On second thought, I do need acquire/release because I want the deferred
node to be queued into the FIFO BEFORE to be committed _before_ I bump the
index.
[...]
== 3 of 3 ==
Date: Thurs, Dec 24 2009 9:20 pm
From: "Chris M. Thomasson"
"Chris M. Thomasson" <no@spam.invalid> wrote in message
news:URUYm.2918$8e4.2821@newsfe03.iad...
> "Dmitriy Vyukov" <dvyukov@gmail.com> wrote in message
> news:c085d068-f533-4ab7-9c1c-4d8fc3aec9eb@j14g2000yqm.googlegroups.com...
[...]
> The key elements are objects are deferred in FIFO order. After two
> mutations
> occur, one can pop a node off the FIFO and destroy it because it's
> quiescent. I believe there are many improvements I can make to this
> lock-based collector as well as non-blocking collectors based on the same
> basic logic. I will do further testing with Relacy...
Test passes 50,000,000 iterations. I cannot seem to find any problems right
now.
> What do you think about this Dmitriy?
> BTW, Merry Christmas Everybody!
>
> :^D
==============================================================================
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