Building a Simple and Performant DSL in Scala

Scala provides different language constructs by which a wide variety of DSLs can be made. Implicits, operators as name of functions, macros, higher order functions etc. are examples of those constructs. However, building a DSL is not a trivial task especially when performance matters. In this blog post, I am going to talk about a simple DSL that I built in Scala to convert objects to a sequence of bytes. As a use case, the resulting byte array can be used to create a hash (e.g. MD5 or SHA) for a piece of data. The DSL’s aim is to be concise and efficient.
Here is a Java way to create a byte array out of a sequence of different values:

final ByteArrayOutputStream baos = new ByteArrayOutputStream();
final DataOutputStream dos = new DataOutputStream(baos);

dos.writeChars("DSL");
dos.writeInt(32);
dos.writeBoolean(true);

dos.close();

final byte[] result = baos.toByteArray();

By running this code, result will contain 10 bytes, out of which 5 bytes to represent str, 4 bytes for i and one single byte for b. In standard UTF-8 encoding, str will encode to 3 bytes but writeUTF creates modified UTF-8 where it starts with preceding two bytes stating the length of the byte sequence. As it is Java, the code has lots of boilerplate but it is quite performant. Obviously, if we come up with a concise DSL to eliminate the boilerplates while preserving the performance, we will achieve our goal. So let’s define the desired DSL syntax first.

Usually APIs become easier to use if they provide meaningful method chaining. Moreover, Scala lets us use operators as the name of functions. This means that we can define DSLs which support operation chaining. I would like to chain ~ operator to create an array of byte representing all the values that formed the chain. Therefore, the above code can be concisely implemented as follows:

val result: Array[Byte] = "DSL" ~ 32 ~ true

To preserve performance, we can keep using DataOutputStream underneath. Thus, we need to create its instance together with an instance of ByteArrayOutputStream as its underlying output stream in the beginning of the flow. Obviously, the DataOutputStream instance should be closed and the bytes should be retrieved from the ByteArrayOutputStream instance at the end of the flow. For simplicity, I add unary operation ~| to our DSLs to show the end of the flow:

val result = "DSL" ~ 32 ~ true ~|

Now we have to find out how it is possible to build this DSL. First, let’s try to break our DSL into small pieces. Here are couple of observations:

  1. Since we want to be able to invoke ~ operator on any object, we have to extend all types to support ~.
  2. At the beginning of the chain, ~ is an operation defined on String and accepts instances of any type as its argument. As mentioned in the previous point, this operator is not just defined on String but on all types. In our example, the first ~ invocation can be desugared to "DSL".~(32).
  3. This operation produces an instance of a type which:
    • Supports ~ operation which accepts instances of any type as its argument. In our example, it accepts true.
    • Carries and mutates DataOutputStream and ByteArrayOutputStream created at the beginning of the flow.
    • Supports operation ~| which closes DataOutputStream instance and retrieves bytes from ByteArrayOutputStream instance.

As seen, I differentiated between the first ~ and the rest. The first one is defined on all types and produces an instance of a special type (let’s say Container). However, other ~ operators, are defined on Container and produce Container.

First, I start with defining Container. As mentioned before, Container is responsible for carrying and mutating DataOutputStream and ByteArrayOutputStream. Moreover, it should support ~ and ~|. The implementation of ~ will come later. The complete source code can be found here.

case class Container(dos: DataOutputStream, baos: ByteArrayOutputStream) {
    // TODO: def ~

    def ~| : Array[Byte] = {
        dos.close()
        baos.toByteArray
    }
}

object Container {
    def apply() = {
        val baos = new ByteArrayOutputStream()
        val dos = new DataOutputStream(baos)
        new Container(dos, baos)
    }
}

Now, we need to provide a mechanism to abstract writing different values into DataOutputStream. Different DataOutputStream methods should be invoked to write different data types into the underlying output stream (e.g. writeInt, writeBoolean etc.). Scala type classes are a perfect way to abstract these differences while keeping extensibility. Take a look at the following code snippet:


