5 ms·

Message passing is fantastic... when you can decompose your problem into lots of small, independent jobs, like a web server. However not many algorithms are lik

Message passing is fantastic... when you can decompose your problem into lots of small, independent jobs, like a web server. However not many algorithms are like that. If you can't decompose your problem into small independent jobs then you will be left with some kind of shared job. For example, an airline seat booking system, where at some point you need to modify a shared set of seat states (no, you can't divide the seat state up, because then you can't take massive bookings if needed). Another example is sorting algorithms. If you divide and conquer, at some point you need to combine results. In Erlang, the normal way to do this is to have a single actor handled that shared job. That then becomes a huge bottleneck, and with more cores it gets to be more and more of a bottleneck. This is Amdahl's law. This is where Erlang breaks. In a language with shared state (that includes Haskell or ML with mutable references) I can use very fine grained locks, or perhaps transactional memory, over this shared part of the problem, and continue to scale beyond what Erlang was capable of. Probably not near n-times for n cores, but much closer than what Erlang would allow. Erlang's message passing creates bottlenecks! And then there's no way out. In shared state you can be nice and message passing, but then also have the power to use very fine grained locks or TM to break down those bottlenecks.

DennisP 14y ago
Sorting algorithms? Let's take mergesort, for example. In Erlang a process could divide its portion of the collection in half, hand each half to another process, wait for two sorted collections to come back, merge them and pass the results up the chain. Conceptually simple and good multicore use. The only time you're down to a single core is on the final merge, between two sorted halves of the whole collection. The merge is an inherently sequential process. Are you claiming that somehow you can merge two sorted arrays in parallel using fine-grained locks? How exactly?
- johndonsp 14y ago
  No, the parallelism in that algorithm is fundamentally limited. That bottleneck is not going away, and was an example of where neither Erlang nor any other model of parallelism will help you. Do you have any good ideas about how I can solve the seat booking example using Erlang's model of parallelism? There is a block of seats. I want to be able to handle seat bookings in parallel. The seats that people might want to book could be in large groups - as large as all of the seats.
  - silentbicycle 14y ago
    You shouldn't, you should use Erlang's model of having a single process ultimately manage the state make implementing transactions easy. Several processes can concurrently try to reserve seats, but ultimately they all have to get in line and submit their reservations, receiving either e.g. {ok, NewState} or {conflict, NewState}.
    - johndonsp 14y ago
      That's the limitation of Erlang, right there. They get in line, creating a bottleneck. You could have 10,000 Erlang processes, but they all wait in line for this one process to service them. If you use transactional memory with threads and mutable state, then all your booking processes can access the board state in parallel with ACI properties. Obviously, parallelism is still limited, as it always it, but as long as your booking processes are accessing different parts of the seat data structure, they can run in parallel. If they try to access the same part of the structure at the same time, all but one will be rolled back, but that one still gets through. Hopefully, they access different parts of the structure and sail through. Your suggested Erlang program has no parallelism in it at all (for the isolated part of the seat booking of course), and will not scale to 2 cores, let alone the 64 cores I have in my machines at work.
      - silentbicycle 14y ago
        Erlang is not about parallelism, it's about fault tolerance. It's about "making reliable distributed systems in the presence of software errors" (as Armstrong's thesis is titled). How will your STM example behave if the computer managing the transactions suddenly has a massive hardware failure?
        johndonsp 14y ago
        I completely agree with you about fault-tolerance. However Erlang, CSP, actors and message passing are heralded as the key to parallelism. The Erlang book still promises n-times speedup for n-cores, with not enough of a caveat.
jlouis 14y ago
Here are some ideas for your two problems. First, the problem is sorting. One very efficient algorithm is to utilize a parallel sampling sort algorithm. The idea is to start off P processes and sampling randomly to obtain P-1 splitting elements. Then the Array of P-1 splitters are distributed to each of the P processes and input data is now sent around so each processor has its batch of data. Next, each process sorts its own batch. It turns out to be pretty fast in practice to run this kind of operation and it may be fast enough. Note the distinct advantage of message passing here: It works, even if a process is running on another physical machine - shared memory doesn't. Also note that Erlang is not really built for parallel computation, and your example is one. My guess is that you can achieve a pretty good speedup with a sampling sort variant on multiple cores. As for your flight seat problem, it really isn't. Keep the state of a plane in a process. That is have a single process assigning seats in the plane. On very large planes you may have 500-1000 seats. Hardly something which will dwarf a single process. Chances are, however, that you may want to assign seats to multiple planes at the same time. In that case you get your concurrency and a possible speedup. As for getting linear speedup in Erlang systems: First, your problem must expose the necessary amount of work. That is, there must always be something to do for an idle processor. In Erlang, this is easy to achieve if there are multiple agents interacting with the system at the same time, or you can create it yourself by spawning off some processes for each incoming job. Second, your program must avoid contention around a single process. That is, you must ensure processors are not all looking for the same resource. We have tools like percept, the lock counter and dtrace for that. An Erlang process works very much like transactional memory if written correctly. But TM has the same problem: contend around a resource and you are in trouble. It might be that the breaking point for contention is different due to different characteristics in overhead, but in principle the contention problem is also there. Finally, there is a "cheating" possibility. Erlang provides ETS which is a tuple space for erlang terms. It allows parallel read and write access outside the process context. And very fast such RW access. For certain problems it can be used to allow multiple processes read access to the same data which can in turn speed their work up considerably. But ETS is not distributed, oh the horror! Enter mnesia, which distributes ETS over multiple machines and optionally provides persistence. Mnesia is really a memcached/redis distributed in memory key/value store with DB-like query properties. Limited - but oh so powerful for certain problems.
theatrus2 14y ago
Akka (Scala actor library on the JVM) allows for STM on multiple actor states.

DennisP 14y ago

Sorting algorithms? Let's take mergesort, for example. In Erlang a process could divide its portion of the collection in half, hand each half to another process, wait for two sorted collections to come back, merge them and pass the results up the chain. Conceptually simple and good multicore use. The only time you're down to a single core is on the final merge, between two sorted halves of the whole collection. The merge is an inherently sequential process. Are you claiming that somehow you can merge two sorted arrays in parallel using fine-grained locks? How exactly?

johndonsp 14y ago
No, the parallelism in that algorithm is fundamentally limited. That bottleneck is not going away, and was an example of where neither Erlang nor any other model of parallelism will help you. Do you have any good ideas about how I can solve the seat booking example using Erlang's model of parallelism? There is a block of seats. I want to be able to handle seat bookings in parallel. The seats that people might want to book could be in large groups - as large as all of the seats.
- silentbicycle 14y ago
  You shouldn't, you should use Erlang's model of having a single process ultimately manage the state make implementing transactions easy. Several processes can concurrently try to reserve seats, but ultimately they all have to get in line and submit their reservations, receiving either e.g. {ok, NewState} or {conflict, NewState}.
  - johndonsp 14y ago
    That's the limitation of Erlang, right there. They get in line, creating a bottleneck. You could have 10,000 Erlang processes, but they all wait in line for this one process to service them. If you use transactional memory with threads and mutable state, then all your booking processes can access the board state in parallel with ACI properties. Obviously, parallelism is still limited, as it always it, but as long as your booking processes are accessing different parts of the seat data structure, they can run in parallel. If they try to access the same part of the structure at the same time, all but one will be rolled back, but that one still gets through. Hopefully, they access different parts of the structure and sail through. Your suggested Erlang program has no parallelism in it at all (for the isolated part of the seat booking of course), and will not scale to 2 cores, let alone the 64 cores I have in my machines at work.
    - silentbicycle 14y ago
      Erlang is not about parallelism, it's about fault tolerance. It's about "making reliable distributed systems in the presence of software errors" (as Armstrong's thesis is titled). How will your STM example behave if the computer managing the transactions suddenly has a massive hardware failure?
      - johndonsp 14y ago
        I completely agree with you about fault-tolerance. However Erlang, CSP, actors and message passing are heralded as the key to parallelism. The Erlang book still promises n-times speedup for n-cores, with not enough of a caveat.

jlouis 14y ago

Here are some ideas for your two problems. First, the problem is sorting. One very efficient algorithm is to utilize a parallel sampling sort algorithm. The idea is to start off P processes and sampling randomly to obtain P-1 splitting elements. Then the Array of P-1 splitters are distributed to each of the P processes and input data is now sent around so each processor has its batch of data. Next, each process sorts its own batch. It turns out to be pretty fast in practice to run this kind of operation and it may be fast enough. Note the distinct advantage of message passing here: It works, even if a process is running on another physical machine - shared memory doesn't. Also note that Erlang is not really built for parallel computation, and your example is one. My guess is that you can achieve a pretty good speedup with a sampling sort variant on multiple cores. As for your flight seat problem, it really isn't. Keep the state of a plane in a process. That is have a single process assigning seats in the plane. On very large planes you may have 500-1000 seats. Hardly something which will dwarf a single process. Chances are, however, that you may want to assign seats to multiple planes at the same time. In that case you get your concurrency and a possible speedup. As for getting linear speedup in Erlang systems: First, your problem must expose the necessary amount of work. That is, there must always be something to do for an idle processor. In Erlang, this is easy to achieve if there are multiple agents interacting with the system at the same time, or you can create it yourself by spawning off some processes for each incoming job. Second, your program must avoid contention around a single process. That is, you must ensure processors are not all looking for the same resource. We have tools like percept, the lock counter and dtrace for that. An Erlang process works very much like transactional memory if written correctly. But TM has the same problem: contend around a resource and you are in trouble. It might be that the breaking point for contention is different due to different characteristics in overhead, but in principle the contention problem is also there. Finally, there is a "cheating" possibility. Erlang provides ETS which is a tuple space for erlang terms. It allows parallel read and write access outside the process context. And very fast such RW access. For certain problems it can be used to allow multiple processes read access to the same data which can in turn speed their work up considerably. But ETS is not distributed, oh the horror! Enter mnesia, which distributes ETS over multiple machines and optionally provides persistence. Mnesia is really a memcached/redis distributed in memory key/value store with DB-like query properties. Limited - but oh so powerful for certain problems.

theatrus2 14y ago

Akka (Scala actor library on the JVM) allows for STM on multiple actor states.