SubScopeSorter is not using a stable sort

[mkommend]

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

[svonolfe]

Material can be found here:

• ​http://msdn.microsoft.com/en-us/library/vstudio/hh507838.aspx
• ​http://msdn.microsoft.com/en-us/library/vstudio/dd293547.aspx
• ​http://msdn.microsoft.com/en-us/library/vstudio/jj155802.aspx

Tested already:

• Changing to SequentialEngine also produces the error, a parallelization issue is thus ruled out

[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.

[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

[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

[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.

[abeham]

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

[gkronber]

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

[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.

[gkronber]

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.

[gkronber]

All other unit tests pass on the builder.

[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.

[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.

[gkronber]

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

[abeham]

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

[gkronber]

Reviewed changes in r10787.

[abeham]

r10864: merged r10324, r10477, r10787 to stable