Expected performance in cpp

[Zohar Levi]

I think casadi behavior in matlab gave me the wrong impression. Generating a function, e.g. with jacobian(), takes some time, but evaluating it is pretty fast. In terms of auto-diff, building the expression tree takes time, but you generate efficient code (e.g. in a C mex) that is fast to eval.

I assume that in c++, this isn't the case. Evaluating an expression tree may not necessarily be faster than evaluating the function and performing, e.g., forward derivative on the fly. This is because c++ isn't a virtual machine, and there's nothing significant in the code to improve (no magic MEX). Beyond that, there isn't symbolic simplification that generates simpler, faster expression to eval.

Is this correct?

[Joris Gillis]

Dear Zohar,

Algorithmic differentiation using "source code transformation" will always have a speed benefit over a strategy using "operator overloading" (aka computing on-tge-fly, e.g. adolc).

CasADi is a bit of a special case.
You construct a symbolic representation of a computation, and perform "source code transformation" on that representation.

If you call plain CasADi Functions (in c++/matlab alike), there is some code (written in casadi c++ core) that loops over the symbolic computations. We call this the CasADi virtual machine. This has overhead.

To remove the overhead and get the speed of a C "source code transformation" tool, you have to go the extra step of code-generation. You can do this in with Function.generate(...)+compile+external(...), or by providing a 'jit' true option to the Functiom constructor (best paired with 'compiler' 'shell'), or by using the codegen API. Typical speedup factor ~4.

CasADi C++ will typically be only marginally faster than CasADi Matlab.
If you compare speed of evaluation of Matlab CasADi including a mex step, to C++ CasADi without codegen/jit, the Matlab variant will be faster.

Best regards,
Joris

[Zohar Levi]

Okay, so cpp and matlab casadi should perform similarly. I don't really go to cpp (mex) if I can avoid it, but I have many small functions to eval, which I can't see how to vectorize.

About the first part, you seem to distinguish between algorithmic and auto diff while they seem to be the one and same:

https://en.wikipedia.org/wiki/Automatic_differentiation 

http://www.autodiff.org/?module=Introduction&submenu=FAQ

In the context of casadi in matlab, I understand what you mean and agree. But if we consider cpp code and compare casadi to something like adolc (I haven't tried it, but I used something similar), then I don't see the difference. There's forward diff, backward diff, and symbolic diff (generate a simpler expression), and I don't see anything beyond that. Meaning, I don't see a better method or anyway to improve this (or otherwise, I'd be happy to see an example).

[Joris Gillis]

Autodiff and algorithmic differentiation are synonyms.

The various tools only differ in how they implement the fundamental concepts of forward mode and adjoint/reverse mode.
In practice, implementation details have an impact on speed. You can find a section of the two implementation families (operator overloading and source code transformation) on that wiki link.

I'm confused about your mex useage. Are you manually writing mex files now with c++ CasADi in them?

[Zohar Levi]

Okay, so there's also source code transformation; I'm learning bit by bit. So, if there's no clear winner between the methods, then at this point, I'll ask about a benchmark that compares the various AD tools?

Usually, I use casadi within a matlab script. Currently, though, I have many small problems (which I can't vectorize), so I need to resort to mex. Since I like to work with Eigen, I chose  to use autodiff.github.io. The performance, though, isn't good enough, and I thought that casadi might do the trick (hence, my other thread asking about using casadi from cpp). Now, I understand that this may or may not be the case, which brings me back to my benchmark question.

[Joris Gillis]

I am insisting that there *is* a clear winner speed-wise when comparing the family of "source code transformation" with "operator overloading"..

If you use CasADi in a way optimized for speed (ie with the codegen step, making it effectively "source code transformation"), it should be faster than any "operator overloading" tool (the autodiff.github.io tool seems to be of that type).

I'm not aware of a universal benchmark initiatives for AD tools. If you wanna take initiative, I can contribute a CasADi part.

Perhaps you can just post your current code?

Best regards,

  Joris

[Zohar Levi]

This guy shares your view:

http://www.autodiff.org/Docs/euroad/14th%20EuroAd%20Workshop%20-%20Robin%20Hogan%20-%20Can%20operator-overloading%20ever%20have%20a%20speed%20approaching%20source-code%20transformation%20for%20reverse-mode%20automatic%20differentiation%20.pdf 

This guy says that it might not be that bad:

 

https://scicomp.stackexchange.com/questions/10280/regarding-automatic-differentiation-is-source-code-transformation-stc-more-ef 

--

Survey and benchmarking is probably a project for one of the research groups:

http://www.autodiff.org/?module=Research%20Groups

-- 

I'm not sure which part of the code you'd like to see. It's cpp using the AD lib that I mentioned. It's a small part of my pipeline, and it probably would take some work to extract a minimal example.