Re: [eigen] nesting

[Hauke Heibel <hauke.heibel@xxxxxxxxxxxxxx>]

Some brainstorming...

1) We have two phases during expression creation and evaluation

a) up-stream-phase: building up the expressions
b) down-stream-phases: expression execution

For the moment I am leaving out a potential reordering phase via the
Evaluator on purpose - I think that could be easily incorporated as
well.

Regarding the temporaries we might do the following. First, let's
assume we handle heap allocations via shared_ptrs. Then we are left
with stack temporaries only. During phase a) in which the expression
tree is build up from bottom to top (thus up-stream), each expression
can propagate its stack memory requirements to the parent - we know it
from the Matrix template parameters. In the end, we have the overall
stack requirement at the top expression.

Then, during the down-stream or execution phase a controller class
needs to trigger the execution and handle the stack memory management.
After the controller allocated the required amount cache, he calls the
expression and passes the cache over to the next expression in the
down-stream. Each expression will then snatch off the required stack
memory from the cache an pass the remaining memory to the child
expressions. Thus, during the evaluation each expression should have
access to the required cache.

Again, this is not an easy task but might be doable. What could be
advantageous is that from a development point of view almost all of
the required components are mutually independent. Handling heap memory
in the up-stream can be implemented independently from the stack
memory propagation as well as the down-stream execution.

It's not yet all 100% clear but I hope I made the idea clear...

- Hauke

On Mon, Feb 8, 2010 at 3:50 AM, Benoit Jacob <jacob.benoit.1@xxxxxxxxx> wrote:
> To summarize the little conversation that happened over irc:
>
> 1) Hauke: a very good reason why we want to evaluate intermediate
> temporaries also in the fixed-size case, as mentioned by Gael, is when
> the cost-model tells us that this reduces the complexity of the
> operation. For example, evaluating b+c in "a*(b+c)".
>
> 2) On the other hand the idea of an "expression evaluator" seems
> really doable (albeit complex) following this strategy:
>
> a) At the time of the construction of the expression, we gather the
> information of where temporaries must be introduced when evaluating
> that expression. That could be a new typedef in ei_traits.
>
> b) when evaluating an expression, we instantiate an object of a
> template "Evaluator" type that uses that information to hold the
> necessary temporary matrices as member data. We then traverse the
> expression tree, evaluating the designated sub-expressions into these
> temporaries.
>
> I'm not saying that I'm finding this _easy_!! This has got to be the
> most complicated templates exercise that we've had to solve. But it
> can be done for sure, as templates allow to do everything. To think
> about that, I'm finding it convenient to think purely in terms of
> pseudo code, and translate this into templates at the last minute.
> Templates are not human-readable code :(