ADFun::optimize() eliminates conditional statements

[BachiLi]

CppADCodegen generates wrong code if there are conditional statements in the tape and if I add an optimization pass in CppAD, for example, the output of the following code:

#include <iosfwd>
#include <vector>
using namespace std;
#include <cppad/cg/cppadcg.hpp>

using namespace CppAD;
using namespace CppAD::cg;

int main(void) {        
    typedef CG<double> CGD;
    typedef AD<CGD> ADCG;

    CppAD::vector<ADCG> U(2);
    U[0] = 0.;
    U[1] = 0.;
    Independent(U);

    CppAD::vector<ADCG> Z(1);

    ADCG a = U[0] * U[1];
    Z[0] = CondExpEq(U[0], ADCG(1.0), a, ADCG(0.0));    

    ADFun<CGD> fun(U, Z); 
    fun.optimize();

    CodeHandler<double> handler;

    CppAD::vector<CGD> indVars(2);
    handler.makeVariables(indVars);

    CppAD::vector<CGD> fwd = fun.Forward(0, indVars);

    LanguageC<double> langC("double");
    LangCDefaultVariableNameGenerator<double> nameGen;

    std::ostringstream code;
    handler.generateCode(code, langC, fwd, nameGen);
    std::cout << code.str();
}

is:

   // dependent variables without operations
   y[0] = 0;

If I remove the fun.optimize() line, the output becomes:

   if( x[0] == 1 ) {
      y[0] = x[0] * x[1];
   } else {
      y[0] = 0;
   }

I notice that CppADCodeGen does some optimizations on its own. Does it mean that I do not need to call fun.optimize() at all?

[joaoleal]

I have tested the issue with debugging information and I get an assertion inside CppAD. CppAD tests if a value is a parameter in forward_cskip_op_0() when it is not, which causes an assertion to fail. Did you run the code with or without debugging information (did you define NDEBUG)?

Calling CppAD optimize may improve slightly the source code generation speed, but typically the bottleneck in CppADCodeGen is the compiler. Optimize shouldn't have much of an effect in the generated code. It may reorder some operations but it shouldn't have a real impact on runtime performance.

I will try to identify better the root cause of the problem.

[BachiLi]

Looks like I did define NDEBUG during compilation, thanks for the response, I will investigate as well.

[bradbell]

On 2/23/2015 11:11 AM, João Rui Leal wrote:

I have tested the issue with debugging information and I get an assertion inside CppAD. CppAD tests if a value is a parameter in forward_cskip_op_0() when it is not, which causes an assertion to fail. Did you run the code with or without debugging information (did you define NDEBUG)?

Calling CppAD optimize may improve slightly the source code generation speed, but typically the bottleneck in CppADCodeGen is the compiler. Optimize shouldn't have much of an effect in the generated code. It may reorder some operations but it shouldn't have a real impact on runtime performance.

I will try to identify better the root cause of the problem.

— Reply to this email directly or view it on GitHub https://github.com/joaoleal/CppADCodeGen/issues/2#issuecomment-75597957.

Which line number and file is the assertion generated at ?

[BachiLi]

cppad-20141230 error from unknown source
Error detected by false result for
    IdenticalPar(left)
at line 126 in the file 
    /usr/include/cppad/local/cskip_op.hpp
Assertion failed: (false), function Default, file /usr/include/cppad/error_handler.hpp, line 210.

By the way, the following code works well:

#include <iosfwd>
#include <vector>
using namespace std;
#include <cppad/cg/cppadcg.hpp>

using namespace CppAD;
using namespace CppAD::cg;

