Changeset 6169


Ignore:
Timestamp:
05/09/11 16:49:26 (10 years ago)
Author:
epitzer
Message:

Add maximum capacity parameter and a least recently used replacement strategy to the evaluation cache (#1516)

Location:
trunk/sources
Files:
5 edited

Legend:

Unmodified
Added
Removed
  • trunk/sources/HeuristicLab.Problems.ExternalEvaluation.Views/3.3/EvaluationCacheView.Designer.cs

    r6140 r6169  
    1 namespace HeuristicLab.Problems.ExternalEvaluation {
     1namespace HeuristicLab.Problems.ExternalEvaluation.Views {
    22  partial class EvaluationCacheView {
    3     /// <summary>
     3    /// <summary> 
    44    /// Required designer variable.
    55    /// </summary>
    66    private System.ComponentModel.IContainer components = null;
    77
    8     /// <summary>
     8    /// <summary> 
    99    /// Clean up any resources being used.
    1010    /// </summary>
     
    1717    }
    1818
    19     #region Windows Form Designer generated code
     19    #region Component Designer generated code
    2020
    21     /// <summary>
    22     /// Required method for Designer support - do not modify
     21    /// <summary> 
     22    /// Required method for Designer support - do not modify 
    2323    /// the contents of this method with the code editor.
    2424    /// </summary>
    2525    private void InitializeComponent() {
    26       this.sizeLabel = new System.Windows.Forms.Label();
    27       this.sizeTextBox = new System.Windows.Forms.TextBox();
    28       this.hitsTextBox = new System.Windows.Forms.TextBox();
    29       this.hitsLabel = new System.Windows.Forms.Label();
     26      this.hits_sizeLabel = new System.Windows.Forms.Label();
     27      this.hits_sizeTextBox = new System.Windows.Forms.TextBox();
    3028      this.clearButton = new System.Windows.Forms.Button();
    3129      ((System.ComponentModel.ISupportInitialize)(this.errorProvider)).BeginInit();
    3230      this.SuspendLayout();
     31      //
     32      // parameterCollectionView
     33      //
     34      this.parameterCollectionView.Location = new System.Drawing.Point(0, 52);
     35      this.parameterCollectionView.Size = new System.Drawing.Size(490, 301);
    3336      //
    3437      // nameTextBox
     
    3740      this.errorProvider.SetIconPadding(this.nameTextBox, 2);
    3841      //
    39       // sizeLabel
     42      // hits_sizeLabel
    4043      //
    41       this.sizeLabel.AutoSize = true;
    42       this.sizeLabel.Location = new System.Drawing.Point(6, 30);
    43       this.sizeLabel.Name = "sizeLabel";
    44       this.sizeLabel.Size = new System.Drawing.Size(30, 13);
    45       this.sizeLabel.TabIndex = 3;
    46       this.sizeLabel.Text = "Size:";
     44      this.hits_sizeLabel.AutoSize = true;
     45      this.hits_sizeLabel.Location = new System.Drawing.Point(3, 29);
     46      this.hits_sizeLabel.Name = "hits_sizeLabel";
     47      this.hits_sizeLabel.Size = new System.Drawing.Size(53, 13);
     48      this.hits_sizeLabel.TabIndex = 4;
     49      this.hits_sizeLabel.Text = "Hits/Size:";
    4750      //
    48       // sizeTextBox
     51      // hits_sizeTextBox
    4952      //
    50       this.sizeTextBox.Anchor = ((System.Windows.Forms.AnchorStyles)(((System.Windows.Forms.AnchorStyles.Top | System.Windows.Forms.AnchorStyles.Left)
     53      this.hits_sizeTextBox.Anchor = ((System.Windows.Forms.AnchorStyles)(((System.Windows.Forms.AnchorStyles.Top | System.Windows.Forms.AnchorStyles.Left)
    5154            | System.Windows.Forms.AnchorStyles.Right)));
    52       this.sizeTextBox.Location = new System.Drawing.Point(58, 27);
    53       this.sizeTextBox.Name = "sizeTextBox";
    54       this.sizeTextBox.ReadOnly = true;
    55       this.sizeTextBox.Size = new System.Drawing.Size(290, 20);
    56       this.sizeTextBox.TabIndex = 4;
    57       //
    58       // hitsTextBox
    59       //
    60       this.hitsTextBox.Anchor = ((System.Windows.Forms.AnchorStyles)(((System.Windows.Forms.AnchorStyles.Top | System.Windows.Forms.AnchorStyles.Left)
    61             | System.Windows.Forms.AnchorStyles.Right)));
    62       this.hitsTextBox.Location = new System.Drawing.Point(58, 54);
    63       this.hitsTextBox.Name = "hitsTextBox";
    64       this.hitsTextBox.ReadOnly = true;
    65       this.hitsTextBox.Size = new System.Drawing.Size(290, 20);
    66       this.hitsTextBox.TabIndex = 5;
    67       //
    68       // hitsLabel
    69       //
    70       this.hitsLabel.AutoSize = true;
    71       this.hitsLabel.Location = new System.Drawing.Point(6, 57);
    72       this.hitsLabel.Name = "hitsLabel";
    73       this.hitsLabel.Size = new System.Drawing.Size(28, 13);
    74       this.hitsLabel.TabIndex = 6;
    75       this.hitsLabel.Text = "Hits:";
     55      this.hits_sizeTextBox.Location = new System.Drawing.Point(59, 26);
     56      this.hits_sizeTextBox.Name = "hits_sizeTextBox";
     57      this.hits_sizeTextBox.ReadOnly = true;
     58      this.hits_sizeTextBox.Size = new System.Drawing.Size(379, 20);
     59      this.hits_sizeTextBox.TabIndex = 5;
    7660      //
    7761      // clearButton
    7862      //
    7963      this.clearButton.Anchor = ((System.Windows.Forms.AnchorStyles)((System.Windows.Forms.AnchorStyles.Top | System.Windows.Forms.AnchorStyles.Right)));
    80       this.clearButton.Location = new System.Drawing.Point(273, 80);
     64      this.clearButton.Location = new System.Drawing.Point(444, 24);
    8165      this.clearButton.Name = "clearButton";
    82       this.clearButton.Size = new System.Drawing.Size(75, 23);
    83       this.clearButton.TabIndex = 7;
     66      this.clearButton.Size = new System.Drawing.Size(43, 23);
     67      this.clearButton.TabIndex = 6;
    8468      this.clearButton.Text = "Clear";
     69      this.toolTip.SetToolTip(this.clearButton, "Clear");
    8570      this.clearButton.UseVisualStyleBackColor = true;
    8671      this.clearButton.Click += new System.EventHandler(this.clearButton_Click);
     
    8974      //
    9075      this.AutoScaleDimensions = new System.Drawing.SizeF(6F, 13F);
    91       this.Controls.Add(this.hitsTextBox);
    92       this.Controls.Add(this.sizeTextBox);
    93       this.Controls.Add(this.sizeLabel);
     76      this.AutoScaleMode = System.Windows.Forms.AutoScaleMode.Font;
     77      this.Controls.Add(this.hits_sizeTextBox);
     78      this.Controls.Add(this.hits_sizeLabel);
    9479      this.Controls.Add(this.clearButton);
    95       this.Controls.Add(this.hitsLabel);
    9680      this.Name = "EvaluationCacheView";
    97       this.Size = new System.Drawing.Size(351, 107);
    98       this.Controls.SetChildIndex(this.hitsLabel, 0);
    9981      this.Controls.SetChildIndex(this.clearButton, 0);
    100       this.Controls.SetChildIndex(this.sizeLabel, 0);
    101       this.Controls.SetChildIndex(this.sizeTextBox, 0);
    102       this.Controls.SetChildIndex(this.hitsTextBox, 0);
     82      this.Controls.SetChildIndex(this.hits_sizeLabel, 0);
     83      this.Controls.SetChildIndex(this.hits_sizeTextBox, 0);
     84      this.Controls.SetChildIndex(this.infoLabel, 0);
     85      this.Controls.SetChildIndex(this.nameTextBox, 0);
    10386      this.Controls.SetChildIndex(this.nameLabel, 0);
    104       this.Controls.SetChildIndex(this.nameTextBox, 0);
    105       this.Controls.SetChildIndex(this.infoLabel, 0);
     87      this.Controls.SetChildIndex(this.parameterCollectionView, 0);
    10688      ((System.ComponentModel.ISupportInitialize)(this.errorProvider)).EndInit();
    10789      this.ResumeLayout(false);
     
    11294    #endregion
    11395
    114     private System.Windows.Forms.Label sizeLabel;
    115     private System.Windows.Forms.TextBox sizeTextBox;
    116     private System.Windows.Forms.TextBox hitsTextBox;
    117     private System.Windows.Forms.Label hitsLabel;
     96    private System.Windows.Forms.Label hits_sizeLabel;
     97    private System.Windows.Forms.TextBox hits_sizeTextBox;
    11898    private System.Windows.Forms.Button clearButton;
    11999  }
  • trunk/sources/HeuristicLab.Problems.ExternalEvaluation.Views/3.3/EvaluationCacheView.cs

    r6140 r6169  
    1 
     1using System;
     2using System.Windows.Forms;
    23using HeuristicLab.Core.Views;
    34using HeuristicLab.MainForm;
    4 namespace HeuristicLab.Problems.ExternalEvaluation {
     5
     6namespace HeuristicLab.Problems.ExternalEvaluation.Views {
    57
    68  [View("EvaluationCacheView")]
    79  [Content(typeof(EvaluationCache), IsDefaultView = true)]
    8   public sealed partial class EvaluationCacheView : NamedItemView {
     10  public sealed partial class EvaluationCacheView : ParameterizedNamedItemView {
    911
    1012    public new EvaluationCache Content {
     
    1820
    1921    protected override void DeregisterContentEvents() {
    20       Content.CacheSizeChanged -= Content_CacheSizeChanged;
    21       Content.CacheHitsChanged -= Content_CacheHitsChanged;
     22      Content.SizeChanged -= new System.EventHandler(Content_StatusChanged);
     23      Content.HitsChanged -= new System.EventHandler(Content_StatusChanged);
    2224      base.DeregisterContentEvents();
    2325    }
     
    2527    protected override void RegisterContentEvents() {
    2628      base.RegisterContentEvents();
    27       Content.CacheSizeChanged += Content_CacheSizeChanged;
    28       Content.CacheHitsChanged += Content_CacheHitsChanged;
     29      Content.SizeChanged += new System.EventHandler(Content_StatusChanged);
     30      Content.HitsChanged += new System.EventHandler(Content_StatusChanged);
    2931    }
    3032
    31 
    3233    #region Event Handlers (Content)
    33     void Content_CacheSizeChanged(object sender, System.EventArgs e) {
    34       sizeTextBox.Text = Content.CacheSize.ToString();
     34    void Content_StatusChanged(object sender, EventArgs e) {
     35      if (InvokeRequired)
     36        Invoke(new EventHandler(Content_StatusChanged), sender, e);
     37      else
     38        hits_sizeTextBox.Text = string.Format("{0}/{1}", Content.Hits, Content.Size);
    3539    }
    3640
    37     void Content_CacheHitsChanged(object sender, System.EventArgs e) {
    38       hitsTextBox.Text = Content.CacheHits.ToString();
    39     }
    4041    #endregion
    4142
     
    4344      base.OnContentChanged();
    4445      if (Content == null) {
    45         sizeTextBox.Text = "";
    46         hitsTextBox.Text = "";
     46        hits_sizeTextBox.Text = "#/#";
    4747      } else {
    48         sizeTextBox.Text = Content.CacheSize.ToString();
    49         hitsTextBox.Text = Content.CacheHits.ToString();
     48        Content_StatusChanged(this, EventArgs.Empty);
    5049      }
    5150    }
     
    5756
    5857    #region Event Handlers (child controls)
    59     private void clearButton_Click(object sender, System.EventArgs e) {
     58    private void clearButton_Click(object sender, EventArgs e) {
    6059      Content.Reset();
    6160    }
    6261    #endregion
    6362  }
    64 
    6563}
  • trunk/sources/HeuristicLab.Problems.ExternalEvaluation.Views/3.3/EvaluationCacheView.resx

    r6140 r6169  
    121121    <value>107, 17</value>
    122122  </metadata>
     123  <metadata name="errorProvider.TrayLocation" type="System.Drawing.Point, System.Drawing, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b03f5f7f11d50a3a">
     124    <value>107, 17</value>
     125  </metadata>
    123126  <metadata name="toolTip.TrayLocation" type="System.Drawing.Point, System.Drawing, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b03f5f7f11d50a3a">
    124127    <value>17, 17</value>
  • trunk/sources/HeuristicLab.Problems.ExternalEvaluation/3.3/CachedExternalEvaluator.cs

    r6140 r6169  
    4343      set { CacheParameter.Value = value; }
    4444    }
    45     public DoubleValue Quality {
     45    protected DoubleValue Quality {
    4646      get { return QualityParameter.ActualValue; }
    4747      set { QualityParameter.ActualValue = value; }
    4848    }
    49     public IEvaluationServiceClient Client {
     49    protected IEvaluationServiceClient Client {
    5050      get { return ClientParameter.ActualValue; }
    5151    }
  • trunk/sources/HeuristicLab.Problems.ExternalEvaluation/3.3/EvaluationCache.cs

    r6140 r6169  
    1717 * You should have received a copy of the GNU General Public License
    1818 * 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>.
    1922 */
    2023#endregion
    21 
    2224
    2325using System;
     
    2729using HeuristicLab.Common.Resources;
    2830using HeuristicLab.Core;
     31using HeuristicLab.Data;
     32using HeuristicLab.Parameters;
    2933using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    3034namespace HeuristicLab.Problems.ExternalEvaluation {
     
    3236  [Item("EvaluationCache", "Cache for external evaluation values")]
    3337  [StorableClass]
    34   public class EvaluationCache : NamedItem {
     38  public class EvaluationCache : ParameterizedNamedItem {
     39
     40    #region Types
     41    private class CacheEntry {
     42
     43      public string Key { get; private set; }
     44      public double Value { get; set; }
     45
     46      public CacheEntry(string key, double value) {
     47        Key = key;
     48        Value = value;
     49      }
     50
     51      public CacheEntry(string key) : this(key, 0) { }
     52
     53      public override bool Equals(object obj) {
     54        CacheEntry other = obj as CacheEntry;
     55        if (other == null)
     56          return false;
     57        return Key.Equals(other.Key);
     58      }
     59
     60      public override int GetHashCode() {
     61        return Key.GetHashCode();
     62      }
     63
     64      public override string ToString() {
     65        return string.Format("{{{0} : {1}}}", Key, Value);
     66      }
     67    }
    3568
    3669    public delegate double Evaluator(SolutionMessage message);
    37 
     70    #endregion
     71
     72    #region Fields
     73    private LinkedList<CacheEntry> list;
     74    private Dictionary<CacheEntry, LinkedListNode<CacheEntry>> index;
     75    #endregion
     76
     77    #region Properties
    3878    public override System.Drawing.Image ItemImage {
    3979      get { return VSImageLibrary.Database; }
    4080    }
    41 
    42     #region Fields & Properties
     81    public int Size {
     82      get { return index.Count; }
     83    }
    4384    [Storable]
    44     private Dictionary<string, double> cache;
    45 
    46     [Storable]
    47     private int cacheHits;
    48 
    49     public int CacheSize { get { return cache.Count; } }
    50 
    51     public int CacheHits { get { return cacheHits; } }
    52     #endregion
    53 
    54     #region Events
    55     public event EventHandler CacheSizeChanged;
    56     public event EventHandler CacheHitsChanged;
    57 
    58     protected virtual void OnCacheSizeChanged() {
    59       EventHandler handler = CacheSizeChanged;
     85    public int Hits { get; private set; }
     86    #endregion
     87
     88    #region events
     89    public event EventHandler SizeChanged;
     90    public event EventHandler HitsChanged;
     91
     92    protected virtual void OnSizeChanged() {
     93      EventHandler handler = SizeChanged;
    6094      if (handler != null)
    6195        handler(this, EventArgs.Empty);
    6296    }
    63 
    64     protected virtual void OnCacheHitsChanged() {
    65       EventHandler handler = CacheHitsChanged;
     97    protected virtual void OnHitsChanged() {
     98      EventHandler handler = HitsChanged;
    6699      if (handler != null)
    67100        handler(this, EventArgs.Empty);
     
    69102    #endregion
    70103
    71 
     104    #region Parameters
     105    public FixedValueParameter<IntValue> CapacityParameter {
     106      get { return (FixedValueParameter<IntValue>)Parameters["Capacity"]; }
     107    }
     108    #endregion
     109
     110    #region Parameter Values
     111    public int Capacity {
     112      get { return CapacityParameter.Value.Value; }
     113      set { CapacityParameter.Value.Value = value; }
     114    }
     115    #endregion
     116
     117    #region Persistence
     118    [Storable(Name="Cache")]
     119    private IEnumerable<KeyValuePair<string, double>> Cache_Persistence {
     120      get {
     121        return index.ToDictionary(kvp => kvp.Key.Key, kvp => kvp.Key.Value);
     122      }
     123      set {
     124        list = new LinkedList<CacheEntry>();
     125        index = new Dictionary<CacheEntry, LinkedListNode<CacheEntry>>();
     126        foreach (var kvp in value) {
     127          var entry = new CacheEntry(kvp.Key);
     128          entry.Value = kvp.Value;
     129          index[entry] = list.AddLast(entry);
     130        }
     131      }
     132    }
     133    [StorableHook(HookType.AfterDeserialization)]
     134    private void AfterDeserialization() {
     135      RegisterEvents();
     136    }
     137    #endregion
    72138
    73139    #region Construction & Cloning
     
    76142    protected EvaluationCache(EvaluationCache original, Cloner cloner)
    77143      : base(original, cloner) {
    78       cache = original.cache.ToDictionary(kvp => kvp.Key, kvp => kvp.Value);
     144      Cache_Persistence = original.Cache_Persistence;
     145      RegisterEvents();
    79146    }
    80147    public EvaluationCache() {
    81       cache = new Dictionary<string, double>();
     148      list = new LinkedList<CacheEntry>();
     149      index = new Dictionary<CacheEntry, LinkedListNode<CacheEntry>>();
     150      Parameters.Add(new FixedValueParameter<IntValue>("Capacity", "Maximum number of cache entries.", new IntValue(10000)));
     151      RegisterEvents();
    82152    }
    83153    public override IDeepCloneable Clone(Cloner cloner) {
     
    86156    #endregion
    87157
     158    #region Event Handling
     159    private void RegisterEvents() {
     160      CapacityParameter.Value.ValueChanged += new EventHandler(Value_ValueChanged);
     161    }
     162
     163    void Value_ValueChanged(object sender, EventArgs e) {
     164      if (Capacity < 0)
     165        throw new ArgumentOutOfRangeException("Cache capacity cannot be less than zero");
     166      Trim();
     167    }
     168    #endregion
     169
     170    #region Methods
     171    public void Reset() {
     172      list = new LinkedList<CacheEntry>();
     173      index = new Dictionary<CacheEntry, LinkedListNode<CacheEntry>>();
     174      Hits = 0;
     175      OnSizeChanged();
     176      OnHitsChanged();
     177    }
     178
    88179    public double GetValue(SolutionMessage message, Evaluator evaluate) {
    89       string s = message.ToString();
    90       double value;
    91       if (cache.TryGetValue(s, out value)) {
    92         cacheHits++;
    93         OnCacheHitsChanged();
     180      CacheEntry entry = new CacheEntry(message.ToString());
     181      LinkedListNode<CacheEntry> node;
     182      if (index.TryGetValue(entry, out node)) {
     183        list.Remove(node);
     184        list.AddLast(node);
     185        Hits++;
     186        OnHitsChanged();
     187        return node.Value.Value;
    94188      } else {
    95         value = evaluate(message);
    96         cache[s] = value;
    97         OnCacheSizeChanged();
    98       }
    99       return value;
    100     }
    101 
    102     public void Reset() {
    103       cache = new Dictionary<string, double>();
    104       OnCacheSizeChanged();
    105       cacheHits = 0;
    106       OnCacheHitsChanged();
    107     }
     189        entry.Value = evaluate(message);
     190        index[entry] = list.AddLast(entry);
     191        Trim();
     192        return entry.Value;
     193      }
     194    }
     195
     196    private void Trim() {
     197      while (list.Count > Capacity) {
     198        LinkedListNode<CacheEntry> item = list.First;
     199        list.Remove(item);
     200        index.Remove(item.Value);
     201      }
     202      OnSizeChanged();
     203    }
     204    #endregion
     205
    108206  }
    109207}
Note: See TracChangeset for help on using the changeset viewer.