Kevin's Weblog

I’ve been tinkering a little more with the Beust Challenge, following up on my previous post. There are a couple significant new developments to report.

First, Hynek (Pichi) Vychodil wrote a faster version using a permutation generator.

Second, I also ported the first “CrazyBob” solution using a bit mask to Erlang.

Third, I discovered that my overly literal ports were actually slowing things down. The CrazyBob code uses an unspecified Listener class that receives the numbers in the series, and presumably computes the actual results from there. (Aside, I cannot actually benchmark against the Java code because I haven’t found what this implementation is.) I fudged this in my original ports by simply spawning a process, which then discarded all the messages it received. After I noticed that the code was pegging both of my CPUs, though, I realized that message passing might actually be the bottleneck in my code. Turns out this was the case, and removing the listener process and just computing the results in the main process actually sped things up substantially.

Finally, I got access to a machine with HiPE enabled.

So... here’s the results. First on my MacBook Pro, without HiPE:

The bitmask solution starts out the fastest, but loses out in the end to the more clever solutions. pichi edges out the crazybob solution by about a third.

Now on Linux 2.6 with HiPE:

And our new winner is... bitmask! HiPE barely helps the original brute-force solutions at all, while crazybob and pichi gain about a factor of two. bitmask, on the other hand, picks up an order of magnitude, and is now only a factor of 3 slower than the posted results for the Java crazybob solution (with unknown differences in hardware).

Conclusion: Erlang doesn’t suck!