WF I: Erlang Ho!

This is the first progress report from the Wide Finder Project. Erlang is the obvious candidate for a Wide Finder implementation. It may be decades old but it’s the new hotness, it’s got a PragBook (@Amazon), I hear heavy breathing from serious software geeks whichever way I listen. So, let’s give it a whirl. [Warning: Long and detailed, but the conclusion comes first.]

Conclusion · Based on a few days’ bashing, I think that if I were starting out on a networked application that needed to run well on many-core systems and I wanted to be really really sure would never go down, Erlang might be just the ticket.

But as for the Wide Finder problem: Erlang, as it ships today, doesn’t work. It’s got slow-ish file I/O and ridiculously, unusably slow regular expression processing. There may be work-arounds.

Leaping In · Joe Armstrong’s book is no Camel or Pickaxe, but it’s OK. Armstrong tends to lead with theory, introducing the language formalisms then showing how you might use them. The coverage is a little thin; there are lots of big important pieces of the library that are entirely bypassed, and lots of omitted pieces in those that are covered. Whatever; if you’re an experienced programmer, you’ll be able to to use this as a bootstrap, and there are decent resources online.

I raised my eyebrows a bit at the near-complete absence of any discussion of text processing, regular expressions, and so on. Also at Erlang’s quaint notions about strings and characters; see Sam Ruby’s ASCII, ISO-8859-1, UCS, and Erlang. Well, the language reflects the book.

The rest of this piece is basically my working notes from the last few days’ work. I’m sure the source-code snippets will make real Erlang experts blanch in horror. That’s OK, I’m probably reasonably typical of an experienced developer picking this stuff up, so my goofs are likely usefully diagnostic.

Looping · Erlang doesn’t want to; it wants you to use tail-recursion instead. Here’s how I process all the lines out of a file:

scan_line(io:get_line(File, ''), File, Pattern, Counter).

scan_line(eof, _, _, _) -> 0;
scan_line(Line, File, Pattern, Counter) ->
    process_match(Line, regexp:match(Line, Pattern), Counter),
    scan_line(io:get_line(File, ''), File, Pattern, Counter).

I suppose this is OK, except for the tail recursion is really a glorified goto statement, and after a while it starts to feel like an elaborate fake-recursive lie.

Counting · In most computer languages, the way you count things is by incrementing a variable. In the Ruby program that the Wide Finders are trying to replicate, it’s like this:

    counts[$1] += 1

Except for, in Erlang, Variables aren’t variable, so you Can’t Do That. I thought of two ways to count things. Every Erlang process has a process dictionary, i.e. a hashtable or content-addressable store or whatever, with get() and put() calls. This is the kind of thing that the Ruby code above depends on; the square brackets are a dictionary lookup. The problem is, Joe Armstrong severely disses the use of the dictionary; you get the idea that if you use it, you’re the kind of person who sniffs little girls’ bicycle seats for thrills.

There’s also a hashtable package called ets, of which Joe expresses less disapproval.

Another way to count things, which I suspect would make Erlinguists happier, is to spawn a process for each thing you need to count, containing code like so:

counter_loop(Count) ->
    receive
	{ incr } ->
	    counter_loop(Count + 1);
	{ report, To } ->
	    To ! { count, Count },
	    counter_loop(Count)
    end.

Then you talk to it with code like this:

incr(Counter) ->
    Counter ! { incr }.

find_count(Counter) ->
    Counter ! { report, self() },
    receive
	{ count, Count } ->
	    Count
    end.

In my logfile, there is a small number of thousands of unique URIs to count, and the Erlang posse loves chest-beating about their process mojo, so this may be a good fit. Of course, you need some extra infrastructure to spawn the counter processes and map each unique URI to the process that’s counting it, but I built that and it seems to work OK.

Performance · Reviewing: that little Ruby program could process a week’s worth of data, a million and change lines, maybe a quarter of a gig, in about 7½ seconds of CPU, 13½ seconds elapsed. Perl was about twice as fast.

My first cut in Erlang, based on the per-process dictionary, took around eight minutes of CPU, and kept one of my MacBook’s Core Duo processors pegged at 97% while it was running. Ouch!

Switching to the ets version made no difference, nor did switching to my lightweight multi-process counter as illustrated above.

Profiling · Erlang comes with no less than three profilers, fairly thinly documented. I ended up using something called fprof. It’s a pig. I put it to work on a 100K-line subset of the test data, and it ground my computer to a halt and exhibited no progress in ten minutes, I killed that and started again with a 10K-line (2M of data) subset. It was still pretty bad; then I noticed that the profile trace was up over 8G in size and growing fast. So I tried again on only a thousand lines (195K), and the profile data was a mere 900M.

Eventually, the profiler revealed the awful truth: my program was spending 90% of its time in regexp:match and another 9% in io:get_line. I put my amazing powers of deduction to work and considered the hypothesis that Erlang regular expressions are slow. I had previously noticed this comment in the implementation:

%% Note that we interpret the syntax tree of a regular expression
%% directly instead of converting it to an NFA and then interpreting
%% that. This method seems to go significantly faster.

Well, a single-digit number of seconds with Google turned up lots of evidence, as for example from Gaspar Chilingarov in Implementatoin of regular expressions in pure Erlang [sic]: “In you tried to use regexp module from base erlang distribution or gregexp from jungerl, you noticed, that they work quite slow and are not usable to real text extraction tasks.”

There are alternatives: Gaspar, quoted above, provides one, and there has been at least one interface to the Posix regex libraries.

So I’ll check these out, because I’d really like to get past this basic stuff and investigate whether, as seems likely, I can get past Erlang’s reluctance to read, parse, and count, and make use of its allegedly-excellent concurrency.

Postscript · And I should say: I’ve really enjoyed having to learn a new way to think about computer programming.

---

---

Contributions