Benchmarking: Using 'Expression' 'Quote' or Neither

Benchmarking: using `expression` `quote` or neither

Your issue is that quote does not produce an expression but a call, so within the call to benchmark, there is no expression to evaluate.

If you evaluate the `call it will actually get evaluated, and the timings are reasonable.

class(quot)
[1] "call"
>class(expr)
[1] "expression"

 benchmark(raw=apply(mat, 2, mean), expr, eval(quot))[, -(7:8)]
        test replications elapsed relative user.self sys.self
3 eval(quot)          100    0.76    1.000      0.77        0
2       expr          100    0.83    1.092      0.83        0
1        raw          100    0.78    1.026      0.78        0

In general, I tend to create a function that contains the call / process I wish to benchmark. Note that it is good practice to include things like assigning the result to a value.

eg

 raw <- function() {x <- apply(mat, 2, mean)}

In which case it looks like that there is a slight improvement by eval(quote(...)).

benchmark(raw(), eval(quote(raw()))

                test replications elapsed relative user.self sys.self 
2 eval(quote(raw()))          100    0.76    1.000      0.75     0.01        
1              raw()          100    0.80    1.053      0.80     0.00        

But often these small differences can be due to overheads in functions and may not reflect how the performance scales to larger problems. See the many questions with benchmarkings of data.table solutions, using a small number of replications but big data may better reflect performance.

Is there a performance gain in using single quotes vs double quotes in ruby?

$ ruby -v
ruby 1.9.3p0 (2011-10-30 revision 33570) [x86_64-darwin11.0.0]

$ cat benchmark_quotes.rb
# As of Ruby 1.9 Benchmark must be required
require 'benchmark'

n = 1000000
Benchmark.bm(15) do |x|
  x.report("assign single") { n.times do; c = 'a string'; end}
  x.report("assign double") { n.times do; c = "a string"; end}
  x.report("concat single") { n.times do; 'a string ' + 'b string'; end}
  x.report("concat double") { n.times do; "a string " + "b string"; end}
end

$ ruby benchmark_quotes.rb 

                      user     system      total        real
assign single     0.110000   0.000000   0.110000 (  0.116867)
assign double     0.120000   0.000000   0.120000 (  0.116761)
concat single     0.280000   0.000000   0.280000 (  0.276964)
concat double     0.270000   0.000000   0.270000 (  0.278146)

Note: I've updated this to make it work with newer Ruby versions, and cleaned up the header, and run the benchmark on a faster system.

This answer omits some key points. See especially these other answers concerning interpolation and the reason there is no significant difference in performance when using single vs. double quotes.

Evaluate call that contains another call (call within call)

To answer this question it might be helpful to split it up in 3 sub problems

1. Locate any call within a call
2. For each call, evaluate the call (invisibly), or replace the call with the original call
3. Return the initial call.

For the answer to be complete, we need to locate any subsequently nested call within the call. In addition we would need to avoid the endless loop of bar <- quote(bar + 3).

As any call might have nested called eg:

a <- 3
zz <- quote(a + 3)
foo <- quote(zz^a)
bar <- quote(foo^zz)

we will have to make sure each stack is evaluated before evaluating the final call.

Following this line of thought, the following function will evaluate even complicated calls.

eval_throughout <- function(x, envir = NULL){
  if(!is.call(x))
    stop("X must be a call!")

  if(isNullEnvir <- is.null(envir))
    envir <- environment()
  #At the first call decide the environment to evaluate each expression in (standard, global environment)
  #Evaluate each part of the initial call, replace the call with its evaluated value
  # If we encounter a call within the call, evaluate this throughout.
  for(i in seq_along(x)){
    new_xi <- tryCatch(eval(x[[i]], envir = envir),
                       error = function(e)
                         tryCatch(get(x[[i]],envir = envir), 
                                  error = function(e)
                                    eval_throughout(x[[i]], envir)))
    #Test for endless call stacks. (Avoiding primitives, and none call errors)
    if(!is.primitive(new_xi) && is.call(new_xi) && any(grepl(deparse(x[[i]]), new_xi)))
      stop("The call or subpart of the call is nesting itself (eg: x = x + 3). ")
    #Overwrite the old value, either with the evaluated call, 
    if(!is.null(new_xi))
      x[[i]] <- 
        if(is.call(new_xi)){
          eval_throughout(new_xi, envir)
        }else
          new_xi
  }
  #Evaluate the final call
  eval(x)
}

Showcase

So lets try a few examples. Initially I'll use the example in the question, with one additional slightly more complicated call.

a <- 1
b <- 2
c <- 3
foo <- quote(a + a)
bar <- quote(foo ^ b)
zz <- quote(bar + c) 

Evaluating each of these gives the desired result:

>eval_throughout(foo)
2
>eval_throughout(bar)
4
>eval_throughout(zz)
7

This is not restricted to simple calls however. Lets extend it to a more interesting call.

massive_call <- quote({
  set.seed(1)
  a <- 2
  dat <- data.frame(MASS::mvrnorm(n = 200, mu = c(3,7), Sigma = matrix(c(2,4,4,8), ncol = 2), empirical = TRUE))
  names(dat) <- c("A","B")
  fit <- lm(A~B, data = dat)
  diff(coef(fit)) + 3 + foo^bar / (zz^bar)
})

Suprisingly enough this also works out just fine.

>eval_throughout(massive_call)
B
4

as when we try to evaluate only the segment that is actually necessary, we get the same result:

>set.seed(1)
>a <- 2
>dat <- data.frame(MASS::mvrnorm(n = 200, mu = c(3,7), Sigma = matrix(c(2,4,4,8), ncol = 2), empirical = TRUE))
>names(dat) <- c("A","B")
>fit <- lm(A~B, data = dat)
>diff(coef(fit)) + 3 + eval_throughout(quote(foo^bar / (zz^bar)))
B
4

Note that this is likely not the most efficient evaluating scheme. Initially the envir variable should be NULL, unless calls like dat <- x should be evaluated and saved in a specific environment.

---

Edit: Summary of currently provided answers and performance overview

This question have been given quite some attention since the additional reward was given, and many different answers have been proposed. In this section I'll give a short overview of the answers, their limitations and some of their benefits as well. Note all the answers currently provided are good options, but solve the problem to a differing degree, with different upsides and downsides. This section is thus not meant as a negative review for any of the answers, but a trial to leave an overview of the different methods.
The examples presented in above in my answer have been adopted by some of the other answers, while a few have been suggested in the comments of this answer which represented different aspects of the problem. I will use the examples in my answer as well as a few below, to try and illustrate the usefulness of the different methods suggested throughout this post. For completion the different examples are shown in code below. Thanks to @Moody_Mudskipper for the additional examples suggested in the comments below!

#Example 1-4:
a <- 1
b <- 2
c <- 3
foo <- quote(a + a)
bar <- quote(foo ^ b)
zz <- quote(bar + c) 
massive_call <- quote({
  set.seed(1)
  a <- 2
  dat <- data.frame(MASS::mvrnorm(n = 200, mu = c(3,7), Sigma = matrix(c(2,4,4,8), ncol = 2), empirical = TRUE))
  names(dat) <- c("A","B")
  fit <- lm(A~B, data = dat)
  diff(coef(fit)) + 3 + foo^bar / (zz^bar)
})
#Example 5
baz <- 1
quz <- quote(if(TRUE) baz else stop())
#Example 6 (Endless recursion)
ball <- quote(ball + 3)
#Example 7 (x undefined)
zaz <- quote(x > 3)

---

Solution versatility

The solutions provided in the answers to the question, solve the problem to various extends. One question might be to which extend these solve the various tasks of evaluating the quoted expressions.
To test the versatility of the solutions, example 1 to 5 was evaluated using the raw function provided in each answer. Example 6 & 7 present different kind of problems, and will be treated seperately in a section below (Safety of Implementation). Note the oshka::expand returns an unevaluated expression, which was evaluated for after running the function call.
In the table below I've visualized the results from the versatility test. Each row is a seperate function in an answer to the question while each column marks an example. For each test the succes is marked as sucess, ERROR and failed for a succesfuly, early interrupted and failed evaluation respectively.
(Codes are availible at the end of the answer for reproducability.)

            function     bar     foo  massive_call     quz      zz
1:   eval_throughout  succes  succes        succes   ERROR  succes
2:       evalception  succes  succes         ERROR   ERROR  succes
3:               fun  succes  succes         ERROR  succes  succes
4:     oshka::expand  sucess  sucess        sucess  sucess  sucess
5: replace_with_eval  sucess  sucess         ERROR   ERROR   ERROR

Interestingly the simpler calls bar, foo and zz are mostly handled by all but one answer. Only oshka::expand succesfuly evaluates every method. Only two methods succeed the massive_call and quz examples, while only oshka::expand craetes a succesfuly evaluating expression for the particularly nasty conditional statement.
One may however note that by design the any intermediate results are saved using the oshka::expand method, which should be kept in mind while used. This could however be simply fixed by evaluating the expression within function or child-environment to the global environment.
Another important note is the 5'th example represents a special problem with most of the answers. As each expression is evaluated individually in 3 out of 5 answers, the call to the stop function, simply breaks the call. Thus any quoted expression containing a call to stop shows a simply and especially devious example.

---

Efficiency comparison:

An alternative performance meassure often of concern is pure efficiency or speed. Even if certain methods failed, being aware of the methods limitations, can yield situations where a simpler method is better, due to the speed performance.
To compare the methods we need to assume that it is the case that we know the method is sufficient for our problems. For this reason and in order to compare the different methods a benchmarking test was performed using zz as the standard. This cuts out one method, for which no benchmarking has been performed. The results are shown below.

Unit: microseconds
            expr      min        lq       mean    median        uq      max neval
 eval_throughout  128.378  141.5935  170.06306  152.9205  190.3010  403.635   100
     evalception   44.177   46.8200   55.83349   49.4635   57.5815  125.735   100
             fun   75.894   88.5430  110.96032   98.7385  127.0565  260.909   100
    oshka_expand 1638.325 1671.5515 2033.30476 1835.8000 1964.5545 5982.017   100

For the purposes of comparison, the median is a better estimate, as the garbage cleaner might taint certain results and thus the mean.
From the output a clear pattern is visible. The more advanced functions takes longer to evaluate.
Of the four functions oshka::expand is the slowest competitor, being a factor 12 slower than the closest competitor (1835.8 / 152.9 = 12), while evalception is the fastest being about twice as fast as fun (98.7 / 49.5 = 2) and three times faster than eval_throughout (damn!)
As such if speed is required, it seems the simplest method that will evaluate succesfuly is the way to go.

---

Safety of implementation
An important aspect of good implementations is their ability identify and handle devious input. For this aspect example 6 & 7 represent different problems, that could break implementations. Example 6 represents an endless recursion, which might break the R session. Example 7 represents the missing value problem.

Example 6 was run under the same condition. The results are shown below.

eval_throughout(ball) #Stops successfully
eval(oshka::expand(ball)) #Stops succesfully
fun(ball) #Stops succesfully
#Do not run below code! Endless recursion
evalception(ball)

Of the four answer, only evalception(bar) fails to detect the endless recursion, and crashes the R session, while the remaining succesfuly stops.

Note: i do not suggest running the latter example.

Example 7 was run under the same condition. The results are shown below.

eval_throughout(zaz) #fails
oshka::expand(zaz) #succesfully evaluates
fun(zaz) #fails
evalception(zaz) #fails

An important note is that any evaluation of example 7 will fail. Only oshka::expand succeeds, as it is designed to impute any existing value into the expression using the underlying environment. This especially useful feature lets one create complex calls and imputing any quoted expression to expand the expression, while the remaining answers (including my own) fail by design, as they evaluate the expression.

---

Final comments

So there you go. I hope the summary of the answers proves useful, showing the positives and possible negatives of each implementation. Each have their possible scenarios where they would outperform the remaining, while only one could be successfully used in all of the represented circumstances.
For versatility the oshka::expand is the clear winner, while if speed is preferred one would have to evaluate if the answers could be used for the situation at hand. Great speed improvements is achievable by going with the simpler answers, while they represent different risks possibly crashing the R session. Unlike my earlier summary, the reader is left to decide for themselves which implementation would work best for their specific problem.

Code for reproducing the summary

Note this code is not cleaned, simply put together for the summary. In addition it does not contain the examples or function, only their evaluations.

require(data.table)
require(oshka)
evals <- function(fun, quotedstuff, output_val, epsilon = sqrt(.Machine$double.eps)){
  fun <- if(fun != "oshka::expand"){
    get(fun, env = globalenv())
  }else
    oshka::expand
  quotedstuff <- get(quotedstuff, env = globalenv())
  output <- tryCatch(ifelse(fun(quotedstuff) - output_val < epsilon, "succes", "failed"), 
                     error = function(e){
                       return("ERROR")
                     })
  output
}
call_table <- data.table(CJ(example = c("foo", 
                                        "bar", 
                                        "zz", 
                                        "massive_call",
                                        "quz"),
                            `function` = c("eval_throughout",
                                           "fun",
                                           "evalception",
                                           "replace_with_eval",
                                           "oshka::expand")))
call_table[, incalls := paste0(`function`,"(",example,")")]
call_table[, output_val := switch(example, "foo" = 2, "bar" = 4, "zz" = 7, "quz" = 1, "massive_call" = 4), 
           by = .(example, `function`)]
call_table[, versatility := evals(`function`, example, output_val), 
           by = .(example, `function`)]
#some calls failed that, try once more
fun(foo)
fun(bar) #suces
fun(zz) #succes
fun(massive_call) #error
fun(quz)
fun(zaz)
eval(expand(foo)) #success
eval(expand(bar)) #sucess
eval(expand(zz)) #sucess
eval(expand(massive_call)) #succes (but overwrites environment)
eval(expand(quz))
replace_with_eval(foo, a) #sucess
replace_with_eval(bar, foo) #sucess
replace_with_eval(zz, bar) #error
evalception(zaz)
#Overwrite incorrect values.
call_table[`function` == "fun" & example %in% c("bar", "zz"), versatility := "succes"]
call_table[`function` == "oshka::expand", versatility := "sucess"]
call_table[`function` == "replace_with_eval" & example %in% c("bar","foo"), versatility := "sucess"]
dcast(call_table, `function` ~ example, value.var = "versatility")
require(microbenchmark)
microbenchmark(eval_throughout = eval_throughout(zz),
               evalception = evalception(zz),
               fun = fun(zz),
               oshka_expand = eval(oshka::expand(zz)))
microbenchmark(eval_throughout = eval_throughout(massive_call),
               oshka_expand = eval(oshka::expand(massive_call)))
ball <- quote(ball + 3)
eval_throughout(ball) #Stops successfully
eval(oshka::expand(ball)) #Stops succesfully
fun(ball) #Stops succesfully
#Do not run below code! Endless recursion
evalception(ball)
baz <- 1
quz <- quote(if(TRUE) baz else stop())
zaz <- quote(x > 3)
eval_throughout(zaz) #fails
oshka::expand(zaz) #succesfully evaluates
fun(zaz) #fails
evalception(zaz) #fails

How to analyze the length of time a specific function runs in R

You can use:

• Sys.time() or system.time()
• The rbenchmark package
• The microbenchmark package
• Or a profiler (e.g. ?RProf)

R use ddply or aggregate

I, too, would recommend data.table here, but since you asked for an aggregate solution, here is one which combines aggregate and merge to get all the columns:

merge(events22, aggregate(saleDate ~ custId, events22, max))

Or just aggregate if you only want the "custId" and "DelivDate" columns:

aggregate(list(DelivDate = events22$saleDate), 
          list(custId = events22$custId),
          function(x) events22[["DelivDate"]][which.max(x)])

Finally, here's an option using sqldf:

library(sqldf)
sqldf("select custId, DelivDate, max(saleDate) `saleDate` 
      from events22 group by custId")

---

Benchmarks

I'm not a benchmarking or data.table expert, but it surprised me that data.table is not faster here. My suspicion is that the results would be quite different on a larger dataset, say for instance, your 400k lines one. Anyway, here's some benchmarking code modeled after @mnel's answer here so you can do some tests on your actual dataset for future reference.

library(rbenchmark)

First, set up your functions for what you want to benchmark.

DDPLY <- function() { 
  x <- ddply(events22, .(custId), .inform = T, 
             function(x) {
               x[x$saleDate == max(x$saleDate),"DelivDate"]}) 
}
DATATABLE <- function() { x <- dt[, .SD[which.max(saleDate), ], by = custId] }
AGG1 <- function() { 
  x <- merge(events22, aggregate(saleDate ~ custId, events22, max)) }
AGG2 <- function() { 
  x <- aggregate(list(DelivDate = events22$saleDate), 
                 list(custId = events22$custId),
                 function(x) events22[["DelivDate"]][which.max(x)]) }
SQLDF <- function() { 
  x <- sqldf("select custId, DelivDate, max(saleDate) `saleDate` 
             from events22 group by custId") }
DOCALL <- function() {
  do.call(rbind, 
          lapply(split(events22, events22$custId), function(x){
            x[which.max(x$saleDate), ]
          })
  )
}

Second, do the benchmarking.

benchmark(DDPLY(), DATATABLE(), AGG1(), AGG2(), SQLDF(), DOCALL(), 
          order = "elapsed")[1:5]
#          test replications elapsed relative user.self
# 4      AGG2()          100   0.285    1.000     0.284
# 3      AGG1()          100   0.891    3.126     0.896
# 6    DOCALL()          100   1.202    4.218     1.204
# 2 DATATABLE()          100   1.251    4.389     1.248
# 1     DDPLY()          100   1.254    4.400     1.252
# 5     SQLDF()          100   2.109    7.400     2.108

Are double and single quotes interchangeable in JavaScript?

The most likely reason for use of single vs. double in different libraries is programmer preference and/or API consistency. Other than being consistent, use whichever best suits the string.

Using the other type of quote as a literal:

alert('Say "Hello"');
alert("Say 'Hello'");

This can get complicated:

alert("It's \"game\" time.");
alert('It\'s "game" time.');

Another option, new in ECMAScript 6, is template literals which use the backtick character:

alert(`Use "double" and 'single' quotes in the same string`);
alert(`Escape the \` back-tick character and the \${ dollar-brace sequence in a string`);