int main(void) {
    typedef double CGD;
    typedef AD<CGD> ADCG;

    CppAD::vector<ADCG> U(2);
    U[0] = 0.;
    U[1] = 0.;
    Independent(U);

    CppAD::vector<ADCG> Z(1);

    ADCG a = U[0] * U[1];
    Z[0] = CondExpEq(U[0], ADCG(1.0), a, ADCG(0.0));    

    ADFun<CGD> fun(U, Z); 
    fun.optimize();

    CppAD::vector<double> U_run(2);
    U_run[0] = 1.0;
    U_run[1] = 0.6;

    CppAD::vector<double> fwd = fun.Forward(0, U_run);
    std::cerr << "fwd:" << fwd[0] << std::endl;

    return 0;
}

[joaoleal]

The line number if 126: CPPAD_ASSERT_UNKNOWN( IdenticalPar(left) );

[joaoleal]

I've added the following code to the tests in cond_exp.cpp:

template<class T>
CppAD::ADFun<T>* CondExp_vpvpFunc(const std::vector<CppAD::AD<T> >& X) {
    using namespace CppAD;
    using namespace std;

    assert(X.size() == 3);

    // parameter value
    AD<T> one = T(1.);
    AD<T> zero = T(0.);

    // dependent variable vector 
    std::vector< AD<T> > Y(5);

    // CondExp(variable, parameter, variable, variable)
    Y[0] = CondExpLt(X[0], one, X[1] , zero);
    Y[1] = CondExpLe(X[0], one, X[1] , zero);
    Y[2] = CondExpEq(X[0], one, X[1] , zero);
    Y[3] = CondExpGe(X[0], one, X[1] , zero);
    Y[4] = CondExpGt(X[0], one, X[1] , zero);

    // create f: X -> Y 
    ADFun<T>* fun = new ADFun<T> (X, Y);
    fun->optimize();

    return fun;
}

and

TEST_F(CppADCGOperationTest, CondExp_vpvp) {
    // independent variable vector
    std::vector<std::vector<double> > u{
        {0, 1, 2},
        {1, 0.5, 2}
    };

    verbose_ = true;
    test0nJac("CondExp_vpvp", &CondExp_vpvpFunc<double >, &CondExp_vpvpFunc<CG<double> >, u);
}

Oddly it generates the correct code... however if I replace the expression in the true branch (X[1]) with an operation such as X[1]*X[2] it will fail.

[joaoleal]

The problem is related with how CppAD uses the optimizations. It will perform the comparison U[0] == ADCG(1.0) in order to skip the evaluation of one of the branches. In the case of an AD this is excellent, however in the case of an AD<CG<double> > one of the branches must not be skipped. I will check what happens with AD<AD<double> > since the behavior should be identical to what I need in CppADCodegen.

[joaoleal]

I have the same issue with AD<AD<double> >:

using namespace CppAD;
    typedef AD<double> adouble;
    typedef AD<adouble> a2double;

    std::vector<double> x{0, 1};

    /**
     * First tape
     */
    std::vector<a2double> a2x(x.size());
    for (size_t i = 0; i < a2x.size(); i++) {
        a2x[i] = adouble(x[i]);
    }
    Independent(a2x);

    std::vector<a2double> a2y(1);
    a2double a = a2x[0] * a2x[1];
    a2y[0] = CondExpEq(a2x[0], a2double(1.0), a, a2double(0.0));

    // create f: X -> Y 
    ADFun<adouble> f1(a2x, a2y);
    f1.optimize();

    /**
     * Second tape
     */
    std::vector<adouble> ax{adouble(1), adouble(0)};
    Independent(ax);

    std::vector<adouble> ay = f1.Forward(0, ax); // <<<<<<<<<<<< BOOM!!!! 

    CppAD::ADFun<double> f2(ax, ay);

    /**
     * Use second tape
     */
    x = {1, 0};

    std::vector<double> y = f2.Forward(0, x);
    std::cout << y[0] << std::endl;

Brad: Would it be possible to add a special behavior in CppAD to skip the optimizations if required?

[bradbell]

On 2/24/2015 4:13 AM, João Rui Leal wrote:

