title: Simple caching makes GC go crazy?
body: <p>I'm using C# 3.5 and VS 2010 ultimate.</p>
  
  <p>I'm optimizing (for speed) a machine learning algorithm that has four nested for-loops.
  I've found that a simple cache (a tensor of objects) could potentially greatly improve the performance, because there's a lot of re-allocating of the same objects.</p>
  
  <p>Here's the before and after implementations.</p>
  
  <p>Before:</p>
  
  <pre><code>four nested for-loops:
     var object = new object(3 parameters);
     Calculate(object, other params)
  </code></pre>
  
  <p>After:</p>
  
  <pre><code>var cache = new object[count1,count2,count3];
  three nested for-loops:
     cache[param1, param2, param3] = new object(3 params);
  
  four nested for-loops:
     var object = cache[3 parameters];
     Calculate(object, other params)
  </code></pre>
  
  <p>I've profiled both methods and the "before" version was quite faster with ~18% time spent in GC, while the "after" version spend ~88% in GC.
  It's obvious that the addition of this cache made the GC activity rise, but I'm failing to see how this is possible. </p>
  
  <p>I am using many long-lived object in the application. My machine wasn't under heavy load at the time of profiling. The tensor was implemented using multi-dimensional array (not jagged arrays). The inner-most loop in both methods above is implemented using the <code>Parallel.For</code> construct, where right before the loop I am allocating a small <code>double</code> array.</p>
  
  <p>How can I reduce the time spent in GC? </p>
  
  <p>EDIT #1: The results are indeed from Release mode.</p>
  
  <p>EDIT #2: Real code of the after method's four for-loop:</p>
  
  <pre><code>List&lt;int&gt; labels = // count = 80
  List&lt;int&gt; tokens = // count = 35
  
  var table = new double[tokens.Count, labels.Count, labels.Count];
  var cachedObjects = new CachedObject[tokens.Count, labels.Count, labels.Count];
  for (int k = 0; k &lt; tokens.Count; k++)
  {
      foreach (var tagCurrent in labels) 
      {
          foreach (var labelBack in labels)
          {
              double[] value = new double[labels.Count];
              Parallel.For(0, labels.Count, (i) =&gt; 
              {
                  CachedObject CachedObject = cachedObjects[k, labelsBackFurther[i], labelBack];
  
                  var me = ModelEstimate(vOptimal, CachedObject, tagCurrent, labels);
                  value[i] = table[k - 1, labels[i], labelBack] * me;
              }); 
  
              var maxValue = 0;
              var maxTagIdx = 0;
              for (int j = 0; j &lt; value.Length; j++)
              {
                  var item = value[j];
                  if (item &gt; maxValue)
                  {
                      maxValue = item;
                      maxTagIdx = j;
                  }
              }
  
              table[k, labelBack, tagCurrent] = maxValue;
          }
      }
  }
  </code></pre>