http://groups.google.com/group/comp.programming.threads?hl=en
comp.programming.threads@googlegroups.com
Today's topics:
* Lockfree_SPMC and the correctness - 1 messages, 1 author
http://groups.google.com/group/comp.programming.threads/t/ef2ecb1f19720ec0?hl=en
* biocomputer of Japan.tv (online.a_z) - 1 messages, 1 author
http://groups.google.com/group/comp.programming.threads/t/cf37fc560762e066?hl=en
* Multi-cores and contention,,, - 5 messages, 2 authors
http://groups.google.com/group/comp.programming.threads/t/b74390b785ea0e26?hl=en
* weird thread behavior on itanium/hp-ux with pthread - 2 messages, 1 author
http://groups.google.com/group/comp.programming.threads/t/b2b5d744b99b760c?hl=en
* C++Framework - C++ multi-platform memory-model solution, with Java
orientation - 1 messages, 1 author
http://groups.google.com/group/comp.programming.threads/t/344086e52caa9171?hl=en
==============================================================================
TOPIC: Lockfree_SPMC and the correctness
http://groups.google.com/group/comp.programming.threads/t/ef2ecb1f19720ec0?hl=en
==============================================================================
== 1 of 1 ==
Date: Tues, Jul 28 2009 11:55 pm
From: "Chris M. Thomasson"
"Amine" <aminer@colba.net> wrote in message
news:ec33d7b3-3680-437e-b88e-0ac3a524066a@y19g2000yqy.googlegroups.com...
On Jul 14, 11:52 pm, "Chris M. Thomasson" <n...@spam.invalid> wrote:
> > "Amine" <ami...@colba.net> wrote in message
> >
> > news:55d911c7-de45-4131-a1b3-527edbf34b29@l31g2000vbp.googlegroups.com...
> > [...]
> >
> > > I have looked at the assembler code and it does not reorder
> > > the two operations.
> >
> > > Hence, my lockfree_SPMC and lockfree_priority_SPMC
> > > are safe and correct.
> >
> > Are you sure that any Pascal compiler will never reorder the operations?
> >
> > [...]
> No Chris, not for any Pascal compiler.
> I have just verified for Delphi and Freepascal.
Of course you can totally eliminate this "possibility" by coding your
`lockfree_SPMC' algorithm in pure assembly language; assemble and link to
the object file.
==============================================================================
TOPIC: biocomputer of Japan.tv (online.a_z)
http://groups.google.com/group/comp.programming.threads/t/cf37fc560762e066?hl=en
==============================================================================
== 1 of 1 ==
Date: Wed, Jul 29 2009 9:52 am
From: doctor-lsd-tv Google
http://www.nanometer.ru/users/microsoft-lsd-tv.html
doctor-lsd-tv@yandex.com
tel.8_9195265461
==============================================================================
TOPIC: Multi-cores and contention,,,
http://groups.google.com/group/comp.programming.threads/t/b74390b785ea0e26?hl=en
==============================================================================
== 1 of 5 ==
Date: Wed, Jul 29 2009 11:35 am
From: Amine
Hello all,
I was thinking about my lock-free Threadpool and lock-free_SPMC
i am using a queue for every thread worker ( and in the producer side
you can push in parallel also) and i have come to the conclusion that
this will scale very well.in the software side...
But i was thinking more about *scalability* and i have come to the
conclusion that there is still a problem, please follow with me:
As Amadahl law state, the Speed = 1 / (1 -P) + P /N (N: number of
cores)
now let's take as an example we are working with a scalable lock-free
Hashtable
now, if the transactions(find,insert..) are coming to the lock-free
hashtable
and the jobs(transactions) are processed in an M/M/m manner with
multiple
threads and cores servicing the jobs, that's very good...
Now suppose that the application like a lock-free Hashtable is
working
frequently with data and we are accessing big data directly in
memory
*AND* the data is randomly accessed *AND* there is contention between
processors over the memory bus in and M/M/1 manner , so, there will
be
an appreciable serial part 1-P in the Amadahl equation, hence:
what would will you expect from the scalable lock-free Hashtable ?
what would be then the performance ? i think this will be very bad.
So, now imagine that we elevate the problem by using an M/M/m in
the bus memory side , this will lower contention. But imagine that
we are using some big in memory data and accessing it *randomly*
with a lock-free Hash-table , what will be the performance then ?
not so good i think...
Also i have another question:
Read this:
http://www.azulsystems.com/events/javaone_2007/2007_LockFreeHash.pdf
How the performance of this lock-free Hashtable can scale well in
performance
on an Azul system with more than 700 cores, if we are using some very
big in
memory data and accessing it *RANDOMLY* ? and what memory bus
architechture
are they using ?...
What do you think about this problem ?
Regards,
Amine Moulay Ramdane.
== 2 of 5 ==
Date: Wed, Jul 29 2009 12:21 pm
From: Amine
I wrote:
> So, now imagine that we elevate the problem by using an M/M/m in
> the bus memory side , this will lower contention. But imagine that
> we are using some big in memory data and accessing it *randomly*
> with a lock-free Hash-table , what will be the performance then ?
> not so good i think...
I mean what is the benefit of a very FAST Ferari car if the roads are
not so good
and they lower a lot it's speed ?
What is the benefit of a very fast lock-free hash-table if the in
memory data
it access is big and it's *randomly* accessed: and this will lower the
speed
*AND*
also there is a contention on the bus in an M/M/1 manner and this
will also
lower the speed ?
Regards,
Amine. Moulay Ramdane.
On Jul 29, 2:35 pm, Amine <ami...@colba.net> wrote:
> Hello all,
>
> I was thinking about my lock-free Threadpool and lock-free_SPMC
>
> http://www.colba.net/~aminer/
>
> i am using a queue for every thread worker ( and in the producer side
> you can push in parallel also) and i have come to the conclusion that
> this will scale very well.in the software side...
>
> But i was thinking more about *scalability* and i have come to the
> conclusion that there is still a problem, please follow with me:
>
> As Amadahl law state, the Speed = 1 / (1 -P) + P /N (N: number of
> cores)
> now let's take as an example we are working with a scalable lock-free
> Hashtable
> now, if the transactions(find,insert..) are coming to the lock-free
> hashtable
> and the jobs(transactions) are processed in an M/M/m manner with
> multiple
> threads and cores servicing the jobs, that's very good...
>
> Now suppose that the application like a lock-free Hashtable is
> working
> frequently with data and we are accessing big data directly in
> memory
> *AND* the data is randomly accessed *AND* there is contention between
> processors over the memory bus in and M/M/1 manner , so, there will
> be
> an appreciable serial part 1-P in the Amadahl equation, hence:
>
> what would will you expect from the scalable lock-free Hashtable ?
>
> what would be then the performance ? i think this will be very bad.
>
> So, now imagine that we elevate the problem by using an M/M/m in
> the bus memory side , this will lower contention. But imagine that
> we are using some big in memory data and accessing it *randomly*
> with a lock-free Hash-table , what will be the performance then ?
> not so good i think...
>
> Also i have another question:
>
> Read this:
>
> http://www.azulsystems.com/events/javaone_2007/2007_LockFreeHash.pdf
>
> How the performance of this lock-free Hashtable can scale well in
> performance
> on an Azul system with more than 700 cores, if we are using some very
> big in
> memory data and accessing it *RANDOMLY* ? and what memory bus
> architechture
> are they using ?...
>
> What do you think about this problem ?
>
> Regards,
> Amine Moulay Ramdane.
== 3 of 5 ==
Date: Wed, Jul 29 2009 12:32 pm
From: Amine
On Jul 29, 3:21 pm, Amine <ami...@colba.net> wrote:
> I wrote:
> > So, now imagine that we elevate the problem by using an M/M/m in
> > the bus memory side , this will lower contention. But imagine that
> > we are using some big in memory data and accessing it *randomly*
> > with a lock-free Hash-table , what will be the performance then ?
> > not so good i think...
>
> I mean what is the benefit of a very FAST Ferari car if the roads are
> not so good
> and they lower a lot it's speed ?
typo:
I mean what is the benefit of a very FAST Ferari car if the roads are
not so good and they lower a lot its speed ?
Regards,
Amine Moulay Ramdane.
>
> What is the benefit of a very fast lock-free hash-table if the in
> memory data
> it access is big and it's *randomly* accessed: and this will lower the
> speed
> *AND*
> also there is a contention on the bus in an M/M/1 manner and this
> will also
> lower the speed ?
>
> Regards,
> Amine. Moulay Ramdane.
>
> On Jul 29, 2:35 pm, Amine <ami...@colba.net> wrote:
>
>
>
> > Hello all,
>
> > I was thinking about my lock-free Threadpool and lock-free_SPMC
>
> >http://www.colba.net/~aminer/
>
> > i am using a queue for every thread worker ( and in the producer side
> > you can push in parallel also) and i have come to the conclusion that
> > this will scale very well.in the software side...
>
> > But i was thinking more about *scalability* and i have come to the
> > conclusion that there is still a problem, please follow with me:
>
> > As Amadahl law state, the Speed = 1 / (1 -P) + P /N (N: number of
> > cores)
> > now let's take as an example we are working with a scalable lock-free
> > Hashtable
> > now, if the transactions(find,insert..) are coming to the lock-free
> > hashtable
> > and the jobs(transactions) are processed in an M/M/m manner with
> > multiple
> > threads and cores servicing the jobs, that's very good...
>
> > Now suppose that the application like a lock-free Hashtable is
> > working
> > frequently with data and we are accessing big data directly in
> > memory
> > *AND* the data is randomly accessed *AND* there is contention between
> > processors over the memory bus in and M/M/1 manner , so, there will
> > be
> > an appreciable serial part 1-P in the Amadahl equation, hence:
>
> > what would will you expect from the scalable lock-free Hashtable ?
>
> > what would be then the performance ? i think this will be very bad.
>
> > So, now imagine that we elevate the problem by using an M/M/m in
> > the bus memory side , this will lower contention. But imagine that
> > we are using some big in memory data and accessing it *randomly*
> > with a lock-free Hash-table , what will be the performance then ?
> > not so good i think...
>
> > Also i have another question:
>
> > Read this:
>
> >http://www.azulsystems.com/events/javaone_2007/2007_LockFreeHash.pdf
>
> > How the performance of this lock-free Hashtable can scale well in
> > performance
> > on an Azul system with more than 700 cores, if we are using some very
> > big in
> > memory data and accessing it *RANDOMLY* ? and what memory bus
> > architechture
> > are they using ?...
>
> > What do you think about this problem ?
>
> > Regards,
> > Amine Moulay Ramdane.- Hide quoted text -
>
> - Show quoted text -
== 4 of 5 ==
Date: Wed, Jul 29 2009 5:34 pm
From: Amine
Hello all,
I wrote:
"I mean what is the benefit of a very FAST Ferari car if the roads
are
not so good and they lower a lot its speed ?"
I was still *thinking* ...
So, let say for example that we are runnning under an Azul system
with more than 700 cores: http://www.azulsystems.com/ and using
this lock-free Hash table:
http://www.azulsystems.com/events/javaone_2007/2007_LockFreeHash.pdf
and millions of transactions (let say find() transactions that search
and return
some data) are coming with an arrival rate, those transations are
mostly
memory bound and let suppose an instant that those are mostly random
transactions
that *miss* the cash, so that they are serviced not in an M/M/m manner
but in M/M/1
with the memory as the server and with its low service rate lower than
the caches,
that will be very bad. So in this situation: how can even this Azul
system with more
than 700 cores with let say a lock-free Hash-table scale in
performance ?
Regards,
Amine.
On Jul 29, 3:32 pm, Amine <ami...@colba.net> wrote:
> On Jul 29, 3:21 pm, Amine <ami...@colba.net> wrote:
>
> > I wrote:
> > > So, now imagine that we elevate the problem by using an M/M/m in
> > > the bus memory side , this will lower contention. But imagine that
> > > we are using some big in memory data and accessing it *randomly*
> > > with a lock-free Hash-table , what will be the performance then ?
> > > not so good i think...
>
> > I mean what is the benefit of a very FAST Ferari car if the roads are
> > not so good
> > and they lower a lot it's speed ?
>
> typo:
>
> I mean what is the benefit of a very FAST Ferari car if the roads are
> not so good and they lower a lot its speed ?
>
> Regards,
> Amine Moulay Ramdane.
>
>
>
>
>
> > What is the benefit of a very fast lock-free hash-table if the in
> > memory data
> > it access is big and it's *randomly* accessed: and this will lower the
> > speed
> > *AND*
> > also there is a contention on the bus in an M/M/1 manner and this
> > will also
> > lower the speed ?
>
> > Regards,
> > Amine. Moulay Ramdane.
>
> > On Jul 29, 2:35 pm, Amine <ami...@colba.net> wrote:
>
> > > Hello all,
>
> > > I was thinking about my lock-free Threadpool and lock-free_SPMC
>
> > >http://www.colba.net/~aminer/
>
> > > i am using a queue for every thread worker ( and in the producer side
> > > you can push in parallel also) and i have come to the conclusion that
> > > this will scale very well.in the software side...
>
> > > But i was thinking more about *scalability* and i have come to the
> > > conclusion that there is still a problem, please follow with me:
>
> > > As Amadahl law state, the Speed = 1 / (1 -P) + P /N (N: number of
> > > cores)
> > > now let's take as an example we are working with a scalable lock-free
> > > Hashtable
> > > now, if the transactions(find,insert..) are coming to the lock-free
> > > hashtable
> > > and the jobs(transactions) are processed in an M/M/m manner with
> > > multiple
> > > threads and cores servicing the jobs, that's very good...
>
> > > Now suppose that the application like a lock-free Hashtable is
> > > working
> > > frequently with data and we are accessing big data directly in
> > > memory
> > > *AND* the data is randomly accessed *AND* there is contention between
> > > processors over the memory bus in and M/M/1 manner , so, there will
> > > be
> > > an appreciable serial part 1-P in the Amadahl equation, hence:
>
> > > what would will you expect from the scalable lock-free Hashtable ?
>
> > > what would be then the performance ? i think this will be very bad.
>
> > > So, now imagine that we elevate the problem by using an M/M/m in
> > > the bus memory side , this will lower contention. But imagine that
> > > we are using some big in memory data and accessing it *randomly*
> > > with a lock-free Hash-table , what will be the performance then ?
> > > not so good i think...
>
> > > Also i have another question:
>
> > > Read this:
>
> > >http://www.azulsystems.com/events/javaone_2007/2007_LockFreeHash.pdf
>
> > > How the performance of this lock-free Hashtable can scale well in
> > > performance
> > > on an Azul system with more than 700 cores, if we are using some very
> > > big in
> > > memory data and accessing it *RANDOMLY* ? and what memory bus
> > > architechture
> > > are they using ?...
>
> > > What do you think about this problem ?
>
> > > Regards,
> > > Amine Moulay Ramdane.- Hide quoted text -
>
> > - Show quoted text -- Hide quoted text -
>
> - Show quoted text -
== 5 of 5 ==
Date: Wed, Jul 29 2009 7:16 pm
From: David Schwartz
On Jul 29, 12:21 pm, Amine <ami...@colba.net> wrote:
> What is the benefit of a very fast lock-free hash-table if the in
> memory data
> it access is big and it's *randomly* accessed: and this will lower the
> speed
> *AND*
> also there is a contention on the bus in an M/M/1 manner and this
> will also
> lower the speed ?
The benefit is that the lock-free hash table stays out of the way and
doesn't have any significant negative impact on performance, and
that's the best you can expect it to do.
> I mean what is the benefit of a very FAST Ferari car if the roads are
> not so good
> and they lower a lot it's speed ?
The benefit is that you only have one thing to work on rather than
two. The roads being slow is not the problem the fast car is intended
to solve.
DS
==============================================================================
TOPIC: weird thread behavior on itanium/hp-ux with pthread
http://groups.google.com/group/comp.programming.threads/t/b2b5d744b99b760c?hl=en
==============================================================================
== 1 of 2 ==
Date: Wed, Jul 29 2009 12:10 pm
From: Jeremy
On Jul 28, 10:03 pm, David Schwartz <dav...@webmaster.com> wrote:
> On Jul 28, 6:15 pm, Jeremy <fc2...@gmail.com> wrote:
>
>
>
> > the pseudo code was totally messed up, here it is again:
>
> > thread 0
>
> > loop
> > mutex.lock();
> > do_something();
> > if ( !signaled) {
> > sleeping = true;
> > while (sleeping)
> > condition.timedwait(1);
> > } else {
> > sleeping = false;
> > }
> > mutex.unlock
>
> > thread 1 -----------------------
>
> > loop
> > if (somethingelse_happened) {
> > mutex.lock();
> > if (sleeping) {
> > sleep = false;
> > condition.signal();
> > }
> > signaled = true;
> > mutex.unlock();
> > }
>
> Why do you have "while(sleeping)" when what you really want is "while(!
> signaled)"? Your "sleeping" variable seems to serve no purpose but to
> make this design at least twice as complex as it needs to be.
>
> DS
Thanks for pointing this out. the is just the legacy code that I need
to figure out why the behavior could ever happen. (btw, the
do_something() should be outside of the critical section)
Jeremy
== 2 of 2 ==
Date: Wed, Jul 29 2009 12:19 pm
From: Jeremy
On Jul 28, 9:25 pm, Loïc Domaigné <loic.domai...@googlemail.com>
wrote:
> Hi Jeremy,
>
>
>
> > the pseudo code was totally messed up, here it is again:
>
> > thread 0
>
> > loop
> > mutex.lock();
> > do_something();
> > if ( !signaled) {
> > sleeping = true;
> > while (sleeping)
> > condition.timedwait(1);
> > } else {
> > sleeping = false;
> > }
> > mutex.unlock
>
> > thread 1 -----------------------
>
> > loop
> > if (somethingelse_happened) {
> > mutex.lock();
> > if (sleeping) {
> > sleep = false;
> > condition.signal();
> > }
> > signaled = true;
> > mutex.unlock();
> > }
>
> I guess, this should be "sleeping = false" in thread 1, right? It's
> difficult to pinpoint problem using pseudo-code. Can you please post a
> minimalistic example (which compiles) that shows your particular
> problem?
Thanks Loic. Yes that was a typo. the problem only happens in a remote
site under particular conditions and could not be readily reproduced
locally. what interests me is whether this sleep/wakeup mechanism is
faulty on HP/Itanium for whatever reasons.
Jeremy
==============================================================================
TOPIC: C++Framework - C++ multi-platform memory-model solution, with Java
orientation
http://groups.google.com/group/comp.programming.threads/t/344086e52caa9171?hl=en
==============================================================================
== 1 of 1 ==
Date: Wed, Jul 29 2009 4:08 pm
From: "Chris M. Thomasson"
On Jul 27, 4:14 am, "Chris M. Thomasson" <n...@spam.invalid> wrote:
> > "MoranTza" <Moran...@gmail.com> wrote in message
> >
> > news:0ead0422-0996-4877-9a38-11cd153f7403@g31g2000yqc.googlegroups.com...
> >
> > > C++ multi-platform memory-model solution, with Java orientation.
> > > You can use all the concurrent concepts laid down by Java-memory-
> > > model.
> > > The idea is smooth transition from Java concurrent programming to C++
> > > concurrent programming.
> > > New Version: 1.4 - High Performance Hazard-Pointer:
> >
> > [...]
> >
> > I have not looked at your code yet, however, I was wondering exactly
> > what
> > you mean by "High Performance" hazard pointer. Do you imply that your
> > implementation does not need the nasty `#StoreLoad' memory barrier?
> > Check
> > this excellent SMR implementation out:
> >
> > http://atomic-ptr-plus.sourceforge.net/design.html
> >
> > Joe Seigh gets around the `#StoreLoad' by running deferred objects
> > through
> > two RCU grace periods. I am very interested in how you can claim
> > high-performance wrt SMR. Also, FWIW, there are patent issues wrt SMR...
"MoranTza" <MoranTza@gmail.com> wrote in message
news:796c5591-b96e-44a3-9b4b-78ba476f61f4@d4g2000yqa.googlegroups.com...
> Thanks ... I'll review this before releasing next version...
IMHO, it will be well worth your valuable time and effort.
> Current code is Pre-Beta, but was tested a lot, the benchmark show no
> memory leak and good performance.
> The major overhead for hazard-pointers comes from scanning the Hazards
> in other threads. So this code is optimized (but can be optimized
> more, lack of time)
The overhead of scanning hazard pointers can be moved to a dedicated polling
thread. There is no requirement for actual application threads to perform
the scanning process.
IMVHO, the "major" overhead for hazard pointers is the #StoreLoad membar in
the acquire logic. Frequently executing this membar makes it very difficult
to keep the processors "caches primed" thus depriving your application of
the full benefits of a modern multi-processor system. Think of reader
threads using hazard pointers to iterate a shared linked list. A #StoreLoad
membar would have to be executed for every node in the list. That's a
boatload of overhead.
> You right I should emphasize the fact that I still not optimized the
> memory-barriers, I hope to do that in next (or next next :) version.
You should see the overall performance of hazard-pointer based non-blocking
algorithms skyrocket when you get around to removing that membar. One more
thing, I notice that your using a fixed amount of threads. Perhaps you
should consider allowing the hazard pointer algorithm to be able to handle a
dynamic number of threads.
==============================================================================
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