OOPSLA ~ External Benchmarks Framian Vectors

This page describes an external benchmark: a full description is outside of the scope of this wiki, but we recommend seeing the io.pellucid.com blog for more information. The reason this benchmark was included in the tutorial is because miniboxing uses a mechanism similar to ildl to transform the function representation.

The benchmark files described in the reminder of this presentation are available in the optimistic-spec-article repository. This case study/benchmark is forked from the pellucid blog that was featured as a series of articles on specialization and miniboxing.

Description

The Framian Vector implementation is an exploration into deeply specializing the immutable Vector bulk storage without using reified types or specialization. The goal of that project is to create a vector datatype, that maintains the performance of C code when mapping over it. The authors relied on hand-written specialized code assisted by runtime reflection and casts and they manage to achieve their goal. We included this experiment because miniboxing (with the additions that are discussed in the paper about the function transformation and a new array type) managed to achieve the same goal with extremely minimal effort.

In more detail the challenge is the following: by simply invoking the map method on a vector that holds values of primitive type (e.g. Double), is it possible to achieve the same performance as a hand-written loop that performs the same operation?

sealed trait Vec[A] {
  def size: Int
  def apply(i: Int): A
  def map[B](f: A => B): Vec[B]
}

object Vec {
  def apply[A](elems: Array[A]): Vec[A] = ???
}

The project is divided into 6 attempts towards the goal and the thought process was documented at the pellucid blog. To play around with the code-base we forked the code that accompanied the blog post's analysis and we provide an updated setup. The command sequence as-is in the original project is shown below (for attempt1, the first in 6 different solutions):

$ git@github.com:biboudis/optimistic-spec-article.git
$ cd optimistic-spec-article
$ sbt
> project attempt1
> benchmark

The miniboxed code is represented by a sixth attempt that was later added to the project:

package respec

final class Vec[@miniboxed T](elems: MbArray[T]) {
  def size: Int = elems.length
  def apply(i: Int): T = elems(i)
  def map[@miniboxed B](f: T => B): Vec[B] = {
    val a = MbArray.empty[B](elems.length)
    var i = 0
    while (i < elems.length) {
      a(i) = f(elems(i))
      i += 1
    }
    new Vec(a)
  }
}

object Vec {
  def apply[@miniboxed A](elems: Array[A]): Vec[A] = new Vec(MbArray.clone(elems))
}

In this code, manual specialization is avoided by using a data structure that is included in the miniboxing plugin, MbArray and is essentially an alternative to Scala's Array. MbArray automatically uses the miniboxing transformation information to create the best array type for each instantiation.

Running the Benchmarks

In the sbt console window and for attempt 6 we run:

$ sbt
> project attempt6
> benchmark

The results of the benchmark are: Results:

| Benchmark                    | μs     |
|------------------------------|--------|
| Manual C-like code           | 0.650  |
| Miniboxing with functions    | 0.705  |
| Generic                      | 13.409 |

From Here:

Congratulations! You've gone through all the benchmarks!

• get back to the home page