Concept for an Image Processing App

July 22nd, 2012 | June 9th, 2016    , , ,

This is a writeup for a concept I had been working on – an image processing application. It did not come to pass but I’d like to share some of the ideas behind it (previous posts touches upon some ideas too). It might be of interest to those of you working on developing full-scale applications integrated in web browsers.

The early days

An early sketchup for the application took inspiration from audio-processing software. In particular SynC Modular (later known as Reaktor). It had several levels of building instruments and effects for audio processing. At the high level, non-expert users could wire up high-level modules that had well-defined input/output sockets. In addition, UI for parameters could be designed that allowed users to configure the internals of modules. At the low level, expert users could program up logic for signal manipulation using predefined low-level primitives. The expert users could then package up the internals in a high-level module that exposed inputs/outputs for wiring.

In my first iteration, the user-interface consisted mostly of html/javascript/css code, but resorted to Flash for display of image, graph manipulation, and processing. Since Flash must be compiled before execution, image processing had to use predefined modules when deployed. New modules resulted in a re-compilation and deployment of the application. This restriction would hinder the usability of the application so the search for an alternative started. The only alternative present at the time was the Java VM. It’s usage was very low but still widely deployed. Next was the search for a compiler that could allow runtime compilation. I stumbled upon the Scala Programming Language which included an open-source compiler. Besides solving my problem, the language was also a great teaching tool for programming languages. With the Scala compiler at hand I could migrate the Flash-based processing to a Scala-based applet.

Putting the ideas into action

Here is a small picture showing the general layout of the application. It shows the result of mandelbrot fractal applied to an image. The module generating the fractal has several input parameters and an input image to apply it to, then an output image to store the resulting image to.

When editing the Fractal node we can see the actual Scala code that generates the image. In this code, the input image is transformed by mapping each pixel over a lambda function which yields the transformed pixel. Behind the scenes, a new image is produced, then stored as the output image.

Pixels in images are not manipulated directly with xy-coordinates. This allows the application to subdivide the image into segments that can be transformed concurrently. In addition, an initial pass on a miniaturized image is performed, allowing the user to view a quick preview. The final image is then progressively refined in the last pass.

A few talks and lectures

October 29th, 2011 | June 13th, 2013    ,

Talks

Rich Hickey on Are We There Yet?

  • How to think about immutability and time.
  • Presents some solutions with these restrictions in mind.
  • Time-varying data.

Alan Kay on Graphical User Interfaces

  • History of graphical user interfaces.
  • Explore and discover new paradigms.

Bret Victor on Inventing on Principle

  • Identify restrictions held by convention.
  • Prefer visual representations that can be manipulated.
  • Integrate text with ui.

Lectures

Hal Abelson and Gerald Jay Sussman gives lectures for Structure and Interpretation of Computer Programs

  • These age-old lectures can still teach you a thing or two.
  • Founded on Lambda Calculus, you’re gradually introduced to programming language paradigms and concepts many of todays languages, like C++11 and Java 8, just recently introduced (or will).
  • All lectures are engagingly taught.

Example usage of sbt build system

September 2nd, 2011 | April 16th, 2014    , ,

The sbt build system

This is a writeup explaining basic usage of the Simple Build Tool system for Scala. The complete build system is fairly comprehensive so I will only be focusing on aspects like setting up the project and using basic commands. A nice property of the build tool is its support for continuous compilation and testing. While you’re working on sourcefiles, the sbt tool will monitor changes then trigger recompilation and retesting whenever you modify code. By the time you need to check for errors in compilation or tests, a report might already be waiting for you.

For this example I’ll refer to a standard text editor and console. Alternatively, there exists sbt integration for IDEs like Eclipse for those that prefer that.

Getting started

Beginning, make sure you have a properly configured Java. Once that is in place you then need to download the sbt-launch.jar (0.13.1) library file. There are two options when using sbt. You can either install it system-wide, or include it with your project. I opted for the last one in this post.

With the download ready you can setup the project structure as follows:

project-name/
  src/
    main/scala/  -- your project sourcefiles goes here
    test/scala/  -- your project testfiles goes here
  lib/  -- manually handled library jars goes here
  build.sbt  -- your project's sbt config file
  sbt  -- sbt launchscript for unix
  sbt.cmd  -- sbt launchscript for windows
  sbt-launch.jar  -- the sbt library

Content of sbt file (if Unix mark it as executable using chmod u+x sbt):

#!/bin/bash
java -Xmx512M -jar $(dirname $(readlink -f "$0"))/sbt-launch.jar run "$@"

Content of sbt.cmd file:

@echo off
set SCRIPT_DIR=%~dp0
java -Xmx512M -jar "%SCRIPT_DIR%sbt-launch.jar" %*

Content of build.sbt file:

// Notes on syntax
//  - settings are initialized with :=
//  - dependency paths given by %
//  - dependency paths against specific scala versions are given by %%
name := "Project"
 
version := "1.0"
 
scalaVersion := "2.10.3"
 
libraryDependencies += "org.scalatest" % "scalatest_2.10" % "2.0" % "test"

With that the project ready for use. All that remains is running sbt from console to pull in required library dependencies (or later manually with update):

D:\test-scala3>sbt
Getting org.fusesource.jansi jansi 1.11 ...
downloading http://repo1.maven.org/maven2/org/fusesource/jansi/jansi/1.11/jansi-1.11.jar ...
        [SUCCESSFUL ] org.fusesource.jansi#jansi;1.11!jansi.jar (639ms)
:: retrieving :: org.scala-sbt#boot-jansi
        confs: [default]
        1 artifacts copied, 0 already retrieved (111kB/26ms)
Getting org.scala-sbt sbt 0.13.1 ...
...

Once started sbt will continue to accept commands (if you need to quit it, simply write exit).

Lets add the sourcefile /src/main/scala/demo/Demo.scala and compile it:

package demo
 
object Demo {
  def clamp(value: Double, min: Double, max: Double): Double = {
    if (value < min) min else if (value > max) max else value
  }
}
> compile
[info] Updating {file:}...
...
[info] Done updating.
[info] Compiling 1 Scala source to target\scala-2.10\classes...
[success] Total time: 2 s, completed 22.jan.2014 18:09:53

Lets also add a test /src/test/scala/demo/DemoSpec.scala and test our assumptions:

package demo
 
import org.scalatest.FlatSpec
import org.scalatest.matchers.ShouldMatchers
import Demo.clamp
 
class DemoSpec extends FlatSpec {
  "clamp" should "handle minimum cases" in {
    assert(clamp(-1.0, 0.0, 1.0) == 0.0)
  }
}
> test
[info] Compiling 1 Scala source to target\scala-2.10\test-classes...
[info] DemoSpec:
[info] clamp
[info] - should handle minimum cases
[info] Run completed in 339 milliseconds.
[info] Total number of tests run: 1
[info] Suites: completed 1, aborted 0
[info] Tests: succeeded 1, failed 0, canceled 0, ignored 0, pending 0
[info] All tests passed.
[success] Total time: 2 s, completed 22.jan.2014 18:12:13

Instead of issuing these commands manually each iteration, lets instead enable automatic testing with ~test (the tilde tells sbt to run the command continuously).

> ~test
[info] DemoSpec:
[info] clamp
[info] - should handle minimum cases
[info] Run completed in 488 milliseconds.
[info] Total number of tests run: 1
[info] Suites: completed 1, aborted 0
[info] Tests: succeeded 1, failed 0, canceled 0, ignored 0, pending 0
[info] All tests passed.
[success] Total time: 1 s, completed 22.jan.2014 18:14:15

Updating /src/test/scala/demo/DemoSpec.scala with additional test-cases now triggers recompile and retesting:

  it should "handle maximum cases" in {
    assert(clamp(2.0, 0.0, 1.0) == 1.0)
  }
