Bug 25742 - Bad performance of in-place quicksort
Summary: Bad performance of in-place quicksort
Status: VERIFIED ANSWERED
Alias: None
Product: Runtime
Classification: Mono
Component: General ()
Version: unspecified
Hardware: Other Mac OS
: --- normal
Target Milestone: ---
Assignee: Bugzilla
URL:
Depends on:
Blocks:
 
Reported: 2015-01-06 09:16 UTC by timm
Modified: 2015-01-06 09:50 UTC (History)
3 users (show)

Tags:
Is this bug a regression?: ---
Last known good build:

Notice (2018-05-24): bugzilla.xamarin.com is now in read-only mode.

Please join us on Visual Studio Developer Community and in the Xamarin and Mono organizations on GitHub to continue tracking issues. Bugzilla will remain available for reference in read-only mode. We will continue to work on open Bugzilla bugs, copy them to the new locations as needed for follow-up, and add the new items under Related Links.

Our sincere thanks to everyone who has contributed on this bug tracker over the years. Thanks also for your understanding as we make these adjustments and improvements for the future.


Please create a new report on GitHub or Developer Community with your current version information, steps to reproduce, and relevant error messages or log files if you are hitting an issue that looks similar to this resolved bug and you do not yet see a matching new report.

Related Links:
Status:
VERIFIED ANSWERED

Description timm 2015-01-06 09:16:53 UTC
Tl;dr
Implementation of in-place quicksort on xamarin performs about 2x slower compared to objective-c implementation.

Software:
Xamarin Studio 5.5.4 (build 15)
Mono 3.10.0
Xam.iOS 8.4.0.47
Xcode 6.1

Hardware:
Tested on iOS 8.1.2, iPhone 6, Xamarin.Forms Project and native iOS Project

10000 Objects of type Person get sorted by secondname.
Code:
-------- C#
public class Person : IComparable
{
	public String firstname { get; set; }
	public String secondname { get; set; }
	public Adress adress { get; set; }
	public String mobile { get; set; }
	public String mail { get; set; }

	public Person ()
	{
	}

	public int CompareTo(Object other)
	{
		return this.secondname.CompareTo(((Person)other).secondname);
	}
}

public double quickSortPersons()
{
	Stopwatch sw = new Stopwatch ();
	this.personsQuickSorted = new ArrayList(persons); // gets copied from previous arraylist
	sw.Start ();
	quickSort (this.personsQuickSorted, 0, this.personsQuickSorted.Count-1);
	sw.Stop ();
	return sw.ElapsedMilliseconds; //about 260ms 
}
private void quickSort(ArrayList field, int first, int last) 
{
	Person pivotPerson = (Person)field [(first + last) / 2];
	int l = first;
	int r = last;

	while (l < r) {
		while (((Person)field [l]).CompareTo (pivotPerson) < 0) { ++l; }
		while (((Person)field [r]).CompareTo (pivotPerson) > 0) { --r; }
		if (l <= r) {
			if (l != r) {
				Person tmp = (Person)field [l];
				field [l] = field [r];
				field [r] = tmp;
			}
			l++; r--;
		}
	}

	if (first < r) {
		quickSort (field, first, r);
	}
	if (last > l) {
		quickSort (field, l, last);
	}
}

-------- ObjC
@implementation Person

- (NSComparisonResult)compare:(Person *)otherObject {
  return [self.secondname compare:otherObject.secondname];
}

-(id) copyWithZone: (NSZone *) zone
{
  Person *copy = [[Person allocWithZone: zone] init];
  
  [copy setFirstname: self.firstname];
  [copy setAdress: self.adress];
  [copy setMail: self.mail];
  [copy setMobile: self.mobile];
  
  return copy;
}
@end
- (double)quickSortPersons
{
  self.personsQuickSorted = [self.persons mutableCopy];
  NSDate *now = [NSDate date];
  [self quickSort: self.personsQuickSorted leftIndex:0 rightIndex:self.personsQuickSorted.count-1];
  NSDate *then = [NSDate date];
  return [then timeIntervalSinceDate:now] *1000; // about 120ms
}

-(void)quickSort:(NSMutableArray *)unsortedDataArray leftIndex:(NSInteger)first rightIndex:(NSInteger) last
{
  NSInteger l = first;
  NSInteger r = last;
  Person *pivotPerson = [unsortedDataArray objectAtIndex: (first + last)/2];
  
  while (l < r) {
    while ([((Person *)[unsortedDataArray objectAtIndex:l]) compare:pivotPerson] < 0) {
      ++l;
    }
    
    while ([((Person *)[unsortedDataArray objectAtIndex:r]) compare:pivotPerson] > 0) {
      --r;
    }
    if (l <= r) {
      if(l != r) { // dont need to switch object wiht itself
        Person *tmp = [unsortedDataArray objectAtIndex:l];
        [unsortedDataArray replaceObjectAtIndex:l withObject: [unsortedDataArray objectAtIndex:r]];
        [unsortedDataArray replaceObjectAtIndex:r withObject: tmp];
      }
      ++l; --r;
    }
  }
  
  if (first < r) {
    [self quickSort:unsortedDataArray leftIndex:first rightIndex:r];
  }
  if (last > l) {
    [self quickSort:unsortedDataArray leftIndex:l rightIndex:last];
  }
}
Comment 1 Rolf Bjarne Kvinge [MSFT] 2015-01-06 09:34:57 UTC
Don't use string.CompareTo, it does a culture-sensitive comparison, which is slow (it's also not what NSString's compare: does).

Use string.Compare (str1, str2, StringComparison.Ordinal) instead.
Comment 2 timm 2015-01-06 09:50:04 UTC
holy... 
c# now down to 15ms...

wasn't aware of this. thank you very much!