Sync’ up! … without getting drained

aug 26

Two Erlang patterns I love

Although there are probably a dozen patterns in Erlang that I love dearly, there are two that I consider my darlings.

Now, these patterns are truly two sides of the same coin, but each do have their specific applications and aren’t used interchangeably.

But first, some background.

Joe’s first book

Joe Armstrong’s first book has these patterns laid out, but because they are textbook Erlang (not OTP), they don’t get a lot of sunlight. What do I mean by textbook Erlang? Well, code that uses the bare mechanics of the language/beam; an approach somewhat discouraged in the Erlang/OTP world, as it means it’s a loose solution, and that you’ll have to be careful when using it.

Generally, any time you’re not using ‘gen_server’ or the other behaviors, you’re potentially opening yourself up to unexpected pitfalls.

But, all the same, sometimes you have to roll your own. And with the ‘K-hunt-gather’ and the ‘O-hunt-gather’ patterns, I generally plow ahead with confidence.

Goals

Both these patterns have the goal to take a numerable amount of identical work, and spread it around to Erlang’s lightweight processes to perform. This first part, is the ‘hunt’ half of the pattern.

The second, and albeit less code intensive half of these patterns, is to ‘gather.’ This, as you might imagine, is just part of the mechanics that collects the results of all the various work, and simply stuffs it all, typically, in a list. A list of yielded results.

Why do this?

Erlang is a concurrency-oriented language. When there’s work that can be marshalled out, Erlang makes it so easy to do this all reliably.

Say you have a routine that takes a while to do some work. Well, there’s the bottleneck for any approach that would take this on sequentially. If there’s just one work-load to do, then, hey, all languages are equally good at tackling it — some faster than others. But if there are ‘K’ work-loads to do, then a sequential approach is terrible, compared to a concurrent one.

Let’s first take a look at the simpler of the two: ‘K-hunt-gather.’

‘K-hunt-gather’

In a dummy ‘foo’ module, here is a bare-bones version of this concurrent work-marshaling pattern:

-module(foo).

-export([start/0]).

start() ->
    Work = lists:seq(1, 999), % N.B. proxy for a list of actual data
    K = erlang:length(Work),
    hunt(Work),
    gather(K, []).

hunt(L) ->
    Parent = erlang:self(),
    Fn = fun faux_expensive_routine/2,
    [ spawn(fun() -> Fn(Parent, X) end) || X <- L ].

gather(0, Acc) -> Acc;
gather(K, Acc) ->
    receive
        {bounty, R} -> gather(K - 1, [ R | Acc ])
    end.

faux_expensive_routine(Parent, _X) ->
    timer:sleep(3000),
    R = gathered, % N.B. usually do something with _X
    Parent ! {bounty, R}.

Working backward, the ‘faux_expensive_routine/2’ is where the bottleneck resides, and if we were to use a sequential approach, then the duration of this work-load would be ‘K’ — or 999 — times three seconds. I ran out of napkins, so I don’t know what that works out to be, but I know it’s slower than the speed of our concurrent version, which will be around three seconds.

The ‘start/0’ routine is the parent process, and it spawns the work to 999 processes and then waits for them all to finish. The waiting all happens in the call to the ‘gather/2’ routine where in the beefier clause, uses the ‘receive’ primative to wait for messages. It will just hang out there until it begins to receive mail from the 999 processes. When a certain criteria is met, it jumps out of the recursiveness, and just yields the accumulator — the first clause of the ‘gather/2’ routine.

In the case of the ‘K-hunt-gather’ pattern, the accumulation stops when ‘K’ counter has been reduced to zero. It should be noted, spawned process 877 could beat process 701. But with this version of the pattern, we don’t care about the final order of the stateless work-load.

(in the ‘O-hunt-gather’ version that follows, it will preserve the ordering).

For such a small chunk of source-code, there is so much of Erlang’s power being showcased: tail-recursion, spawning of processes, message passing, closures (called funs), to identify the more interesting ones. That’s why I love these patterns. But let’s look at the more complicated of the two before getting too excited.