[info] Compiling 1 Scala source to target\scala-2.10\test-classes...
[info] DemoSpec:
[info] clamp
[info] - should handle minimum cases
[info] - should handle maximum cases
[info] Run completed in 346 milliseconds.
[info] Total number of tests run: 2
[info] Suites: completed 1, aborted 0
[info] Tests: succeeded 2, failed 0, canceled 0, ignored 0, pending 0
[info] All tests passed.
[success] Total time: 2 s, completed 22.jan.2014 18:16:16
  it should "handle inrange cases" in {
    assert(clamp(0.9, 0.0, 1.0) == 0.5)
  }
[info] Compiling 1 Scala source to target\scala-2.10\test-classes...
[info] DemoSpec:
[info] clamp
[info] - should handle minimum cases
[info] - should handle maximum cases
[info] - should handle inrange cases *** FAILED ***
[info]   0.9 did not equal 0.5 (DemoSpec.scala:15)
[info] Run completed in 411 milliseconds.
[info] Total number of tests run: 3
[info] Suites: completed 1, aborted 0
[info] Tests: succeeded 2, failed 1, canceled 0, ignored 0, pending 0
[info] *** 1 TEST FAILED ***
[error] Failed tests:
[error]         demo.DemoSpec
[error] (test:test) sbt.TestsFailedException: Tests unsuccessful
[error] Total time: 2 s, completed 22.jan.2014 18:16:40

Here the tests did not complete. The error message points to where corrections are needed:

  it should "handle inrange cases" in {
    assert(clamp(0.5, 0.0, 1.0) == 0.5)
  }
[info] Compiling 1 Scala source to target\scala-2.10\test-classes...
[info] DemoSpec:
[info] clamp
[info] - should handle minimum cases
[info] - should handle maximum cases
[info] - should handle inrange cases
[info] Run completed in 372 milliseconds.
[info] Total number of tests run: 3
[info] Suites: completed 1, aborted 0
[info] Tests: succeeded 3, failed 0, canceled 0, ignored 0, pending 0
[info] All tests passed.
[success] Total time: 2 s, completed 22.jan.2014 18:17:59
5. Waiting for source changes... (press enter to interrupt)

If you want API documentation generated, simply issue the doc command then locate them in /target/scala-version/api:

> doc
[info] Main Scala API documentation to target\scala-2.10\api...
model contains 3 documentable templates
[info] Main Scala API documentation successful.
[success] Total time: 1 s, completed 22.jan.2014 18:18:25

Once editing of sourcecode is done you can issue package commands to generate the final libraries:

> package
[info] Packaging target\scala-2.10\project_2.10-1.0.jar ...
[info] Done packaging.
[success] Total time: 0 s, completed 22.jan.2014 18:18:39
> package-doc
[info] Packaging target\scala-2.10\project_2.10-1.0-javadoc.jar ...
[info] Done packaging.
[success] Total time: 0 s, completed 22.jan.2014 18:18:52
> package-src
[info] Packaging target\scala-2.10\project_2.10-1.0-sources.jar ...
[info] Done packaging.
[success] Total time: 0 s, completed 22.jan.2014 18:19:06

Further pointers

Presented here was just the absolute basics of sbt to get you started. There are tons of commands available within sbt (use tab-completion to show them all), additional configuration options, and plugins which extend it. If you want more in-depth information about sbt then visit its documentation page. Development on sbt is still ongoing so expect some changes in the future, but by including the sbt build system with your project you can largely ignore upgrades until you’re ready for them.

A compact UI layout for tag-based search

June 8th, 2011 | August 8th, 2011    

I’ve always been impressed by tags as a way to do search and have been looking to make use of them myself. In my application my initial design for categorizing items was based on the familiar directory-structure, but this presented several problems in relation to search. I needed a more efficient way of locating items so I chose to replace the old solution with a tag-based one. An added bonus was that I could reuse this several other places in my application.

In my application the screen space available for tag search is fairly small. This led me to experiment with how of represent the UI elements. A current sketch is given below. It consists of a tags- and values-section. In the tags-section the left-hand side gives a search input and a page browser. The right-hand side lists the current page of matching tags (constrained by the search text and selected tags). In the values-section a similar search input and page browser is found. The right-hand side lists the current page of matching values (constrained by the search text and selected tags).

In the previous sketch no tags were selected. The next one shows when two tags has been selected, where tag4 is included and tag7 is excluded. Together these will constrain which tags and values are currently searchable.

A possible extension could be types of tags. Not sure if this is something I’d like to add but could be useful for integrating other metadata into the search system. Here tags are extended with types and search input extended with a type constraint which can also reuse the search mechanism for selecting a different type. To abbreviate tag naming some sort of color coding could for example be used to represent types.

In summary, I’m still experimenting with this layout but it seem to working as intended. In my case the search will probably involve some 10 to 1000 items. Tags are usually employed on much larger volumes but I think this UI layout will work out atleast for my setup.

A small benchmark util for Scala continued

May 19th, 2011 | February 21st, 2012    , , ,

Extending the benchmark

Note: This is a follow-up post of a previous post. You might want to read the first to get a simpler view of the extensions added here.

One improvement I wanted to add to the previous benchmark util was monitors which generate statistics for the task being benchmarked. I chose traits for implementing them. That way I’ll be able to adapt the monitor using inheritance. A Monitor is simply defined as having a begin() and end() method, where end() returns a sequence of statistical data. The type of data returned is defined by the type parameter of Monitor.

In addition to the Monitor trait the previous code get extended with a newMonitor() argument for instantiating them:

case class TaskDone[Id,Stats](id: Id, run: Int, stats: Seq[Stats])
case class TaskFail[Id,Stats](id: Id, run: Int, stats: Seq[Stats], error: Throwable)
case class BenchDone[Id,Stats](warmups: Seq[Task[Id,Stats]], runs: Seq[Task[Id,Stats]])
 
trait Monitor[Stats] {
  private[this] var step = 0
  def begin(): Unit = {
    assert(step == 0, "Improperly handled monitor.")
    step = 1
  }
  def end(): Seq[Stats] = {
    assert(step == 1, "Improperly handled monitor.")
    step = 2
    Nil
  }
}
 
type Report[Result]  = Result => Unit
type Make[Value]     = () => Value
type Task[Id,Stats]  = Either[TaskFail[Id,Stats],TaskDone[Id,Stats]]
type Bench[Id,Stats] = BenchDone[Id,Stats]
type Batch[Id,Stats] = Seq[Bench[Id,Stats]]
 
def task[Id,Stats]
    (id: Id, fn: () => Unit)
    (run: Int)
    (newMonitor: Make[Monitor[Stats]])
    (report: Report[Task[Id,Stats]]): Task[Id,Stats] = {
  val monitor = newMonitor()
  monitor.begin()
  val result = try {
    fn()
    Right(TaskDone(id=id,run=run,stats=monitor.end()))
  } catch {
    case exp: Throwable =>
      Left(TaskFail(id=id,run=run,stats=monitor.end(),error=exp))
  }
  report(result)
  result
}
 
def benchmark[Id,Stats]
    (task: Int => Make[Monitor[Stats]] => Report[Task[Id,Stats]] => Task[Id,Stats])
    (runs: Int, warmups: Int)
    (newMonitor: Make[Monitor[Stats]])
    (warmupReport: Report[Task[Id,Stats]], runReport: Report[Task[Id,Stats]])
    (benchReport: Report[Bench[Id,Stats]]): Bench[Id,Stats] = {
  assert(runs > 0, "Number of runs must be greater than zero.")
  assert(warmups >= 0, "Number of warmups must be zero or greater.")
 
  val (warmupsResults,runsResults) = (
    (1 to warmups) map (run => task(run)(newMonitor)(warmupReport)),
    (1 to runs) map (run => task(run)(newMonitor)(runReport))
  )
  val result = BenchDone(warmups=warmupsResults,runs=runsResults)
  benchReport(result)
  result
}
 
def batch[Id,Stats]
    (benchs: Seq[Report[Bench[Id,Stats]] => Bench[Id,Stats]])
    (benchReport: Report[Bench[Id,Stats]])
    (batchReport: Report[Batch[Id,Stats]]) {
  val result = benchs map (bench => bench(benchReport))
  batchReport(result)
}

