From 049a16d1b1a683487a0c17014e9f7c477820a132 Mon Sep 17 00:00:00 2001 From: Carlo Zancanaro Date: Mon, 9 Jul 2012 13:10:32 +1000 Subject: Fixed up the newer strategy iteration stuff Trivial 100000 var case in 15s on my Uni machine. --- impl/EquationSystem.hpp | 35 ++++++++++++++++++---- impl/IdSet.hpp | 10 +++++++ impl/ImprovementOperator.hpp | 71 ++++++++++++++++++++++++++------------------ impl/Log.hpp | 2 ++ impl/Makefile | 2 +- impl/main.cpp | 1 + 6 files changed, 85 insertions(+), 36 deletions(-) diff --git a/impl/EquationSystem.hpp b/impl/EquationSystem.hpp index d09bef2..c7e5f4c 100644 --- a/impl/EquationSystem.hpp +++ b/impl/EquationSystem.hpp @@ -7,12 +7,16 @@ #include "Operator.hpp" #include "Expression.hpp" #include "VariableAssignment.hpp" +#include "IdMap.hpp" template struct MaxStrategy; template struct EquationSystem { + EquationSystem() + : _expr_to_var(NULL) { } + virtual ~EquationSystem() { for (typename std::set*>::iterator it = _expressions.begin(); it != _expressions.end(); @@ -24,6 +28,8 @@ struct EquationSystem { ++it) { delete *it; } + if (_expr_to_var) + delete _expr_to_var; } MaxExpression& maxExpression(const std::vector*>& arguments) { @@ -86,7 +92,7 @@ struct EquationSystem { StableVariableAssignment* assignment(const Domain& value) const { return new StableVariableAssignment(_variables.size(), value); } - VariableAssignment* eval(const VariableAssignment& rho) const { + StableVariableAssignment* eval(const VariableAssignment& rho) const { StableVariableAssignment* result = this->assignment(-infinity()); for (unsigned int i = 0, length = _variables.size(); i < length; @@ -97,7 +103,7 @@ struct EquationSystem { } return result; } - VariableAssignment* eval(const VariableAssignment& rho, const MaxStrategy& strat) const { + StableVariableAssignment* eval(const VariableAssignment& rho, const MaxStrategy& strat) const { StableVariableAssignment* result = this->assignment(-infinity()); for (unsigned int i = 0, length = _variables.size(); i < length; @@ -109,12 +115,28 @@ struct EquationSystem { return result; } - Variable* varFromExpr(const Expression& expr) const { + void indexMaxExpressions() { + _expr_to_var = new IdMap,Variable*>(maxExpressionCount(), NULL); for (unsigned int i = 0, length = _right_sides.size(); i < length; ++i) { - if (_right_sides[i] == &expr) - return _variables[i]; + (*_expr_to_var)[*_right_sides[i]] = _variables[i]; + } + } + + Variable* varFromExpr(const Expression& expr) const { + if (_expr_to_var) { // we've indexed: + auto* maxExpr = dynamic_cast*>(&expr); + if (maxExpr) { + return (*_expr_to_var)[*maxExpr]; + } else { + return NULL; + } + } else { + for (unsigned int i = 0, length = _right_sides.size(); i < length; ++i) { + if (_right_sides[i] == &expr) + return _variables[i]; + } + return NULL; } - return NULL; } virtual bool equalAssignments(const VariableAssignment& l, const VariableAssignment& r) const { @@ -141,6 +163,7 @@ struct EquationSystem { std::set*> _expressions; std::vector*> _variables; std::map*> _variable_names; + IdMap, Variable*>* _expr_to_var; std::vector*> _max_expressions; std::vector*> _right_sides; }; diff --git a/impl/IdSet.hpp b/impl/IdSet.hpp index 99f89cc..950b1e1 100644 --- a/impl/IdSet.hpp +++ b/impl/IdSet.hpp @@ -39,6 +39,16 @@ class IdSet { } } + IdSet inverse() const { + IdSet other(_range); + for (unsigned int i = 0; i < _range; ++i) { + if (_set.find(i) == _set.end()) { + other._set.insert(i); + } + } + return other; + } + bool contains(const T& obj) const { return _set.find(obj.id()) != _set.end(); } diff --git a/impl/ImprovementOperator.hpp b/impl/ImprovementOperator.hpp index 5cee78c..e6b2ded 100644 --- a/impl/ImprovementOperator.hpp +++ b/impl/ImprovementOperator.hpp @@ -10,7 +10,7 @@ struct ImprovementOperator { virtual bool improve( EquationSystem& system, ConcreteMaxStrategy& strat, - const VariableAssignment& rho, + StableVariableAssignment& rho, IdSet >& changedIn, IdSet >& changedOut ) const = 0; @@ -21,7 +21,7 @@ struct NaiveImprovementOperator : public ImprovementOperator { bool improve( EquationSystem& system, ConcreteMaxStrategy& strat, - const VariableAssignment& rho, + StableVariableAssignment& rho, IdSet >&, IdSet >& ) const { @@ -52,12 +52,12 @@ struct RepeatedImprovementOperator : public ImprovementOperator { bool improve( EquationSystem& system, ConcreteMaxStrategy& strat, - const VariableAssignment& rho, + StableVariableAssignment& rho, IdSet >& changedIn, IdSet >& changedOut ) const { if (_subImprovement.improve(system, strat, rho, changedIn, changedOut)) { - VariableAssignment* rho2 = system.eval(rho, strat); + StableVariableAssignment* rho2 = system.eval(rho, strat); improve(system, strat, *rho2, changedIn, changedOut); delete rho2; return true; @@ -81,7 +81,7 @@ struct SmartImprovementOperator : public ImprovementOperator { const EquationSystem& system, ConcreteMaxStrategy& strat, IdMap,IdSet>>& influence, - const VariableAssignment& rho, + StableVariableAssignment& rho, IdSet>& stable, IdSet>& changed ) : _system(system), @@ -125,7 +125,7 @@ struct SmartImprovementOperator : public ImprovementOperator { struct DependencyAssignment : public VariableAssignment{ DependencyAssignment(const DynamicMaxStrategy& strat, - const VariableAssignment& rho, + StableVariableAssignment& rho, const MaxExpression& expr) : _strat(strat), _rho(rho), @@ -133,11 +133,12 @@ struct SmartImprovementOperator : public ImprovementOperator { } const Domain& operator[](const Variable& var) const { _strat._influence[*_strat._system[var]].insert(_expr); + _rho[var] =_strat._system[var]->eval(_rho, _strat); return _rho[var]; } private: const DynamicMaxStrategy& _strat; - const VariableAssignment& _rho; + StableVariableAssignment& _rho; const MaxExpression& _expr; }; @@ -148,7 +149,9 @@ struct SmartImprovementOperator : public ImprovementOperator { } unsigned int get(const MaxExpression& e) const { _strat.solve(e); - _strat._influence[e].insert(_expr); + if (&_expr != &e) { + _strat._influence[e].insert(_expr); + } return _strat._values.get(e); } private: @@ -158,7 +161,7 @@ struct SmartImprovementOperator : public ImprovementOperator { private: const EquationSystem& _system; - const VariableAssignment& _rho; + StableVariableAssignment& _rho; ConcreteMaxStrategy& _values; IdSet>& _stable; IdSet>& _changed; @@ -166,28 +169,34 @@ struct SmartImprovementOperator : public ImprovementOperator { }; void invalidateSubexpressions(IdSet>& set, Expression& expr) const { - MaxExpression* maxExpr = static_cast*>(&expr); + MaxExpression* maxExpr = dynamic_cast*>(&expr); if (maxExpr != NULL && maxExpr->id() < _system.maxExpressionCount()) { - invalidateAll(set, *maxExpr); - for (auto it = maxExpr->arguments().begin(), - end = maxExpr->arguments().end(); - it != end; - ++it) { - invalidateSubexpressions(set, **it); + if (invalidateAll(set, *maxExpr)) { + for (auto it = maxExpr->arguments().begin(), + end = maxExpr->arguments().end(); + it != end; + ++it) { + invalidateSubexpressions(set, **it); + } } } } - void invalidateAll(IdSet>& set, MaxExpression& expr) const { + bool invalidateAll(IdSet>& set, MaxExpression& expr) const { if (!set.contains(expr)) { set.insert(expr); for (auto it = _influence[expr].begin(), end = _influence[expr].end(); it != end; ++it) { - invalidateSubexpressions(set, _system.maxExpression(*it)); + if (!set.contains(_system.maxExpression(*it))) { + set.insert(_system.maxExpression(*it)); + } + //invalidateSubexpressions(set, _system.maxExpression(*it)); } + return true; } + return false; } void markChanged(IdSet>& set, MaxExpression& expr, IdSet>& seen) const { @@ -210,14 +219,16 @@ struct SmartImprovementOperator : public ImprovementOperator { bool improve( EquationSystem&, ConcreteMaxStrategy& stratOut, - const VariableAssignment& rho, + StableVariableAssignment& rho, IdSet >& changedIn, IdSet >& changedOut ) const { IdSet> invalidSet(_system.maxExpressionCount()); IdSet> changedSet(_system.maxExpressionCount()); + IdSet> stableSet(_system.maxExpressionCount()); if (_first_run) { - _first_run = false; + invalidSet.invert(); // everything is invalid on the first run + _first_run = false; } else { for (auto it = changedIn.begin(), end = changedIn.end(); @@ -225,17 +236,19 @@ struct SmartImprovementOperator : public ImprovementOperator { ++it) { invalidateSubexpressions(invalidSet, *_system[_system.variable(*it)]); } - invalidSet.invert(); + stableSet = invalidSet.inverse(); } - log::debug << "stable: " << invalidSet; - log::debug << "infl: " << _influence; - DynamicMaxStrategy strat(_system, stratOut, _influence, rho, invalidSet, changedSet); - auto inv = invalidSet; - for (unsigned int i = 0, length = _system.maxExpressionCount(); - i < length; - ++i) { - strat.get(_system.maxExpression(i)); + log::strategy << "stable: " << stableSet; + log::strategy << "infl: " << _influence; + DynamicMaxStrategy strat(_system, stratOut, _influence, rho, stableSet, changedSet); + log::strategy << "invalid: " << invalidSet; + for (auto it = invalidSet.begin(), + end = invalidSet.end(); + it != end; + ++it) { + log::strategy << _system.maxExpression(*it); + strat.get(_system.maxExpression(*it)); } IdSet> seen; for (auto it = changedSet.begin(), diff --git a/impl/Log.hpp b/impl/Log.hpp index a920906..1e340c7 100644 --- a/impl/Log.hpp +++ b/impl/Log.hpp @@ -40,8 +40,10 @@ namespace log { return logger; } + Logger info(std::cout, "info"); Logger trace(std::cerr, "trace"); Logger strategy(std::cerr, "strategy"); + Logger fixpoint(std::cerr, "fixpoint"); Logger debug(std::cerr, "debug"); } diff --git a/impl/Makefile b/impl/Makefile index 588c3ab..3192191 100644 --- a/impl/Makefile +++ b/impl/Makefile @@ -1,7 +1,7 @@ CC=gcc CPP=g++ BUILD=build/ -FLAGS=-Wall -Werror -Wextra -pedantic -g -lantlr3c -pg -std=c++11 +FLAGS=-Wall -Werror -Wextra -pedantic -lantlr3c -std=c++11 -g -pg all: main diff --git a/impl/main.cpp b/impl/main.cpp index 0317390..31f2937 100644 --- a/impl/main.cpp +++ b/impl/main.cpp @@ -155,6 +155,7 @@ int main (int argc, char* argv[]) { } log::debug << system; + system.indexMaxExpressions(); // make reverse-lookup O(1) instead of O(n) StableVariableAssignment result(system.variableCount(), infinity()); ConcreteMaxStrategy strategy(system); IdSet> s1(system.variableCount()); -- cgit v1.2.3