Where's my non-classical shared memory concurrency technology?

Where's my non-classical shared memory concurrency technology?

[Berke Durak]

[-- Attachment #1: Type: text/plain, Size: 816 bytes --]

On Sun, May 18, 2008 at 12:03 AM, Jon Harrop <jon@ffconsultancy.com> wrote:

>
> Avoiding threads does not improve the safety of the language, it simply
> degrades the capabilities of the language.
>

Avoiding threads is like avoiding malloc() in a C program and doing only
static and stack allocation: it is cumbersome and impractical, but avoids a
whole class of allocation bugs.

Similarly, avoiding threads removes concurrency bugs - while reducing the
concurrency capabilities.  So it's not really improvement of safety, but
rather avoidance of unsafety - a purely semantic issue.

I think we are still lacking programming language technology to integrate
safe and easy-to-use shared memory concurrency in ML-like languages.  Does
anyone know of anything in this area aside from transactional memory?
-- 
Berke

[-- Attachment #2: Type: text/html, Size: 1100 bytes --]

Re: Where's my non-classical shared memory concurrency technology?

[Jon Harrop]

On Sunday 18 May 2008 09:39:15 Berke Durak wrote:> On Sun, May 18, 2008 at 
12:03 AM, Jon Harrop <jon@ffconsultancy.com> wrote:
> > Avoiding threads does not improve the safety of the language, it simply
> > degrades the capabilities of the language.
>
> Avoiding threads is like avoiding malloc() in a C program and doing only
> static and stack allocation: it is cumbersome and impractical, but avoids a
> whole class of allocation bugs.
>
> Similarly, avoiding threads removes concurrency bugs...

Are you sure? Can you not still have two agents mutually waiting on each other 
for a message (a deadlock) or messages not being ordered before consumption 
(a race condition)?

I don't believe you have removed any concurrency bugs. I think you just pushed 
them around a bit.

> I think we are still lacking programming language technology to integrate
> safe and easy-to-use shared memory concurrency in ML-like languages.  Does
> anyone know of anything in this area aside from transactional memory?

Data parallelism in Microsoft's Task Parallel Library. I have no use for STM 
myself.

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/products/?e

Re: [Caml-list] Re: Where's my non-classical shared memory concurrency technology?

[Martin Berger]

Jon Harrop wrote:

>> Similarly, avoiding threads removes concurrency bugs...

> I don't believe you have removed any concurrency bugs. I think you just pushed 
> them around a bit.

I couldn't agree more. If you 'avoid' concurrency by writing your own
'sequential' event handling code, you have not removed the concurrency,
you just face it in a slightly different form, and you have to
program the event handling code yourself, rather than relying
on a tried and tested library, i.e. you have an additional
source of bugs, without removing the problems that are inherent
in concurrency (e.g. deadlocks, livelocks, fairness ...). There
are reasons why writing your own concurrency mechanisms might
be the way to go, but it's a highly non-trivial endeavor.

Concurrency is hard, and no matter how one presents the concurrency
(message passing, shared memory, event handling etc), the fundamental
problems will always be there.

> Data parallelism in Microsoft's Task Parallel Library. I have no 
> use for STM  myself.

Do you have industrial experience with STM? I wonder how it
performs in industrial settings. Reading STM papers by their
inventors makes them sound like the best thing since sliced
bread, but I have a (probably irrational) feeling that it's
difficult to beat fine grained locking if one can handle
the programming difficulties their use imposes.

Martin Berger

Re: [Caml-list] Re: Where's my non-classical shared memory concurrency technology?

[Berke Durak]

[-- Attachment #1: Type: text/plain, Size: 4169 bytes --]

On Mon, May 19, 2008 at 1:45 PM, Martin Berger <M.Berger@doc.ic.ac.uk>
wrote:

> Jon Harrop wrote:
>
>  Similarly, avoiding threads removes concurrency bugs...
>>>
>>
>  I don't believe you have removed any concurrency bugs. I think you just
>> pushed them around a bit.
>>
>
> I couldn't agree more. If you 'avoid' concurrency by writing your own
> 'sequential' event handling code, you have not removed the concurrency,
> you just face it in a slightly different form, and you have to
> program the event handling code yourself, rather than relying
> on a tried and tested library, i.e. you have an additional
> source of bugs, without removing the problems that are inherent
> in concurrency (e.g. deadlocks, livelocks, fairness ...). There
> are reasons why writing your own concurrency mechanisms might
> be the way to go, but it's a highly non-trivial endeavor.


Let's say that there are two kinds of concurrency bugs : consistency bugs
and
synchronization bugs.

- Consistency bugs arise when two or more threads mutate the same
datastructure concurrently,
leading to inconsistent data.

- Synchronization bugs occur when you have things like starvation (a queue
with waiter never gets filled),
unfairness (some code almost never gets a chance to run), deadlocking (ye
olde deadlock), livelocking
(threads spend time communicating back and forth without making progress),
etc.

Avoiding threads means to me that you're either using Lwt-style monadic
threads, or an event-based
framework (the two being similar).

Avoiding threads almost eliminates consistency bugs.

Code you write is, by default, atomic.  Concurrency must be explicitly
invoked, and
generally shows in the types of functions using concurrency (one of the
situations where monad
creep seems to be a good thing.)

If you take a data structure that was not intended for concurrency, then it
will almost certainly be
concurrency-safe unless it is some kind of structure that can store thunks
and invoke them, and
you store concurrency-producing thunks in them.

Hence, using, say, Lwt, I can have tens of thousands of lightweight threads
that happily mutate
an unprotected, possibly complex datastructure implemented in a
concurrency-agnostic module.
For instance, I can and do use a global reference to a Map module and mutate
it without any lock
of any kind.

Now let me classify synchronization bugs in two sorts :
  - Type A: Logical synchronization bugs due to algorithmic issues
(livelocks, etc.)
  - Type B: Synchronization bugs due to consistency bug avoidance
techniques,

Short of a formal system where concurrency properties are statically proven,
you probably can't
avoid type A bugs, since it's a high-level correctness issue.

Take for instance two mutually-recursive functions calling themselves using
an inter-process mechanism.
If they were supposed to terminate, it's a livelock, otherwise - if they are
some kind of persistent client-server
combination, they are running as usual.  Yet they will be using the same
primitives.

So no one expects logical synchronization bugs to be statically detected.

Type B bugs typically occur when you or someone else peppers code with
locks/unlock pairs (or "synchronized"
attributes, or "perform_under_lock" higher-order function...) and get a
deadlock.

While some type B bugs can be dynamically (and even statically) detected, or
some lock/unlock pairs be
removed by your JIT, others type B bugs will slip thru: even if you maintain
some kind of dependency graph
between locks, as you cannot model a synchronization effect conditioned on
another lock if the unlocking goes
thru a piece of unknown code.

If you avoid threads, type A bugs become much less likely.  Hence you won't
need to wrap almost
every shared datastructure with locks to prevent them, and hence you will
avoid a lot of type B bugs.

In short, with monadic threads, you can safely invoke non-concurrent code
from concurrent code.  (The inverse
can be dangerous - but you usually don't do this anyway since you will end
up optaining an 'a Lwt.t).
This means that locking is almost never needed and hence your code is
safer.  Sequential, yes, but safer.
-- 
Berke Durak

[-- Attachment #2: Type: text/html, Size: 5221 bytes --]

Re: [Caml-list] Re: Where's my non-classical shared memory concurrency technology?

[Jon Harrop]

On Monday 19 May 2008 13:24:26 Berke Durak wrote:
> > > > Similarly, avoiding threads removes concurrency bugs...
>
> Avoiding threads means to me
> ...
> Avoiding threads almost eliminates consistency bugs
> ...
> If you avoid threads
> ...

There are two problems with what you wrote in this context:

1. You are replying to a thread about shared-memory parallelism with a 
discussion of sequential concurrency, which is completely different.

2. You keep saying "avoiding threads" but what you mean is "avoiding 
parallelism".

In essence, your solution to bugs that arise due to parallelism is to avoid 
parallelism. While true, that is not going to help anyone exploit multicores.

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/products/?e

Re: [Caml-list] Re: Where's my non-classical shared memory concurrency technology?

[Berke Durak]

On Mon, May 19, 2008 at 11:47 PM, Jon Harrop <jon@ffconsultancy.com> wrote:
>
> There are two problems with what you wrote in this context:
>
> 1. You are replying to a thread about shared-memory parallelism with a
> discussion of sequential concurrency, which is completely different.
>
> 2. You keep saying "avoiding threads" but what you mean is "avoiding
> parallelism".

No, because Ocaml threads today avoid parallelism, but you can still get
inconsistency bugs.  You'd only get them faster with parallel execution :)

> In essence, your solution to bugs that arise due to parallelism is to avoid
> parallelism. While true, that is not going to help anyone exploit multicores.

We're going in circles again.  I was just arguing, again, that Thread.create +
Mutex.lock = more bugs than event-driven execution.  Now, yes, that doesn't
heat all your cores, so that's why I changed the subject to "where is
my shared-memory concurrency technology?" - not a rhetorical question,
but a real one.

So, my question is :

Given that shared, mutable global state accessed with multiple threads
is a recipe for bugs that no amount of data hiding can solve (because
-locking-sections-don't-compose-),
did anyone invent and implement a usable type or other system for
making concurrency
and parallelism safe?

If the answer is STM, please show me some non-trivial application that
uses it, preferably
in an impure language.
-- 
Berke Durak

Re: [Caml-list] Re: Where's my non-classical shared memory concurrency technology?

[Raoul Duke]

> If the answer is STM, please show me some non-trivial application that
> uses it, preferably
> in an impure language.

yes, that would be interesting to see. presumably the example would
have to come from Haskell, Clojure, or classically some SQL database?
i am under the impression that STM is harder to optimize since
generally you don't know what the transactions collided on. whereas
with a "hot lock" you can see precisely what code uses that lock and
what it locks.

Re: [Caml-list] Re: Where's my non-classical shared memory concurrency technology?

[Pierre-Evariste Dagand]

Hi all,

>  i am under the impression that STM is harder to optimize since
>  generally you don't know what the transactions collided on. whereas
>  with a "hot lock" you can see precisely what code uses that lock and
>  what it locks.

I'm not so sure... In fact, my work in the past 4 months has been to
build a toy language to experiment with the Automatic Mutual Exclusion
semantic defined in [1]. At the beginning, I was, just like most of
you, quite sceptical about STM and its performance.

Besides, in this language, *everything* is under a transaction :
unless you specify it explicitly with the keyword "unprotected", every
access to memory is saved in a transaction. This have the nice
property to produce, by default, proven thread-safe code.

But, without transactional processors, this have a high performance
cost, as you can imagine. The second part of my work has been to
develop a kind of profiler that provide the developer with the "hot
transactions". And I have just finished it a minute ago, hence I can
show you a nice, typical output :

Frequency          Definition pos.          Transactions
80.%               88                       { [ 31247 | read ]  } <->
{ [ 31247 | read ] [ 31318 | write ]  }
                                            { [ 31247 | read ]  } <->
{ [ 31247 | read ] [ 31318 | write ]  }
                                            { [ 31247 | read ]  } <->
{ [ 31247 | read ] [ 31318 | write ]  }
                                            { [ 31247 | read ]  } <->
{ [ 31247 | read ] [ 31318 | write ]  }
20.%               49                       { [ 31425 | read ]  } <->
{ [ 31425 | read ] [ 31450 | write ]  }

Therefore, you first develop your code, with everything in a
transaction. Then, you run the profiler. Here, you see that the
reference cell defined at character 88 of the source code is a the
root of 80% of the conflicts. And you know the conflicting
transactions. At that point, you can either change the code to get
less contention of this reference cell (my choice here) or shorten the
transactions by, explicitly, committing them more frequently.

( this profiles my implementation of a concurrent Queue and the cell
at char 88 contains the size of the queue that is
incremented/decremented when we push/pop )

Hence, concerning performance, you will be able to, easily, identify
"hot transactions" and reduce the number of conflicts. But I see
someone in the room arguing that he don't even want to bother with
transactions because there is a 4242% decrease in speed. Good news !
With the "unprotected" keyword, you can work out of any transactions,
at full speed, *without sacrificing thread-safety* (and this is
ensured by the type-system).

To sum up, the idea is "thread-safe by default" and then "earn more
(speedup) by working more". Some people has been elected with such
ideas, I might get the Turing award for that...

If someone is interested in this toy language, let me know. But the
great and crazy part now is to transfer this technology in OCaml. For
the programmer, that's just 3 new keywords in the language. For the
guy that will implement AME in OCaml, well... that's a lot of work...

Regards,


[1]: http://research.microsoft.com/~tharris/papers/2008-popl.pdf

-- 
Pierre-Evariste DAGAND
http://perso.eleves.bretagne.ens-cachan.fr/~dagand/

Re: [Caml-list] Re: Where's my non-classical shared memory concurrency technology?

[David Teller]

IIRC, there are already type systems which may prevent deadlocks in
pi-calculus. And since pi-calculus is essentially the base for
CML/OCaml's Event/lwt (I'm not 100% sure for lwt), my guess is that it
shouldn't be too hard to get them to work for purely functional threaded
code. The missing step would be to detect whether code is purely
functional, which is a rather easy task (if tedious). 

The alternative to that missing step would be to detect whether
impurities are localized to each thread -- something which I believe
would also be quite feasible, provided you limit side-effects to the use
of a well-defined, thread-local, API.

Cheers,
 David


On Tue, 2008-05-20 at 00:24 +0200, Berke Durak wrote:
> Given that shared, mutable global state accessed with multiple threads
> is a recipe for bugs that no amount of data hiding can solve (because
> -locking-sections-don't-compose-),
> did anyone invent and implement a usable type or other system for
> making concurrency
> and parallelism safe?
> 
> If the answer is STM, please show me some non-trivial application that
> uses it, preferably
> in an impure language.
-- 
David Teller
 Security of Distributed Systems
  http://www.univ-orleans.fr/lifo/Members/David.Teller
 Angry researcher: French Universities need reforms, but the LRU act
brings liquidations. 

Re: [Caml-list] Re: Where's my non-classical shared memory concurrency technology?

[Martin Berger]

David Teller wrote:

> IIRC, there are already type systems which may prevent deadlocks in
> pi-calculus.

This is true but (1) these typing systems are quite complicated
and it will take heroic educational efforts to push such
new typing systems into programming mainstream; (2) these typing
systems (or at least most of them, the Kobayashi/Igarashi scheme
is extremely general) are  relatively restrictive and many useful
concurrent programming idioms turn out to be not typable.

Regarding (1), I think using such typing systems for concurrency
is completely unavoidable for a variety of reasons, and they will
be adopted in the medium term (in about 10 years), but they are
not ready for the mainstream yet. As to (2), extending the typing
systems is an active research area, and these problems will be
solved eventually. Moreover, recent success in extending Hoare
Logics to concurrency mean that we don't have to rely on typing
systems alone, instead with can take typing systems of medium
complexity to prevent the great majority of concurrency bugs
and have logics for rare hard cases. (Well, that's the hope
anyway!)

Martin

Re: [Caml-list] Re: Where's my non-classical shared memory concurrency technology?

[Martin Berger]

> In short, with monadic threads, you can safely invoke non-concurrent 
> code from concurrent code.  (The inverse
> can be dangerous - but you usually don't do this anyway since you will 
> end up optaining an 'a Lwt.t).

In my experience that rarely works, in the sense of scaling to code of
significant size.

Such code must be written with the concurrency mechanism at the forefront
from the start.

I don't agree that event based mechanisms prevent syncronisation bugs
or consistency bugs as you call them, but the issue has already been
taken up by others in this thread, so I shall keep this message short.

Martin

Re: [Caml-list] Re: Where's my non-classical shared memory concurrency technology?

[Gerd Stolpmann]

Am Montag, den 19.05.2008, 12:45 +0100 schrieb Martin Berger:
> Jon Harrop wrote:
> 
> >> Similarly, avoiding threads removes concurrency bugs...
> 
> > I don't believe you have removed any concurrency bugs. I think you just pushed 
> > them around a bit.
> 
> I couldn't agree more. If you 'avoid' concurrency by writing your own
> 'sequential' event handling code, you have not removed the concurrency,
> you just face it in a slightly different form, and you have to
> program the event handling code yourself, 

I cannot agree. Just use Ocamlnet! Or other libraries doing it for you.

> rather than relying
> on a tried and tested library, 

On the contrary: Shared memory parallelization has the fundamental
disadvantage that you cannot reason about it, and so the only way of
checking the quality of the code is testing. Event handing concurrency,
while not giving you parallelization, is basically sequential
programming, and it is possible to reason about such programs.

With "reasoning" I don't necessarily mean formal techniques. The more
frequent case is that the programmer thinks about the program guided by
the laws of logic.

The impossibility to do this with truly parallelized code is an
important source of bugs, so I would say this code inherently more
buggy.

> i.e. you have an additional
> source of bugs, without removing the problems that are inherent
> in concurrency (e.g. deadlocks, livelocks, fairness ...).

This is simply nonsense. Different concurrency techniques have different
problems. For example, in event handling-based concurrency you do not
need locks, hence you cannot run into deadlocks.

>  There
> are reasons why writing your own concurrency mechanisms might
> be the way to go, but it's a highly non-trivial endeavor.

Maybe in a mainstream language, but in FP I found it always relatively
easy to do it.

> Concurrency is hard, and no matter how one presents the concurrency
> (message passing, shared memory, event handling etc), the fundamental
> problems will always be there.

As pointed out, I cannot agree with your premises. There are different
types of concurrency built on top of different fundaments.

Gerd

> 
> > Data parallelism in Microsoft's Task Parallel Library. I have no 
> > use for STM  myself.
> 
> Do you have industrial experience with STM? I wonder how it
> performs in industrial settings. Reading STM papers by their
> inventors makes them sound like the best thing since sliced
> bread, but I have a (probably irrational) feeling that it's
> difficult to beat fine grained locking if one can handle
> the programming difficulties their use imposes.
> 
> Martin Berger
> 
> 
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
> 
-- 
------------------------------------------------------------
Gerd Stolpmann * Viktoriastr. 45 * 64293 Darmstadt * Germany 
gerd@gerd-stolpmann.de          http://www.gerd-stolpmann.de
Phone: +49-6151-153855                  Fax: +49-6151-997714
------------------------------------------------------------

Re: [Caml-list] Re: Where's my non-classical shared memory concurrency technology?

[Richard Jones]

On Mon, May 19, 2008 at 04:09:04PM +0200, Gerd Stolpmann wrote:
> This is simply nonsense. Different concurrency techniques have different
> problems. For example, in event handling-based concurrency you do not
> need locks, hence you cannot run into deadlocks.

Mostly.  You do however need to pay attention to which functions can
schedule.  Thus code like this may need a lock:

  let f () =
    let a = !global_structure in
    call_a_function_which_can_schedule ();
    global_structure := a + 1

For small programs this is manageable, but for large programs tracking
functions which can schedule can be intractable.  Particularly it's a
problem when some fundamental function changes (eg. a fundamental
function calls a logging library which changes from logging to local
disk, to logging remotely -- hence starts to call schedule).

My pthrlib library[1] has locks for this reason, and programs which
use the library sometimes use the locks, although mostly they aren't
needed.

Rich.

[1] Google it ... another contribution to the world of lightweight
non-preemptable threading libs.

-- 
Richard Jones
Red Hat

Re: [Caml-list] Re: Where's my non-classical shared memory concurrency technology?

[Jon Harrop]

On Monday 19 May 2008 15:09:04 Gerd Stolpmann wrote:
> On the contrary: Shared memory parallelization has the fundamental
> disadvantage that you cannot reason about it,

I have been reasoning about shared memory parallel programs for many years.

> and so the only way of checking the quality of the code is testing.

I often assess the correctness of my parallel codes just by reading them.

> Event handing concurrency, while not giving you parallelization, is
> basically sequential programming, and it is possible to reason about such
> programs. 

Programs are parallelized in the interests of efficiency. Event handling 
concurrency is orders of magnitude less efficient in the context of 
CPU-intensive tasks that are not embarassingly parallel so it is not an 
alternative.

> With "reasoning" I don't necessarily mean formal techniques. The more
> frequent case is that the programmer thinks about the program guided by
> the laws of logic.

Then it is a subjective belief.

> The impossibility to do this with truly parallelized code is an
> important source of bugs, so I would say this code inherently more
> buggy.

Your remit is concurrency and not parallelism.

> > i.e. you have an additional
> > source of bugs, without removing the problems that are inherent
> > in concurrency (e.g. deadlocks, livelocks, fairness ...).
>
> This is simply nonsense. Different concurrency techniques have different
> problems. For example, in event handling-based concurrency you do not
> need locks, hence you cannot run into deadlocks.

Two agents cannot proceed because they are waiting on events from each other 
=> they are deadlocked even though there are no mutexes.

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/products/?e

Re: [Caml-list] Re: Where's my non-classical shared memory concurrency technology?

[Ulf Wiger (TN/EAB)]

Gerd Stolpmann skrev:
> 
> This is simply nonsense. Different concurrency techniques
 > have different problems.

True.

 > For example, in event
 > handling-based concurrency you do not need locks, hence
 > you cannot run into deadlocks.

Yes you can. We've even had to write design rules to this
effect to educate our commercial Erlang programmers.

There seems to be a common belief that switching from
synchronous to asynchronous communication will eliminate
the risk for deadlock, but just like Jon noted, if two
threads/processes wait for events from the other
processes, they may deadlock*. Using asynchronous
programming just makes the deadlock much more difficult
to detect, than if the processes communicate synchronously.

* In the sense that neither can continue. Deadlock doesn't
require the presence of locks at all.

Going back to Jon's observation that you cannot exploit
multicore with event-based programming, I'm inclined to
agree, even though I think that message-passing concurrency
is quite suitable for making use of multiple cores (albeit
addressing a wholly different problem from data parallelism).

The problem with event-based programming is that it doesn't
scale complexity-wise, and just as when programming with
mutexes, introducing true parallelism just makes it worse.
While there may be some simple applications which actually
can scale up this way, doing so with more "interesting"
concurrency patterns is courting disaster.

I could list some juicy examples of important commercial
products that are limited to a single core for this very
reason, but alas I'm not permitted to. I have to ask you
to take my word for it.

When scaling up message-passing (or event-based) concurrency,
you have to do one of two things:

1) ensure that your code is stable in the face of timing
    variations and message reordering
2) calculate the entire event/state matrix

For hard real-time, you must do (2) anyway. For soft real-time,
you don't have to, since a missed deadline can be viewed as
a temporary glitch rather than a system error. And (2) suffers
from the same problems as model checking - it doesn't scale
well.

For a phone system (soft real-time), if you pick up the phone
and don't get dial tone, you replace the handset, then pick
it up again - normally, it will work then. Everyone's experienced
this, and it doesn't bother us unless it happens often.
Similarly, we can accept if it occasionally takes a few seconds
longer than usual.

The same behavior would be extremely unnerving - possibly fatal -
if the breaks on your car (hard real-time) started exhibiting it.

BR,
Ulf W

Re: [Caml-list] Re: Where's my non-classical shared memory concurrency technology?

[Martin Berger]

Ulf Wigner wrote:

> Going back to Jon's observation that you cannot exploit
> multicore with event-based programming, I'm inclined to
> agree, even though I think that message-passing concurrency
> is quite suitable for making use of multiple cores (albeit
> addressing a wholly different problem from data parallelism).

As more and more core will be put on a single chip, most
cores will be communicating via a network on chip. Hence
message passing is unavoidable. And if it is unavoidable
then maybe we should have it all the way.

> When scaling up message-passing (or event-based) concurrency,
> you have to do one of two things:
> 
> 1) ensure that your code is stable in the face of timing
>    variations and message reordering
> 2) calculate the entire event/state matrix

That's right.

Martin

Re: [Caml-list] Re: Where's my non-classical shared memory concurrency technology?

[Martin Berger]

Gerd Stolpmann wrote:

> I cannot agree. Just use Ocamlnet! Or other libraries doing it for you.

OK I was speaking carelessly. Of course one can use libraries for
e.g. event-handling.

> On the contrary: Shared memory parallelization has the fundamental
> disadvantage that you cannot reason about it, and so the only way of
> checking the quality of the code is testing. 

Here I disagree. Shared  memory concurrency is a specific form
of message passing: Writing to a memory cell is in fact sending
a message to that cell carrying two items, the new value and a
return channel that is used to inform the writer that sending
has succeeded, and likewise for reading. This way of thinking
about shared memory concurrency has enabled the construction of
powerful logics and typing systems to reason about shared memory.

I agree with the spirit of your claim though: shared memory is
a form of message passing that is especially difficult.

> With "reasoning" I don't necessarily mean formal techniques. The more
> frequent case is that the programmer thinks about the program guided by
> the laws of logic.
> 
> The impossibility to do this with truly parallelized code is an
> important source of bugs, so I would say this code inherently more
> buggy.

There is a lot of truth in what you say, but if you consider complex
event handling programs, you essentially do concurrent programming,
wether you like it or not. You just don't call it by that name.

> This is simply nonsense. Different concurrency techniques have different
> problems. For example, in event handling-based concurrency you do not
> need locks, hence you cannot run into deadlocks.

I disagree, but as the issue has already been dealt with by other
posters, I shall leave it at that.

> Maybe in a mainstream language, but in FP I found it always relatively
> easy to do it.

Maybe you are an especially skilled programmer. Or maybe the applications
that you have coded are not demanding in terms of concurrency.

Martin

Re: [Caml-list] Re: Where's my non-classical shared memory concurrency technology?

[Gerd Stolpmann]

Am Mittwoch, den 21.05.2008, 09:06 +0100 schrieb Martin Berger:
> Here I disagree. Shared  memory concurrency is a specific form
> of message passing: Writing to a memory cell is in fact sending
> a message to that cell carrying two items, the new value and a
> return channel that is used to inform the writer that sending
> has succeeded, and likewise for reading. This way of thinking
> about shared memory concurrency has enabled the construction of
> powerful logics and typing systems to reason about shared memory.

But this is still academic, right? The practice is that there is almost
no utility that helps programmers to write (more) correct code.

> I agree with the spirit of your claim though: shared memory is
> a form of message passing that is especially difficult.

> > With "reasoning" I don't necessarily mean formal techniques. The more
> > frequent case is that the programmer thinks about the program guided by
> > the laws of logic.
> > 
> > The impossibility to do this with truly parallelized code is an
> > important source of bugs, so I would say this code inherently more
> > buggy.
> 
> There is a lot of truth in what you say, but if you consider complex
> event handling programs, you essentially do concurrent programming,
> wether you like it or not. You just don't call it by that name.

Of course, it is possible to e.g. develop locking mechanism in event
handling programs, and then to run into the same problems. My experience
is different, however. The worst thing I've encountered so far in
practice is the "forgotten continuation" so that the event system
freezes. 

Another result from using this is in practice is that it is
comparatively easy to debug synchronization problems, because the
debugging code is not itself concurrent code. This is different to e.g.
multi-threaded programs where the whole program is concurrent, and you
cannot locally escape from this environment.

> > This is simply nonsense. Different concurrency techniques have different
> > problems. For example, in event handling-based concurrency you do not
> > need locks, hence you cannot run into deadlocks.
> 
> I disagree, but as the issue has already been dealt with by other
> posters, I shall leave it at that.

Granted, "cannot run into deadlocks" is too strong.

> > Maybe in a mainstream language, but in FP I found it always relatively
> > easy to do it.
> 
> Maybe you are an especially skilled programmer. Or maybe the applications
> that you have coded are not demanding in terms of concurrency.

Well, it's probably one of the biggest programs that has ever been coded
in O'Caml... It's a search engine (wink.com), and I would say it is very
demanding in terms of concurrency.

Keep in mind that I am not a researcher. When I make statements, then
from a practical point of view. My observation is simply that you run
far quicker into complicated synchronization problems with shared memory
concurrency than with the types of concurrency I prefer.

Gerd
-- 
------------------------------------------------------------
Gerd Stolpmann * Viktoriastr. 45 * 64293 Darmstadt * Germany 
gerd@gerd-stolpmann.de          http://www.gerd-stolpmann.de
Phone: +49-6151-153855                  Fax: +49-6151-997714
------------------------------------------------------------

Re: [Caml-list] Re: Where's my non-classical shared memory concurrency technology?

[Damien Doligez]

On 2008-05-21, at 10:06, Martin Berger wrote:

> Here I disagree. Shared  memory concurrency is a specific form
> of message passing: Writing to a memory cell is in fact sending
> a message to that cell carrying two items, the new value and a
> return channel that is used to inform the writer that sending
> has succeeded, and likewise for reading.

This is completely wrong.  A few machines have a simple model like
that, but they were all built in the last century.  Nowadays, writing
to memory is more like broadcasting a message and having no idea when
it will arrive at each destination.  And if you write to another piece
of memory, you don't know in what order the updates will become
visible to a given processor.

You are neglecting a very important parameter, which is called the
"memory model" of your multiprocessor.

-- Damien

Re: [Caml-list] Re: Where's my non-classical shared memory concurrency technology?

[Jon Harrop]

On Monday 26 May 2008 16:29:53 Damien Doligez wrote:
> On 2008-05-21, at 10:06, Martin Berger wrote:
> > Here I disagree. Shared  memory concurrency is a specific form
> > of message passing: Writing to a memory cell is in fact sending
> > a message to that cell carrying two items, the new value and a
> > return channel that is used to inform the writer that sending
> > has succeeded, and likewise for reading.
>
> This is completely wrong.  A few machines have a simple model like
> that, but they were all built in the last century.  Nowadays, writing
> to memory is more like broadcasting a message and having no idea when
> it will arrive at each destination.  And if you write to another piece
> of memory, you don't know in what order the updates will become
> visible to a given processor.
>
> You are neglecting a very important parameter, which is called the
> "memory model" of your multiprocessor.

The memory model of a multiprocessor is just a specific form of communication 
fabric. That does not disagree with Martin's statement. So he was certainly 
not "completely wrong". At worst it was a simplification. I suspect he simply 
did not aticipate anyone treating his comment as a seminal work on multicore 
computing.

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/products/?e

Re: [Caml-list] Re: Where's my non-classical shared memory concurrency technology?

[Martin Berger]

>> Here I disagree. Shared  memory concurrency is a specific form
>> of message passing: Writing to a memory cell is in fact sending
>> a message to that cell carrying two items, the new value and a
>> return channel that is used to inform the writer that sending
>> has succeeded, and likewise for reading.
> 
> This is completely wrong.  A few machines have a simple model like
> that, but they were all built in the last century.  Nowadays, writing
> to memory is more like broadcasting a message and having no idea when
> it will arrive at each destination.  And if you write to another piece
> of memory, you don't know in what order the updates will become
> visible to a given processor.
> 
> You are neglecting a very important parameter, which is called the
> "memory model" of your multiprocessor.

But broadcasting is a form of message-passing too! I was not
forgetting the memory model, I was just arguing at a higher
level of abstraction. Moreover, asynchronous message-passing,
which is the dominant for of message passing studied in concurrency
theory, doesn't make guarantees about the order of communication.

Exactly what kind of message passing is appropriate depends on
the used processors and on the chosen level of abstraction.

Martin

Re: [Caml-list] Re: Where's my non-classical shared memory concurrency technology?

[Damien Doligez]

On 2008-05-27, at 11:34, Martin Berger wrote:

>>> Here I disagree. Shared  memory concurrency is a specific form
>>> of message passing: Writing to a memory cell is in fact sending
>>> a message to that cell carrying two items, the new value and a
>>> return channel that is used to inform the writer that sending
>>> has succeeded, and likewise for reading.
>>
>
[...]
>
> But broadcasting is a form of message-passing too!

That wasn't my point.  My point was that there is no return channel.
If you want to know when your write is done, you have to use a lock
or a memory barrier.  Both are very expensive.

-- Damien

Re: [Caml-list] Re: Where's my non-classical shared memory concurrency technology?

[Jon Harrop]

On Wednesday 28 May 2008 12:18:37 Damien Doligez wrote:
> On 2008-05-27, at 11:34, Martin Berger wrote:
> >>> Here I disagree. Shared  memory concurrency is a specific form
> >>> of message passing: Writing to a memory cell is in fact sending
> >>> a message to that cell carrying two items, the new value and a
> >>> return channel that is used to inform the writer that sending
> >>> has succeeded, and likewise for reading.
>
> [...]
>
> > But broadcasting is a form of message-passing too!
>
> That wasn't my point.  My point was that there is no return channel.
> If you want to know when your write is done, you have to use a lock
> or a memory barrier.  Both are very expensive.

Very expensive compared to what?

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/products/?e

Re: [Caml-list] Re: Where's my non-classical shared memory concurrency technology?

[Martin Berger]

>> But broadcasting is a form of message-passing too!
> 
> That wasn't my point.  My point was that there is no return channel.
> If you want to know when your write is done, you have to use a lock
> or a memory barrier.  Both are very expensive.

As I said, it's a matter of abstraction level. My point is:
you can model both abstraction levels with message passing.

Moreover, using shared memory doesn't magically make these
synchronisation issues go away. They remain.

Martin

Re: [Caml-list] Re: Where's my non-classical shared memory concurrency technology?

[Frédéric Gava]

> That wasn't my point.  My point was that there is no return channel.
> If you want to know when your write is done, you have to use a lock
> or a memory barrier.  Both are very expensive.

Barriers of synchronisation are a little expensive (one of the main 
drawbacks with a too restricted way of communication) but have many
advantages as deadlock free and possibility to optimized the 
"communications" (copy of the data in the shared memory or juste the 
pointer).

FG