The revised diagram sketch now visualizes how statistics generated by the monitor is fed back to reporters:

Example usage

In this revised example we need to define some statistical datatypes. These will be TaskTime and TaskMem which collect time and memory usage. They are case classes extended from the sealed trait TaskStats which will allow us to pattern match them.

type Id = String
 
case class MemStats(free: Long, total: Long, max: Long) {
  def used(): Long = total - free
}
 
sealed trait TaskStats
 
case class TaskTime(duration: Long) extends TaskStats
 
case class TaskMem(samples: Seq[MemStats]) extends TaskStats {
  def avgUsed(): Long = {
    val totals = samples map (mem => mem.used)
    if (totals.nonEmpty) totals.sum / totals.length else 0
  }
  def minUsed(): Long = {
    samples.collect{ case mem: MemStats => mem.used }.min
  }
  def maxUsed(): Long = {
    samples.collect{ case mem: MemStats => mem.used }.max
  }
}

For utility we add some more convenience methods for text conversion and calculating statistics of memory usage.

def timeToText(value: Long): String = {
  def pad(n: Int, value: Long): String =
    value.toString.reverse.padTo(n,"0").reverse.mkString
  // utility for turning nanoseconds into text
  val ms      = (value / 1000000L).toLong
  val msPart  = ms % 1000L
  val sec     = (ms - msPart) / 1000L
  val secPart = sec % 60L
  val min     = (sec - secPart) / 60L
  val minPart = min
  if (minPart > 0) minPart + "m" + pad(2,secPart) + "s" + pad(3,msPart) + "ms"
  else if (secPart > 0)  secPart + "s" + pad(3,msPart) + "ms"
  else msPart + "ms"
}
 
def memToText(value: Long): String = {
  def pad(n: Int, value: Long): String =
    value.toString.reverse.padTo(n,"0").reverse.mkString
  // utility for turning bytes into text
  val mb     = value / (1024L * 1024L)
  val mbPart = mb % 1024L
  val gb     = (mb - mbPart) / 1024L
  val gbPart = gb
  if (gbPart > 0) gbPart + "gb" + pad(3,mbPart) + "mb"
  else mbPart + "mb"
}
 
def taskId[Id](bench: Bench[Id,TaskStats]): Id = {
  // utility for extracting task id
  val firstDone = bench.runs find (result => result.isRight)
  val firstFail = bench.runs find (result => result.isLeft)
  if (firstDone.nonEmpty) firstDone.get.right.get.id
  else firstFail.get.left.get.id
}
 
def isDone[Id](bench: Bench[Id,TaskStats]): Boolean = {
  // utility for detecting a bench without errors
  val warmupsFail = bench.warmups collect { case Left(task) => task }
  val runsFail    = bench.runs collect { case Left(task) => task }
  warmupsFail.isEmpty && runsFail.isEmpty
}
 
def avgTime(bench: Bench[Id,TaskStats]): Long = {
  // utility for calculating average time of runs in a benchmark
  val totals = bench.runs.collect{
    case Right(task) => task.stats.collect{ case TaskTime(value) => value }.sum
    case Left(task)  => task.stats.collect{ case TaskTime(value) => value }.sum
  }
  if (totals.nonEmpty) totals.sum / totals.length else 0
}
 
def minTime(bench: Bench[Id,TaskStats]): Long = {
  // utility for calculating minimum time of runs in a benchmark
  val totals = bench.runs.collect{
    case Right(task) => task.stats.collect{ case TaskTime(value) => value }.min
    case Left(task)  => task.stats.collect{ case TaskTime(value) => value }.min
  }
  totals.min
}
 
def noTime(bench: Bench[Id,TaskStats]): Long = {
  // utility for calculating number of runs in a benchmark
  val totals = bench.runs.collect{
    case Right(task) => task.stats.collect{ case TaskTime(value) => 1 }.sum
    case Left(task)  => task.stats.collect{ case TaskTime(value) => 1 }.sum
  }
  totals.sum
}
 
def avgMem(bench: Bench[Id,TaskStats]): Long = {
  // utility for calculating average memory usage in benchmark
  val totals = bench.runs.collect{
    case Right(task) => task.stats.collect{ case mem: TaskMem => mem.avgUsed }.sum
    case Left(task)  => task.stats.collect{ case mem: TaskMem => mem.avgUsed }.sum
  }
  if (totals.nonEmpty) totals.sum / totals.length else 0
}
 
def maxMem(bench: Bench[Id,TaskStats]): Long = {
  // utility for calculating max memory usage in benchmark
  val totals = bench.runs.collect{
    case Right(task) => task.stats.collect{ case mem: TaskMem => mem.maxUsed }.max
    case Left(task)  => task.stats.collect{ case mem: TaskMem => mem.maxUsed }.max
  }
  totals.max
}
 
def noMem(bench: Bench[Id,TaskStats]): Long = {
  // utility for calculating number of memory samples taken in benchmark
  val totals = bench.runs.collect{
    case Right(task) => task.stats.collect{ case TaskMem(samples) => samples.length }.sum
    case Left(task)  => task.stats.collect{ case TaskMem(samples) => samples.length }.sum
  }
  totals.sum
}

Next up, we need to refine the reporters to account for the new datatypes and output relevant statistics on memory usage.

def taskReport(title: String)(result: Task[Id,TaskStats]) {
  result match {
    case Right(task) =>
      val time = task.stats.collect{ case TaskTime(value) => value }.sum
      println(
        "%s %s %s completed in %s"
          .format(task.id.toString, title, task.run, timeToText(time))
      )
    case Left(task) =>
      val time = task.stats.collect{ case TaskTime(value) => value }.sum
      val error = task.error.getClass.getName
      println(
        "%s %s %s failed after %s from %s"
          .format(task.id.toString, title, task.run, timeToText(time), error)
      )
  }
}
 
val warmupReport = taskReport("warmup") _
 
val runReport = taskReport("run") _
 
def benchReport[Id](bench: Bench[Id,TaskStats]) {
  val id = taskId(bench)
  if (isDone(bench)) {
    val totalTime = bench.runs.collect{
      case Right(task) =>
        task.stats.collect{ case TaskTime(value) => value }.sum
    }.sum
    println(id + " finished in " + timeToText(totalTime) + "\n")
  }
  else
    println(id + " failed\n")
}
 
def batchReport(batch: Batch[Id,TaskStats]) {
  def propsToText(): String = {
    import scala.util.{Properties => Props}
    val os = java.lang.management.ManagementFactory.getOperatingSystemMXBean
    val props = scala.collection.immutable.SortedMap(
      "os" -> (os.getName + " (" + os.getVersion + ")"),
      "arch" -> os.getArch,
      "cpus" -> os.getAvailableProcessors.toString,
      "java" -> (Props.javaVmName + " " + Props.javaVersion),
      "scala" -> Props.versionString.replace("version","").trim
    )
    props.map{ case (k,v) => k + ":" + "\"" + v + "\"" }.mkString(" ")
  }
  def statsToText(status: String, benchs: Seq[Bench[Id,TaskStats]]): String = {
    benchs
      .map(bench => (
        avgTime(bench),noTime(bench),minTime(bench),
        avgMem(bench),noMem(bench),maxMem(bench),taskId(bench)
      ))
      .sortWith((a,b) => a._1 < b._1) // sort on durations
      .map(item =>
        "%2s %12s/%-6s %12s %10s/%-6s %10s %s"
         .format(
           status,timeToText(item._1),item._2,timeToText(item._3),
           memToText(item._4),item._5,memToText(item._6),item._7)
      )
      .mkString("\n")
  }
  val (doneBenchs,failedBenchs) = batch partition isDone
  println(
    "Batch of benchmarks finished with %s completed and %s failed.\n"
      .format(doneBenchs.length,failedBenchs.length)
  )
  println("Statistics for benchmarks:\n")
  println(
    "   %12s/%-6s %12s %10s/%-6s %10s %s"
      .format("avgtime","no","mintime","avgmem","no","maxmem","id")
  )
  println(statsToText("ok", doneBenchs))
  println(statsToText("na", failedBenchs))
  println("\nSystem properties:")
  println(propsToText)
}