trait ByteSequenceRepr[A] {
    def writer: (Container, A) => Unit

    def toByteSequence(arg: A): Container = {
        val baos = new ByteArrayOutputStream()
        val dos = new DataOutputStream(baos)
        toByteSequence(Container(dos, baos), arg)
    }

    def toByteSequence(container: Container, arg: A): Container = {
        writer(container, arg)
        container
    }
}

ByteSequenceRepr is the actual type class which accepts a type parameter. It provides a writer higher order function which yields a function to write instances of type A into DataOutputStream embedded in the Container instance. Additionally, our type class has two other functions which actually mutate (or create and mutate) the Container instance using available writer. Later, I will explain how this type class is going to help us.

Now, let’s implement the missing ~ operator on Container case class:


...

def ~[A](arg: A)(implicit bsr: ByteSequenceRepr[A]) = bsr.toByteSequence(this, arg)
...

~ accepts an argument of type A and it needs an instance of ByteSequenceRepr of type A available in the scope. The logic is quite simple; using the available ByteSeqeunceRepr, the given instance of A is written into DataOutputStream carried by Container instance. Of course, you may rewrite this function using context bound and implicitly mechanism.
To make the life of DSL’s users even easier, we can provide default ByteSequenceRepr implicits for primitive data types. I created LowPriorityDefaultByteSequenceReprImplicits trait and put different ByteSequenceRepr there (the complete version is here):


trait LowPriorityDefaultByteSequenceReprImplicits {
    implicit val intToByteSequence: ByteSequenceRepr[Int] =
    new ByteSequenceRepr[Int] {
        val writer: (Container, Int) => Unit = _.dos.writeInt(_)
    }

    implicit val stringToByteSequence: ByteSequenceRepr[String] =
    new ByteSequenceRepr[String] {
        val writer: (Container, String) => Unit = _.dos.writeChars(_)
    }

    implicit val booleanToByteSequence: ByteSequenceRepr[Boolean] =
    new ByteSequenceRepr[Boolean] {
        val writer: (Container, Boolean) => Unit = _.dos.writeBoolean(_)
    }
}

object ByteSequenceRepr extends LowPriorityDefaultByteSequenceReprImplicits

Implicits have been defined in ByteSequenceRepr companion object. In this way, the default implicits will have the lowest priority when they are being looked up. Thus, for example, if the user wants to provide a new implementation for string ByteSequenceRepr, she/he just needs to add a new implicit in the scope and that one will have the higher priority than the default one. Here, you can find a detailed explanation of implicits finding rules.

As mentioned before, in addition to Container which supports ~ and ~| operator, all data types should also support them. Implicit function and implicit class are two mechanisms in Scala to extend the existing APIs without introducing new inherited data types. It is known as “Pimp my library” pattern:


object Implicits {
    implicit class WithTilde[A](val left: A) extends AnyVal {
        def ~[B](right: B)(implicit seqA: ByteSequenceRepr[A], seqB: ByteSequenceRepr[B]): Container = {
            val container = seqA.toByteSequence(left)
            seqB.toByteSequence(container, right)
        }

        def ~|(implicit seqA: ByteSequenceRepr[A]): Array[Byte] = seqA.toByteSequence(left).~|
    }
}

Let’s have another look to our example:

val result = "DSL" ~ 32 ~ true ~|

The first invocation of ~ is on "DSL" and the argument of this call is 32. Therefore, first, the Container instance should be created having "DSL" written into its DataOutputStream field. Then it should be mutated by writing 32 in it. This happens by calling two different overloads of toByteSequence on available ByteSequenceRepr instances in WithTilde ~ implementation. ~ yields a Container instance, so all the subsequent ~ invocations (i.e. ~ true) will be done on that resulting container. WithTilde implicit class extends AnyVal so a new instance of WithTilde class is not created every time that the conversion needed. Moreover Container instance is mutated and passed through instead of being re-created every time so the heap size is not increased drastically.

