Optimizing Jet using expression template

[datta ramadasan]

Hi,

Based on Jet class, I have tested a simple implementation of expression template core to accelerate automatic differentiation.

The time improvement I get is about 25% with the Snavely error function. If I re-write the Snavely function to take advantage of the core expression, I have a 50% improvement.

Advantages :

 - the expression core code is quite short (< 160 lines)

 - it's easy to add new functions (no hardcore meta-template needed)

Disadvantages :

 - for code clarity, I used c++14 (with g++ -std=c++1y), so there are lot of "auto" keywords

 - expression like "a + b * T(1.0)" works, but "a + b * T(c + d)" doesn't work, because the core expression doesn't manage temporaries...

 - I only wrote the function needed by the Snavely functor.

I use it in my own project but if anyone is interesting, I attached an example.

It works at least with g++-4.9 and -std=c++1y option (-O3 is welcome).

Datta

++

[Keir Mierle]

Hi Datta,

This is very cool! We've experimented with expression templated autodiff in the past with mixed results. On some cases it was faster, and in other cases it was slower. However, our investigation was not deep enough to discover if we could make the ET-based autodiff universally faster.

I'll take a look at your code soon, but welcome any further discussion.

Thanks,

Keir

--
You received this message because you are subscribed to the Google Groups "Ceres Solver" group.
To unsubscribe from this group and stop receiving emails from it, send an email to ceres-solver...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/ceres-solver/06cbd333-0b7d-4945-9e3d-646aae8e17bd%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[datta ramadasan]

Hi Keir,

The main idea of the implementation is to convert the jet expression to an eigen expression and let eigen do the optimization. So the limitation should be the eigen core expression limitation.

If you have some functions to test, I can try and see the performances.

++

[Keir Mierle]

Hi Datta,

I took a look at the code. This is a smarter approach than what we attempted before; previously we implemented our own expression template autodiff rather than leverage Eigen's expression templates. We will definitely take a closer look at this. There are some challenges that we will have to address around compatibility; in particular, we may have to have a separate "et-jet.h".

Are you using this approach in production today?

Thanks for contributing,

Keir

To view this discussion on the web visit https://groups.google.com/d/msgid/ceres-solver/ca5bbc75-c9a8-4007-9ba0-2c10c800401a%40googlegroups.com.

[Keir Mierle]

On further inspection, I realize the use of C++11 is not possible for Ceres due to our wide compatibility requirements. Do you expect any difficulties removing C++11 from the core ET-based Jet implementation?

[datta ramadasan]

I have used this code to work on the BAL dataset. Results are correct with the Snavely functor. In production I use analytic derivative.

It's possible to avoid c++11 with a more verbose code and maybe a good knowledge of Eigen which unfortunately is not my case...

A possible way to remove c++11 (this code isn't tested):

template<class A> auto operator-(const Expr<A>& a) { return Unary<A,Minus>(a.cast()); }

becomes

template<class A> auto operator-(const Expr<A>& a) { return Unary<A,Minus<A>>(a.cast()); }

template<class A, class Op> struct Unary : Expr<Unary<A,Op>>
{
  typename Traits<A>::type a;
  Unary(const A& a_):a(a_){}
  auto value() const { return Op::value(a); }
  ...
};

becomes 

template<class A, class Op> struct Unary : Expr<Unary<A,Op>>
{
  typename Traits<A>::type a;
  Unary(const A& a_):a(a_){}
  typename Op::Value value() const { return Op::value(a); }
  ...
};

and

struct Minus
{
  template<class A> static auto value (const A& a) { return - a.value();}
  ...
};

may approximately becomes

template<class A> struct Minus
{
  typedef Eigen::CwiseUnaryOp<Eigen::internal::scalar_opposite_op<double>, const A > Value;
  static Value value(const A& a) { return Value<A>(a.value());}
  ...
};

[datta ramadasan]

Or you can emulate the auto keyword with something like BOOST_AUTO/BOOST_AUTO_TPL,..

[Pablo Speciale]

Hi,

This is great! Thanks Datta for sharing it.

There is a library called Sacado (part of the Trilinos) that implements Automatic Differentiation (AD) using Expression Templates. It could be useful to see its implementation for some ideas. Slides (see page 4 for an example):

   http://trilinos.sandia.gov/events/trilinos_user_group_2009/presentations/SacadoTUG09.pdf

One paper about Efficient Expression Templates in Sacado:

   http://arxiv.org/abs/1205.3506

Also, something related to AD that might be interested for Ceres Solver to improve performance:

   Automatic Differentiation on Differentiable Manifolds as a Tool for Robotics

   Hannes Sommer, Cedric Pradalier, and Paul Furgale

   http://dream.georgiatech-metz.fr/sites/default/files/isrr13-optimization.pdf

(there is a comparison between their method and Ceres AD implementation)

Best regards,

--

Pablo

[datta ramadasan]

Hi,

I didn't know these works. I have take a loot at this page http://www.autodiff.org/ which contains a lot of libraries, and I have tested Adept and FADBAD but I found worst performances than the default jet implementation.

++

[Pablo Speciale]

On Fri, Dec 5, 2014 at 1:01 PM, datta ramadasan <datta.r...@gmail.com> wrote:

I didn't know these works. I have take a loot at this page http://www.autodiff.org/ which contains a lot of libraries, and I have tested Adept and FADBAD but I found worst performances than the default jet implementation.

I don't know about the Sacado performance in comparison with jet implementation, I just saw they were trying with expression template.

Another library I recently found is called Stan (it is a probabilistic programming language), and they also have an implementation of automatic differentiation (forward and reverse mode). They say it performs better than Sacado (but it should be measured). Here some examples:

    https://github.com/stan-dev/stan/blob/develop/src/test/unit/agrad/autodiff_test.cpp

It would be nice to have a sort of benchmark to compare these implementations. @Keir: how were you comparing between the different implementations (jet and E.T.) in the past?

Best regards,

--

Pablo

PS: btw, I like your implementation :) Thanks again for sharing it.

[Keir Mierle]

We were running the bundle adjustment benchmarks, as well as some internal Google stuff that's not public.

 

Best regards,

--

Pablo

PS: btw, I like your implementation :) Thanks again for sharing it.

--
You received this message because you are subscribed to the Google Groups "Ceres Solver" group.
To unsubscribe from this group and stop receiving emails from it, send an email to ceres-solver...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/ceres-solver/CAKu04dVhGz-LJCmQHFMM1%3DirPWsbZmfAUi2bSQGqab4LakMBKQ%40mail.gmail.com.