Boost logo

Boost :

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.


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk