Re: [boost] Minimal recalculation in formulas, using boost::proto

Subject: Re: [boost] Minimal recalculation in formulas, using boost::proto
From: Joel Falcou (joel.falcou_at_[hidden])
Date: 2011-02-05 12:31:39

On 05/02/11 18:25, remi.chateauneu_at_[hidden] wrote:
> Hi,
>
> I have a program which needs to recalculate a formula of independant 
> arguments (doubles or integers). These arguments can be updated at any 
> time.
>
> This math formula is expensive to evaluate, and performance-wise it is 
> worth, depending of which input argument changes, to recalculate only 
> a part of the evaluation tree. Here is a simplistic exemple:
> z = sin(x+1)*cos(y-3)
> When the argument x changes, it is not necessary to recompute cos(y-3).
>
> I wrote a prototype lib to do this, where expressions are made of 
> cells wrapping operators, input cells and intermediate values, plus 
> the list of depending cells.
>
> When the value of an argument, an input cell, changes, the lib just 
> builds the topologically sorted list of dependant cells, and 
> reevaluates them, performing what I think is the minimum recalculation 
> (Excel style).
>
> (An alternate strategy is to let each data update invalidate its cell 
> and its descendants - the actual calculation being done only when 
> needed).
>
> Instead of reinventing the wheel, my thought was to try to use 
> boost::proto for this. Does it make sense ? Any code change needed 
> please ?

Proto will help you set up the operators and functions overload for this.
Then I think the best way to do this is turn the proto AST into a 
ordered list of cells as you said, the order being given by dependencies.
Make this list a function object and have its operator() forward to 
cells operator() which will do the invalidation check and computation.

This may require a formula type that will keep this list of cells 
somewhere and recall it whenever needed.