‘O-hunt-gather’

I use this pattern an order of magnitude less than his brother, but there are times when nothing else will do. As forementioned, this pattern preserves the yield-order, in the same sequence it was created. To be clear, when iterated over the work via a list comprehension (a foreach in some other languages), the ‘K-hunt-gather’ pattern lost control as soon as it spawned it all up. Here, we use Erlang’s esoteric ‘selective receive’ feature to preserve the order, and do so, without much effort.

Here’s the code:

-module(bar).

-export([start/0]).
-export([letters/2]) % N.B. MFA export

start() ->
    Us = [a, b, c, d, e, f],
    Pids = hunt(Us),
    gather(Pids).

hunt(As) ->
    U = erlang:self(),
    [ spawn(bar, letters, [U, X]) || X <- As ].

gather([]) -> [];
gather([ Pid | T ]) ->
    receive
        {Pid, bounty, U} ->
            [ U | gather(T) ]
    end.

letters(Pid, a) ->
    U = erlang:self(),
    timer:sleep(200),
    Pid ! {U, bounty, <<"a">>};
letters(Pid, A) ->
    U = erlang:self(),
    V = erlang:atom_to_binary(A),
    Pid ! {U, bounty, V}.

Instead of a ‘faux_expensive_routine/2,’ here, we have code that converts a list of atoms (letters) into their binary equivalents. To drive the point home on the ‘O-hunt-gather’ pattern, we put a little snag for the process that has to deal with ‘a’ — that process goes to sleep for a 5th of a second, then behaves as the other normal clause does. We do this to showcase that the ‘O-hunt-gather’ pattern, utilizing ‘selective receive,’ will indeed yield the same ordering list — only a list of bitstrings, not atoms.

Now, in the footnote, you can find the exact mechanics of Erlang’s ‘selective receive,’ but the nickle-tour of it, as it pertains to this post, goes a little something like…

Try to match an incoming message, if can’t be matched, deal with it later.

Imagine: if the letter ‘f’ got finished first, ahead of every other letter, but its associated worker (a Pid, used also as a ordering tag) wasn’t expected yet… So, just put it off until it’s waited its turn.

This isn’t a blocking mechanism, rather, it’s just a queue, whereby eager beavers are just put to the side until the rightful process is collected first.

In a way, this is the more lucid version of the ‘hunt-gather’ patterns, as it just leans of Erlang’s ‘selective receive,’ whereby you don’t have to bother about the details. However, like I indicated, I do use the ‘K-hunt-gather’ the majority of the time.

Wrap-up

Hopefully you can see how these patterns would be useful in any language. And if you’re just getting into OTP, don’t forget that writing textbook Erlang from time to time is a completely viable way forward.

And if there’s one take-away for everyone, I’m hoping it’s this: Erlang is a concurrency-oriented language, and as such, juggling work-loads through code is both trivial, and beautiful.

Footnote

Here is the official breakdown of Erlang’s ‘selective receive’:

  1. When we enter a receive statement, we start a timer (but only if an ‘after’ section is present in the expression)
  2. Take the first message in the mailbox and try to match it against Pattern1, Pattern2, and so on. If the match succeeds, the message is removed from the mailbox, and the expressions following the pattern are evaluated
  3. If none of the patterns in the receive statement matches the first message in the mailbox, then the first message is removed from the mailbox and put into a ‘save queue.’ The second message in the mailbox is then tried. This procedure is repeated until a matching message is found or until all the messages in the mailbox have been examined
  4. If none of the messages in the mailbox matches, then the process is suspended and will be rescheduled for execution the next time a new message is put in the mailbox. Note that when a new message arrives, the messages in the save queue are not rematched; only the new message is matched
  5. As soon as a message has been matched, then all messages that have been put into the save queue are reentered into the mailbox in the order in which they arrived at the process. If a timer was set, it is cleared
  6. If the timer elapses when we are waiting for a message, then evaluate the expressions ‘ExpressionsTimeout’ and put any saved messages back into the mailbox in the order in which they arrived at the process.