Template literals offer a clean syntax for: variable interpolation, multi-line strings, and more.

Note that JSON is formally specified to use double quotes, which may be worth considering depending on system requirements.

Evaluate function inside quotation

You can use PowerPack's Eval to evaluate only the arguments to the Call expression:

match e with
| Call(_,mi,[arg1;arg2]) ->
  let arg1Value, arg2Value = arg1.Eval(), arg2.Eval()
  ...

And similarly for Lambda expressions, etc. Noticed this frees you from enumerating permutations of Value, Property, and other argument expressions.

Update

Since you want to avoid using Eval (for good reason if you are implementing a performance conscious application), you'll need to implement your own eval function using reflection (which is still not lightening fast, but should be faster than PowerPack's Eval which involves an intermediate translation of F# Quotations to Linq Expressions). You can get started by supporting a basic set of expressions, and expand from there as needed. Recursion is the key, the following can help you get started:

open Microsoft.FSharp.Quotations
open System.Reflection

let rec eval expr =
    match expr with
    | Patterns.Value(value,_) -> value //value
    | Patterns.PropertyGet(Some(instance), pi, args) -> //instance property get
        pi.GetValue(eval instance, evalAll args) //notice recursive eval of instance expression and arg expressions
    | Patterns.PropertyGet(None, pi, args) -> //static property get
        pi.GetValue(null, evalAll args)
    | Patterns.Call(Some(instance), mi, args) -> //instance call
        mi.Invoke(eval instance, evalAll args)
    | Patterns.Call(None, mi, args) -> //static call
        mi.Invoke(null, evalAll args)
    | _ -> failwith "invalid expression"
