diff options
author | Carlo Zancanaro <carlo@pc-4w14-0.cs.usyd.edu.au> | 2012-07-02 17:44:17 +1000 |
---|---|---|
committer | Carlo Zancanaro <carlo@pc-4w14-0.cs.usyd.edu.au> | 2012-07-02 17:44:17 +1000 |
commit | 785d762d4f5d69e3c89855f68cb0654aace4608d (patch) | |
tree | cf26981337afa2ce59dc921bc22655faf33c4281 /impl/FixpointAlgorithm.hpp | |
parent | 9e0d0b59f44d781d2cbbff4f83d2ab71b7dc0121 (diff) |
Dependency-aware smart fixpoint.
Slows it down *heaps* for the moment.
Still need to add the MaxStrategy part, which should speed it up a fair
bit. At the moment it has to do a fair bit more work for no benefit.
Diffstat (limited to 'impl/FixpointAlgorithm.hpp')
-rw-r--r-- | impl/FixpointAlgorithm.hpp | 101 |
1 files changed, 85 insertions, 16 deletions
diff --git a/impl/FixpointAlgorithm.hpp b/impl/FixpointAlgorithm.hpp index b39a915..350047f 100644 --- a/impl/FixpointAlgorithm.hpp +++ b/impl/FixpointAlgorithm.hpp @@ -9,36 +9,64 @@ template<typename Domain> struct FixpointAlgorithm { virtual ~FixpointAlgorithm() { } - virtual VariableAssignment<Domain>* maxFixpoint(const EquationSystem<Domain>&) const = 0; + virtual void maxFixpoint( + const EquationSystem<Domain>& system, + StableVariableAssignment<Domain>& rho, + IdSet<Variable<Domain> >& changedIn, + IdSet<Variable<Domain> >& changedOut + ) = 0; }; template<typename Domain> struct NaiveFixpointAlgorithm : public FixpointAlgorithm<Domain> { - virtual VariableAssignment<Domain>* maxFixpoint(const EquationSystem<Domain>& system) const { + NaiveFixpointAlgorithm(const EquationSystem<Domain>& system) + : _system(system) { } + virtual void maxFixpoint( + const EquationSystem<Domain>& system, + StableVariableAssignment<Domain>& rhoOut, + IdSet<Variable<Domain> >& changedIn, + IdSet<Variable<Domain> >& changedOut + ) { VariableAssignment<Domain>* rho = NULL; VariableAssignment<Domain>* result = system.assignment(infinity<Domain>()); do { if (rho) delete rho; rho = result; - result = system.eval(*rho); - } while (!system.equalAssignments(*rho, *result)); + result = _system.eval(*rho); + } while (!_system.equalAssignments(*rho, *result)); if (rho) delete rho; - return result; + + for (unsigned int i = 0, length = system.variableCount(); i < length; ++i) { + Variable<Domain> var = system.variable(i); + rhoOut[var] = (*result)[var]; + } } + private: + const EquationSystem<Domain>& _system; }; template<typename Domain> struct SmartFixpointAlgorithm : public FixpointAlgorithm<Domain> { + SmartFixpointAlgorithm(const EquationSystem<Domain>& system) + : _system(system), + _influence(system.variableCount(), IdSet<Variable<Domain> >(system.variableCount())){ + } + struct DynamicVariableAssignment : public VariableAssignment<Domain> { - DynamicVariableAssignment(const EquationSystem<Domain>& system) - : _system(system), - _values(system.variableCount(), infinity<Domain>()), - _stable(system.variableCount()), - _influence(system.variableCount(), IdSet<Variable<Domain> >(system.variableCount())) { } + DynamicVariableAssignment( + const EquationSystem<Domain>& system, + IdMap<Variable<Domain>,IdSet<Variable<Domain> > >& influence, + StableVariableAssignment<Domain>& rho, + IdSet<Variable<Domain> >& stable, + IdSet<Variable<Domain> >& changed + ) : _system(system), + _values(rho), + _stable(stable), + _changed(changed), + _influence(influence) { } const Domain& operator[](const Variable<Domain>& var) const { solve(var); - //std::cout << _values << std::endl; return _values[var]; } @@ -54,6 +82,7 @@ struct SmartFixpointAlgorithm : public FixpointAlgorithm<Domain> { IdSet<Variable<Domain> > oldInfluence = _influence[x]; _influence[x].clear(); _values[x] = val; + _changed.insert(x); _stable.filter(oldInfluence); @@ -62,6 +91,7 @@ struct SmartFixpointAlgorithm : public FixpointAlgorithm<Domain> { ++it) { solve(_system.variable(*it)); } + _influence[x] = oldInfluence; } } } @@ -80,14 +110,53 @@ struct SmartFixpointAlgorithm : public FixpointAlgorithm<Domain> { }; const EquationSystem<Domain>& _system; - mutable IdMap<Variable<Domain>,Domain> _values; - mutable IdSet<Variable<Domain> > _stable; - mutable IdMap<Variable<Domain>,IdSet<Variable<Domain> > > _influence; + StableVariableAssignment<Domain>& _values; + IdSet<Variable<Domain> >& _stable; + IdSet<Variable<Domain> >& _changed; + IdMap<Variable<Domain>,IdSet<Variable<Domain> > >& _influence; }; - virtual VariableAssignment<Domain>* maxFixpoint(const EquationSystem<Domain>& system) const { - return new DynamicVariableAssignment(system); + void invalidate(const IdSet<Variable<Domain> >& set, IdSet<Variable<Domain> >& changed, StableVariableAssignment<Domain>& rho) const { + for (typename IdSet<Variable<Domain> >::iterator it = set.begin(), + end = set.end(); + it != end; + ++it) { + Variable<Domain>& var = _system.variable(*it); + if (!changed.contains(var)) { + rho[var] = infinity<Domain>(); + changed.insert(var); + invalidate(_influence[var], changed, rho); + } + } + } + + virtual void maxFixpoint( + const EquationSystem<Domain>& system, + StableVariableAssignment<Domain>& rhoOut, + IdSet<Variable<Domain> >& changedIn, + IdSet<Variable<Domain> >& changedOut + ) { + for (typename IdSet<Variable<Domain> >::iterator it = changedIn.begin(), + end = changedIn.end(); + it != end; + ++it) { + //std::cout << *it << " "; + Variable<Domain>& var = _system.variable(*it); + rhoOut[var] = infinity<Domain>(); + invalidate(_influence[var], changedIn, rhoOut); + } + + changedIn.invert(); + DynamicVariableAssignment rho(system, _influence, rhoOut, changedIn, changedOut); + for (unsigned int i = 0, length = system.variableCount(); i < length; ++i) { + rho[system.variable(i)]; + } + /*std::cout << _influence << std::endl; + std::cout << std::endl;*/ } + private: + const EquationSystem<Domain>& _system; + IdMap<Variable<Domain>,IdSet<Variable<Domain> > > _influence; }; #endif |