WideFinder 2 Strawman implemented in Scala

Tim Bray has posted a strawman of the WideFinder 2 Benchmark and also posted an implementation in Ruby. It's similar in spirit to the original WideFinder, with the following differences:

1. much more logic: more pattern matching, counting, and conditional logic per record, which is designed to increase the CPU load
2. much more data: over 40GB in fact.
3. much more power: Sun Fire T2000 UltraSparcT1, 32 cores

Once again, recreating this basic implementation in Scala will help later to factor out any differences in performance based on language/runtime alone. Once pure language/runtime differences are understood, it will be easier to discern differences between various algorithmic approaches to concurrency. So without further ado, here is the basic, single-threaded, Scala version of the benchmark:

import scala.collection.mutable._

/** A normal HTML report: Top 10 popular URLs by hits and bytes, top 10 404s, *
 *  top 10 client IPs by hits, and the top 10 referrers.  Only, skip the HTML */
object WideFinder2 extends Application {
    class Counter extends HashMap[String,Long] {
        override def default(key:String) = 0L
        // override update to workaround http://lampsvn.epfl.ch/trac/scala/ticket/904
        override def update(k:String,v:Long) = super.update(k,v) 
    }
    
    val hits, bytes, s404s, clients, refs = new Counter
    val uriRegex = """/ongoing/When/\d\d\dx/\d\d\d\d/\d\d/\d\d/[^ .]+$""".r
    val refExclRegex = "-|http://www\\.tbray\\.org/ongoing/".r

    def record(host: String, uri: String, ref: String) {
        if(uriRegex.findPrefixOf(uri).isDefined) {
            hits(uri) += 1
            clients(host) += 1
            if(refExclRegex.findPrefixOf(ref).isEmpty) 
                refs(ref) += 1
        }
    }

    def report(label: String, map: Map[String,Long], megabytes: Boolean) {
        printf("Top %s:\n", label)
        val keysByCount = map.keySet.toList.sort { (a,b) =>
            (map(a) - map(b)) match {
                case 0 => a < b
                case n => n > 0
            }
        }
        for(key <- keysByCount.take(10)) {
            val format = if(megabytes) "%10.1fM: %s\n" else "%11.0f: %s\n"
            val value: Double = if(megabytes) map(key)/(1024.0d*1024.0d) else map(key)
            printf(format, value, if(key.length > 60) key.take(60) + "..." else key)
        }   
        println
    }

    override def main(args: Array[String]) {
        def toInt(a:String) = try {a.toInt} catch {case _=>0}
        for(line <- io.Source.fromFile(args(0)).getLines) {
            val f = line.split("\\s+")
            if(f(5) == "\"GET") {
                val (host, uri, status, size, ref) = 
                    (f(0), f(6), toInt(f(8)), toInt(f(9)), f(10).slice(1,f(10).length-1))

                status match {
                    case 200 => 
                        bytes(uri) += size
                        record(host, uri, ref)
                    case 304 => record(host, uri, ref)
                    case 404 => s404s(uri) += 1
                    case _ =>
                }
            }
        } 
        report("URIs by hit", hits, false)
        report("URIs by bytes", bytes, true)
        report("404s", s404s, false)
        report("client addresses", clients, false)
        report("refs", refs, false)
    }
}

The program can be run using this command:

java -cp .:scala-library.jar WideFinder2 O.100k

Interestingly, it has similar performance to the Ruby version, taking 23 seconds to process 100k lines on the test system, producing results identical to these. Besides input performance, which is neccessarily single threaded and can only be improved incrementally, there are three areas to focus on distributing:

1. matching
2. counting
3. sorting

However, the incremental improvement to input, which I hinted at in my last post, changes the nature of the problem quite a bit, so before getting into these three areas, maybe I should tackled that first. The basic idea is, instead of tying up the single input thread with extra work (namely character decoding and newline detection), just read large arbitrarily aligned blocks of bytes, and let worker theads deal with them in parallel. This causes two new problems:

1. multibyte and variable byte character encodings are more difficult to handle as a single character may span across multiple blocks
2. the content you're looking for (let's call this the target data) may span across multiple blocks

Luckily he first one is easy to deal with: only support ASCII for the time-being. Any fixed-width character encoding can be handled pretty trivially by buffering and appending/truncating each input block to make it an even multiple of N. Variable-width encoding, like UTF-8, for example, would be much harder to handle. This might be a good subject for a future project.

Likewise, the second problem has a straightforward solution to deal the WideFinder data, and more complex solutions to deal with the general case. The WideFinder data is line based text, and the WideFinder benchmark deals with finding patterns on single lines of text. So we can save the head and tail of each line that spans multiple blocks and re-join them for processing (i.e. join the tail of block 1 with the head of block 2 to get the line that spans blocks 1 and 2). For the general case, there are a few other strategies to collect and join endpieces, each with a requirement on the nature of the target data:

