Opened 4 years ago

Closed 3 years ago

Last modified 3 years ago

#2106 closed defect (done)

SubScopeSorter is not using a stable sort

Reported by: mkommend Owned by: abeham
Priority: high Milestone: HeuristicLab 3.3.10
Component: Tests Version: 3.3.8
Keywords: Cc:

Description (last modified by abeham)

Currently both tabu search sample unit test (VRP & TSP) fail and hence the stable binaries are not created. If have taken a quick look at this issue and found out the in the VS2012 testing environment the achieved best, average, and worst quality differ from the excepted values. Within the VS2010 testing environment and directly in HL the achieved and expected values match. As the genetic algorithm VRP & TSP sample unit test pass, I assume this has something to do with the tabu search itself.

Update: The sort was not stable

Attachments (2)

stablesort.patch (1.9 KB) - added by abeham 4 years ago.
TSTSPRuntime.PNG (20.1 KB) - added by abeham 3 years ago.

Download all attachments as: .zip

Change History (26)

comment:1 Changed 4 years ago by svonolfe

  • Description modified (diff)
  • Status changed from new to accepted

comment:2 Changed 4 years ago by svonolfe

Material can be found here:

Tested already:

  • Changing to SequentialEngine also produces the error, a parallelization issue is thus ruled out
  • Removed random operators and changed from MersenneTwister to FastRandom
Last edited 4 years ago by svonolfe (previous) (diff)

comment:3 Changed 4 years ago by mkommend

I muted the unit test in teamcity. This means the unit test are still executed, but do not affect the build status, if they fail. They are automatically unmuted, when the unit tests pass once.

comment:4 Changed 4 years ago by svonolfe

The unit test passes when running MSTest with the /noisolation switch. When omitting this switch, the unit test fails. This has to be further investigated.

  • on hive the algorithm executes correctly in the sandbox
  • when running with VSTest.Console.exe the test run passes, even if the /InIsolation switch is specified
Last edited 4 years ago by svonolfe (previous) (diff)

comment:5 Changed 4 years ago by svonolfe

In VisualStudio the test run passes when no Test Settings File is used. Whenever the TestRun.testrunconfig file is selected, the test run fails

comment:6 Changed 4 years ago by abeham

The problem is likely to be that the Tabu Search uses the SubScopeSorter which uses Array.Sort - an unstable sort and the GA uses OrderBy - a stable sort (by MSDN).

I created a patch that wraps the Comparison<T> into a TempComparer and replaced list.Sort with list = list.OrderBy(x => x, new TempComparer(comparison)).ToList(). I see that it returns 1473 as BestQuality in the tests (with or without testsettings enabled) and in the Optimizer.

I still can't explain this though.

Last edited 4 years ago by abeham (previous) (diff)

Changed 4 years ago by abeham

comment:7 Changed 4 years ago by abeham

Note that the patch is only for showing the effect and not meant as a fix for the problem.

comment:8 Changed 4 years ago by abeham

  • Owner changed from svonolfe to architects
  • Status changed from accepted to assigned

comment:9 Changed 4 years ago by ascheibe

  • Owner changed from architects to gkronber

comment:10 Changed 3 years ago by mkommend

  • Milestone changed from HeuristicLab 3.3.x Backlog to HeuristicLab 3.3.10

comment:11 Changed 3 years ago by gkronber

I recommend to make the Array.Sort() -> .OrderBy() change.

comment:12 Changed 3 years ago by gkronber

r10324: changed methods for sorting in ObservableArray and ObservableList to use a stable sort (via Enumerable.OrderBy()). This is implemented as extension methods in HeuristicLab.Common. This implementation requires additional memory O(n).

The unit tests for tabu search had to be updated as the stable sort changes the results of the sample.

comment:13 Changed 3 years ago by gkronber

  • Owner changed from gkronber to abeham
  • Status changed from assigned to reviewing

The unit tests for the GA-TSP, ES-Testfunction, and GP-Regression samples all pass. Hopefully, all other unit tests also pass in the nightly run.

We should check if the runtime of samples decreases because of the additional memory allocations before we release these changes to stable.

comment:14 Changed 3 years ago by gkronber

All other unit tests pass on the builder.

Changed 3 years ago by abeham

comment:15 Changed 3 years ago by abeham

It's difficult to say if this change caused performance to drop. The third dot from the right is the first execution after the changeset has been committed. The red line mark failed tests. I really wonder about the changes from 10s to 25s.

comment:16 Changed 3 years ago by abeham

Regarding changes in r10324: In ListExtensions.StableSort you clear the list before adding the sorted values. You do not add the values that were not sorted (index > 0).

The following code

var arr = new double[5] { 3, 4, 2, 5, 1 };
var list = new List<double>() { 3, 4, 2, 5, 1};
arr.StableSort(1, 3);
list.StableSort(1, 3);
Console.WriteLine("arr: " + string.Join(", ", arr));
Console.WriteLine("list: " + string.Join(", ", list));

returns

arr: 3, 2, 4, 5, 1
list: 2, 4, 5

In other overloads of ListExtensions.StableSort the index and count parameters are ignored. I think instead of Clear() and AddRange() you should use a for loop to copy the values. In my opinion it's better to only use the index operator when modifying the list.

comment:17 Changed 3 years ago by abeham

  • Owner changed from abeham to gkronber
  • Status changed from reviewing to assigned

comment:18 Changed 3 years ago by gkronber

  • Status changed from assigned to accepted

comment:19 Changed 3 years ago by gkronber

r10477: changed ListExtensions.StableSort to behave in the same way as ArrayExtensions.StableSort() as suggested in the review comments

comment:20 Changed 3 years ago by gkronber

  • Owner changed from gkronber to abeham
  • Status changed from accepted to reviewing

comment:21 Changed 3 years ago by abeham

  • Owner changed from abeham to gkronber

r10787: Changed StableSort extension methods:

  • Parameters index and count were ignored in List<T>.StableSort(int, int, Comparison<T>)
  • Made both StableSortComparer<T> private classes
  • Added sanity checks similar to those of Array.Sort and List<T>.Sort
    • Before it was possible that index + count was bigger than the size of the list
  • Reduced number of method overloads to 2 by introducing IComparer<T> as optional parameter

comment:22 Changed 3 years ago by gkronber

  • Owner changed from gkronber to abeham
  • Status changed from reviewing to readytorelease

Reviewed changes in r10787.

comment:23 Changed 3 years ago by abeham

  • Resolution set to done
  • Status changed from readytorelease to closed

r10864: merged r10324, r10477, r10787 to stable

comment:24 Changed 3 years ago by abeham

  • Description modified (diff)
  • Summary changed from TabuSearch unit tests fail to SubScopeSorter is not using a stable sort
Note: See TracTickets for help on using tickets.