From 785d762d4f5d69e3c89855f68cb0654aace4608d Mon Sep 17 00:00:00 2001
From: Carlo Zancanaro <carlo@pc-4w14-0.cs.usyd.edu.au>
Date: Mon, 2 Jul 2012 17:44:17 +1000
Subject: 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.
---
 impl/FixpointAlgorithm.hpp | 101 ++++++++++++++++++++++++++++++++++++++-------
 1 file changed, 85 insertions(+), 16 deletions(-)

(limited to 'impl/FixpointAlgorithm.hpp')

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
-- 
cgit v1.2.3