[Mono-devel-list] [Patch] Array.Sort

[Ben Maurer]

On Wed, 2005-03-02 at 16:06 -0600, Carlos Alberto Cortez wrote:
> Attached is a patch for implementing Array.Sort generic methods. Could
> somebody review it?

There is one major risk to these patches:

Array.Sort <T> will be a better binding than Array.Sort. This means that
people will automatically be using the generic version.

Comparer<T> looks like:

> 			public override int Compare (T x, T y)
> 			{
> 				// `null' is less than any other ref type
> 				if (x == null)
> 					return y == null ? 0 : -1;
> 				else if (y == null)
> 					return 1;
> 	
> 				if (x is IComparable<T>)
> 					return ((IComparable<T>) x).CompareTo (y);
> 				else if (x is IComparable)
> 					return ((IComparable) x).CompareTo (y);
> 				else
> 					throw new ArgumentException ("does not implement right interface");
> 			}


So, that is really bad for perf. We need to figure out a faster way to do that.

Some specific comments:


+                       IComparer<K> comp = comparer != null ? comparer : Comparer<K>.Default;
+                       Comparison<K> comparison = (Comparison<K>) Delegate.CreateDelegate (typeof (Comparison<K>), comp, "Compare");

Let's not do reflection on Sort. I would just have a version for comparison and one for comparer.

+                       //
+                       // Check for value types which can be sorted without Compare () method
+                       //
+                       if (default (K) != null) {
+                               Swapper iswapper;
+                               if (items == null)
+                                       iswapper = null;
+                               else 
+                                       iswapper = get_swapper (items);
+                               if (keys is double[]) {
+                                       combsort (keys as double[], index, length, iswapper);
+                                       return;
+                               }
+                               if (keys is int[]) {
+                                       combsort (keys as int[], index, length, iswapper);
+                                       return;
+                               }
+                               if (keys is char[]) {
+                                       combsort (keys as char[], index, length, iswapper);
+                                       return;
+                               }
+                       }

This is pretty hackish. Is there any way other than default (K) != null?
Or is this just a new generic idiom?

Also, the comparison is wrong in the case where comparison is something
other than the default.

Here is what I think we should do:


1) pass null for the comparison if it is the default (or even better,
this should be a method that takes Comparer<T>

2)
if (comparison == null && keys is IComparable<T>) {
	my_quick_sort (...)
}

Where my_quick_sort calls keys.Compare <T>. For value types, the
comparison should be able to get inlined.

-- Ben