The problem is related with how CppAD uses the optimizations. It will perform the comparison U[0] == ADCG(1.0) in order to skip the evaluation of one of the branches. In the case of an AD this is excellent, however in the case of an AD > one of the branches must not be skipped. I will check what happens with AD > since the behavior should be identical to what I need in CppADCodegen.

— Reply to this email directly or view it on GitHub https://github.com/joaoleal/CppADCodeGen/issues/2#issuecomment-75738465.

During a zero order forward sweep, the optimizer currently determines which operations can be skipped (because they are not used in the final result).

I can see that this would possible break how CppADCodeGen is using CppAD.

My first step in fixing any problem is to generate as simple as possible of a case that demonstrates the problem. In this case, that requires CppADCodeGen to do so. Thus I have to add CppADCodeGen to the list of optional packages that can be used with CppAD; see the heading package_prefix on http://www.coin-or.org/CppAD/Doc/cmake.htm#package_prefix So my first step is to figure out the install a testing version of CppADCodeGen in a sandbox (not on the system).

Once I have a simple test that does not work, I can fix the problem. I am not yet sure how I will do this (how I will make the removal of conditional expressions optional).

In the mean time, I think I know how you can modify a copy of the CppAD source code to fix the problem (for now). In the file https://github.com/coin-or/CppAD/blob/master/cppad/local/forward0sweep.hpp comment out the lines 353 to 355; i.e., forward_cskip_op_0( i_var, arg, num_par, parameter, J, taylor, cskip_op );

[joaoleal]

Perhaps you could do the test case with AD<AD<double>> instead of AD<CG<double>> since it will exhibit the same issue. This way there is no need to CppADCodegen specific tests.

[bradbell]

On 2/24/2015 6:29 AM, João Rui Leal wrote:

Perhaps you could do the test case with |AD<AD>| instead of |AD<CG>| since it will exhibit the same issue. This way there is no need to CppADCodegen specific tests.

— Reply to this email directly or view it on GitHub https://github.com/joaoleal/CppADCodeGen/issues/2#issuecomment-75755886.

Can you create a bug report using the format in bug/template.sh as a template. See the other files in bug/* for examples of how to do so.

Thanks !

[joaoleal]

I've added a bug report in CppAD at: https://github.com/coin-or/CppAD/issues/7

[bradbell]

On 2/24/2015 7:03 AM, João Rui Leal wrote:

I've added a bug report in CppAD at: coin-or/CppAD#7 https://github.com/coin-or/CppAD/issues/7

— Reply to this email directly or view it on GitHub https://github.com/joaoleal/CppADCodeGen/issues/2#issuecomment-75760869.

Thanks.

[bradbell]

On 2/24/2015 7:03 AM, João Rui Leal wrote:

I've added a bug report in CppAD at: coin-or/CppAD#7 https://github.com/coin-or/CppAD/issues/7

— Reply to this email directly or view it on GitHub https://github.com/joaoleal/CppADCodeGen/issues/2#issuecomment-75760869.

Sorry, I closed the issue by mistake, so I reopened it.

[joaoleal]

I'll leave this open until the issue has been completely fixed in CppAD. For now see work around at https://github.com/coin-or/CppAD/issues/7#issuecomment-76700854

[bradbell]

On 3/4/2015 8:20 AM, João Rui Leal wrote:

I'll leave this open until the issue has been completely fixed in CppAD. For now see work around at coin-or/CppAD#7 https://github.com/coin-or/CppAD/issues/7

— Reply to this email directly or view it on GitHub https://github.com/joaoleal/CppADCodeGen/issues/2#issuecomment-77189364.

To be specific, the temporary work around is to use f.optimize("no_conditional_skip") This option to the optimize routine may go away in the future depending on how https://github.com/coin-or/CppAD/issues/7 is fixed.

[joaoleal]

Fixed in CppAD 20150527. The argument "no_conditional_skip" is no longer required.