and evalAll exprs =
    exprs |> Seq.map eval |> Seq.toArray

And then wrapping this in an Active Pattern will improve syntax:

let (|Eval|) expr =
    eval expr

match e with 
| Patterns.Call(_, mi, [Eval(arg1Value); Eval(arg2Value)]) -> ...

Update 2

OK, this thread got me motivated to try and implement a robust reflection based solution, and I've done so with good results which are now part of Unquote as of version 2.0.0.

It turned out not to be as difficult as I thought it would be, currently I am supporting all quotation expressions except for AddressGet, AddressSet, and NewDelegate. This is already better than PowerPack's eval, which doesn't support PropertySet, VarSet, FieldSet, WhileLoop, ForIntegerRangeLoop, and Quote for example.

Some noteworthy implementation details are with VarSet and VarGet, where I need to pass around an environment name / variable lookup list to each recursive call. It is really an excellent example of the beauty of functional programming with immutable data-structures.

Also noteworthy is special care taken with issues surrounding exceptions: striping the TargetInvokationExceptions thrown by reflection when it catches exceptions coming from methods it is invoking (this is very important for handling TryWith evaluation properly, and also makes for better user handling of exceptions which fly out of the quotation evaluation.

Perhaps the most "difficult" implementation detail, or really the most grueling, was the need to implement all of the core operators (well, as most I could discover: the numeric and conversion operators, checked versions as well) since most of them are not given dynamic implementations in the F# library (they are implemented using static type tests with no fallback dynamic implementations), but also means a serious performance increase when using these functions.

Some informal benchmarking I observe performance increases of up to 50 times over PowerPack's (not pre-compiled) eval.

I am also confident that my reflection-based solution will be less bug prone then PowerPack's, simply because it is less complicated than the PowerPack's approach (not to mention I've backed it up with about 150 unit tests, duly fortified by Unquotes additional 200+ unit tests which now is driven by this eval implementation).

If you want to peek at the source code, the main modules are Evaluation.fs and DynamicOperators.fs (I've locked the links into revision 257). Feel free to grab and use the source code for your own purposes, it licensed under Apache License 2.0! Or you could wait a week or so, when I release Unquote 2.0.0 which will include evaluation operators and extensions publicly.

Regular expression to match strings in quotes with double-quotes inside

In order to fail in a reasonable time you need, indeed, to avoid catastrophic backtracking. This can be done using atomic grouping (?>...):

/(\w+)=(\d+|"(?>(?>""|[^"]+)+)"(?!"))

# (?>(?>""|[^"]+)+)
(?>               # throw away the states created by (...)+
    (?>           # throw away the states created by [^"]+
        ""|[^"]+
    )+
)

Your issue when using (?:""|[^"]+)+ on a string that will never match, is linked to the fact that each time you match a new [^"] character the regex engine can choose to use the inner or outer + quantifier.

This leads to a lot of possibilities for backtracking, and before returning a failure the engine has to try them all.

We know that if we haven't found a match by the time the engine reaches the end, we never will: all we need to do is throw away the backtracking positions to avoid the issue, and that's what atomic grouping is for.

See a DEMO: 24 steps on failure, while preserving the speed on the successful cases (not a real benchmarking tool, but catastrophic backtracking would be pretty easy to spot)

---

Related Topics