Proto for Boost mailing list page: Re: [proto] Precomputing common matrix products in an expression

Subject: Re: [proto] Precomputing common matrix products in an expression
From: Mathias Gaunard (mathias.gaunard_at_[hidden])
Date: 2012-07-15 02:04:00

On 07/14/2012 08:46 AM, Joel Falcou wrote:

> In NT2, we use a schedule transform that iterate the expression tree and
> evaluate expression tagged as being needed to be evaluated once and
> store them in some shared_ptr like terminal. This allow us to "schedule"
> our loop nests in the proper order.
>
> This "scheduling" is what requried us to store everything proto by value
> inside expression. Mathias correct me if I diverge.

I don't see how this has anything to do with what the OP wants, which is 
memoization. The "once" in NT2 only has to do with how loops are 
expanded, it doesn't prevent the same expression from being evaluated 
every time it's called.

We don't do anything of the sort, but I don't see any difficulty in 
doing this.

Assuming your expressions are CopyConstructible and you evaluate your 
expressions with something like this being called recursively

template<class Expr>
struct evaluate
{
    typedef ... result_type;
    result_type operator()(Expr& e) const
    {
       ...
    }
};

You could just replace it with

template<class Expr>
struct memoize_evaluate
{
    typedef evaluate<Expr> impl;
    typedef typename impl::result_type result_type;

    result_type operator()(Expr& e) const
    {
      typename result_map::iterator it = get_results().find(e);
      if(it != get_results().end())
        return *it;

      return get_results().insert(std::make_pair(e, impl()(e))).first;
    }

private:
    typedef std::map<Expr, result_type> result_map;
    static result_map& get_results()
    {
      static result_map results;
      return results;
    }

};

Of course Proto expressions are not safely CopyConstructible by default, 
so you'd have to be careful to make it work.

This is a global approach, so you'll end up committing to memory all 
your past results. This is probably not desirable so you might prefer 
storing the map in the state instead of a singleton.