Regarding automatic differentiation, is source-code-transformation (STC) more efficient than operator-overloading (OO)?

Question

We are working on a Bayesian model for a space-time process, and are using a No-U-Turn sampler (NUTS) that requires a model for the log-probability and it's gradient with respect to the model parameters. More succinctly, we have fairly complicated log-probability function $f : \mathbb{R}^n \rightarrow \mathbb{R}$, involving statistical distributions, kronecker products, exponentials, ratios, if-else statements etc, and need to provide it and it's gradient to NUTS. Several packages (Stan and Julia's MCMC) use operator-overloading (to the best of my knowledge) to obtain the gradient automatically.

If we were able to create our own gradient function, perhaps using a source-code-transformation auto-diff tool, would we get better performance, or is OO just as good or better?

Answer 1

Source-to-source transformation is considered the gold standard in terms of performance. OO approaches seem to be almost as good, in that there are more OO packages out there, and performance is not mentioned as a significant drawback. If you find an OO library you like for the language you're working in, I'd use it first, and then figure out later if you absolutely need source-to-source transformation, and if such a tool meeting your needs exists. The typical cost of an automatic-differentiation-generated derivative is roughly three to five times that of a function evaluation, to put things in context.

There are more OO packages out there because it's easier to implement automatic differentiation tools using operator overloading than it is to use source-to-source translation. Implementing a source-to-source translator is tantamount to writing a compiler: source code must be parsed and tokenized, then transformation rules must be applied to the resulting expression tree. Andreas Griewank's book, Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation, Second Edition, goes into more detail regarding the tradeoffs.

Answer 2

For gradient computation, you use the reverse mode of AD. This requires in both cases to build an operand stack, the OO version also needs to build up an operations stack, which has to be interpreted in the reverse traversal of the code. Source transformed code writes out the reverse-ordered operations as additional source code that is compiled. The overhead to have the operations interpreter in the code can be significant. There are comparisons of Tapenade generated code and Adol-C that come out in favor of Tapenade.