Hacker News Reader

Comment by sirclueless | Hacker News Reader

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.

View on HN

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 :)

Please correct me, but as best I can tell, the Enum.map will, sequentially, start the first receive, and that receive will operate against every incoming message until ^pid matches, adding its result as the first member of the collection while the unmatched messages accumulate in the mailbox; then it will do the second receive, which will scan the mailbox for its ^pid, and either find it or wait until the matching message arrives, adding its result as the second member of the collection; then it will do the third receive, etc. Assuming a random distribution of message arrivals, the last message to arrive will on average be the n/2 message, so for (on average) n/2 messages, the n/2 length mailbox (full of the (n/2) through n messages) will need to be scanned n/2 times, e.g., O(n*n). There might be some way to reduce the mailbox scanning time to O(1), but my shallow dive in the source code didn't show it.

Since the reason for the 'waiting till the one with the right order to come in' behaviour is the use of ^pid, presumably you could get rid of mailbox scanning time by getting rid of the caret (matching any message), so the mailbox never has >1 message.

This means you get results filling up the array in the order they come rather than the original order, but if order's important, you can always pass around an index and sort by that after the fact.

Now, this suggests that messages that aren't handled will build up over time?

Yes, but pretty much by definition a message that isn't handled is almost certainly a bug.

I haven't been doing Erlang or Elixir recently so I may be missing something, but I think that's destructuring, not selection (Erlang/Elixir supports selective receive, but the pattern there -- a source pid and message with no assertions as to structure -- is, IIRC, whatever everything deliver to an erlang processes mailbox looks like.)

Reply on news.ycombinator.com