[Mono-bugs] [Bug 351638] Most Array.Sort<T>() overloads call Array.Sort<K, V>() to get their work done

[bugzilla_noreply at novell.com]

https://bugzilla.novell.com/show_bug.cgi?id=351638

User juraj at hotfeet.ch added comment
https://bugzilla.novell.com/show_bug.cgi?id=351638#c2





--- Comment #2 from Juraj Skripsky <juraj at hotfeet.ch>  2008-03-04 07:40:32 MST ---
Created an attachment (id=198530)
 --> (https://bugzilla.novell.com/attachment.cgi?id=198530)
patch implementing proper argument checking and performance enhancements

The attached patch implements proper argument checking and various performance
enhancements. Using qsort<K,V> methods for Sort<T> turned out not to be a
bottleneck. Instead the inner-most loops in qsort had to be optimized:

while (low < high0 && compare (keys.GetValueImpl (low), objPivot, comparer) <
0)
    ++low;
while (high > low0 && compare (objPivot, keys.GetValueImpl (high), comparer) <
0)
    --high;


Changes:
========

- Sort (...) without IComparer param call Sort (..., (IComparer)null) siblings
- Sort (keys, items,...) with items == null call Sort (keys, ...) siblings 

- Sort (..., IComparer) methods do argument checking only, call SortImpl
- SortImpl methods do the real work (via combsort/sortNulls+qsort)

- add sortNulls(keys, items, low, high, bool ensureComparable) methods:
  - moves nulls to beginning of array
  - ensures that all non-null items implement IComparable/IComparable<T>
  - returns new "low" value (i.e. index of first non-null item)

- optimize qsort by employing multiple, faster copies of inner-most loop:
  - for case "comparer != null"
  - for case "pivot is IComparable<T>"
  - for case "pivot is IComparable"
- remove compare methods as the inner loops do their work


Performance improvements:
========================
15-20%  Array.Sort(object[]) (non-generic, array contains boxed ints)
25-30%  Array.Sort<T>(T[])
10-15%  Array.Sort<T>(T[], IComparer<Dummy>) (T being a struct)


All unit tests pass.
Please review.


-- 
Configure bugmail: https://bugzilla.novell.com/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are the QA contact for the bug.
You are the assignee for the bug.