source: trunk/sources/HeuristicLab.Problems.ExternalEvaluation/3.4/EvaluationCache.cs @ 13180

Last change on this file since 13180 was 13180, checked in by pfleck, 4 years ago

#1674

  • ProtoBuff QualityMessages
    • Changed the QualityMessage to be able to be used for single- and multi-objective problems.
    • The new SingleObjectiveQualityMessage and MultiObjectiveQualityMessage now "inherits" from QualityMessages to be able to be used in a polymorph manner.
    • This is done via protobuf's nested extensions (see http://www.indelible.org/ink/protobuf-polymorphism/).
  • EvaluationCache
    • The EvaluationCache now now stores the QualityMessage instead of a single double. This way the cache can be used for single- and multi-objective problems and additionally opens the possibility to extend the quality message with any data. (previously extended data was lost when the cache was persisted and loaded again)
    • When deserializing an older version of the cache a new single objective quality message is created from the double value. This way, no compatibility is broken and version must not be incremented.
  • Adapted the ExternalEvaluationProblem to the changes of the EvaluationCache and the QualityMessage.
  • Added a MultiObjectiveExternalEvaluationProblem on basis of the ExternalEvaluationProblem and added a IExternalEvaluationProblem interface.
File size: 11.1 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 *
20 * The LRU cache is based on an idea by Robert Rossney see
21 * <http://csharp-lru-cache.googlecode.com>.
22 */
23#endregion
24
25using System;
26using System.Collections.Generic;
27using System.Globalization;
28using System.IO;
29using System.Linq;
30using System.Text.RegularExpressions;
31using System.Threading;
32using Google.ProtocolBuffers;
33using HeuristicLab.Common;
34using HeuristicLab.Common.Resources;
35using HeuristicLab.Core;
36using HeuristicLab.Data;
37using HeuristicLab.Parameters;
38using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
39
40namespace HeuristicLab.Problems.ExternalEvaluation {
41
42  [Item("EvaluationCache", "Cache for external evaluation values")]
43  [StorableClass]
44  public class EvaluationCache : ParameterizedNamedItem {
45
46    #region Types
47    private sealed class CacheEntry {
48
49      public readonly string Key;
50
51      private QualityMessage message;
52      private byte[] rawMessage;
53
54      public byte[] RawMessage {
55        get { return rawMessage; }
56        set {
57          rawMessage = value;
58          message = null;
59        }
60      }
61
62      public CacheEntry(string key) {
63        Key = key;
64      }
65
66      public QualityMessage GetMessage(ExtensionRegistry extensions) {
67        if (message == null && rawMessage != null)
68          message = QualityMessage.ParseFrom(ByteString.CopyFrom(rawMessage), extensions);
69        return message;
70      }
71      public void SetMessage(QualityMessage value) {
72        message = value;
73        rawMessage = value.ToByteArray();
74      }
75
76      public override bool Equals(object obj) {
77        CacheEntry other = obj as CacheEntry;
78        if (other == null)
79          return false;
80        return Key.Equals(other.Key);
81      }
82
83      public override int GetHashCode() {
84        return Key.GetHashCode();
85      }
86
87      public string QualityString(IFormatProvider formatProvider = null) {
88        if (formatProvider == null) formatProvider = CultureInfo.CurrentCulture;
89        if (RawMessage == null) return "-";
90        var msg = message ?? CreateBasicQualityMessage();
91        switch (msg.Type) {
92          case QualityMessage.Types.Type.SingleObjectiveQualityMessage:
93            return msg.GetExtension(SingleObjectiveQualityMessage.QualityMessage_).Quality.ToString(formatProvider);
94          case QualityMessage.Types.Type.MultiObjectiveQualityMessage:
95            var qualities = msg.GetExtension(MultiObjectiveQualityMessage.QualityMessage_).QualitiesList;
96            return string.Format("[{0}]", string.Join(",", qualities.Select(q => q.ToString(formatProvider))));
97          default:
98            return "-";
99        }
100      }
101      private QualityMessage CreateBasicQualityMessage() {
102        var extensions = ExtensionRegistry.CreateInstance();
103        ExternalEvaluationMessages.RegisterAllExtensions(extensions);
104        return QualityMessage.ParseFrom(ByteString.CopyFrom(rawMessage), extensions);
105      }
106
107      public override string ToString() {
108        return string.Format("{{{0} : {1}}}", Key, QualityString());
109      }
110    }
111
112    public delegate QualityMessage Evaluator(SolutionMessage message);
113    #endregion
114
115    #region Fields
116    private LinkedList<CacheEntry> list;
117    private Dictionary<CacheEntry, LinkedListNode<CacheEntry>> index;
118
119    private HashSet<string> activeEvaluations = new HashSet<string>();
120    private object cacheLock = new object();
121    #endregion
122
123    #region Properties
124    public static new System.Drawing.Image StaticItemImage {
125      get { return VSImageLibrary.Database; }
126    }
127    public int Size { get { lock (cacheLock) return index.Count; } }
128    public int ActiveEvaluations { get { lock (cacheLock) return activeEvaluations.Count; } }
129
130    [Storable]
131    public int Hits { get; private set; }
132    #endregion
133
134    #region events
135    public event EventHandler Changed;
136
137    protected virtual void OnChanged() {
138      EventHandler handler = Changed;
139      if (handler != null)
140        handler(this, EventArgs.Empty);
141    }
142    #endregion
143
144    #region Parameters
145    public FixedValueParameter<IntValue> CapacityParameter {
146      get { return (FixedValueParameter<IntValue>)Parameters["Capacity"]; }
147    }
148    public FixedValueParameter<BoolValue> PersistentCacheParameter {
149      get { return (FixedValueParameter<BoolValue>)Parameters["PersistentCache"]; }
150    }
151    #endregion
152
153    #region Parameter Values
154    public int Capacity {
155      get { return CapacityParameter.Value.Value; }
156      set { CapacityParameter.Value.Value = value; }
157    }
158    public bool IsPersistent {
159      get { return PersistentCacheParameter.Value.Value; }
160    }
161    #endregion
162
163    #region Persistence
164    #region BackwardsCompatibility3.4
165    [Storable(Name = "Cache")]
166    private IEnumerable<KeyValuePair<string, double>> Cache_Persistence {
167      get { return Enumerable.Empty<KeyValuePair<string, double>>(); }
168      set {
169        var rawMessages = value.ToDictionary(kvp => kvp.Key,
170          kvp => QualityMessage.CreateBuilder()
171            .SetSolutionId(0)
172            .SetExtension(
173              SingleObjectiveQualityMessage.QualityMessage_,
174              SingleObjectiveQualityMessage.CreateBuilder().SetQuality(kvp.Value).Build())
175            .Build().ToByteArray());
176        SetCacheValues(rawMessages);
177      }
178    }
179    #endregion
180    [Storable(Name = "CacheNew")]
181    private IEnumerable<KeyValuePair<string, byte[]>> CacheNew_Persistence {
182      get { return IsPersistent ? GetCacheValues() : Enumerable.Empty<KeyValuePair<string, byte[]>>(); }
183      set { SetCacheValues(value); }
184    }
185    [StorableHook(HookType.AfterDeserialization)]
186    private void AfterDeserialization() {
187      RegisterEvents();
188    }
189    #endregion
190
191    #region Construction & Cloning
192    [StorableConstructor]
193    protected EvaluationCache(bool deserializing) : base(deserializing) { }
194    protected EvaluationCache(EvaluationCache original, Cloner cloner)
195        : base(original, cloner) {
196      SetCacheValues(original.GetCacheValues());
197      Hits = original.Hits;
198      RegisterEvents();
199    }
200    public EvaluationCache() {
201      list = new LinkedList<CacheEntry>();
202      index = new Dictionary<CacheEntry, LinkedListNode<CacheEntry>>();
203      Parameters.Add(new FixedValueParameter<IntValue>("Capacity", "Maximum number of cache entries.", new IntValue(10000)));
204      Parameters.Add(new FixedValueParameter<BoolValue>("PersistentCache", "Save cache when serializing object graph?", new BoolValue(false)));
205      RegisterEvents();
206    }
207    public override IDeepCloneable Clone(Cloner cloner) {
208      return new EvaluationCache(this, cloner);
209    }
210    #endregion
211
212    #region Event Handling
213    private void RegisterEvents() {
214      CapacityParameter.Value.ValueChanged += new EventHandler(CapacityChanged);
215    }
216
217    void CapacityChanged(object sender, EventArgs e) {
218      if (Capacity < 0)
219        throw new ArgumentOutOfRangeException("Cache capacity cannot be less than zero");
220      lock (cacheLock)
221        Trim();
222      OnChanged();
223    }
224    #endregion
225
226    #region Methods
227    public void Reset() {
228      lock (cacheLock) {
229        list = new LinkedList<CacheEntry>();
230        index = new Dictionary<CacheEntry, LinkedListNode<CacheEntry>>();
231        Hits = 0;
232      }
233      OnChanged();
234    }
235
236    public QualityMessage GetValue(SolutionMessage message, Evaluator evaluate, ExtensionRegistry extensions) {
237      var entry = new CacheEntry(message.ToString());
238      bool lockTaken = false;
239      bool waited = false;
240      try {
241        Monitor.Enter(cacheLock, ref lockTaken);
242        while (true) {
243          LinkedListNode<CacheEntry> node;
244          if (index.TryGetValue(entry, out node)) {
245            list.Remove(node);
246            list.AddLast(node);
247            Hits++;
248            lockTaken = false;
249            Monitor.Exit(cacheLock);
250            OnChanged();
251            return node.Value.GetMessage(extensions);
252          } else {
253            if (!waited && activeEvaluations.Contains(entry.Key)) {
254              while (activeEvaluations.Contains(entry.Key))
255                Monitor.Wait(cacheLock);
256              waited = true;
257            } else {
258              activeEvaluations.Add(entry.Key);
259              lockTaken = false;
260              Monitor.Exit(cacheLock);
261              OnChanged();
262              try {
263                entry.SetMessage(evaluate(message));
264                Monitor.Enter(cacheLock, ref lockTaken);
265                index[entry] = list.AddLast(entry);
266                Trim();
267              } finally {
268                if (!lockTaken)
269                  Monitor.Enter(cacheLock, ref lockTaken);
270                activeEvaluations.Remove(entry.Key);
271                Monitor.PulseAll(cacheLock);
272                lockTaken = false;
273                Monitor.Exit(cacheLock);
274              }
275              OnChanged();
276              return entry.GetMessage(extensions);
277            }
278          }
279        }
280      } finally {
281        if (lockTaken)
282          Monitor.Exit(cacheLock);
283      }
284    }
285
286    private void Trim() {
287      while (list.Count > Capacity) {
288        var item = list.First;
289        list.Remove(item);
290        index.Remove(item.Value);
291      }
292    }
293
294    private IEnumerable<KeyValuePair<string, byte[]>> GetCacheValues() {
295      lock (cacheLock) {
296        return index.ToDictionary(kvp => kvp.Key.Key, kvp => kvp.Key.RawMessage);
297      }
298    }
299
300    private void SetCacheValues(IEnumerable<KeyValuePair<string, byte[]>> value) {
301      lock (cacheLock) {
302        if (list == null) list = new LinkedList<CacheEntry>();
303        if (index == null) index = new Dictionary<CacheEntry, LinkedListNode<CacheEntry>>();
304        foreach (var kvp in value) {
305          var entry = new CacheEntry(kvp.Key) { RawMessage = kvp.Value };
306          index[entry] = list.AddLast(entry);
307        }
308      }
309    }
310
311    public void Save(string filename) {
312      using (var writer = new StreamWriter(filename)) {
313        lock (cacheLock) {
314          foreach (var entry in list) {
315            writer.WriteLine(string.Format(CultureInfo.InvariantCulture,
316              "\"{0}\", {1}",
317              Regex.Replace(entry.Key, "\\s", "").Replace("\"", "\"\""),
318              entry.QualityString(CultureInfo.InvariantCulture)));
319          }
320        }
321        writer.Close();
322      }
323    }
324    #endregion
325  }
326}
Note: See TracBrowser for help on using the repository browser.