For implementing the Monitor trait I use mixin inheritance for this example. One for TimeUsage and one for MemUsage. These traits can be stacked together and accumulate the statistics generated. TimeUsage is just an abstraction of the previous post’s task() code. MemUsage on the other hand is a little more involved. It will stay active during benchmarking and sample memory usage at regular intervals.

For multithreaded sampling I chose actors since they are fairly simple in use. A MemUsage object simply starts the sampler actor by sending a message with NextSample. This will trigger the sampler to start regular recordings of memory usage. When the benchmark is done the MemUsage object will send and wait for reply for a LastSample message. The sampler will reply with the sequence of MemStats samples collected and terminate. Last, the samples are stored in a TaskMem object and accumulated with the other TaskStats results.

trait TimeUsage extends Monitor[TaskStats] {
  var startTime: Long = 0L
 
  override def begin() {
    super.begin()
    startTime = System.nanoTime  
  }
 
  override def end(): Seq[TaskStats] = {
    List(TaskTime(duration=System.nanoTime - startTime)) ++ super.end()
  }
}
 
trait MemUsage extends Monitor[TaskStats] {
  import MemUsage.{NextSample,LastSample}
 
  val sampleRate: Long
  private val rt = java.lang.Runtime.getRuntime
  private val sampler = new actors.Actor {
    var samples = List.empty[MemStats]
    var running = true
    def act() {
      while(running) {
        try { receive {
          case NextSample =>
            samples ::=
              MemStats(free=rt.freeMemory, total=rt.totalMemory, max=rt.maxMemory)
            java.lang.Thread.sleep(sampleRate)
            this ! NextSample
          case LastSample =>
            running = false
            samples ::=
              MemStats(free=rt.freeMemory, total=rt.totalMemory, max=rt.maxMemory)
            reply(samples)
        } }
        catch {
          case error: java.lang.OutOfMemoryError =>
            // skip this sample then wait for LastSample
            java.lang.Thread.sleep(sampleRate)
        }
      }
    }
  }
 
  override def begin() {
    rt.gc()
    sampler.start()
    sampler ! NextSample
    super.begin()
  }
 
  override def end(): Seq[TaskStats] = {
    val stats = super.end()
    (sampler !? LastSample) match {
      case samples => List(TaskMem(samples.asInstanceOf[List[MemStats]])) ++ stats
    }
  }
}
 
object MemUsage {
  private case object NextSample
  private case object LastSample
}

In the new benchmark code we now need to make some adjustments to accommodate the extensions made. First we need to add a function for generating new monitors. Here we use inheritance to select which statistics we are interested in collecting and set relevant configuration. Finally, we also need to update task() calls. Since its a partially applied function where the Stats type parameter is specificed by a later argument, we now need to specify type parameters ahead of time.

val newMonitor = () => {
  new Monitor[TaskStats] with MemUsage with TimeUsage {
    val sampleRate = 50L
  }
}
val (warmups,runs) = (1,2)
val (start,end) = (1,5000000)
val sum = (a: Int, b: Int) => a + b
 
 
@scala.annotation.tailrec
def loopWithTailrec(start: Int, end: Int, sum: Int): Int = {
  if (start <= end) loopWithTailrec(start + 1, end, sum + start)
  else sum
}
 
val rangeTasks = List(
  task[Id,TaskStats](id="range+sum",
    fn=() => (start to end).sum) _,
  task[Id,TaskStats](id="range+foldLeft",
    fn=() => (start to end).foldLeft(0)(sum)) _,
  task[Id,TaskStats](id="range+foldRight",
    fn=() => (start to end).foldRight(0)(sum)) _
)
 
val listTasks = List(
  task[Id,TaskStats](id="list+sum",
    fn=() => List.range(start,end).sum) _,
  task[Id,TaskStats](id="list+foldLeft",
    fn=() => List.range(start,end).foldLeft(0)(sum)) _,
  task[Id,TaskStats](id="list+foldRight",
   fn=() => List.range(start,end).foldRight(0)(sum)) _
)
 
val vectorTasks = List(
  task[Id,TaskStats](id="vector+sum",
    fn=() => Vector.range(start,end).sum) _,
  task[Id,TaskStats](id="vector+foldLeft",
    fn=() => Vector.range(start,end).foldLeft(0)(sum)) _,
  task[Id,TaskStats](id="vector+foldRight",
    fn=() => Vector.range(start,end).foldRight(0)(sum)) _
)
 
val arrayTasks = List(
  task[Id,TaskStats](id="array+sum",
    fn=() => Array.range(start,end).sum) _,
  task[Id,TaskStats](id="array+foldLeft",
    fn=() => Array.range(start,end).foldLeft(0)(sum)) _,
  task[Id,TaskStats](id="array+foldRight",
    fn=() => Array.range(start,end).foldRight(0)(sum)) _
)
 
val streamTasks = List(
  task[Id,TaskStats](id="stream+sum",
    fn=() => Stream.range(start,end).sum) _,
  task[Id,TaskStats](id="stream+foldLeft",
    fn=() => Stream.range(start,end).foldLeft(0)(sum)) _,
  task[Id,TaskStats](id="stream+foldRight",
    fn=() => Stream.range(start,end).foldRight(0)(sum)) _
)
 
val itrTasks = List(
  task[Id,TaskStats](id="list+itr+foldRight",
    fn=() => List.range(start,end).iterator.foldRight(0)(sum)) _,
  task[Id,TaskStats](id="stream+itr+sum",
    fn=() => Stream.range(start,end).iterator.sum) _,
  task[Id,TaskStats](id="stream+itr+foldRight",
    fn=() => Stream.range(start,end).iterator.foldRight(0)(sum)) _
)
 
val loopTasks = List(
  task[Id,TaskStats](id="loop+for",
    fn=() => {
      var sum = 0
      for (i <- start to end) {
        sum = sum + i
      }
      sum
    }) _,
  task[Id,TaskStats](id="loop+while",
    fn=() => {
      var sum = 0
      var i = start
      while (i <= end) {
        sum = sum + i
        i = i + 1
      }
      sum
    }) _,
  task[Id,TaskStats](id="loop+tailrec",
    fn=() => {
      loopWithTailrec(start, end, 0)
    }) _
)
 
val benchs = (
  rangeTasks ++ listTasks ++ vectorTasks ++ arrayTasks ++
    streamTasks ++ itrTasks ++ loopTasks
).map(
  task => benchmark(task)(runs=runs,warmups=warmups)(newMonitor)(warmupReport,runReport) _
)
batch[Id,TaskStats](benchs)(benchReport)(batchReport)

Lets run the updated benchmark and see how memory usage plays into the equation. Now keep in mind that the memory related statistics isn’t necessarily accurate. Generated statistics accumulate memory. The JVM reserves memory for all kinds of optimizations so it might not reflect the actual memory usage of the data-structures. Runtime optimizations performed by the JVM might behave differently when code is used in an implementation. Different JVMs and hardware setups will also affect the result. Atleast you can get some idea of the time and memory usage involved and maybe get some insights into tradeoffs involved.

Batch of benchmarks finished with 16 completed and 5 failed.
 
Statistics for benchmarks:
 
        avgtime/no          mintime     avgmem/no         maxmem id
ok          5ms/2               5ms        3mb/4             3mb loop+while
ok          9ms/2               8ms        3mb/4             3mb loop+tailrec
ok         39ms/2              38ms        7mb/4            12mb loop+for
ok        152ms/2             150ms        3mb/8             7mb range+foldLeft
ok        181ms/2             178ms        4mb/9             8mb range+sum
ok        251ms/2             250ms       23mb/11           27mb array+foldRight
ok        254ms/2             253ms       21mb/10           25mb array+foldLeft
ok        294ms/2             291ms       34mb/12           58mb array+sum
ok      1s101ms/2           1s086ms       13mb/39           36mb stream+foldLeft
ok      1s366ms/2           1s361ms       78mb/45          139mb vector+foldLeft
ok      1s419ms/2           1s416ms       80mb/43          155mb vector+sum
ok      1s547ms/2           1s513ms      123mb/23          201mb range+foldRight
ok      2s002ms/2           1s989ms      112mb/36          199mb list+foldLeft
ok      2s062ms/2           2s061ms      116mb/38          212mb list+sum
ok      2s350ms/2           2s278ms      117mb/45          224mb vector+foldRight
ok      7s166ms/2           6s726ms      181mb/88          247mb list+itr+foldRight
na          2ms/2               2ms        1mb/4             1mb stream+foldRight
na      1s505ms/2           1s247ms       91mb/34          185mb list+foldRight
na     19s834ms/2          19s563ms      193mb/88          247mb stream+sum
na     26s811ms/2          26s255ms      193mb/101         247mb stream+itr+foldRight
na     26s869ms/2          26s692ms      186mb/114         247mb stream+itr+sum
 
System properties:
arch:"x86" cpus:"2" java:"Java HotSpot(TM) Client VM 1.6.0_27" os:"Windows 7 (6.1)" scala:"2.9.1.final"

A small benchmark util for Scala

May 8th, 2011 | August 23rd, 2011    , ,

Specifying the benchmark

Note: there’s now also a follow-up post which extends this benchmark.

This post was inspired by an answer to the Hidden features of Scala question over at StackOverflow.com (and also another blog post I cannot find back to). I expanded a little on the code that was posted, which resulted in the following neat lump of code.

case class TaskDone[Id](id: Id, run: Int, duration: Long)
case class TaskFail[Id](id: Id, run: Int, duration: Long, error: Throwable)
case class BenchDone[Id](warmups: Seq[Task[Id]], runs: Seq[Task[Id]])
 
type Report[Result] = Result => Unit
type Task[Id]       = Either[TaskFail[Id],TaskDone[Id]]
type Bench[Id]      = BenchDone[Id]
type Batch[Id]      = Seq[Bench[Id]]
 
def task[Id](id: Id, fn: () => Unit)(run: Int)(report: Report[Task[Id]]): Task[Id] = {
  val begin = System.nanoTime
  val result = try {
    fn()
    Right(TaskDone(id=id,run=run,duration=System.nanoTime - begin))
  } catch {
    case exp: Throwable =>
      Left(TaskFail(id=id,run=run,duration=System.nanoTime - begin,error=exp))
  }
  report(result)
  result
}
 
def benchmark[Id](task: Int => Report[Task[Id]] => Task[Id])(runs: Int, warmups: Int)
                 (warmupReport: Report[Task[Id]], runReport: Report[Task[Id]])
                 (benchReport: Report[Bench[Id]]): Bench[Id] = {
  assert(runs > 0, "Number of runs must be greater than zero.")
  assert(warmups >= 0, "Number of warmups must be zero or greater.")
 
  val (warmupsResults,runsResults) = (
    (1 to warmups) map (run => task(run)(warmupReport)),
    (1 to runs) map (run => task(run)(runReport))
  )
  val result = BenchDone(warmups=warmupsResults,runs=runsResults)
  benchReport(result)
  result
}
 
def batch[Id](benchs: Seq[Report[Bench[Id]] => Bench[Id]])
             (benchReport: Report[Bench[Id]])(batchReport: Report[Batch[Id]]) {
  val result = benchs map (bench => bench(benchReport))
  batchReport(result)
}

What this code does is create a task() with an id and a function of () => Unit to apply. This task is then added to a benchmark(), which is further specified with how many runs and warmups to perform, and a set of task reporters which handles individual results. Finally, a batch() is constructed and given a set of benchmarks and a benchmark reporter. When this batch is completed with a batch reporter, it will trigger the benchmarks to run, and subsequently the individual tasks. The benchmark results are then accumulated and fed back into the batch reporter.

The following diagram gives visual sketch of the code. Note that half-open endpoints signify arguments already specified from outside all the enclosing functions.

Example usage

Before specifying the tasks, lets first define the reporters that will handle the results. This is where the largest bulk of code resides.

For tasks we can define two kinds of reporters. One for warmup runs and the other for ordinary runs. Each reporter handles a result in form of an Either[TaskFail[Id],TaskDone[Id]] which it can pattern matched against. A Right[TaskDone[Id]] result indicates a successful run with data on id, run number and duration. If not, there is a Left[TaskFail[Id]] result that indicates a failed run with data on id, run number, duration, and an exception. A benchmark reporter is also defined which handles the accumulated results of warmups runs and ordinary runs. The resulting data from all benchmarks is then finally fed into a batch reporter.

In the following code warmupReport() and runReport() specifies the task reporters, benchReport() handles the accumulated runs, and batchReport() presents the final statistics.

type Id = String
 
def timeToText(value: Long): String = {
  // utility for turning nanoseconds into text
  val ms      = (value / 1000000L).toLong
  val msPart  = ms % 1000L
  val sec     = (ms - msPart) / 1000L
  val secPart = sec % 60L
  val min     = (sec - secPart) / 60L
  val minPart = min
  if (minPart > 0) minPart + "m" + secPart + "s" + msPart + "ms"
  else if (secPart > 0)  secPart + "s" + msPart + "ms"
  else msPart + "ms"
}
 
def taskId[Id](bench: Bench[Id]): Id = {
  // utility for extracting task id
  val firstDone = bench.runs find (result => result.isRight)
  val firstFail = bench.runs find (result => result.isLeft)
  if (firstDone.nonEmpty) firstDone.get.right.get.id
  else firstFail.get.left.get.id
}
 
def isDone[Id](bench: Bench[Id]): Boolean = {
  // utility for detecting a bench without errors
  val warmupsFail = bench.warmups collect { case Left(task) => task }
  val runsFail    = bench.runs collect { case Left(task) => task }
  warmupsFail.isEmpty && runsFail.isEmpty
}
 
def avgTime(bench: Bench[Id]): Long = {
  // utility for calculating average time of runs in a benchmark
  val totals = bench.runs.collect{
    case Right(task) => task.duration
    case Left(task)  => task.duration
  }
  if (totals.nonEmpty) totals.sum / totals.length else 0
}
 
def taskReport(title: String)(result: Task[Id]) {
  result match {
    case Right(task) =>
      println(
        task.id.toString + " " + title + " " + task.run + " completed in " +
          timeToText(task.duration)
      )
    case Left(task) =>
      println(
        task.id.toString + " " + title + "  " + task.run + " failed after " + 
          timeToText(task.duration) + " from " + task.error.getClass.getName
      )
  }
}
 
val warmupReport = taskReport("warmup") _
 
val runReport = taskReport("run") _
 
def benchReport[Id](bench: Bench[Id]) {
  val id = taskId(bench)
  if (isDone(bench)) {
    val totalTime = bench.runs.collect{ case Right(task) => task.duration }.sum
    println(id + " finished in " + timeToText(totalTime) + "\n")
  }
  else
    println(id + " failed\n")
}
 
def batchReport(batch: Batch[Id]) {
  val (doneBenchs,failedBenchs) = batch partition isDone
  println(
    "Batch of benchmarks finished with %s completed and %s failed.\n"
      .format(doneBenchs.length,failedBenchs.length)
  )
  println("Average times for benchmarks:")
  println(
    doneBenchs
      .map(bench => (taskId(bench),avgTime(bench)))
      .sortWith((a,b) => a._2 < b._2) // sort on durations
      .map(item => "%10s %s".format(timeToText(item._2),item._1))
      .mkString("\n")
  )
  println(
    failedBenchs
      .map(bench => "%10s %s".format("na",taskId(bench)))
      .mkString("\n")
  )
}