Actually, we are done. By importing Implicits._, we can benefit from our concise DSL. We can extend it easily for any composite data type as well. You just need to provide a ByteSequenceRepr instance of that type in the scope:


case class Point(x: Int, y: Int)

implicit val pointToByteSequence: ByteSequenceRepr[Point] =
new ByteSequenceRepr[Point] {
    val writer: (Container, Point) => Unit = { (container, point) =>
        container.dos.writeInt(point.x)
        container.dos.writeInt(point.y)
    }
}

val result = Point(12, 15) ~ "Hello" ~ 127 ~ 123L ~ true ~|

Our DSL has a very small memory usage overhead comparing to the pure java approach due to intermediate Container objects that being created. However, since for each chain, we instantiate Container just once, it is negligible.

We can go even further by using shapeless to define a general ByteSequenceRepr to convert any case class to a sequence of bytes. The basic idea is that shapeless provides HList data type to model heterogenous lists. Additionally, shapeless supports a mechanism to implicitly convert any case class to a HList. So, if you provide an implicit ByteSequenceRepr for HList, you can use it to implicitly convert any case class to an array of bytes. By having that, you do not need to provide an implicit ByteSequenceRepr for Point case class in the above example. Of course, it is not without cost and because of those intermediate implicit conversions, the memory consumption will be increased. The complete source code of using shapeless can be also found here. I am not going more into details of shapeless but you may get the basic idea by reading this.

Drawback

Although the DSL is concise and performant, it is not fold friendly. If there is a list containing different objects and the goal is to create a single byte array out of all of them, we have to do it as follows:


val list = List("DSL", 32, true)

val result = list.foldLeft(Container())(_ ~ _) ~|

So it leaks some underlying structures (Container) which is not ideal.

Conclusion

Building a custom DSL should be done carefully especially from the memory management point of view. If you are using different internal DSLs in your server side application, under the load, the sum of the memory usage of them may negatively impact the server performance. Moreover, although we need to keep immutability, sometimes to improve performance, we may use a mutable data structure underneath but that should be encapsulated properly.

Advertisements

Scala Streams: A Deeper Look

To start, let’s take a look at the following code:

def process(xs: => Traversable[Int]) = xs.map(_ + 10).filter(_ % 3 == 0).map(_ * 2)

process function is just a chain of transformations on the given Traversable. Each of these transformations will create an intermediate traversable to be passed to the next transformation function. Given xs = Array(1, 2, 5), the manual tracing output would be:

1 is increased by 10 so transferred to 11
2 is increased by 10 so transferred to 12
5 is increased by 10 so transferred to 15
11 is filtered out because it is not a multiple of 3
12 is kept because it is a multiple of 3
15 is kept because it is a multiple of 3
12 is multiplied by 2 so transferred to 24
15 is multiplied by 2 so transferred to 30

In imperative programming style, this computation can be done “easily” with a while loop which transform each element of xs to the final desired value in one go. So no intermediate traversable will be created and this means less memory allocation. In this case, the manual tracing output would be:

1 is increased by 10 so transferred to 11
11 is filtered out because it is not a multiple of 3
2 is increased by 10 so transferred to 12
12 is kept because it is a multiple of 3
12 is multiplied by 2 so transferred to 24
5 is increased by 10 so transferred to 15
15 is kept because it is a multiple of 3
15 is multiplied by 2 so transferred to 30

How can we keep the compositional style (composing higher order functions like map, filter etc.) but without creating intermediate results to use memory more efficiently?

This can be achieved by using non-strict data structures. Non-strict (or lazy) data structures defer a computation until it is needed. In Scala, Stream is an implementation of non-strict sequence. Here is a simplified version of Stream implementation:

trait Stream[+A]
case class Cons[+A](head: A, tail: () => Stream[A]) extends Stream[A]
case object Empty extends Stream[Nothing]  

As seen above, the main difference between Stream and other strict sequences such as List is that the tail is a function instead of a strict value. So, tail is not being evaluated until it is forced. Let’s play with our Stream data structure to see how it works.