1. if the target data is guaranteed to not overlap, then the head and tail to be re-joined is any data between the end of the last match of a block, and the beginning of the first match in the next block. If the targets are too few and far between, and the size of the re-joined endpieces are frequently comparable to the input blocks themselves, this strategy results in too much repeated matching to be useful.
2. if the target data is guaranteed to only overlap partially, the above strategy changes to taking all data between just after the start of the last match in a block, and just before the end of the first match in the next block. This strategy has the same problem for sparse matches
3. if the target is guaranteed to be no bigger than some reasonably small (relative to the input block) size, then either of the two overlap strategies can be augmented with a maximum size which should reduce the redundant matching in huge endpieces.

For now, there is no need for any of these complex strategies to deal with re-joining endpieces, and we only have to worry about ASCII encoding. Maybe this can all be tackled in some future WideFinder 3.

WiderFinder

Continuing on the theme of Scala WideFinding, I made a couple of attempts to scale the performance across multiple cores without much luck. These mostly involved using Actors in various ways to distribute load. For example, I tried distributing the regex matching, the counter lookup and incrementing, as well as the result sorting. None of that yielded much in the way of improved performance.

From what I can tell, there is some lower common denominator in all cases that keeps performance from improving, and it seems to be the use of Source.getLines in the main thread. Here's how it looked in the original version:

for (input <- fromFile(args(0),"ASCII").getLines if matcher.reset(input).find) {
    counts(matcher.group(1)) += 1
}

That didn't change too much across the experiments so far, with the one major exception of distributing the regex matching. If you haven't seen how Actors are used Scala, it might seem a little foreign, so let me briefly digress and explain how they work at a very high level so you'll understand what follows. The basic idea is that each Actor is an object that may own a thread or may participate in a thread pool. You send message objects to the Actors, and they decide when and how to handle each message in their queue. The syntax is dead simple:

actor ! message

where actor is an implementation of Actor, and message is basically any old object. Using Actors to distribute the regular expression matching made the above for expression look something like this:

var n = 0
for (input <- fromFile(args(0),"ASCII").getLines) {
    regexMatchers(n % numMatchers) ! Some(input)
    n += 1
}

This expression sends input lines to a number of different regexMatcher Actors in a round robin fashion. Regex matching is quite CPU intensive and each line is independent from the next, so this seems like a worthy candidate for parallelization. Unfortunately, the benefit is never realized since it sits behind what I suspect is a slow input source. Two things that stand our are:

1. Source.fromFile() returns a BufferedSource which is an Iterator[Char], and getLines() returns an Iterator[String] which itself iterates over the BufferedSource character by character, looking for a newline, building up a string as it goes. Seems rather tedious for the main input thread to be doing this while multiple regex matching worker threads wait for input.
2. By default, BufferedSource uses a 2048 character buffer. That's smaller than a single cluster on most filesystems, and is likely another source of slowness

Other areas to investigate are

1. NIO offers scattering reads that can read into a number of buffers at once
2. java.util.concurrent has some non-blocking and limited-blocking data structures that may help speed things up

WideFinder in Scala

Tim Bray has put forth another challenge in Wide Finder 2. The purpose of this round is to try and take advantage of concurrent programming techniques on a single machine to better utilize the multiple cores commonly found in modern CPUs.

I didn't take part in the first Wide Finder project, so I feel I have a little catching up to do before tackling the current version. Since I'm also taking every opportunity I can to learn more Scala, I decided it would be best to just recreate the original version in Scala, preserving as much of the elegance and simplicity found in Tim's original Beautiful Code. That, plus it happens to be a requirement to participate to reproduce his results with a minimal version... Here's what I came up with:

import java.util.regex.Pattern
import scala.collection.mutable.{Map,HashMap}
import scala.io.Source.fromFile

object WideFinder extends Application {
    override def main(args: Array[String]) = {
        val counts: Map[String, Int] = new HashMap[String, Int] {
            override def default(key:String) = 0
        }
        
        val pattern = "GET /ongoing/When/\\d{3}x/(\\d{4}(/\\d{2}){2}[^ .]+) "
        val matcher = Pattern.compile(pattern).matcher("")
        
        for (input <- fromFile(args(0),"ASCII").getLines if matcher.reset(input).find) {
            counts(matcher.group(1)) += 1
        }
        
        val keysByCount = counts.keySet.toList.sort {(a,b) => counts(a) > counts(b)}
        for (key <- keysByCount.take(10)) {
            println(counts(key) + ": " + key)
        }
    }
}

Its ended up pretty close to the original Ruby code. Performance wise, it seems reasonable when tested against the 100K sample files on my 2.33 GHz MacBook Pro, taking about a second to complete. I'm chomping at the bit to do a concurrent version to handle the 45GB of log data on a 32 core server.