Object-graph traversal does not finish in some cases / algorithm does not stop

[gkronber]

I observed a problem in the object graph traversal on several occasions.

The problem becomes apparent when an algorithm seemingly does not stop at the end of a run. The underlying issue seems to be the object graph traversal which seemingly terminates after a while with an error (which is not handled or displayed).

No run is produced, the algorithm is not set to state stopped, no thread is running.

This is related to traversal of structs (see below).

[gkronber]

Investigated this and found an interesting reason. The culprit was the way a hashcode is calculated for structs. The CLR default implementation can lead to a large number of collisions for the "objects"-HashSet in the object graph traversal which leads to very bad runtime performance.

​http://stackoverflow.com/questions/5926776/how-does-native-implementation-of-valuetype-gethashcode-work/5927853#5927853

[gkronber]

HL-Script to reproduce the problem:

using System;
using System.Linq;
using System.Collections.Generic;

using HeuristicLab.Core;
using HeuristicLab.Common;
using System.Diagnostics;

public class MyScript : HeuristicLab.Scripting.CSharpScriptBase {  
  public struct MyStruct {
    public int a;
    public int b;
    public string c;
    // default implementation of GetHashCode() for structs returns only the hash-code of field a
  }

  private MyStruct s;  
  private MyStruct[] sArr;
  
  public override void Main() {
    try {
      this.s = new MyStruct();
      this.sArr = new MyStruct[3000];
      
      // slow
      for(int i=0;i<sArr.Length;i++) {
        sArr[i].a = 1; // -> all elements have the same hash-code
        sArr[i].b = i;
        sArr[i].c = string.Empty;
      }
      var sw = new Stopwatch();
      sw.Start();
      var objects = HeuristicLab.Common.ObjectExtensions.GetObjectGraphObjects(sArr).ToArray();
      sw.Stop();
      Console.WriteLine("{0}", objects.Length);
      Console.WriteLine("{0}", sw.Elapsed);

      // fast 
      for(int i=0;i<sArr.Length;i++) {
        sArr[i].a = i; // -> all elements have a different hash-code
        sArr[i].b = 1;
        sArr[i].c = string.Empty;
      }
      sw.Reset();
      sw.Start();
      objects = HeuristicLab.Common.ObjectExtensions.GetObjectGraphObjects(sArr).ToArray();
      sw.Stop();
      Console.WriteLine("{0}", objects.Length);
      Console.WriteLine("{0}", sw.Elapsed);

      Console.WriteLine("Done");
    } catch(Exception e) {
      Console.WriteLine(e.Message);
    }
  }
}