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

[Carlos Alberto Cortez]

Hello Ben,

Comments inline:

El mié, 02-03-2005 a las 17:25 -0500, Ben Maurer escribió:
> 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.

All right.

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

I had the same feeling, but decided to have the same method for both of
them. We can have a qsort for each of them, however. 

> +                       //
> +                       // 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.

Sorry, I sent an older version ;-), this error is corrected in my last
patch version.

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

I will take a look at those cases, to find out that best way.

Carlos.