thread memory size

David Schwartz wrote:

Actually, after reading it agains I see where your misunderstanding is.

> This is a serious misunderstanding on your part. They *do* need to
> share it and lock it. The reason for the message passing is precisely
> to allow the threads to easily share and lock data.

I was not not talking about message passing, I was just talking about
threads that share the same memory address space.

If there is a message passing mechanism involved then mostly yes. In
many implementation there would need to be some synchronisation within
the message passing implementation.
Mind you, there are such concurrency structures that can be implemented
without locks, they are called lock-free implementations and are usually
based on state machines.
But, the program is not required to focus on that any more, because its
all in the library instead of in the program code.

And that is my entire point, that when one uses a simple mechanism as
message passing, synchronisation is left to the library, not the
program. The program code does not need to worry about it, since data is
not shared by the programs threads, but just by the messaging library
for a brief nanosecond, once. That's quite a simple model.
So this reduced concurrency control requirement is dependent on two new
aspects. Letting the message passing library deal with it the
concurrency, since it is easy to test and verify. And structuring the
program differently so that it utilises message passing and enables
massive parallelism instead of the sequential programming model of today.

regards

Jan

David Schwartz wrote:

> Huh? Now you've lost me. We were talking about architectures that use
> message passing for scalability.

That is true. But your claim was that one always needs locking. which I
explained one does not always need.

> There would always have to be. The scalability advantage of message
> passing does not come from the message passing itself being somehow
> incredibly efficient. In fact, in general message passing is less
> efficient than other types of IPC.

I have have never said that the implementation of the message passing
makes it more efficient. I have said that the scalability advantage
comes from the fact that one can parallelise the program without the
need for locking. Hence it makes it more efficient in the fact that more
work can be done in parallel, possibly massively parallel. That an
advantage that is diminishing by the day, with sequential programming
practice of today.

An example is graphics cards. the processor in such a card is not one
big ordinary processor, its one with several hundred cores, that can
parallelise the operations.

>
>> Mind you, there are such concurrency structures that can be implemented
>> without locks, they are called lock-free implementations and are usually
>> based on state machines.
>
> That changes nothing. Lock-free synchronization is still
> synchronization.

Synchronisation is not the problem, contention by locking is. All
programs have to synchronise somehow. But that's a result of the
algorithm, or structure of the program, selected to create the result
If one can change those parameters of the program, when locking nor
synchronisation poses such a big problem any more.

>> So this reduced concurrency control requirement is dependent on two new
>> aspects. Letting the message passing library deal with it the
>> concurrency, since it is easy to test and verify. And structuring the
>> program differently so that it utilises message passing and enables
>> massive parallelism instead of the sequential programming model of today.
>
> I still see no evidence you have understood anything I'm saying.

dont be rude, you dont seem to understand what I am saying either so
there is no need for that kind attitude, it does not help the discussion.

> You seem to completely misunderstand the entire point of going to the
> trouble of using message passing. You erroneously think this somehow
> makes design and implementation easier, when in fact it makes design
> and implementation harder. (Why? Because you can always make any IPC
> look like message passing. But when you commit to using message
> passing *FOR* *SCALABILITY* you lose the ability to use other forms of
> IPC such as shared memory.)

The possibility of scalability does not come in one form only. Shared
memory is one answer, but it has its limitations. Message passing is
another, which addressed many of the limitations of shared memory, with
respect to concurrency. Other than that see my answers above.

regards

Jan

David Schwartz wrote:
> On Oct 6, 5:17 am, Jan Helgesen <s....TakeThisOut@nospam.com> wrote:
>
>> The problem with shared resource are all the different access patterns,
>> and the difficulty with mapping out all patterns so as to make sure you
>> have covered every angle and every combination of access to the data.
>
> Nonsense. You can trivially implement something like message passing
> and use that.

Finally a message passing algorithm is so easy to implement that the
problems with concurrency can be contained within that single
implementation. So by structuring the application to use message passing
instead of lots and lots of locally reinvented algorithms to access
shared data, one can use reduce the concurrency problems of shared data
to that simple message passing implementation

> You mean with message passing, you *can't* do that even if you want
> to. That is a *cost* that only makes sense to pay if there's some
> corresponding *benefit*.
>
> The benefit is simple -- you don't have to share memory. And that is
> the *only* benefit to prohibiting the use of other synchronization
> mechanisms.

