How does shared memory vs message passing handle l

Question

In looking at Go and Erlang's approach to concurrency, I noticed that they both rely on message passing.

This approach obviously alleviates the need for complex locks because there is no shared state.

However, consider the case of many clients wanting parallel read-only access to a single large data structure in memory -- like a suffix array.

My questions:

• Will using shared state be faster and use less memory than message passing, as locks will mostly be unnecessary because the data is read-only, and only needs to exist in a single location?

• How would this problem be approached in a message passing context? Would there be a single process with access to the data structure and clients would simply need to sequentially request data from it? Or, if possible, would the data be chunked to create several processes that hold chunks?

• Given the architecture of modern CPUs & memory, is there much difference between the two solutions -- i.e., can shared memory be read in parallel by multiple cores -- meaning there is no hardware bottleneck that would otherwise make both implementations roughly perform the same?

Answer 1

The problem at the moment is indeed that the locking and cache-line coherency might be as expensive as copying a simpler data structure (e.g. a few hundred bytes).

Most of the time a clever written new multi-threaded algorithm that tries to eliminate most of the locking will always be faster - and a lot faster with modern lock-free data structures. Especially when you have well designed cache systems like Sun's Niagara chip level multi-threading.

If your system/problem is not easily broken down into a few and simple data accesses then you have a problem. And not all problems can be solved by message passing. This is why there are still some Itanium based super computers sold because they have terabyte of shared RAM and up to 128 CPU's working on the same shared memory. They are an order of magnitude more expensive then a mainstream x86 cluster with the same CPU power but you don't need to break down your data.

Another reason not mentioned so far is that programs can become much easier to write and maintain when you use multi-threading. Message passing and the shared nothing approach makes it even more maintainable.

As an example, Erlang was never designed to make things faster but instead use a large number of threads to structure complex data and event flows.

I guess this was one of the main points in the design. In the web world of google you usually don't care about performance - as long as it can run in parallel in the cloud. And with message passing you ideally can just add more computers without changing the source code.

Answer 2

Usually message passing languages (this is especially easy in erlang, since it has immutable variables) optimise away the actual data copying between the processes (of course local processes only: you'll want to think your network distribution pattern wisely), so this isn't much an issue.

Answer 3

What is a large data structure?

One persons large is another persons small.

Last week I talked to two people - one person was making embedded devices he used the word "large" - I asked him what it meant - he say over 256 KBytes - later in the same week a guy was talking about media distribution - he used the word "large" I asked him what he meant - he thought for a bit and said "won't fit on one machine" say 20-100 TBytes

In Erlang terms "large" could mean "won't fit into RAM" - so with 4 GBytes of RAM data structures > 100 MBytes might be considered large - copying a 500 MBytes data structure might be a problem. Copying small data structures (say < 10 MBytes) is never a problem in Erlang.

Really large data structures (i.e. ones that won't fit on one machine) have to be copied and "striped" over several machines.

So I guess you have the following:

Small data structures are no problem - since they are small data processing times are fast, copying is fast and so on (just because they are small)

Big data structures are a problem - because they don't fit on one machine - so copying is essential.

Answer 4

The other concurrent paradigm is STM, software transactional memory. Clojure's ref's are getting a lot of attention. Tim Bray has a good series exploring erlang and clojure's concurrent mechanisms

http://www.tbray.org/ongoing/When/200x/2009/09/27/Concur-dot-next

http://www.tbray.org/ongoing/When/200x/2009/12/01/Clojure-Theses

Answer 5

Note that your questions are technically non-sensical because message passing can use shared state so I shall assume that you mean message passing with deep copying to avoid shared state (as Erlang currently does).

Will using shared state be faster and use less memory than message passing, as locks will mostly be unnecessary because the data is read-only, and only needs to exist in a single location?

Using shared state will be a lot faster.

How would this problem be approached in a message passing context? Would there be a single process with access to the data structure and clients would simply need to sequentially request data from it? Or, if possible, would the data be chunked to create several processes that hold chunks?

Either approach can be used.

Given the architecture of modern CPUs & memory, is there much difference between the two solutions -- i.e., can shared memory be read in parallel by multiple cores -- meaning there is no hardware bottleneck that would otherwise make both implementations roughly perform the same?

Copying is cache unfriendly and, therefore, destroys scalability on multicores because it worsens contention for the shared resource that is main memory.

Ultimately, Erlang-style message passing is designed for concurrent programming whereas your questions about throughput performance are really aimed at parallel programming. These are two quite different subjects and the overlap between them is tiny in practice. Specifically, latency is typically just as important as throughput in the context of concurrent programming and Erlang-style message passing is a great way to achieve desirable latency profiles (i.e. consistently low latencies). The problem with shared memory then is not so much synchronization among readers and writers but low-latency memory management.

Answer 6

One thing to realise is that the Erlang concurrency model does NOT really specify that the data in messages must be copied between processes, it states that sending messages is the only way to communicate and that there is no shared state. As all data is immutable, which is fundamental, then an implementation may very well not copy the data but just send a reference to it. Or may use a combination of both methods. As always, there is no best solution and there are trade-offs to be made when choosing how to do it.

The BEAM uses copying, except for large binaries where it sends a reference.