First, let’s create a convenient apply function

object Stream {
   def apply[A](xs: A*): Stream[A] = if (xs.isEmpty) Empty else Cons(xs.head, () => apply(xs.tail:_*))
}

Now let’s add a simple version of map and filter to our Stream trait.

trait Stream[+A] {
   def map[B](f: A => B): Stream[B] = this match {
      case Empty => Empty
      case Cons(h, t) => Cons(f(h), () => t().map(f))
   }

   def filter(f: A => Boolean): Stream[A] = this match {
      case Empty => Empty
      case Cons(h, t) =>
         if (f(h)) 
            Cons(h, () => t().filter(f)) 
         else 
            t().filter(f)
  }
}

Now, let’s partially trace our motivating example:

Stream(1, 2, 5).map(_ + 10).filter(_ % 3 == 0).map(_ * 2)

Upon the invocation of the first map, Stream(1, 2, 5) is matched with the second case (line 4) so Cons(11, function0) is created. function0 notation denotes on a function which if it is invoked, it calls map(_ + 10) on the tail of the original stream. Next, filter function is invoked on the result of the first step which was Cons(11, function0). So it is matched with the second case (line 9). Since 11 is not a multiple of 3, it should be filtered out so else branch is executed. Therefore, function0 is invoked to be evaluated. So we enter again in the map function and again we match to the second case (line 4) and Cons(12, function1) is created. Upon executing filter on this intermediate result, it is again matched to the second case (line 9) but this time, since 12 is a multiple of 3, it is not filtered out (line 11). So Cons(12, function2) is created. Now, map(_ * 2) will be executed on this intermediate result and so on so forth.

As you see:

  • Intermediate results are type of Stream which only has its head evaluated and the rest is not evaluated.
  • The order of the transformations is the same as while loop.

This is why sometimes streams are referred as first-class loops [1]. It seems that we should use this first-class loop instead of strict collections whenever we have a chain of transformations. Is it true?

To answer this question, I benchmarked Scala standard Stream against Array from both memory and throughput aspects. The benchmark source code can be found here.

For memory usage comparison, I implemented MemoryUsage application and monitored the memory usage of different approaches with VisualVM.

I increased the size of data to 50 million elements to make the result more visible in VisualVM. Here is the result:

Streaming vs Collection

As seen, applying the aforementioned chain of transformations on Array needs considerably bigger heap size. However, when the size of data is smaller, the differences is less tangible. But memory usage is just one side of the coin. What about throughput?

Stream data structure heavily uses memoizing. This means that functions that are passed to the constructor are cached in lazy vals to prevent being re-computed. Although lazy values have been designed exactly for this purpose, comparing to vals, they have worse performance. So we can expect that the throughput of stream transformations is less than arrays (or generally strict collections). To experiment this, I did a micro-benchmark using jmh and sbt-jmh. I chose Array and Stream with 10000 elements with the following benchmark setup:

sbt "run -i 5 -wi 5 -f1 -t1 \"StreamingBenchmark\""

And here is the result:

[info]
[info] # Run complete. Total time: 00:00:20
[info]
[info] Benchmark                             Mode  Cnt     Score     Error  Units
[info] StreamingBenchmark.streaming         thrpt    5   880.009 ±  75.244  ops/s
[info] StreamingBenchmark.strictProcessing  thrpt    5  4078.819 ± 276.049  ops/s

As seen, given the previously mentioned transformation chain, Stream throughput is around 4 times less than Array throughput.

Conclusion

Although Streams eliminate intermediate collections upon transformations, it has considerably less throughput comparing Array (of course Array is optimised for traversing but I also executed the benchmark against other strict data structures like Vector and List and in all cases Stream has worse performance but with different ratios). Stream and other non-strict data types are great data structures but they should be used when their characteristics are really needed.

[1]. Chiusano P. and Bjarnason R. (2015). Functional Programming in Scala by Manning