7 ms·

Parallel Map in Elixir

• rdtsc 12y ago
  Elixir is great. It is built on an awesome industrial grade, battle tested VM with really unique features like lightweight but memory safe processes. Has a friendly syntax (although I personally like Erlang's syntax). Another great thing about Elixir is the community -- it is helpful, friendly, oriented for learning and newcomers. Also Jose Valim is really an incredible guy.
  • davidw 12y ago
    I'm really surprised at how fast the Elixir folks are moving. They're building all kinds of stuff that took Erlang a long time to get. First and foremost the Phoenix web framework.
    • dpeck 12y ago
      I've been deep in elixir for about the last 4 months and ventured into erlang a bit to go with it, and its seems like the metaprogramming possible in elixir is the game changer with regard to speed of development and growth of things like phoenix.
    • yellowapple 12y ago
      It helps that Erlang already did the heavy lifting for us Elixir folks (or what heavy lifting wasn't already done was then done by Valim and friends in Elixir, Plug, Ecto, etc.). A pretty hefty amount of Elixir code (including most frameworks, like Phoenix, Sugar, Weber, etc.) leverages the same old Erlang/OTP, just with some funny-looking (in some cases better, in some cases perhaps worse, depending on perspective) syntax and Plug. Even the dominant web server in the Elixir realm - Cowboy - is actually entirely written in Erlang. Compatibility with existing Erlang code (and vice versa) makes for fewer wheels being reinvented. It also helps that Elixir came about right around the time when folks were starting to realize that this old telecom language called "Erlang" might actually be precisely what we need for modern web development, hence why web frameworks ended up evolving pretty quickly relative to Erlang (which also saw a growth in available web frameworks at around the same time; Chicago Boss is a particularly-excellent example).
  • vezzy-fnord 12y ago
    I personally experience Elixir's syntax to be quite deceptive in that, for me personally, it lures me into assuming Ruby semantics and this just makes it feel uncanny. It feels noisier in general and as if I lose some of the homoiconic feeling I get from Erlang where matching on literal data types is essential and can lead to very concise code. I know that a lot of people find Erlang's syntax to be a pain point (I don't, I actually like it), but as a unique language it helps to have a fitting syntax that's easy on the mind for context switching to and from. And I'd say it's quite perfectly optimized for a language whose backbone is terms, processes and pattern matching. It's also far less learning than most other functional languages, quite frankly. It probably has a lot to do with its culture that sees the FP aspect as a tool that fits into the paradigm of solving engineering problems related to high availability distributed systems, rather than FP being the end itself, although we need both kinds of languages. But hey, anything to get BEAM into the spotlight is probably a good thing. I'd just prefer if it was pure Erlang.
    • davidw 12y ago
      > It's also far less learning than most other functional languages, quite frankly. The type system is pretty recognizable to most people, unlike something like Haskell where it's a big part of learning the language.
  • scandox 12y ago
    Agreed: Jose Valim does an incredible amount of work responding to people and engaging with the community. I am amazed at all the different levels of questions he takes the time to address.
  • fiatjaf 12y ago
    I don't know what is a "paralell map", and also don't know Erlang, but I like it. In general Erlang's syntax seem much better, much cleaner: http://rosetta.alhur.es/compare/erlang/elixir/ http://rosetta.alhur.es/compare/erlang/elixir/
• Ono-Sendai 12y ago
  Looks somewhat ugly and also slow. (each element is processed in a separate process)
  • bismark 12y ago
    These are Erlang VM processes which are actually quite fast. Re ugly: well, eye of the beholder I suppose.
    • Ono-Sendai 12y ago
      Here's a map in my functional language (winter). It's not parallel yet, that shouldn't affect the syntax though. (map is already manifestly parallel) def square(float x) float : x*x def main(array<float, 256> a) array<float, 256> : map(square, a)
      • nine_k 12y ago
        Now make it efficiently parallel and show us the implementation. Then we could compare it with the Elixir snippet, which does just that.
        • DoggettCK 12y ago
          Not just efficiently parallel, but easily distributable to multiple nodes.
          • scandox 12y ago
            Exactly. With a tiny change you can be spawning those processes to any number of other nodes.
      • kbenson 12y ago
        Well, if we are putting forth other languages, here's Perl 6: sub pmap(Code $func, @items) { return await @items.map: { start { $func($_) } } }
  • 12y ago
• davidw 12y ago
  Erlang actually has this in the rpc module, in the standard library: http://erlang.org/doc/man/rpc.html#pmap-3 http://erlang.org/doc/man/rpc.html#pmap-3 So you could call that from Elixir if you wanted.
  • phamilton 12y ago
    One difference is that the Enum library works on anything that implements Enumerable. rpc.pmap only works on lists.
• sirclueless 12y ago
  Is this piece of code idiomatic Elixir/Erlang? receive do { ^pid, result } -> result end Without looking up what the "receive" procedure does, it suggests that the current ("main"?) process is going to block waiting for an incoming message that matches the pattern. Done in a loop as I presume the Enum.map function does, it looks like the main process might be blocked waiting for the matching message while some internal mailbox fills up. In the worst case I would expect this to have an O(n^2) running time unless there is something fancy going on when pattern matching against a full mailbox. Please correct me if I'm wrong. This looks elegant, but I would expect it to be considerably less performant than, say, the equivalent Go program which would issue a select on a channel of incoming messages, thus only blocking until any message is received, rather than a specific message in series.
  • johnzim 12y ago
    Not the case here, my friend. From the horse's mouth: "Each process has its own input queue for messages it receives. New messages received are put at the end of the queue. When a process executes a receive, the first message in the queue is matched against the first pattern in the receive, if this matches, the message is removed from the queue and the actions corresponding to the the pattern are executed. However, if the first pattern does not match, the second pattern is tested, if this matches the message is removed from the queue and the actions corresponding to the second pattern are executed. If the second pattern does not match the third is tried and so on until there are no more pattern to test. If there are no more patterns to test, the first message is kept in the queue and we try the second message instead. If this matches any pattern, the appropriate actions are executed and the second message is removed from the queue (keeping the first message and any other messages in the queue). If the second message does not match we try the third message and so on until we reach the end of the queue. If we reach the end of the queue, the process blocks (stops execution) and waits until a new message is received and this procedure is repeated." The Erlang VM accomplishes this by providing computation credits to each process, which are spent to perform actions ensuring the complete, non-blocking, parallel system that guzzles information at a startling rate all over the globe as we type this :)
    • 12y ago
• RootDynasty 12y ago
  Here is another cool version of parallel map in Erlang that uses a fold instead of two parallel maps. parallel_map(Fun, List) -> Last = lists:foldl(fun(Value, Parent) -> spawn(fun() -> MappedValue = Fun(Value), receive Rest -> Parent ! [MappedValue|Rest] end end) end, self(), List), Last ! [], receive Result -> Result end. It essentially sets up a chain of processes which pass their results to their parent when they finish their mapping operation.
  • mononcqc 12y ago
    This implementation does rely on a lot of memory copying going on there. Rather than copying the original element to the new process, then the new mapped element back to the original process (giving you the original list's worth of memory copied twice), you'll be copying each list element once to every worker you spawn, and then you'll copy the parts of the list worked on to the next worker, on and on, until the full list is finally copied back to the caller. So instead of copying 2n elements over the processes, you'll be copying roughly 2nlogn (or is it n(n+1)/2 ?) elements around.
    • RootDynasty 12y ago
      One thing to note is that the the parallel map consisting of two mapping operations has a different hidden overhead. If a message is received by a process that does not pattern match with any clauses in the receive block, the message is stored in a queue. When a new receive block is entered, all messages in the queue are pattern matched against the new receive block. In the worst case scenario, the worker process mapping the elements will finish in list order, so a great many pattern matches will be tried. The solution to this problem is just to store messages as they are received inside of a map data structure, so that there is no overhead for receives. This requires indexing the list which makes the code a lot more inelegant. Edit: Given n processors and an input of size n, I believe the time complexities are: Two map solution: O(n^2)+O(f) Fold solution: O(n^2)+O(f) Two map with map data structure: O(n)+O(f) Where O(f) is the asymptotic upper bound of the function being mapped Edit 2: This has me thinking about what will be the most efficient way to assign an element from the list to worker processes. In Erlang, it's clear that there isn't a way to avoid the O(n) overhead since the original process must reconstruct the list in order using cons. In an imperative language this isn't necessary. Perhaps the original process can recursively assign indicies by spawning two children worker processes which are given a range of indicies to work on (who then create their own assignment processes). I believe the overhead is then only O(log n)...
• psylence519 12y ago
  Seems silly to use the pipe to feed the collection into the first map call. Otherwise pretty nifty, I’ve been enjoying learning Elixir the last few months.
• Aarvay 12y ago
  When choosing to apply parallelism, it should never be about the length of the collection but only the computational intensity of the function that's being applied. There's a considerable overhead in spawning processes and collecting the result from them
  • ismaelga 12y ago
    There's a considerable overhead unless they are _lightweight_ processes.
• deleted 12y ago
  [deleted]
• rvirding 12y ago
  They don't handle errors very well.
• wz1000 12y ago
  Here is a parallel map in Haskell pmap f xs = map f xs `using` parList rdeepseq The cool thing about this is that `map` is just the regular map function. However, as Haskell is lazy, `map f xs` returns a thunk and is not immediately evaluated. `using` allows you to evaluate the resultant thunk using any "evaluation strategy", and `parList rdeepseq` describes a strategy for evaluating lists in parallel! Also, like the Erlang VM, GHC has fast, lightweight "green threads". Edit: Another way to write it would be pmap _ [] = [] pmap f (x:xs) = runEval $ do x' <- rpar (f x) xs' <- rpar (pmap f xs) return $ (x':xs')
• deleted 12y ago
  [deleted]
• xfalcox 12y ago
  Any recomendations on Elixir learning resources?
  • scandox 12y ago
    Dave Thomas' book is an easy read: https://pragprog.com/book/elixir/programming-elixir https://pragprog.com/book/elixir/programming-elixir