With the reporters in place we can begin to define some tasks to do benchmarks on. We want to check how well the Scala collections library handles folding over ranges. A range in Scala is simply created by writing 1 to 100 which represents the list of numbers from 1 to 100. Now, this doesn’t actually create and allocate a whole list. The individual elements are instead lazily constructed. What we want to check is how this data structure behaves when we fold it to sum up its elements. We will do fold from left-to-right and from right-to-left. If there are any problems associated with ranges they will most likely show up with large enough ranges. For comparison, we will also create ordinary lists, vectors, arrays, and streams to compare against.

val (start,end) = (1,5000000)
val sum = (a: Int, b: Int) => a + b
 
val rangeTasks = List(
  task(id="range+sum",       fn=() => (start to end).sum) _,
  task(id="range+foldLeft",  fn=() => (start to end).foldLeft(0)(sum)) _,
  task(id="range+foldRight", fn=() => (start to end).foldRight(0)(sum)) _
)
 
val listTasks = List(
  task(id="list+sum",       fn=() => List.range(start,end).sum) _,
  task(id="list+foldLeft",  fn=() => List.range(start,end).foldLeft(0)(sum)) _,
  task(id="list+foldRight", fn=() => List.range(start,end).foldRight(0)(sum)) _
)
 
val vectorTasks = List(
  task(id="vector+sum",       fn=() => Vector.range(start,end).sum) _,
  task(id="vector+foldLeft",  fn=() => Vector.range(start,end).foldLeft(0)(sum)) _,
  task(id="vector+foldRight", fn=() => Vector.range(start,end).foldRight(0)(sum)) _
)
 
val arrayTasks = List(
  task(id="array+sum",       fn=() => Array.range(start,end).sum) _,
  task(id="array+foldLeft",  fn=() => Array.range(start,end).foldLeft(0)(sum)) _,
  task(id="array+foldRight", fn=() => Array.range(start,end).foldRight(0)(sum)) _
)
 
val streamTasks = List(
  task(id="stream+sum",       fn=() => Stream.range(start,end).sum) _,
  task(id="stream+foldLeft",  fn=() => Stream.range(start,end).foldLeft(0)(sum)) _,
  task(id="stream+foldRight", fn=() => Stream.range(start,end).foldRight(0)(sum)) _
)
 
val itrTasks = List(
  task(id="list+itr+foldRight",   fn=() => List.range(start,end).iterator.foldRight(0)(sum)) _,
  task(id="stream+itr+sum",       fn=() => Stream.range(start,end).iterator.sum) _,
  task(id="stream+itr+foldRight", fn=() => Stream.range(start,end).iterator.foldRight(0)(sum)) _
)
 
val benchs = (
  rangeTasks ++ listTasks ++ vectorTasks ++ arrayTasks ++ streamTasks ++ itrTasks
).map(
  task => benchmark(task)(runs=2,warmups=1)(warmupReport,runReport) _
)
 
batch(benchs)(benchReport)(batchReport)

Running this code had the following results on my computer. It shows that foldRight() is having problems in most collections. Lists and streams seems to have stumbled upon some problems with the callstack. If the range is extended slightly further, it will also show that foldRight() on a range will run out of memory. Don’t get too worried though. If the number of elements are quite small, these constraints have little influence. Also, per Scala mailing list you can avoid this problem by turning your sequence into an iterator with seq.iterator.foldRight(), which will add the necessary optimizations to counter the lack of tail-call optimization in the JVM.

range+sum warmup 1 completed in 185ms
range+sum run 1 completed in 139ms
range+sum run 2 completed in 140ms
range+sum finished in 279ms
 
range+foldLeft warmup 1 completed in 138ms
range+foldLeft run 1 completed in 140ms
range+foldLeft run 2 completed in 140ms
range+foldLeft finished in 280ms
 
range+foldRight warmup 1 completed in 2s774ms
range+foldRight run 1 completed in 1s280ms
range+foldRight run 2 completed in 1s249ms
range+foldRight finished in 2s529ms
 
list+sum warmup 1 completed in 1s682ms
list+sum run 1 completed in 1s179ms
list+sum run 2 completed in 1s581ms
list+sum finished in 2s761ms
 
list+foldLeft warmup 1 completed in 1s428ms
list+foldLeft run 1 completed in 1s615ms
list+foldLeft run 2 completed in 1s478ms
list+foldLeft finished in 3s94ms
 
list+foldRight warmup  1 failed after 682ms from java.lang.StackOverflowError
list+foldRight run  1 failed after 869ms from java.lang.StackOverflowError
list+foldRight run  2 failed after 741ms from java.lang.StackOverflowError
list+foldRight failed
 
vector+sum warmup 1 completed in 792ms
vector+sum run 1 completed in 945ms
vector+sum run 2 completed in 783ms
vector+sum finished in 1s728ms
 
vector+foldLeft warmup 1 completed in 831ms
vector+foldLeft run 1 completed in 908ms
vector+foldLeft run 2 completed in 745ms
vector+foldLeft finished in 1s654ms
 
vector+foldRight warmup 1 completed in 2s67ms
vector+foldRight run 1 completed in 1s888ms
vector+foldRight run 2 completed in 2s51ms
vector+foldRight finished in 3s939ms
 
array+sum warmup 1 completed in 587ms
array+sum run 1 completed in 303ms
array+sum run 2 completed in 284ms
array+sum finished in 588ms
 
array+foldLeft warmup 1 completed in 268ms
array+foldLeft run 1 completed in 269ms
array+foldLeft run 2 completed in 328ms
array+foldLeft finished in 597ms
 
array+foldRight warmup 1 completed in 254ms
array+foldRight run 1 completed in 267ms
array+foldRight run 2 completed in 245ms
array+foldRight finished in 512ms
 
stream+sum warmup  1 failed after 10s30ms from java.lang.OutOfMemoryError
stream+sum run  1 failed after 9s46ms from java.lang.OutOfMemoryError
stream+sum run  2 failed after 9s271ms from java.lang.OutOfMemoryError
stream+sum failed
 
stream+foldLeft warmup 1 completed in 575ms
stream+foldLeft run 1 completed in 606ms
stream+foldLeft run 2 completed in 574ms
stream+foldLeft finished in 1s181ms
 
stream+foldRight warmup  1 failed after 1ms from java.lang.StackOverflowError
stream+foldRight run  1 failed after 2ms from java.lang.StackOverflowError
stream+foldRight run  2 failed after 2ms from java.lang.StackOverflowError
stream+foldRight failed
 
list+itr+foldRight warmup 1 completed in 2s925ms
list+itr+foldRight run 1 completed in 2s812ms
list+itr+foldRight run 2 completed in 3s19ms
list+itr+foldRight finished in 5s831ms
 
stream+itr+sum warmup 1 completed in 1s547ms
stream+itr+sum run 1 completed in 1s41ms
stream+itr+sum run 2 completed in 871ms
stream+itr+sum finished in 1s912ms
 
stream+itr+foldRight warmup 1 completed in 3s715ms
stream+itr+foldRight run 1 completed in 3s438ms
stream+itr+foldRight run 2 completed in 3s623ms
stream+itr+foldRight finished in 7s62ms
 
Batch of benchmarks finished with 15 completed and 3 failed.
 
Average times for benchmarks:
     139ms range+sum
     140ms range+foldLeft
     256ms array+foldRight
     294ms array+sum
     298ms array+foldLeft
     590ms stream+foldLeft
     827ms vector+foldLeft
     864ms vector+sum
     956ms stream+itr+sum
   1s264ms range+foldRight
   1s380ms list+sum
   1s547ms list+foldLeft
   1s969ms vector+foldRight
   2s915ms list+itr+foldRight
   3s531ms stream+itr+foldRight
        na list+foldRight
        na stream+sum
        na stream+foldRight

Making objects queryable in Scala

May 2nd, 2011 | June 22nd, 2011    , ,

Defining a Queryable trait

In a running program its often nice to have a way of querying and updating the various components of the application. In this example I’ll demonstrate one way you could do this in Scala by defining a Queryable trait. By inheriting this trait, an object can make available properties for reads and updates, and enable traversal to other objects. The data-format used for read results and updates is xml.

The query uses syntax similar to xpath. A few example usages could be:

  • Read a property by config.cache.dir
  • Filter on collection of objects by app.tasks[status='idle'].id
  • Write to a single-valued property by config.screen.width = <width>800</width>
  • Write to a structural-valued property by config.audio.format = <format chan="2" rate="48.0kHz" res="24bit"/>
  • Apply a method by app.playlist.queue = <file type="mp3" loc="http://tunes.com/tune.mp3"/>

Queryable objects can choose between the following kinds of properties:

  • QueryVal for read-only access
  • QueryVar for read-write access
  • QueryDef for an applicable property (similar to write)
  • QueryPath for traversal to named object(s)

The complete sourcecode for the trait is defined as follows.

import scala.util.matching.Regex
import scala.util.parsing.combinator._
 
/**
 * Query Syntax
 *   query         ::= {query-path `.`} query-leaf query-value?
 *   query-path    ::= name-path filters?
 *   query-leaf    ::= name-leaf
 *   query-value   ::= `=` <a xml element>
 *   name-path     ::= ([a-zA-Z][-a-zA-Z0-9]*)
 *   name-leaf     ::= ([a-zA-Z][-a-zA-Z0-9]*)|[?]
 *   filters       ::= `[` {filter `,`} `]`
 *   filter        ::= filter-key `=` `'` filter-value `'`
 *   filter-key    ::= [a-zA-Z][-a-zA-Z0-9]*
 *   filter-value  ::= `'` <an escaped string> `'`
 */
trait Queryable {
  import Queryable._
 
  private val queryKeys: () => Seq[xml.Elem] =
    () => {
      for (item <- queryMap.keys.toSeq) yield {
        <key name={item} doc={queryMap(item)._1} type={queryMap(item)._2.typeId}/>
      }
    }
 
  protected var queryMap = Map[String,(String,QueryNode)](
    "?" -> (
      "Lists all queryable keys." -> QueryVal(
        read = queryKeys
      )
    )
  )
 
  final def query(expr: String): Either[String,xml.Elem] = {
    try {
      val parser = new QueryParser
      parser.parseAll(parser.queryPath, expr) match {
        case parser.Success((path,value), remaining) =>
          Right(<query expr={expr}>{ query(path,value) }</query>)
        case parser.Error(msg, remaining) =>
          Left("error while parsing query: " + msg)
        case parser.Failure(msg, remaining) =>
          Left("failure while parsing query: " + msg)
        case err =>
          Left("unknown error while parsing query: " + err)
      }
    }
    catch {
      case exp: Exception => Left("exception caught during query: " + exp)
    }
  }
 
  private def query(path: Seq[Prop], value: Option[xml.Elem]): Seq[xml.Elem] = {
    path.toList match {
      case (key,filters) :: Nil if queryMap contains key =>
        (queryMap(key)._2,value) match {
          case (QueryVal(read),None)           => read()
          case (QueryVar(read,_),None)         => read()
          case (QueryVar(_,write),Some(value)) => write(value)
          case (QueryDef(apply),Some(value))   => apply(value)
          case _                               => Nil
        }
      case (key,filters) :: tail if queryMap contains key =>
        queryMap(key)._2 match {
          case QueryPath(next) =>
            next()
              .filter(node => filters.forall(item => contains(node,item)))
              .flatMap(node => node.query(tail,value))
          case _ => Nil
        }
      case _ => Nil
    }
  }
 
  private def contains(node: Queryable, check: (String,String)): Boolean = {
    if (node.queryMap.contains(check._1) == false) {
      false
    }
    else {
      val regex = new Regex(check._2)
      node.queryMap(check._1)._2 match {
        case QueryVal(read) =>
          read().headOption.exists(
            item => regex.findPrefixOf(item.text).isDefined
          )
        case QueryVar(read,_) =>
          read().headOption.exists(
            item => regex.findPrefixOf(item.text).isDefined
          )
        case _ => false
      }
    }
  }
}
 
 
object Queryable {
  import xml.XML.{loadString => toXml}
 
  private type Prop = (String,Map[String,String])
 
  sealed trait QueryNode {
    def typeId(): String
  }
  case class QueryVal(read: () => Seq[xml.Elem]) extends QueryNode {
    def typeId(): String = "val"
  }
  case class QueryVar(read: () => Seq[xml.Elem],
                      write: xml.Elem => Seq[xml.Elem]) extends QueryNode {
    def typeId(): String = "var"
  }
  case class QueryDef(apply: xml.Elem => Seq[xml.Elem]) extends QueryNode {
    def typeId(): String = "def"
  }
  case class QueryPath(next: () => Seq[Queryable]) extends QueryNode {
    def typeId(): String = "path"
  }
 
  private class QueryParser extends JavaTokenParsers {
    def queryPath: Parser[(Seq[Prop],Option[xml.Elem])] =
      repsep(query, ".") ~ opt(white ~ "=" ~> white ~> queryValue) ^^ {
        case path ~ value => (path,value)
      }
 
    def query: Parser[Prop] =
      queryName ~ opt(queryFilters) ^^ {
        case name ~ Some(filters) => (name,filters)
        case name ~ None          => (name,Map())
      }
 
    def queryName: Parser[String] = """([a-zA-Z][-a-zA-Z]*)|[\?]""".r
 
    def queryFilters: Parser[Map[String,String]] =
      "[" ~ white ~> repsep(queryFilter, white ~> "," <~ white) <~ "]" ^^ {
        (Map() ++ _)
      }
 
    def queryFilter: Parser[(String,String)] =
      filterKey ~ "=" ~ filterValue ^^ {
        case key ~ "=" ~ value => (key,value)
      }
 
    def queryValue(): Parser[xml.Elem] =
      new Parser[xml.Elem] {
        def apply(in: Input): ParseResult[xml.Elem] = {
          // manually parse xml element from text
          val (begin,end) = (in.offset,in.source.length)
          if (begin >= end) {
            Error("Empty value", in)
          }
          else {
            val elem = toXml(in.source.subSequence(begin,end).toString)
            Success(elem, in.drop(end - begin))
          }
        }
      }
 
    def filterKey: Parser[String] = """[a-zA-Z][-a-zA-Z]*""".r
 
    def filterValue: Parser[String] =
      "'" ~> """[^']+""".r <~ "'" ^^ {
        (value: String) => value
      }
 
    def white: Parser[Option[String]] = opt("""[ \t]+""".r)
  }
}

An example usage

For the demonstration, lets define a few classes that implements the Queryable trait.

case class Song(title: String, composer: String, duration: String)
  extends Queryable {
  import Queryable._
 
  queryMap += (
    "title" -> ("The song's title." -> QueryVal(
      read = () => {<title>{title}</title> :: Nil}
    )),
    "composer" -> ("The song's composer." -> QueryVal(
      read = () => {<composer>{composer}</composer> :: Nil}
    )),
    "xml" -> ("Transform into xml." -> QueryVal(
      read = () => {<song title={title} composer={composer} duration={duration}/> :: Nil}
    ))
  )
}
 
class Jukebox extends Queryable {
  import Queryable._
 
  private var status = "idle"
  private var songs  = List.empty[Song]
 
  def queue(song: Song) { songs = song :: songs }
 
  queryMap += (
    "xml" -> ("Transform into xml." -> QueryVal(
      read = () => {<jukebox status={status} size={songs.length.toString}/> :: Nil}
    )),
    "status" -> ("Status of jukebox." -> QueryVal(
      read = () => {<status>{status}</status> :: Nil}
    )),
    "songs" -> ("Traverse to songs." -> QueryPath(
      next = () => {songs}
    )),
    "queue" -> ("Queues a song from xml." -> QueryDef(
       apply = (elem: xml.Elem) => {
         val song = Song(
           title    = (elem \ "@title").text,
           composer = (elem \ "@composer").text,
           duration = (elem \ "@duration").text
         )
         songs = song :: songs
         <queue>done</queue> :: Nil
       }
    ))
  )
}
 
class App extends Queryable {
  import Queryable._
 
  var status = "ready"
  val jukebox = new Jukebox
 
