-
Notifications
You must be signed in to change notification settings - Fork 122
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Reduce cloning complexity in forward mode #47
Comments
efremale
added a commit
to efremale/clad
that referenced
this issue
Aug 12, 2018
reevaluating them in forward mode. Remove unnecessary cloning in forward mode. Refactor DerivativeBuilder.cpp Forward mode now supports storing expression results in intermediate variables. This allows to avoid reevaluation if derived expressions are used on several places. For example, for: ``` double t = std::sin(x) * std::cos(x); ``` We now produce: ``` double _t0 = std::sin(x); double _t1 = std::cos(x); double _d_t = sin_darg0(x) * (_d_x) * _t1 + _t0 * cos_darg0(x) * (_d_x); double t = _t0 * _t1; ``` Instead of: ``` double _d_t = sin_darg0(x) * (_d_x) * cos(x) + sin(x) * cos_darg0(x) * (_d_x); double t = sin(x) * cos(x); ``` which allows us to avoid reevaluation of sin and cos. This commit solves the issue vgvassilev#47 in case of forward mode. For example, when deriving BinaryOperator, instead of cloning its whole tree and visiting it (potentially cloning the subtrees again), e.g. ``` auto ClonedBO = Clone(BO); // both LHS and RHS are cloned auto LHS = ClonedBO->getLHS(); auto LHSDiff = Visit(LHS) // LHS will be cloned inside again auto RHS = ClonedBO->getRHS(); auto RHSDiff = Visit(RHS); auto BODiff = ...// Build BODiff from LHSDiff and RHSDiff ``` we first visit the whole tree and rebuild the original operation from the results of subtrees, e.g. ``` auto [LHS, LHSDiff] = Visit(BO->getLHS()); auto [RHS, RHSDiff] = Visit(BO->getRHS()); auto ClonedBO = BuildOp(OpKind, LHS, RHS); auto BODiff = ...// Build BODiff from LHSDiff and RHSDiff. ``` Some refactoring was applied to DerivativeBuilder.cpp to support new way of visiting. Some functions of DerivativeBuilder and Visitors were moved to VisitorBase.
efremale
added a commit
to efremale/clad
that referenced
this issue
Aug 12, 2018
reevaluating them in forward mode. Remove unnecessary cloning in forward mode. Refactor DerivativeBuilder.cpp Forward mode now supports storing expression results in intermediate variables. This allows to avoid reevaluation if derived expressions are used on several places. For example, for: ``` double t = std::sin(x) * std::cos(x); ``` We now produce: ``` double _t0 = std::sin(x); double _t1 = std::cos(x); double _d_t = sin_darg0(x) * (_d_x) * _t1 + _t0 * cos_darg0(x) * (_d_x); double t = _t0 * _t1; ``` Instead of: ``` double _d_t = sin_darg0(x) * (_d_x) * cos(x) + sin(x) * cos_darg0(x) * (_d_x); double t = sin(x) * cos(x); ``` which allows us to avoid reevaluation of sin and cos. This commit solves the issue vgvassilev#47 in case of forward mode. For example, when deriving BinaryOperator, instead of cloning its whole tree and visiting it (potentially cloning the subtrees again), e.g. ``` auto ClonedBO = Clone(BO); // both LHS and RHS are cloned auto LHS = ClonedBO->getLHS(); auto LHSDiff = Visit(LHS) // LHS will be cloned inside again auto RHS = ClonedBO->getRHS(); auto RHSDiff = Visit(RHS); auto BODiff = ...// Build BODiff from LHSDiff and RHSDiff ``` we first visit the whole tree and rebuild the original operation from the results of subtrees, e.g. ``` auto [LHS, LHSDiff] = Visit(BO->getLHS()); auto [RHS, RHSDiff] = Visit(BO->getRHS()); auto ClonedBO = BuildOp(OpKind, LHS, RHS); auto BODiff = ...// Build BODiff from LHSDiff and RHSDiff. ``` Some refactoring was applied to DerivativeBuilder.cpp to support new way of visiting. Some functions of DerivativeBuilder and Visitors were moved to VisitorBase.
efremale
added a commit
to efremale/clad
that referenced
this issue
Aug 12, 2018
reevaluating them in forward mode. Remove unnecessary cloning in forward mode. Refactor DerivativeBuilder.cpp Forward mode now supports storing expression results in intermediate variables. This allows to avoid reevaluation if derived expressions are used on several places. For example, for: ``` double t = std::sin(x) * std::cos(x); ``` We now produce: ``` double _t0 = std::sin(x); double _t1 = std::cos(x); double _d_t = sin_darg0(x) * (_d_x) * _t1 + _t0 * cos_darg0(x) * (_d_x); double t = _t0 * _t1; ``` Instead of: ``` double _d_t = sin_darg0(x) * (_d_x) * cos(x) + sin(x) * cos_darg0(x) * (_d_x); double t = sin(x) * cos(x); ``` which allows us to avoid reevaluation of sin and cos. This commit solves the issue vgvassilev#47 in case of forward mode. For example, when deriving BinaryOperator, instead of cloning its whole tree and visiting it (potentially cloning the subtrees again), e.g. ``` auto ClonedBO = Clone(BO); // both LHS and RHS are cloned auto LHS = ClonedBO->getLHS(); auto LHSDiff = Visit(LHS) // LHS will be cloned inside again auto RHS = ClonedBO->getRHS(); auto RHSDiff = Visit(RHS); auto BODiff = ...// Build BODiff from LHSDiff and RHSDiff ``` we first visit the whole tree and rebuild the original operation from the results of subtrees, e.g. ``` auto [LHS, LHSDiff] = Visit(BO->getLHS()); auto [RHS, RHSDiff] = Visit(BO->getRHS()); auto ClonedBO = BuildOp(OpKind, LHS, RHS); auto BODiff = ...// Build BODiff from LHSDiff and RHSDiff. ``` Some refactoring was applied to DerivativeBuilder.cpp to support new way of visiting. Some functions of DerivativeBuilder and Visitors were moved to VisitorBase.
efremale
added a commit
to efremale/clad
that referenced
this issue
Aug 12, 2018
reevaluating them in forward mode. Remove unnecessary cloning in forward mode. Refactor DerivativeBuilder.cpp Forward mode now supports storing expression results in intermediate variables. This allows to avoid reevaluation if derived expressions are used on several places. For example, for: ``` double t = std::sin(x) * std::cos(x); ``` We now produce: ``` double _t0 = std::sin(x); double _t1 = std::cos(x); double _d_t = sin_darg0(x) * (_d_x) * _t1 + _t0 * cos_darg0(x) * (_d_x); double t = _t0 * _t1; ``` Instead of: ``` double _d_t = sin_darg0(x) * (_d_x) * cos(x) + sin(x) * cos_darg0(x) * (_d_x); double t = sin(x) * cos(x); ``` which allows us to avoid reevaluation of sin and cos. This commit solves the issue vgvassilev#47 in case of forward mode. For example, when deriving BinaryOperator, instead of cloning its whole tree and visiting it (potentially cloning the subtrees again), e.g. ``` auto ClonedBO = Clone(BO); // both LHS and RHS are cloned auto LHS = ClonedBO->getLHS(); auto LHSDiff = Visit(LHS) // LHS will be cloned inside again auto RHS = ClonedBO->getRHS(); auto RHSDiff = Visit(RHS); auto BODiff = ...// Build BODiff from LHSDiff and RHSDiff ``` we first visit the whole tree and rebuild the original operation from the results of subtrees, e.g. ``` auto [LHS, LHSDiff] = Visit(BO->getLHS()); auto [RHS, RHSDiff] = Visit(BO->getRHS()); auto ClonedBO = BuildOp(OpKind, LHS, RHS); auto BODiff = ...// Build BODiff from LHSDiff and RHSDiff. ``` Some refactoring was applied to DerivativeBuilder.cpp to support new way of visiting. Some functions of DerivativeBuilder and Visitors were moved to VisitorBase.
efremale
added a commit
to efremale/clad
that referenced
this issue
Aug 12, 2018
reevaluating them in forward mode. Remove unnecessary cloning in forward mode. Refactor DerivativeBuilder.cpp Forward mode now supports storing expression results in intermediate variables. This allows to avoid reevaluation if derived expressions are used on several places. For example, for: ``` double t = std::sin(x) * std::cos(x); ``` We now produce: ``` double _t0 = std::sin(x); double _t1 = std::cos(x); double _d_t = sin_darg0(x) * (_d_x) * _t1 + _t0 * cos_darg0(x) * (_d_x); double t = _t0 * _t1; ``` Instead of: ``` double _d_t = sin_darg0(x) * (_d_x) * cos(x) + sin(x) * cos_darg0(x) * (_d_x); double t = sin(x) * cos(x); ``` which allows us to avoid reevaluation of sin and cos. This commit solves the issue vgvassilev#47 in case of forward mode. For example, when deriving BinaryOperator, instead of cloning its whole tree and visiting it (potentially cloning the subtrees again), e.g. ``` auto ClonedBO = Clone(BO); // both LHS and RHS are cloned auto LHS = ClonedBO->getLHS(); auto LHSDiff = Visit(LHS) // LHS will be cloned inside again auto RHS = ClonedBO->getRHS(); auto RHSDiff = Visit(RHS); auto BODiff = ...// Build BODiff from LHSDiff and RHSDiff ``` we first visit the whole tree and rebuild the original operation from the results of subtrees, e.g. ``` auto [LHS, LHSDiff] = Visit(BO->getLHS()); auto [RHS, RHSDiff] = Visit(BO->getRHS()); auto ClonedBO = BuildOp(OpKind, LHS, RHS); auto BODiff = ...// Build BODiff from LHSDiff and RHSDiff. ``` Some refactoring was applied to DerivativeBuilder.cpp to support new way of visiting. Some functions of DerivativeBuilder and Visitors were moved to VisitorBase.
efremale
added a commit
to efremale/clad
that referenced
this issue
Aug 12, 2018
reevaluating them in forward mode. Remove unnecessary cloning in forward mode. Refactor DerivativeBuilder.cpp Forward mode now supports storing expression results in intermediate variables. This allows to avoid reevaluation if derived expressions are used on several places. For example, for: ``` double t = std::sin(x) * std::cos(x); ``` We now produce: ``` double _t0 = std::sin(x); double _t1 = std::cos(x); double _d_t = sin_darg0(x) * (_d_x) * _t1 + _t0 * cos_darg0(x) * (_d_x); double t = _t0 * _t1; ``` Instead of: ``` double _d_t = sin_darg0(x) * (_d_x) * cos(x) + sin(x) * cos_darg0(x) * (_d_x); double t = sin(x) * cos(x); ``` which allows us to avoid reevaluation of sin and cos. This commit solves the issue vgvassilev#47 in case of forward mode. For example, when deriving BinaryOperator, instead of cloning its whole tree and visiting it (potentially cloning the subtrees again), e.g. ``` auto ClonedBO = Clone(BO); // both LHS and RHS are cloned auto LHS = ClonedBO->getLHS(); auto LHSDiff = Visit(LHS) // LHS will be cloned inside again auto RHS = ClonedBO->getRHS(); auto RHSDiff = Visit(RHS); auto BODiff = ...// Build BODiff from LHSDiff and RHSDiff ``` we first visit the whole tree and rebuild the original operation from the results of subtrees, e.g. ``` auto [LHS, LHSDiff] = Visit(BO->getLHS()); auto [RHS, RHSDiff] = Visit(BO->getRHS()); auto ClonedBO = BuildOp(OpKind, LHS, RHS); auto BODiff = ...// Build BODiff from LHSDiff and RHSDiff. ``` Some refactoring was applied to DerivativeBuilder.cpp to support new way of visiting. Some functions of DerivativeBuilder and Visitors were moved to VisitorBase.
efremale
added a commit
to efremale/clad
that referenced
this issue
Aug 12, 2018
reevaluating them in forward mode. Remove unnecessary cloning in forward mode. Refactor DerivativeBuilder.cpp Forward mode now supports storing expression results in intermediate variables. This allows to avoid reevaluation if derived expressions are used on several places. For example, for: ``` double t = std::sin(x) * std::cos(x); ``` We now produce: ``` double _t0 = std::sin(x); double _t1 = std::cos(x); double _d_t = sin_darg0(x) * (_d_x) * _t1 + _t0 * cos_darg0(x) * (_d_x); double t = _t0 * _t1; ``` Instead of: ``` double _d_t = sin_darg0(x) * (_d_x) * cos(x) + sin(x) * cos_darg0(x) * (_d_x); double t = sin(x) * cos(x); ``` which allows us to avoid reevaluation of sin and cos. This commit solves the issue vgvassilev#47 in case of forward mode. For example, when deriving BinaryOperator, instead of cloning its whole tree and visiting it (potentially cloning the subtrees again), e.g. ``` auto ClonedBO = Clone(BO); // both LHS and RHS are cloned auto LHS = ClonedBO->getLHS(); auto LHSDiff = Visit(LHS) // LHS will be cloned inside again auto RHS = ClonedBO->getRHS(); auto RHSDiff = Visit(RHS); auto BODiff = ...// Build BODiff from LHSDiff and RHSDiff ``` we first visit the whole tree and rebuild the original operation from the results of subtrees, e.g. ``` auto [LHS, LHSDiff] = Visit(BO->getLHS()); auto [RHS, RHSDiff] = Visit(BO->getRHS()); auto ClonedBO = BuildOp(OpKind, LHS, RHS); auto BODiff = ...// Build BODiff from LHSDiff and RHSDiff. ``` Some refactoring was applied to DerivativeBuilder.cpp to support new way of visiting. Some functions of DerivativeBuilder and Visitors were moved to VisitorBase.
efremale
added a commit
to efremale/clad
that referenced
this issue
Aug 12, 2018
reevaluating them in forward mode. Remove unnecessary cloning in forward mode. Refactor DerivativeBuilder.cpp Forward mode now supports storing expression results in intermediate variables. This allows to avoid reevaluation if derived expressions are used on several places. For example, for: ``` double t = std::sin(x) * std::cos(x); ``` We now produce: ``` double _t0 = std::sin(x); double _t1 = std::cos(x); double _d_t = sin_darg0(x) * (_d_x) * _t1 + _t0 * cos_darg0(x) * (_d_x); double t = _t0 * _t1; ``` Instead of: ``` double _d_t = sin_darg0(x) * (_d_x) * cos(x) + sin(x) * cos_darg0(x) * (_d_x); double t = sin(x) * cos(x); ``` which allows us to avoid reevaluation of sin and cos. This commit solves the issue vgvassilev#47 in case of forward mode. For example, when deriving BinaryOperator, instead of cloning its whole tree and visiting it (potentially cloning the subtrees again), e.g. ``` auto ClonedBO = Clone(BO); // both LHS and RHS are cloned auto LHS = ClonedBO->getLHS(); auto LHSDiff = Visit(LHS) // LHS will be cloned inside again auto RHS = ClonedBO->getRHS(); auto RHSDiff = Visit(RHS); auto BODiff = ...// Build BODiff from LHSDiff and RHSDiff ``` we first visit the whole tree and rebuild the original operation from the results of subtrees, e.g. ``` auto [LHS, LHSDiff] = Visit(BO->getLHS()); auto [RHS, RHSDiff] = Visit(BO->getRHS()); auto ClonedBO = BuildOp(OpKind, LHS, RHS); auto BODiff = ...// Build BODiff from LHSDiff and RHSDiff. ``` Some refactoring was applied to DerivativeBuilder.cpp to support new way of visiting. Some functions of DerivativeBuilder and Visitors were moved to VisitorBase.
efremale
added a commit
to efremale/clad
that referenced
this issue
Aug 18, 2018
reevaluating them in forward mode. Remove unnecessary cloning in forward mode. Refactor DerivativeBuilder.cpp Forward mode now supports storing expression results in intermediate variables. This allows to avoid reevaluation if derived expressions are used on several places. For example, for: ``` double t = std::sin(x) * std::cos(x); ``` We now produce: ``` double _t0 = std::sin(x); double _t1 = std::cos(x); double _d_t = sin_darg0(x) * (_d_x) * _t1 + _t0 * cos_darg0(x) * (_d_x); double t = _t0 * _t1; ``` Instead of: ``` double _d_t = sin_darg0(x) * (_d_x) * cos(x) + sin(x) * cos_darg0(x) * (_d_x); double t = sin(x) * cos(x); ``` which allows us to avoid reevaluation of sin and cos. This commit solves the issue vgvassilev#47 in case of forward mode. For example, when deriving BinaryOperator, instead of cloning its whole tree and visiting it (potentially cloning the subtrees again), e.g. ``` auto ClonedBO = Clone(BO); // both LHS and RHS are cloned auto LHS = ClonedBO->getLHS(); auto LHSDiff = Visit(LHS) // LHS will be cloned inside again auto RHS = ClonedBO->getRHS(); auto RHSDiff = Visit(RHS); auto BODiff = ...// Build BODiff from LHSDiff and RHSDiff ``` we first visit the whole tree and rebuild the original operation from the results of subtrees, e.g. ``` auto [LHS, LHSDiff] = Visit(BO->getLHS()); auto [RHS, RHSDiff] = Visit(BO->getRHS()); auto ClonedBO = BuildOp(OpKind, LHS, RHS); auto BODiff = ...// Build BODiff from LHSDiff and RHSDiff. ``` Some refactoring was applied to DerivativeBuilder.cpp to support new way of visiting. Some functions of DerivativeBuilder and Visitors were moved to VisitorBase.
efremale
added a commit
to efremale/clad
that referenced
this issue
Aug 18, 2018
reevaluating them in forward mode. Remove unnecessary cloning in forward mode. Refactor DerivativeBuilder.cpp Forward mode now supports storing expression results in intermediate variables. This allows to avoid reevaluation if derived expressions are used on several places. For example, for: ``` double t = std::sin(x) * std::cos(x); ``` We now produce: ``` double _t0 = std::sin(x); double _t1 = std::cos(x); double _d_t = sin_darg0(x) * (_d_x) * _t1 + _t0 * cos_darg0(x) * (_d_x); double t = _t0 * _t1; ``` Instead of: ``` double _d_t = sin_darg0(x) * (_d_x) * cos(x) + sin(x) * cos_darg0(x) * (_d_x); double t = sin(x) * cos(x); ``` which allows us to avoid reevaluation of sin and cos. This commit solves the issue vgvassilev#47 in case of forward mode. For example, when deriving BinaryOperator, instead of cloning its whole tree and visiting it (potentially cloning the subtrees again), e.g. ``` auto ClonedBO = Clone(BO); // both LHS and RHS are cloned auto LHS = ClonedBO->getLHS(); auto LHSDiff = Visit(LHS) // LHS will be cloned inside again auto RHS = ClonedBO->getRHS(); auto RHSDiff = Visit(RHS); auto BODiff = ...// Build BODiff from LHSDiff and RHSDiff ``` we first visit the whole tree and rebuild the original operation from the results of subtrees, e.g. ``` auto [LHS, LHSDiff] = Visit(BO->getLHS()); auto [RHS, RHSDiff] = Visit(BO->getRHS()); auto ClonedBO = BuildOp(OpKind, LHS, RHS); auto BODiff = ...// Build BODiff from LHSDiff and RHSDiff. ``` Some refactoring was applied to DerivativeBuilder.cpp to support new way of visiting. Some functions of DerivativeBuilder and Visitors were moved to VisitorBase.
efremale
added a commit
to efremale/clad
that referenced
this issue
Aug 18, 2018
reevaluating them in forward mode. Remove unnecessary cloning in forward mode. Refactor DerivativeBuilder.cpp Forward mode now supports storing expression results in intermediate variables. This allows to avoid reevaluation if derived expressions are used on several places. For example, for: ``` double t = std::sin(x) * std::cos(x); ``` We now produce: ``` double _t0 = std::sin(x); double _t1 = std::cos(x); double _d_t = sin_darg0(x) * (_d_x) * _t1 + _t0 * cos_darg0(x) * (_d_x); double t = _t0 * _t1; ``` Instead of: ``` double _d_t = sin_darg0(x) * (_d_x) * cos(x) + sin(x) * cos_darg0(x) * (_d_x); double t = sin(x) * cos(x); ``` which allows us to avoid reevaluation of sin and cos. This commit solves the issue vgvassilev#47 in case of forward mode. For example, when deriving BinaryOperator, instead of cloning its whole tree and visiting it (potentially cloning the subtrees again), e.g. ``` auto ClonedBO = Clone(BO); // both LHS and RHS are cloned auto LHS = ClonedBO->getLHS(); auto LHSDiff = Visit(LHS) // LHS will be cloned inside again auto RHS = ClonedBO->getRHS(); auto RHSDiff = Visit(RHS); auto BODiff = ...// Build BODiff from LHSDiff and RHSDiff ``` we first visit the whole tree and rebuild the original operation from the results of subtrees, e.g. ``` auto [LHS, LHSDiff] = Visit(BO->getLHS()); auto [RHS, RHSDiff] = Visit(BO->getRHS()); auto ClonedBO = BuildOp(OpKind, LHS, RHS); auto BODiff = ...// Build BODiff from LHSDiff and RHSDiff. ``` Some refactoring was applied to DerivativeBuilder.cpp to support new way of visiting. Some functions of DerivativeBuilder and Visitors were moved to VisitorBase.
efremale
added a commit
to efremale/clad
that referenced
this issue
Aug 20, 2018
Forward mode now supports storing expression results in intermediate variables. This allows to avoid reevaluation if derived expressions are used on several places. For example, for: ``` double t = std::sin(x) * std::cos(x); ``` We now produce: ``` double _t0 = std::sin(x); double _t1 = std::cos(x); double _d_t = sin_darg0(x) * (_d_x) * _t1 + _t0 * cos_darg0(x) * (_d_x); double t = _t0 * _t1; ``` Instead of: ``` double _d_t = sin_darg0(x) * (_d_x) * cos(x) + sin(x) * cos_darg0(x) * (_d_x); double t = sin(x) * cos(x); ``` which allows us to avoid reevaluation of sin and cos. This commit also removes unnecessary cloning in forward mode, solving the issue vgvassilev#47 in case of forward mode. For example, when deriving BinaryOperator, instead of cloning its whole tree and visiting it (potentially cloning the subtrees again), e.g. ``` auto ClonedBO = Clone(BO); // both LHS and RHS are cloned auto LHS = ClonedBO->getLHS(); auto LHSDiff = Visit(LHS) // LHS will be cloned inside again auto RHS = ClonedBO->getRHS(); auto RHSDiff = Visit(RHS); auto BODiff = ...// Build BODiff from LHSDiff and RHSDiff ``` we first visit the whole tree and rebuild the original operation from the results of subtrees, e.g. ``` auto [LHS, LHSDiff] = Visit(BO->getLHS()); auto [RHS, RHSDiff] = Visit(BO->getRHS()); auto ClonedBO = BuildOp(OpKind, LHS, RHS); auto BODiff = ...// Build BODiff from LHSDiff and RHSDiff. ``` Some refactoring was applied to DerivativeBuilder.cpp to support new way of visiting. Some functions of DerivativeBuilder and Visitors were moved to VisitorBase.
vgvassilev
pushed a commit
that referenced
this issue
Aug 21, 2018
…ating them in forward mode. Remove unnecessary cloning in forward mode. Refactor DerivativeBuilder.cpp (#80) Store reused expressions in intermediate variables Forward mode now supports storing expression results in intermediate variables. This allows to avoid reevaluation if derived expressions are used on several places. For example, for: ``` double t = std::sin(x) * std::cos(x); ``` We now produce: ``` double _t0 = std::sin(x); double _t1 = std::cos(x); double _d_t = sin_darg0(x) * (_d_x) * _t1 + _t0 * cos_darg0(x) * (_d_x); double t = _t0 * _t1; ``` Instead of: ``` double _d_t = sin_darg0(x) * (_d_x) * cos(x) + sin(x) * cos_darg0(x) * (_d_x); double t = sin(x) * cos(x); ``` which allows us to avoid reevaluation of sin and cos. This commit also removes unnecessary cloning in forward mode, solving the issue #47 in case of forward mode. For example, when deriving BinaryOperator, instead of cloning its whole tree and visiting it (potentially cloning the subtrees again), e.g. ``` auto ClonedBO = Clone(BO); // both LHS and RHS are cloned auto LHS = ClonedBO->getLHS(); auto LHSDiff = Visit(LHS) // LHS will be cloned inside again auto RHS = ClonedBO->getRHS(); auto RHSDiff = Visit(RHS); auto BODiff = ...// Build BODiff from LHSDiff and RHSDiff ``` we first visit the whole tree and rebuild the original operation from the results of subtrees, e.g. ``` auto [LHS, LHSDiff] = Visit(BO->getLHS()); auto [RHS, RHSDiff] = Visit(BO->getRHS()); auto ClonedBO = BuildOp(OpKind, LHS, RHS); auto BODiff = ...// Build BODiff from LHSDiff and RHSDiff. ``` Some refactoring was applied to DerivativeBuilder.cpp to support new way of visiting. Some functions of DerivativeBuilder and Visitors were moved to VisitorBase.
efremale
added a commit
to efremale/clad
that referenced
this issue
Aug 21, 2018
reevaluating them in forward mode. Remove unnecessary cloning in forward mode. Refactor DerivativeBuilder.cpp Forward mode now supports storing expression results in intermediate variables. This allows to avoid reevaluation if derived expressions are used on several places. For example, for: ``` double t = std::sin(x) * std::cos(x); ``` We now produce: ``` double _t0 = std::sin(x); double _t1 = std::cos(x); double _d_t = sin_darg0(x) * (_d_x) * _t1 + _t0 * cos_darg0(x) * (_d_x); double t = _t0 * _t1; ``` Instead of: ``` double _d_t = sin_darg0(x) * (_d_x) * cos(x) + sin(x) * cos_darg0(x) * (_d_x); double t = sin(x) * cos(x); ``` which allows us to avoid reevaluation of sin and cos. This commit solves the issue vgvassilev#47 in case of forward mode. For example, when deriving BinaryOperator, instead of cloning its whole tree and visiting it (potentially cloning the subtrees again), e.g. ``` auto ClonedBO = Clone(BO); // both LHS and RHS are cloned auto LHS = ClonedBO->getLHS(); auto LHSDiff = Visit(LHS) // LHS will be cloned inside again auto RHS = ClonedBO->getRHS(); auto RHSDiff = Visit(RHS); auto BODiff = ...// Build BODiff from LHSDiff and RHSDiff ``` we first visit the whole tree and rebuild the original operation from the results of subtrees, e.g. ``` auto [LHS, LHSDiff] = Visit(BO->getLHS()); auto [RHS, RHSDiff] = Visit(BO->getRHS()); auto ClonedBO = BuildOp(OpKind, LHS, RHS); auto BODiff = ...// Build BODiff from LHSDiff and RHSDiff. ``` Some refactoring was applied to DerivativeBuilder.cpp to support new way of visiting. Some functions of DerivativeBuilder and Visitors were moved to VisitorBase.
@efremale can we now close this? |
I believe some work is still required in the reverse mode. |
vgvassilev
changed the title
Reduce cloning complexity
Reduce cloning complexity in forward mode
Sep 28, 2018
Ok, that's #94. |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Each call to Clone() has complexity of O(n), where n is the size of the Stmt's subtree, since it recursively calls Clone() on every substatement until leaves are reached.
When differentiating a function via Forward/ReverseModeVisitor, we potentially call Clone() on every node of the AST tree (which recursively clones all subnodes, we are cloning same nodes multiple times) and have the total complexity of O(n^2).
Wouldn't it be more efficient to Clone() the whole tree just once before calling Visit() on it? The complexity should be just 2xO(n).
The text was updated successfully, but these errors were encountered: