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.