Re: [proto] Precomputing common matrix products in an expression
On 7/14/2012 11:07 PM, Mathias Gaunard wrote: > On 07/15/2012 08:04 AM, Mathias Gaunard wrote: > >> Assuming your expressions are CopyConstructible For the record, in proto-11 no rvalues are stored by reference within expressions by default. > You'd also need them to be EqualityComparable or to use a comparator to > use them as keys. A recursive call to fusion::equal_to would probably be > a good definition. That wouldn't check the tag type. But as Bart says, this is unnecessary in his case. In proto-11, expressions currently satisfy EqualityComparable. operator== builds an expression node that has an implicit conversion to bool IFF the left and right operands are compatible. Likewise for the other relational operators. This is admittedly a kludge and I'm not sure how I feel about it. -- Eric Niebler BoostPro Computing http://www.boostpro.com ___ proto mailing list proto@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/proto
Re: [proto] Precomputing common matrix products in an expression
On 07/15/2012 10:25 AM, Bart Janssens wrote: OK, thanks for the comments. It's similar to what I had in mind, but (unless I'm missing something) all product terms in our expressions should have a distinct type if they represent different values, so I could get away with just using a fusion map and avoid the copying and even the map lookup. In which case, you can replace the std::map by a boost::optional. ___ proto mailing list proto@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/proto
Re: [proto] Precomputing common matrix products in an expression
On Sun, Jul 15, 2012 at 8:04 AM, Mathias Gaunard wrote: > 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. OK, thanks for the comments. It's similar to what I had in mind, but (unless I'm missing something) all product terms in our expressions should have a distinct type if they represent different values, so I could get away with just using a fusion map and avoid the copying and even the map lookup. Given the performance hit we're currently taking due to the many evaluations, I'll definitely try to implement this. Another alternative would be some sort of temporary values, but that places the burden of isolating common terms on the user and I think it would be almost as complicated to add support for this. The main thing I'm still concerned about is how to recurse over the expression in a way that can handle nested products. Ideally, the "leaf" products should be evaluated and stored in the map first, so subsequent higher level multiply expressions that use the result can look it up, even while the map is still being constructed. Cheers, -- Bart ___ proto mailing list proto@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/proto
Re: [proto] Precomputing common matrix products in an expression
On Friday, July 13, 2012 21:51:40 Bart Janssens wrote: > Hi guys, > > I've been thinking about a feature for our DSEL, where lots of matrix > products can occur in an expression. Part of an expression might be: > nu_eff * transpose(nabla(u)) * nabla(u) + transpose(N(u) + > coeffs.tau_su*u_adv*nabla(u)) * u_adv*nabla(u) > > Here, u_adv*nabla(u) is a vector-matrix product that occurs twice, so > it would be beneficial to calculate it only once. I was wondering if > it would be doable to construct a fusion map, with as keys the type of > each product occurring in an expression, and evaluate each member of > the map before evaluating the actual expression. When the expression > is evaluated, matrix products would then be looked up in the map. > > Does this sound like something that's doable? I'm assuming the fold > transform can help me in the construction of the fusion map. Note also > that each matrix has a compile-time size, so any stored temporary > would need to have its type computed. In a way, this reminds me of how local variables in phoenix work. You have the key (the variables name) which is a distinct type, and you look up the value of that key in a fusion map. The only real difference is that local variables aren't computed lazily, but that should be a nobrainer to add. Might get interesting in a multi-threaded environment though. > > Cheers, ___ proto mailing list proto@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/proto
Re: [proto] Precomputing common matrix products in an expression
On 07/15/2012 08:04 AM, Mathias Gaunard wrote: Assuming your expressions are CopyConstructible You'd also need them to be EqualityComparable or to use a comparator to use them as keys. A recursive call to fusion::equal_to would probably be a good definition. ___ proto mailing list proto@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/proto
Re: [proto] Precomputing common matrix products in an expression
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
struct evaluate
{
typedef ... result_type;
result_type operator()(Expr& e) const
{
...
}
};
You could just replace it with
template
struct memoize_evaluate
{
typedef evaluate 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 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.
___
proto mailing list
proto@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/proto
Re: [proto] Precomputing common matrix products in an expression
Le 13/07/2012 23:55, Eric Niebler a écrit : This is an instance of the larger "common subexpression elimination" problem. The problem is complicated by the fact that it can't be solved with type information alone. u_adv*nable(u) might have the same type as u_adv*nable(v) but different values. A hybrid solution is needed where you cache a set of results indexed both by type information and the identities (addresses) of the constituents of the subexpressions. This is hard, and nobody has attempted it yet. I can give you encouragement, but not guidance. If you find a general and elegant solution, it would certainly be worth putting in Proto, since lots of folks would benefit. 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. ___ proto mailing list proto@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/proto
Re: [proto] Precomputing common matrix products in an expression
On Fri, Jul 13, 2012 at 11:55 PM, Eric Niebler wrote: > On 7/13/2012 12:51 PM, Bart Janssens wrote: > This is an instance of the larger "common subexpression elimination" > problem. The problem is complicated by the fact that it can't be solved > with type information alone. u_adv*nable(u) might have the same type as > u_adv*nable(v) but different values. A hybrid solution is needed where > you cache a set of results indexed both by type information and the > identities (addresses) of the constituents of the subexpressions. This > is hard, and nobody has attempted it yet. I can give you encouragement, > but not guidance. If you find a general and elegant solution, it would > certainly be worth putting in Proto, since lots of folks would benefit. OK, in my case things are somewhat simpler after all then, since every multiplication does have a distinct type, the u and u_adv are also proto terminals, distinguished using an mpl integer, so that's why I was hoping that a fusion map combined with some clever expression analysis would suffice. Cheers, -- Bart ___ proto mailing list proto@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/proto
Re: [proto] Precomputing common matrix products in an expression
On 7/13/2012 12:51 PM, Bart Janssens wrote: > Hi guys, > > I've been thinking about a feature for our DSEL, where lots of matrix > products can occur in an expression. Part of an expression might be: > nu_eff * transpose(nabla(u)) * nabla(u) + transpose(N(u) + > coeffs.tau_su*u_adv*nabla(u)) * u_adv*nabla(u) > > Here, u_adv*nabla(u) is a vector-matrix product that occurs twice, so > it would be beneficial to calculate it only once. I was wondering if > it would be doable to construct a fusion map, with as keys the type of > each product occurring in an expression, and evaluate each member of > the map before evaluating the actual expression. When the expression > is evaluated, matrix products would then be looked up in the map. > > Does this sound like something that's doable? I'm assuming the fold > transform can help me in the construction of the fusion map. Note also > that each matrix has a compile-time size, so any stored temporary > would need to have its type computed. This is an instance of the larger "common subexpression elimination" problem. The problem is complicated by the fact that it can't be solved with type information alone. u_adv*nable(u) might have the same type as u_adv*nable(v) but different values. A hybrid solution is needed where you cache a set of results indexed both by type information and the identities (addresses) of the constituents of the subexpressions. This is hard, and nobody has attempted it yet. I can give you encouragement, but not guidance. If you find a general and elegant solution, it would certainly be worth putting in Proto, since lots of folks would benefit. -- Eric Niebler BoostPro Computing http://www.boostpro.com ___ proto mailing list proto@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/proto
