[erlang-questions] Representation of a map in bytecode?

[Hugh Perkins]

On 9/18/07, Robert Virding <rvirding@REDACTED> wrote:
> There is another problem with automatic parallelisation and Erlang. As
> Erlang DOES have side-effects, message passing basically, the order in which
> things are evaluated is significant.

Hmmm, interesting.  Good point.

>  In the Barklund spec, which you helped write, it states clearly that the
only order which is specified is that of expressions in a body. In an
example, (X=8) + (X=9) is used to illustrate how the evaluation order can
cause different run-time behavior(*), whereas the compiler accepts it, since
all possible orders are valid at compile-time. (Chapter 6.5)

Hmmm, interesting too. So, is the order of execution of lists:map
guaranteed to proceed always in a certain order?

> Erlang DOES have side-effects, message passing basically

Apart from io:format, are there any other side-effects possible in Erlang?

Could one use a kindof MapReduce implementation where a map is
evaluated as following:
- incoming list to map split into n sub-lists, where n is number of
available cores (eg on 64-core machine, if 17 cores are free at moment
of execution of map, n = 17)
- map run in n child processes, with one sub-list given to each process
- any outgoing messages are cached temporarily
- once all the child processes are finished, the messages are sent to
their targets, in order (this is the "Reduce" part of the MapReduce
implementation)

Presumably, one could do the same thing for any io:formats too actually?

Of course, another approach could be to use Haskell style monads to
ensure purity, but Haskell has a number of other issues, such as lack
of a vm.

(By the way, just to clarify, in answer to objections such as:

> If a system already is parallellized
into e.g. one Erlang process per connection in a web-server, one
Erlang process per ongoing call in a telecom system etc. there is very
little reason trying to parallellize each map if there are thousands
of call or connection processes
executing simultaneously and that each of those potentially will
perform a map operation as part of their work.

I'm not really good at communication :-) so it's not really obvious in
my proposition, but when I say "number of available cores", I dont
mean the total number of cores on the system, I mean the number of
available cores *at the time of execution of the map*.

For example, example 1, imagine our program looks like this:

dosomething(Max) -> lists:map( fun blah/1, [1..Max] ).

Imagine we're running on a 64-core machine.

At the time of execution of the map, there is a single process
running, this one, and 63 other cores free, so there are a total of 64
cores available to the map.

So, the list will be split into chunks of about (Max / 64 ) elements.

Now, example 2, imagine our program is a webserver (your example), and
the webpage runs a map.

Example 2b, lets say there are 98 requests currently being handled, so
at least 98 processes running.  All 64 cores are in use.  When we
reach the map statement, we dont bother to split it into chunks,
there's no point, as you say.

Example 2b, lets say there is 1 request currently being handled, plus
our new request.  The request currently being handled is using 54
cores (lets say), so there are 10 cores free.

Now, when we reach our map statement, it makes sense to split the map
across the 10 available cores.

Of course, the chunking will never be perfect, but its' really easy to
do, and transparent to the programmer (in the absence of side-effects,
but see above for mapreduce approach, or maybe use monads).  It's
generally going to be fairly optimal compared to static approaches,
such as SPJ's NDP, or hard-coding directly by the programmer?