Exactly and that is the one benefit I am talking about. It allows
massive parallelisation of code, which is an enourmous benefit. That
benefit can be utilised when computers move to more and more cores per
processors, instead of the old game that was about more and more
kilo/mega/giga hertz.

regards

Jan

Jan Helgesen <spam.TakeThisOut@nospam.com> writes:

> David Schwartz wrote:
>
>> It would help if you showed some indication that you understood what I
>> was saying.
>
> I think you need to take a class about Computer architectures and one
> about assembler programming or advanced programming, that will explain
> to you why you are wrong.

Jan, you have a very brittle understanding of what virtual memory is and
how it works, which is limited to the dictionary definition and doesn't
recognize consequences. David's been extraordinarily patient in trying
to explain how these terms are used in practice; you really need to go
back and re-read what he's told you. I haven't been in this discussion
because he and Rainer have been doing an excellent job of trying to
explain this stuff to you.

But now you've made a comment that somebody other than David needs to
address: he's got his flaws, but *he* *knows* *his* *stuff*. Any time
you think he's wrong about something because he's got a fundamental
misunderstanding, you *really* need to look more deeply into what you
think you know.

Let me ask you a question that gets at the points he's trying to make in
a different way: suppose you've got two processors sharing memory, and
you wish to implement message-passing between two threads (one on each
processor) sharing not only the physical memory but also all their
virtual memory. What is the most efficient way for one of these
threads to pass a 1K buffer to the other? Is your answer any different
if you've got 1024 threads on 1024 cores doing the same thing?
--
As we enjoy great advantages from the inventions of others, we should
be glad of an opportunity to serve others by any invention of ours;
and this we should do freely and generously. (Benjamin Franklin)

On Oct 9, 2:03 am, David Schwartz <dav....DeleteThis@webmaster.com> wrote:

> But I appreciate your attempt at catching me in a minor "gotcha" so as
> to waste time and avoid the major issues.

I apologize for this comment. It was unwarranted.

DS

David Schwartz wrote:

> You are still confused. "Lock-free" is a misnomer. There are still
> locks, they are just not locks that block. For example, the primitive
> lock-free algorithms are made out of contain atomic 'compare and
> replace' operations or atomic 'swap' operations. These operations
> internally contain locks, for example, they lock cache lines.

The fact that in the strictest technical terms a CAS operation does
create a lock, but does not block, is true. But a CAS operation returns
if it fails to succeed. That gives it the opportunity to try again. At
the hardware level it will succeed, eventually. Even with four billion
threads contending for the value, it will succeed almost instantly (It
does not take that long to 4 billion such operations)

Also, CAS and similar operations depend on the cpu architecture and
which specific instruction it has implemented. The simpler ones allow
for less concurrency than the more advanced ones. The latest addition of
advanced concurrent CAS operations are AMDs ASF for AMD64 (Advanced
Synchorinisation Facility). Its experimental yet, but seems to promise
even more concurrency within CAS operations than previous types of CAS
operation.

On a software level, the operations are not single instruction atomic.
This means that a critical region can obtain one lock, then obtain
another lock and cause a deadlock. Even how one accesses a single
variable can be subject to the lock strategy chosen. If one chooses an
operation that specifically uses a CAS instruction only, then its the
same as if it were hardware, but if one uses critical regions or the
like, then there is a high probability it will cause problems.

So even if there is locking in the cpu, it is irrelevant. The reason for
this is that a (software level) lock-free algorithm, can use CAS
operations and obtain a much higher level of concurrency than a lock
based algorithm. Now, with a message passing implementation that is so
simple, in both implementation and model, it will be able to scale and
perform pretty well using these techniques.

+++++++++++++++++++++++++++++++++++

Now lets get back on track again. Unfortunately this discussion have
become a little pedantic and possibly a little self serving, that is
because it was sidetracked into discussing technical details of lesser
importance.

If I were to implement this within one process (i.e. threads shared
memory), I would probably implement a message queue algorithm, that uses
optimistic locking by help of CAS operations or using a state machine.
It depends on which gives the best performance.
That's a good implementation for single process communication between
threads. It can use message passing which reduced the thread level
contention one would normally get if one used lock based algorithms. So
it increases concurrency, scalability and performance by concurrency. It
does come with a small threads level decrease in efficiency, but the
scalability and concurrency outweighs that disadvantages by so much that
it is nothing to care about. As concurrency mechanisms increase its
performance other strategies can be chosen.