  queryMap += (
    "xml" -> ("Transform into xml." -> QueryVal(
      read = () => {<app status={status}/> :: Nil}
    )),
    "jukebox" -> ("Traverse to jukebox." -> QueryPath(
      next = () => {jukebox :: Nil}
    ))
  )
}

Before demonstrating the Queryable trait using the App, Jukebox, and Song classes, lets also create an utility function for printing out the Either values that Queryable.query() returns.

def print(value: Either[String,xml.Elem]) {
  val printer = new xml.PrettyPrinter(width=80,step=2)
  value match {
    case Right(result) => println(printer format result)
    case Left(error)   => println(error)
  }
}

Lets start by creating the app and query which properties it and the jukebox has.

val app = new App
print(app query "?")
print(app query "jukebox.?")
<query expr="?">
  <key doc="Lists all queryable keys." type="val" name="?"></key>
  <key doc="Transform into xml." type="val" name="xml"></key>
  <key doc="Traverse to jukebox." type="path" name="jukebox"></key>
</query>
<query expr="jukebox.?">
  <key doc="Queues a song from xml." type="def" name="queue"></key>
  <key doc="Traverse to songs." type="path" name="songs"></key>
  <key doc="Transform into xml." type="val" name="xml"></key>
  <key doc="Status of jukebox." type="val" name="status"></key>
  <key doc="Lists all queryable keys." type="val" name="?"></key>
</query>

Now, lets add some songs programatically and query the jukebox for status and songs.

app.jukebox.queue(Song(title="Mars", composer="Gustav Holst", duration="7m05s"))
app.jukebox.queue(Song(title="Jupiter", composer="Gustav Holst", duration="7m51s"))
print(app query "jukebox.status")
print(app query "jukebox.songs.xml")
<query expr="jukebox.status">
  <status>idle</status>
</query>
<query expr="jukebox.songs.xml">
  <song composer="Gustav Holst" title="Jupiter" duration="7m51s"></song>
  <song composer="Gustav Holst" title="Mars" duration="7m05s"></song>
</query>

And a narrow search against specific songs using filtering (note that filter values are treated as regexes).

print(app query "jukebox.songs[title='Ma',composer='Gustav'].xml")
<query expr="jukebox.songs[title='Ma',composer='Gustav'].xml">
  <song composer="Gustav Holst" title="Mars" duration="7m05s"></song>
</query>

Lets queue a new song on the jukebox by specifying its data in xml.

print(app query ("jukebox.queue = " + <song title="Nocturnes III" composer="Claude Debussy" duration="10m40s"/>))
<query
expr="jukebox.queue = &lt;song composer=&quot;Claude Debussy&quot; title=&quot;Nocturnes III&quot; duration=&quot;10m40s
&quot;&gt;&lt;/song&gt;">
  <queue>done</queue>
</query>

And finally, searching for the included song.

print(app query "jukebox.songs[composer='Claude'].xml")
<query expr="jukebox.songs[composer='Claude'].xml">
  <song composer="Claude Debussy" title="Nocturnes III" duration="10m40s"></song>
</query>

In summary

Fairly little code was necessary to integrate a querying mechanism into objects. Both the parser combinators and the collection library were of great help. Now, the parser combinators aren’t know to be high performance but that is hardly a problem with the small chunks of text being parsed. There are still some places where this solution is lacking though, like filtering being restricted to single-valued properties, lack of validation, and the dependence on a specific data-format like xml. Maybe the trait should be more asynchronous? This is still work in progress and might receive some updates later on.

If you have any suggestions please drop a comment!

Learning Scala

April 19th, 2011 | September 5th, 2011    ,

Learning the basics

The first edition of Programming in Scala has been made available in html on Artima.com. It’s a great book to learn Scala from if you’re interested in learning this language. I should note that this book assumes you are already familiar with at least some programming languages like Java or C/C++. Expect some months worth of work before getting familiar with Scala. Especially concepts related to functional programming and type system which can take years to appreciate. Higher-order-functions/closures should be easier to pick up if you have experience with dynamic languages like Javascript. New concepts in relation to object-oriented programming builds on established ones.

A couple of notes on how Scala might differ

Besides including an ordinary compiler for generating code, Scala can also run code interactively from shell/command. With a properly set up installation, you can start it by typing scala in your shell/command.

C:\Users\Trond>scala
Welcome to Scala version 2.8.1.final (Java HotSpot(TM) Client VM, Java 1.6.0_24).
Type in expressions to have them evaluated.
Type :help for more information.
 
scala> val (evens,odds) = (0 to 9).partition(item => item % 2 == 0)
evens: scala.collection.immutable.IndexedSeq[Int] = Vector(0, 2, 4, 6, 8)
odds: scala.collection.immutable.IndexedSeq[Int] = Vector(1, 3, 5, 7, 9)
 
scala>

Syntax is a little bit different than what you might be familiar with. Variables does not follow the int x = 0; convention, but instead uses `declare` `name`: `type` = `expression`.

val x: Int = 0 // a val declared variable can only be assigned once
var y: Int = 1 // a var declared variable can be assigned multiple times
y = 2

Type inference means you don’t need to write out the type for variables (nor semicolons ending expressions).

val x = "Hello" // the type of x is inferred to be String

The object-oriented side of Scala offers the concept of a class’ companion object. This means that the static side and instanced side of a class are separated. The static side is now located in the companion object. This solution also enables the companion object to implement and inherit other functionality without affecting the companion class.

// the companion object
object Transform with MatrixUtil[Double] {
  val Identity = Transform(IdentityMatrix4)
}
 
// the companion class
class Transform(private val elems: Array[Double]) {
}

One last thing about Scala. It is not based on programming using statements as in C-like languages. Every line of code is instead an expression that will yield a value. The resulting type for an expression that would be similar to a statement is Unit who’s only value is (). As being based on expressions you rarely need the return keyword.

// the full syntax version
def say(value: Int): Unit = {
  println("I have a " + value)
  ()  // the Unit value
}
// the short syntax version
def say(value: Int): Unit = {
  println("I have a " + value) // the type of println is String -> Unit
}
// the shortest syntax version
def say(value: Int) { println("YEEHAW! I got me a " + value) }

Programming in Scala will give you a thorough introduction to the language. It a fun and expressive language to use, and if you have a small project that targets the Java Virtual Machine I think you’ll be pleasantly surprised with Scala.

Profiling performance in Scala

February 13th, 2011 | February 1st, 2014    ,

Boxing and unboxing of primitive types

Using primitive types in parameterized generic classes can lead to some performance degradation in Scala. Type parameters in generic classes cannot be resolved as primitive types and instead becomes Object references. This mean primitive types like Int or Float in type parameters must be converted to and from an Object for each method invocation involving these type parameters. This boxing and unboxing can be optimized away using the @specialized annotation introduced in Scala 2.8. Some additional classes and methods for handling primitive types will as a result get added for each specialized generic class.

class Data[@specialized T](x: Int, y: Int, value: T)

To get the benefits of @specialized you need to annotate type parameters in your generic classes. If you are unsure where unboxing and boxing leads to the biggest performance hits, you need to profile your application with a tool like VisualVM, which is freely available and is fairly easy to get started with. It runs in it’s own JVM and let you connect to and profile other running JVMs.

During profiling you need to look for invocation of methods from scala.runtime.BoxesRunTime. These will be listed as BoxesRunTime.boxToInt and BoxesRunTime.unboxToInt etc. for each primitive type. A high number of invocations of these methods means your generic classes can be optimized for boxing and unboxing. To find the stacktraces that resulted in these calls, you must create snapshots from the running profiler. In these snapshots you can trace where the boxing and unboxing originated from.

For more information about the @specialized annotation see this talk by Iulian Dragos who was responsible for its implementation in Scala.

References

Common operations in the Scala collection library

January 23rd, 2011 | March 8th, 2014    ,

Here’s a list of most operations you can perform on scala collections. Notation is mostly ordinary Scala syntax except for some set-like builder notation and type signature of functions.

common-collections-methods