Changeset 6183 for trunk/sources/HeuristicLab.Problems.ExternalEvaluation

Timestamp:

05/11/11 15:36:30 (14 years ago)

Author:

epitzer

Message:

Prepare for parallel external evaluation (#1516)
~ move cache to problem for better visibility
+ configurable persistence of cache Content
+ proper synchronization for parallel access to cache

Location:

trunk/sources/HeuristicLab.Problems.ExternalEvaluation/3.3

Files:

• CachedExternalEvaluator.cs (modified) (4 diffs)
• EvaluationCache.cs (modified) (9 diffs)
• ExternalEvaluationProblem.cs (modified) (2 diffs)

trunk/sources/HeuristicLab.Problems.ExternalEvaluation/3.3/CachedExternalEvaluator.cs

@@ -21 +21 @@
 
 
+using System.Threading;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -33 +34 @@
 
     #region Parameters
-    public OptionalValueParameter<EvaluationCache> CacheParameter {
-      get { return (OptionalValueParameter<EvaluationCache>)Parameters["Cache"]; }
+    public ValueLookupParameter<EvaluationCache> CacheParameter {
+      get { return (ValueLookupParameter<EvaluationCache>)Parameters["Cache"]; }
     }
     #endregion
 
     #region Parameter Values
-    public EvaluationCache Cache {
-      get { return CacheParameter.Value; }
-      set { CacheParameter.Value = value; }
-    }
     protected DoubleValue Quality {
       get { return QualityParameter.ActualValue; }
@@ -49 +46 @@
     protected IEvaluationServiceClient Client {
       get { return ClientParameter.ActualValue; }
+    }
+    protected EvaluationCache Cache {
+      get { return CacheParameter.ActualValue; }
+      set { CacheParameter.ActualValue = value; }
     }
     #endregion
@@ -61 +62 @@
     public CachedExternalEvaluator()
       : base() {
-      Parameters.Add(new OptionalValueParameter<EvaluationCache>("Cache", "Cache of previously evaluated solutions"));
+      Parameters.Add(new ValueLookupParameter<EvaluationCache>("Cache", "Cache of previously evaluated solutions"));
     }
     #endregion
 
     public override IOperation Apply() {
-      if (Cache == null) Cache = new EvaluationCache();
+      if (Cache == null)
+        return base.Apply();
+
       if (Quality == null) Quality = new DoubleValue(0);
-
       Quality.Value = Cache.GetValue(BuildSolutionMessage(), m => Client.Evaluate(m).Quality);
-
       if (Successor != null)
         return ExecutionContext.CreateOperation(Successor);

trunk/sources/HeuristicLab.Problems.ExternalEvaluation/3.3/EvaluationCache.cs

@@ -26 +26 @@
 using System.Collections.Generic;
 using System.Linq;
+using System.Threading;
 using HeuristicLab.Common;
 using HeuristicLab.Common.Resources;
@@ -73 +74 @@
     private LinkedList<CacheEntry> list;
     private Dictionary<CacheEntry, LinkedListNode<CacheEntry>> index;
+    private static HashSet<string> activeEvaluations = new HashSet<string>();
+    private static object cacheLock = new object();
+    private static object evaluationLock = new object();
+    private static AutoResetEvent evaluationDone = new AutoResetEvent(false);
     #endregion
 
@@ -80 +85 @@
     }
     public int Size {
-      get { return index.Count; }
+      get {
+        lock (cacheLock) {
+          return index.Count;
+        }
+      }
+    }
+    public int ActiveEvaluations {
+      get {
+        lock (evaluationLock) {
+          return activeEvaluations.Count;
+        }
+      }
     }
     [Storable]
@@ -89 +105 @@
     public event EventHandler SizeChanged;
     public event EventHandler HitsChanged;
+    public event EventHandler ActiveEvalutionsChanged;
 
     protected virtual void OnSizeChanged() {
@@ -100 +117 @@
         handler(this, EventArgs.Empty);
     }
+    protected virtual void OnActiveEvalutionsChanged() {
+      EventHandler handler = ActiveEvalutionsChanged;
+      if (handler != null)
+        handler(this, EventArgs.Empty);
+    }
     #endregion
 
@@ -105 +127 @@
     public FixedValueParameter<IntValue> CapacityParameter {
       get { return (FixedValueParameter<IntValue>)Parameters["Capacity"]; }
+    }
+    public FixedValueParameter<BoolValue> PersistentCacheParameter {
+      get { return (FixedValueParameter<BoolValue>)Parameters["PersistentCache"]; }
     }
     #endregion
@@ -113 +138 @@
       set { CapacityParameter.Value.Value = value; }
     }
+    public bool IsPersistent {
+      get { return PersistentCacheParameter.Value.Value; }
+    }
     #endregion
 
@@ -119 +147 @@
     private IEnumerable<KeyValuePair<string, double>> Cache_Persistence {
       get {
+        if (IsPersistent) {
+          return GetCacheValues();
+        } else {
+          return Enumerable.Empty<KeyValuePair<string, double>>();
+        }
+      }
+      set {
+        SetCacheValues(value);
+      }
+    }
+    [StorableHook(HookType.AfterDeserialization)]
+    private void AfterDeserialization() {
+      RegisterEvents();
+    }
+    #endregion
+
+    #region Construction & Cloning
+    [StorableConstructor]
+    protected EvaluationCache(bool deserializing) : base(deserializing) { }
+    protected EvaluationCache(EvaluationCache original, Cloner cloner)
+      : base(original, cloner) {
+      SetCacheValues(original.GetCacheValues());
+      RegisterEvents();
+    }
+    public EvaluationCache() {
+      list = new LinkedList<CacheEntry>();
+      index = new Dictionary<CacheEntry, LinkedListNode<CacheEntry>>();
+      Parameters.Add(new FixedValueParameter<IntValue>("Capacity", "Maximum number of cache entries.", new IntValue(10000)));
+      Parameters.Add(new FixedValueParameter<BoolValue>("PersistentCache", "Save cache when serializing object graph?", new BoolValue(false)));
+      RegisterEvents();
+    }
+    public override IDeepCloneable Clone(Cloner cloner) {
+      return new EvaluationCache(this, cloner);
+    }
+    #endregion
+
+    #region Event Handling
+    private void RegisterEvents() {
+      CapacityParameter.Value.ValueChanged += new EventHandler(Value_ValueChanged);
+    }
+
+    void Value_ValueChanged(object sender, EventArgs e) {
+      if (Capacity < 0)
+        throw new ArgumentOutOfRangeException("Cache capacity cannot be less than zero");
+      Trim();
+    }
+    #endregion
+
+    #region Methods
+    public void Reset() {
+      lock (cacheLock) {
+        list = new LinkedList<CacheEntry>();
+        index = new Dictionary<CacheEntry, LinkedListNode<CacheEntry>>();
+        Hits = 0;
+      }
+      OnSizeChanged();
+      OnHitsChanged();
+    }
+
+    public double GetValue(SolutionMessage message, Evaluator evaluate) {
+      CacheEntry entry = new CacheEntry(message.ToString());
+      LinkedListNode<CacheEntry> node;
+      bool lockTaken = false;
+      try {
+        Monitor.Enter(cacheLock, ref lockTaken);
+        if (index.TryGetValue(entry, out node)) {
+          list.Remove(node);
+          list.AddLast(node);
+          Hits++;
+          lockTaken = false;
+          Monitor.Exit(cacheLock);
+          OnHitsChanged();
+          return node.Value.Value;
+        } else {
+          lockTaken = false;
+          Monitor.Exit(cacheLock);
+          return Evaluate(message, evaluate, entry);
+        }
+      } finally {
+        if (lockTaken)
+          Monitor.Exit(cacheLock);
+      }
+    }
+
+    private double Evaluate(SolutionMessage message, Evaluator evaluate, CacheEntry entry) {
+      bool lockTaken = false;
+      try {
+        Monitor.Enter(evaluationLock, ref lockTaken);
+        if (activeEvaluations.Contains(entry.Key)) {
+          while (activeEvaluations.Contains(entry.Key)) {
+            lockTaken = false;
+            Monitor.Exit(evaluationLock);
+            evaluationDone.WaitOne();
+            Monitor.Enter(evaluationLock, ref lockTaken);
+          }
+          lock (cacheLock) {
+            return index[entry].Value.Value;
+          }
+        } else {
+          activeEvaluations.Add(entry.Key);
+          lockTaken = false;
+          Monitor.Exit(evaluationLock);
+          OnActiveEvalutionsChanged();
+          entry.Value = evaluate(message);
+          lock (cacheLock) {
+            index[entry] = list.AddLast(entry);
+          }
+          lock (evaluationLock) {
+            activeEvaluations.Remove(entry.Key);
+            evaluationDone.Set();
+          }
+          OnActiveEvalutionsChanged();
+          Trim();
+          return entry.Value;
+        }
+      } finally {
+        if (lockTaken)
+          Monitor.Exit(evaluationLock);
+      }
+    }
+
+    private void Trim() {
+      lock (cacheLock) {
+        while (list.Count > Capacity) {
+          LinkedListNode<CacheEntry> item = list.First;
+          list.Remove(item);
+          index.Remove(item.Value);
+        }
+      }
+      OnSizeChanged();
+    }
+    private IEnumerable<KeyValuePair<string, double>> GetCacheValues() {
+      lock (cacheLock) {
         return index.ToDictionary(kvp => kvp.Key.Key, kvp => kvp.Key.Value);
       }
-      set {
+    }
+    private void SetCacheValues(IEnumerable<KeyValuePair<string, double>> value) {
+      lock (cacheLock) {
         list = new LinkedList<CacheEntry>();
         index = new Dictionary<CacheEntry, LinkedListNode<CacheEntry>>();
@@ -131 +294 @@
       }
     }
-    [StorableHook(HookType.AfterDeserialization)]
-    private void AfterDeserialization() {
-      RegisterEvents();
-    }
-    #endregion
-
-    #region Construction & Cloning
-    [StorableConstructor]
-    protected EvaluationCache(bool deserializing) : base(deserializing) { }
-    protected EvaluationCache(EvaluationCache original, Cloner cloner)
-      : base(original, cloner) {
-      Cache_Persistence = original.Cache_Persistence;
-      RegisterEvents();
-    }
-    public EvaluationCache() {
-      list = new LinkedList<CacheEntry>();
-      index = new Dictionary<CacheEntry, LinkedListNode<CacheEntry>>();
-      Parameters.Add(new FixedValueParameter<IntValue>("Capacity", "Maximum number of cache entries.", new IntValue(10000)));
-      RegisterEvents();
-    }
-    public override IDeepCloneable Clone(Cloner cloner) {
-      return new EvaluationCache(this, cloner);
-    }
-    #endregion
-
-    #region Event Handling
-    private void RegisterEvents() {
-      CapacityParameter.Value.ValueChanged += new EventHandler(Value_ValueChanged);
-    }
-
-    void Value_ValueChanged(object sender, EventArgs e) {
-      if (Capacity < 0)
-        throw new ArgumentOutOfRangeException("Cache capacity cannot be less than zero");
-      Trim();
-    }
-    #endregion
-
-    #region Methods
-    public void Reset() {
-      list = new LinkedList<CacheEntry>();
-      index = new Dictionary<CacheEntry, LinkedListNode<CacheEntry>>();
-      Hits = 0;
-      OnSizeChanged();
-      OnHitsChanged();
-    }
-
-    public double GetValue(SolutionMessage message, Evaluator evaluate) {
-      CacheEntry entry = new CacheEntry(message.ToString());
-      LinkedListNode<CacheEntry> node;
-      if (index.TryGetValue(entry, out node)) {
-        list.Remove(node);
-        list.AddLast(node);
-        Hits++;
-        OnHitsChanged();
-        return node.Value.Value;
-      } else {
-        entry.Value = evaluate(message);
-        index[entry] = list.AddLast(entry);
-        Trim();
-        return entry.Value;
-      }
-    }
-
-    private void Trim() {
-      while (list.Count > Capacity) {
-        LinkedListNode<CacheEntry> item = list.First;
-        list.Remove(item);
-        index.Remove(item.Value);
-      }
-      OnSizeChanged();
-    }
     #endregion
 

trunk/sources/HeuristicLab.Problems.ExternalEvaluation/3.3/ExternalEvaluationProblem.cs

@@ -86 +86 @@
       get { return (ValueParameter<ItemList<IOperator>>)Parameters["Operators"]; }
     }
+    public OptionalValueParameter<EvaluationCache> CacheParameter {
+      get { return (OptionalValueParameter<EvaluationCache>)Parameters["Cache"]; }
+    }
     #endregion
 
@@ -148 +151 @@
       Parameters.Add(new OptionalValueParameter<IScope>("BestKnownSolution", "The best known solution for this external evaluation problem."));
       Parameters.Add(new ValueParameter<ItemList<IOperator>>("Operators", "The operators that are passed to the algorithm.", new ItemList<IOperator>()));
+      Parameters.Add(new OptionalValueParameter<EvaluationCache>("Cache", "Cache of previously evaluated solutions."));
 
       InitializeOperators();