But that misses the functional requirement of being able to communicate
between processes on same or different machines. I.e the truly scalable
solution (the ultimate scalability would be atomic computing, but that's
a different matter). To be able to communicate between processes on
different machines network communication is need, that frees us from the
concurrency algorithms one normally would use if the program where
running in a single process. If set up properly, i,e, fiber cables for
networking and so on

But, using network to communicate messages within the same machine or
process is not very efficient so the implementation could be smart and
choose the mechanism depending on the proximity of the peer process.
That means it would use network, Shared Memory or process memory as needed.
But that leads us to a different discussion, how are the processes
interconnected, by 100/1000Mb network, by fibre, by supercomputer fibre
cable switches etc. It all depends on the efficiency of the
communicating technology chosen. With s slow network connection or IP
stack implementation one might want to try to use a Shared Memory
message passing implementation to make it more efficient.




> The forest is this -- message passing is inefficient.

for the sake of clarity can you give some definitions and explain a
couple of things before we continue:

how would you implement it with shared memory and without message
passing? (overall solution)

what do you define as efficient and what do you define as inefficient?

> The reason
> people use it for performance and scalability is because if you limit
> yourself to message passing only, you can get the concurrency of
> threads without the inherent performance penalties of threads.

And that is not a good reason to use message passing?

> Right, the advantage of message passing is that it doesn't have the
> limitations of shared memory.

What limitations are you thinking of?

> You would suffer all the disadvantages of
> threads and get absolutely *none* of the benefits.

And what do you define as the disadvantages and benefits?



Regards

Jan

David Schwartz wrote:
> On Oct 9, 2:03 am, David Schwartz <dav... RemoveThis @webmaster.com> wrote:
>
>> But I appreciate your attempt at catching me in a minor "gotcha" so as
>> to waste time and avoid the major issues.
>
> I apologize for this comment. It was unwarranted.

Apology accepted.

regards

Jan

David Schwartz wrote:
> On Oct 9, 12:11 am, Jan Helgesen <s... DeleteThis @nospam.com> wrote:
>
>>> The benefit is simple -- you don't have to share memory. And that is
>>> the *only* benefit to prohibiting the use of other synchronization
>>> mechanisms.
>
>> Exactly
>
> So why are you asking about threads which do have to share memory?

Sorry but that's not the paragraph i intended to comment on. I forgot to
remove the latter part of that paragraph

Let me re-comment it again:

-------
> That is a *cost* that only makes sense to pay if there's some
> corresponding *benefit*.

Exactly and that is the one benefit I am talking about. It allows
massive parallelisation of code, which is an enormous benefit. That
benefit can be utilised when computers move to more and more cores per
processors, instead of the old game that was about more and more
kilo/mega/giga hertz.
---------

But as I said we are off track in this discussion, please see my other
post to you, which should help us focus the discussion on the real
matter again.

regards

Jan

Joe Pfeiffer wrote:
>
> Jan, you have a very brittle understanding of what virtual memory is and
> how it works, which is limited to the dictionary definition and doesn't
> recognize consequences.

Please explain to me what is wrong with my understanding of virtual
memory. Because as you say, no one else in this discussion has been able
to do so, So why don't you try it and see if you can word it differently
so that I truly understand.

> Let me ask you a question that gets at the points he's trying to make in
> a different way: suppose you've got two processors sharing memory, and
> you wish to implement message-passing between two threads (one on each
> processor) sharing not only the physical memory but also all their
> virtual memory. What is the most efficient way for one of these
> threads to pass a 1K buffer to the other? Is your answer any different
> if you've got 1024 threads on 1024 cores doing the same thing?

Firstly, I know what you are getting at. Which is that even with a
message passing library, 1024 threads would compete for access to the
message queue, which would require locks and so on. And that that would
be a waste on top of a shared memory, which in it self would need locks
to allow the threads to access the shared data properly. It would be
butter on lard, as it were. I get it, but that is not the entire truth.

Secondly, I would not program the solution my self unless I was forced
to. Mainly because, with concurrent algorithms its better to use a well
known and tested solution than to create my own. But if I had to create
my own, the following would probably be my answer to your question:

The number of threads matter. An implementation that only
has to cater for a few threads will survive nicely by using the more
naive, and perhaps pre made, solutions. Because provides enough
concurrency and is fast enough. But more importantly it would be much
easier to program or to find for that matter. It does not have have
perfect performance or concurrency, but it will do for less critical
solutions.

