Context:
On my previous project, we wanted to transform a MongoDB document based on what user specified. Say for example, we are offering 20% discount on totalAmount, then we’d expect the user to say something like –
# Our Custom DSL:
#
# Transform a field by using a built-in Arithmetic Operators.
# It takes in an input field and an expression containing built-in
# arithmetic function and returns the result by setting it on the
# output field.
#
# syntax:
# db.things.transform("outputFieldName", "{ $add: ["$age", 1] }")
##################################################################
db.orders.transform('totalAmount', '{ $subtract: ["$totalAmount", { $multiply: ["$totalAmount", 0.2] } ] }')
Apart from the transform operation, there are many other operations that we offer to the user. For each operation we produce a corresponding lambda expression. Many such operations specified by the user result in a collection of lambda expressions that would be applied sequentially one-at-a-time to transform the existing document.
The lambda expression for the above transform operation looked something like this.
def transform(outputField: String, expressionJson: String) : BSONObject => BSONObject = {
((document: BSONObject) => {
try {
val expression: Expression = parse(expressionJson)
val literal = expression.evaluate(document)
document + (outputField, literal.value)
} catch {
case t: Throwable => injectException(document, outputField, t)
}
})
}
As you see in the above code, we return a lambda expression, that goes from document to document (BSONObject). Look at line 4, where we parse the expressionJson, a String to an Expression tree and then the tree is evaluated by consuming the document. This happens each time the lambda is called. This is a serious problem…why? Because,
- Each time the lambda is invoked, the parsing expression JsonString to expression tree is a expensive computation
- Parsing errors are not known until run-time, ideally I would be like to know them when my DSL is parsed
Solution:
I could move the parsing expression line outside of the lambda and satisfy both the above problems, that is, parsing will happen once and closure would close over the expression. This means effectively cached expression tree will be available each time and there would not be any performance penalty of parsing. It would also throw parse errors at DSL compile time, where I map user operation to lambda expression by calling the above transform function.
Forces:
- Preventing Force
In order for me to move to such a solution, there were impediments – we allow users to change DSL at run-time, so that means the new transformation lambdas will be regenerated on-the-fly and the way application worked this out was to generate textual Scala file, compile it and hot-deploy the code into running JVM. So doing the parsing outside the body of the returned lambda meant losing the reference to the expression tree generated during DSL compilation. So the only option was to keep the parsing call within the body of lambda.
- Pushing Force
One of the obvious pushing force is Performance, parsing again and again for every document in the collection, is an expensive computation to repeat, imagine 1000s of documents and many such transform operations, this will make it hellishly slow to respond to requests.
Which Force to tackle?:
Well, it turns out that Pushing Force was easy to nullify as compared to a long-term solution needed to solve the Preventing Force. This is where memoization comes to the rescue. Simply put, if you have a pure function (read side-effect free), then I know that calling it again and again with same set of inputs, results in the same output. This means that we can optimize the program by calling the function once, do the computation and cache its result. For future calls, return the result directly from the cache, thus avoiding that expensive computation. Thus, memoization gives us the ability compute-once, use-many times, a nice technique that trades space for time.
So below is the same function after applying memoization to it.
def transform(outputField: String, expressionJson: String) : BSONObject => BSONObject = {
((document: BSONObject) => {
try {
val expression: Expression = Memoize(parse)(expressionJson)
val literal = expression.evaluate(document)
document + (outputField, literal.value)
} catch {
case t: Throwable => injectException(document, outputField, t)
}
})
}
As Scala does not offer memoization out-of-box, you can easily hand-toss one or use libraries like Scalaz.
In the code below, I use a simple mutable map to cache the result of evaluation by using function argument as a key. So Memoize is a Function as it extends from Function1, that takes in single argument T1 and returns the result R. It is a class at the same time and its apply method first checks for the presence of the argument in the cache, if the argument is found, it returns the result of previously stored computation, else it evaluates the function, caches its result and then returns it to the caller.
import scala.collection.mutable.Map
class Memoize[-T1, +R] private (fn: T1 => R) extends (T1 => R) {
private[this] val cache = Map[T1, R]()
def apply(arg: T1): R = {
if(cache.contains(arg)) {
cache(arg)
} else {
val result = fn(arg)
cache += ((arg, result))
result
}
}
}
object Memoize {
def apply[T1, R](fn: T1 => R) = new Memoize[T1, R](fn)
}
Below are the tests that were used to flush it out. We used the Specs2 framework.
@RunWith(classOf[JUnitRunner])
class MemoizeSpecs extends Specification {
"Memoizer" should {
def square(x: Int) = x * x
"evaluate a function correctly" in {
//Given
val memoizedSquare = Memoize(square)
//When
val x = 2
//Then
memoizedSquare(x) mustEqual square(x)
}
"ensures it calls a function with same arguments just once and memoizes for later use" in {
//Given
var called = 0
def aFunction(x: Int): (Int, Int) = {
called += 1
(x, called)
}
val memoizedFunction = Memoize(aFunction)
//When
val x = 1
val resultOnce = memoizedFunction(x)
val resultTwice = memoizedFunction(x)
//Then
resultOnce mustEqual (x, 1)
resultTwice mustEqual (x, 1)
}
"calls a function with different arguments just once and memoizes for later use" in {
//Given
var called = 0
def aFunction(x: Int): (Int, Int) = {
called += 1
(x, called)
}
val memoizedFunction = Memoize(aFunction)
//When
val x = 1
val resultXOnce = memoizedFunction(x)
val resultXTwice = memoizedFunction(x)
val y = 2
val resultYOnce = memoizedFunction(y)
val resultYTwice = memoizedFunction(y)
//Then
resultXOnce mustEqual (x, 1)
resultXTwice mustEqual (x, 1)
resultYOnce mustEqual (y, 2)
resultYTwice mustEqual (y, 2)
}
}
}
So, in the Memoize code above, you may have wondered, what is the use of private[this] on line 4 that is highlighted. Why can’t I just use private here?
When I used private here, I get the following 2 compile errors:
contravariant type T1 occurs in invariant position in type => scala.collection.mutable.Map[T1,R] of value cache private val cache = Map[T1, R]()
covariant type R occurs in invariant position in type => scala.collection.mutable.Map[T1,R] of value cache private val cache = Map[T1, R]()
To be honest with you I had to fight this one out, the compiler would not simply take in private and not much help from googling as well. Eventually, I could not find any better explanation in other than Martin Odersky’s book – Programming in Scala, Chapter 19, Section 19.7. Just inlining it here for reference
….You might wonder whether this code passes the Scala type checker. After all,
queues now contain two reassignable fields of the covariant parameter type T.
Is this not a violation of the variance rules? It would be indeed, except for
the detail that leading and trailing have a private[this] modifier and are thus
declared to be object private.
As mentioned in Section 13.5, object private members can be accessed only from within
the object in which they are defined. It turns out that accesses to variables from
the same object in which they are defined do not cause problems with variance. The
intuitive explanation is that, in order to construct a case where variance would
lead to type errors, you need to have a reference to a containing object that has a
statically weaker type than the type the object was defined with. For accesses to
object private values, however, this is impossible.
Scala’s variance checking rules contain a special case for object private definitions.
Such definitions are omitted when it is checked that a type parameter with
either a + or – annotation occurs only in positions that have the same variance
classification. Therefore, the code below compiles without error.
On the other hand, if you had left out the [this] qualifiers from the two private
modifiers, you would see two type errors:…
So, the private[this] is really needed here, because mutable Map[T1, R] here has invariant types.
Just to complete this post, eventually, we tackled the Preventing Force, where we no longer hot deploy the code by generating a text file, compiling it and hot deploying bytecode into the JVM. Now, the transform method finally looks like –
def transform(outputField: String, expressionJson: String) : BSONObject => BSONObject = {
val expression: Expression = Try { parse(expressionJson) } match {
case scala.util.Success(expr) => expr
case scala.util.Failure(failure) => throw failure
}
((document: BSONObject) => {
try {
val literal = expression.evaluate(document)
document + (outputField, literal.value)
} catch {
case t: Throwable => injectException(document, outputField, t)
}
})
}
Thats it!
Like this:
Like Loading...
