Opened 2 years ago

Closed 2 years ago

#2381 closed defect (invalid)

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

Reported by: gkronber Owned by: gkronber
Priority: high Milestone: HeuristicLab 3.3.12
Component: Common Version: 3.3.11
Keywords: Cc:

Description (last modified by 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).

Change History (7)

comment:1 Changed 2 years ago by gkronber

  • Description modified (diff)

comment:2 Changed 2 years ago by 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

comment:3 Changed 2 years ago by 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);
    }
  }
}

comment:4 Changed 2 years ago by gkronber

  • Description modified (diff)

comment:5 Changed 2 years ago by gkronber

  • Owner set to architects
  • Status changed from new to assigned

comment:6 Changed 2 years ago by ascheibe

  • Owner changed from architects to gkronber

comment:7 Changed 2 years ago by gkronber

  • Resolution set to invalid
  • Status changed from assigned to closed
Note: See TracTickets for help on using tickets.