But, if I know there is going to be thousands of threads competing for
the same resource. I know a naive solution is not going to scale vary
well. So I would put effort into creating an algorithm that can scale.
Scalability has a lot to do with it, so does the effort one puts into
making sure the chosen solution performs according to the requirements
and are error-free. Any concurrent algorithms has to be thoroughly
tested, but a simpler scenario is easier to the than a more advanced
scenario.
So, as I mentioned in reply to David, I would program an algorithm that
uses optimistic locking with CAS instructions on a hardware level or a
state machine with CAS instructions.

The discussion has become too pedantic and hence side tracked. Please
read my post to David so we can get back on track. I have spent more
time on this discussion than I intended to do and there is still no
progression.

regards

Jan

On Oct 10, 3:50 pm, Jan Helgesen <s... RemoveThis @nospam.com> wrote:

> With this answer are you saying that you don't have any comments to the
> other stuff in my answer, or do you disagree with it and use the answer
> below as the reason for disagreeing?

I'm honestly not sure what you're referring to. It seems that most of
what you said that I didn't respond to was completely irrelevant and
so didn't really matter if it was correct or incorrect.

If you meant the stuff about lock-free algorithms, you are (in
general) wrong. Lock-free algorithms typically perform significantly
worse than comparable lock-based algorithms expect in very special
circumstances (the ones where clueful people use them).

Contention is bad, it results in CPUs wasting their time synchronizing
with each other. Lock-free algorithms actually tend to maximize
contention, as it encourages contending threads to run in parallel.

For example, consider two cores running four threads, A1, A2, B1, and
B2. Assume threads A1 and A2 both frequently access structure A and
threads B1 and B2 both frequently access structure B. If structures A
and B are locked, threads A1 and A2 will not run concurrently. If
thread A1 is running, A2 will be blocked and B1 or B2 will run. There
will be minimal contention.

Now imagine we switch collections A and B to a lock-free algorithm.
Now, there's a 50 percent chance that one thread will be A1 or A2 and
the other will be B1 or B2. In this case, there will be frequent
contention and the shared collection will constantly ping-pong from
cache to cache. FOR NO REASON.

Lock-free algorithms are specialized algorithms. They're useful in
very unusual circumstances where this huge disadvantage is outweighed
by something else. (For example, they're useful in kernel hot code
paths, because there's a good chance more or less every thread in the
system will pass those paths.)

DS

On Oct 11, 9:22 pm, David Schwartz <dav....DeleteThis@webmaster.com> wrote:

> Now imagine we switch collections A and B to a lock-free algorithm.
> Now, there's a 50 percent chance that one thread will be A1 or A2 and
> the other will be B1 or B2. In this case, there will be frequent
> contention and the shared collection will constantly ping-pong from
> cache to cache. FOR NO REASON.

Grr. Of course, this should read "that one thread will be A1 and the
other will be A2, or one thread will be B1 and the other will be B2".
In either case, for no reason at all, two threads are horribly
contending and saturating the FSB. Worse, if you have more than two
cores running threads from other processes, those threads can't make
decent forward progress because the FSB is saturated.

(My terminology assumes there *is* an FSB. But the issues are similar,
though not always precisely the same or as bad, if you have some other
technology.)

DS

On Oct 12, 2:27 am, Jan Helgesen <s....DeleteThis@nospam.com> wrote:

> It is with these advances in technology, I base my arguments. Since the
> people working on these algorithms are acknowledged experts on the
> matter of concurrency, I trust them a bit more than your unsupported
> claims. Since you have not been able to convince me with your arguments,
>   nor have you been able to produce any references that supports your
> claim, I have little incentive to agree with you.

I cannot convince you with my arguments because you are beyond
rational persuasion. I notice that you don't point out any errors or
flaws of any kind, you simply point to something completely irrelevant
and claim that it somehow refutes my argument when, ironically, it
actually supports it.

In any event, continue doing what you're doing having no understanding
of any of the concepts involved. I have exhausted my patience trying
to educate you.

DS

On Oct 12, 3:09 am, Jan Helgesen <s... DeleteThis @nospam.com> wrote:

> you have seen one of my references, maybe you could explain why you
> think that is irrelevant.

That it is possible to do something right does not refute an argument
that it is possible to do something wrong. If you look at my last
paragraph of the post you didn't respond to, I explained that.

But this is a waste of time. You actively refuse to think and I'm
through trying. (I see no evidence you even attempted to understand my
argument.)

DS