How to write generic code avoiding indirect calls?

Question

Is it possible to call a call to common programs and writing algorithms in C #, and to avoid the overhead of a dynamic solution?

Consider a simple example:

static void QuickSort<T>(T[] arr, int left, int right, Comparison<T> compare) { do { int i = left; int j = right; var x = arr[i + ((j - i) >> 1)]; do { while (i < arr.Length && compare(x, arr[i]) > 0) i++; while (j >= 0 && compare(x, arr[j]) < 0) j--; if (i > j) { break; } if (i < j) { var temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } i++; j--; } while (i <= j); if (j - left <= right - i) { if (left < j) QuickSort(arr, left, j, compare); left = i; } else { if (i < right) QuickSort(arr, i, right, compare); right = j; } } while (left < right); } 

What could you name:

 QuickSort(buffer, 0, buffer.Length - 1, (a, b) => a.CompareTo(b)) 

Despite its apparent effectiveness, this benign example performs an indirect (i.e. virtual) call for each comparison.

Obviously, the processor cannot optimize indirect calls, and therefore they work poorly. On my computer, this means a 25% reduction in performance - from about 3,600 pips / ms to 2,700 units / ms.

Is there a way to avoid such indirect calls when writing generic code?
Regardless of how much I deal with delegates, DynamicMethod and the like, there always seems to be an indirect call between library code and user code, which clearly negatively affects performance.

Answer 1

Actually, I finally realized that the solution is dead simple:

Use generics + interfaces instead of delegates!

Example:

 static void QuickSort<TCmp, T>(T[] arr, int left, int right, TCmp cmp) where TCmp : IComparer<T> { do { int i = left; int j = right; var x = arr[i + ((j - i) >> 1)]; do { while (i < arr.Length && cmp.Compare(x, arr[i]) > 0) i++; while (j >= 0 && cmp.Compare(x, arr[j]) < 0) j--; if (i > j) { break; } if (i < j) { var temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } while (++i <= --j); if (j - left <= right - i) { if (left < j) QuickSort<TCmp, T>(arr, left, j, cmp); left = i; } else { if (i < right) QuickSort<TCmp, T>(arr, i, right, cmp); right = j; } } while (left < right); } 

On my computer, when I compare the old version with

 QuickSort(copy1, 0, copy1.Length - 1, (x, y) => x.CompareTo(y)); 

with a new version that uses

 QuickSort(copy1, 0, copy1.Length - 1, comparer); 

I get a good (~ 30%) gain in speed.

Answer 2

In the case of comparing elements, the answer is negative: you cannot put, say, > between x and arr[j] , and expect the compiler to find out that you intended to use its built-in > on objects of type T

However, your decision could be optimized a little, because you pay for indirectness twice. Since you already declared your T an IComparable<T> , you can reset the comparator parameter and call x.CompareTo(arr[j]) without passing the lambda. This would reduce the overhead of the second indirectness. Of course, this will not allow you to set up a way to compare your elements, but this will be a usual case of flexibility when using processor cycles.

Answer 3

Your results will greatly depend on type T and how expensive the comparisons are.

I created custom versions of your QuickSort methods: one that expects an int array, and one that expects an array from string . Changes are limited to deleting the comparison parameter and changing two comparisons in the delimiter. I changed them to sort in reverse order, for example:

 while (i < arr.Length && arr[i].CompareTo(x) > 0) i++; while (j >= 0 && arr[j].CompareTo(x) < 0) j--; 

Then I tested these methods against your general method using arrays of 10 million elements. My results:

 Int: Generic QuickSort - 2,190 ms Int: Custom QuickSort - 1,252 ms String: Generic QuickSort - 32,902 ms String: Custom QuickSort - 31,634 ms 

My conclusion is that if the comparison is very inexpensive (as with int and other native types), you will notice a big difference in performance. If the comparison is expensive (strings are quite expensive to compare), then the overhead of the virtual call is lost in the cost of comparison.

I know that does not provide a solution to your problem; I do not think he is. Flexibility often comes at a cost.

The people who built the base class libraries realized this. For example, they created special cases for primitive types that use the default value of IComparer . Compare the difference in runtime when calling Array.Sort two ways (using int[10000000] ):

 Array.Sort(a); // 845 ms Array.Sort(a, (a, b) => a.CompareTo(b)); // 2,339 ms 

It turns out that Array.Sort has built-in optimizations for primitive types that use them by default, IComparer . See Of Comparison and IComparer for more information on this.

Answer 4

I think dasblinkenlight is right, but I will venture to suggest why:

When you pass Comparer to the QuickSort method, the Framework creates a general delegate implementation of System.Comparison ( System.Comparison 1), for example). The calls for any common delegates are virtual, which makes sense: how could the compiler statically generate a method call on a generic type that is created only at runtime?

Reed Copsi describes this in more detail here: http://social.msdn.microsoft.com/Forums/en-US/csharplanguage/thread/b94c7506-e21f-43b1-be9a-bf88f8f72f36

The closest I could get was a factory template that returns a non-virtual call for known types:

 using System; using System.Diagnostics; using System.Linq; namespace ConsoleApplication1 { class Program { static void Main(string[] args) { const int size = 50000; var ra = RandomArray(size); var buffer = Enumerable.Range(0, size).OrderBy(i => ra[i]).ToArray(); Debug.WriteLine(String.Join(",", buffer)); new IntSorter().QuickSort(buffer); Debug.WriteLine(String.Join(",", buffer)); } public IQuickSorter<T> GetSorter<T>() where T : IComparable<T> { if (typeof(T).Equals(typeof(Int32))) return (IQuickSorter<T>) new IntSorter(); return new GenericSorter<T>(); } public static Int32[] RandomArray(Int32 length) { var r = new Random(); return Enumerable.Range(0, length).Select(i => r.Next(0, length + 1)).ToArray(); } } public class IntSorter : IQuickSorter<int> { public void QuickSort(int[] arr) { QuickSortInner(arr, 0, arr.Length-1); } public void QuickSortInner(int[] arr, int left, int right) { do { int i = left; int j = right; var x = arr[i + ((j - i) >> 1)]; do { while (i < arr.Length && x.CompareTo(arr[i]) > 0) i++; while (j >= 0 && x.CompareTo(arr[j]) < 0) j--; if (i > j) { break; } if (i < j) { var temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } i++; j--; } while (i <= j); if (j - left <= right - i) { if (left < j) QuickSortInner(arr, left, j); left = i; } else { if (i < right) QuickSortInner(arr, i, right); right = j; } } while (left < right); } } public class GenericSorter<T> : IQuickSorter<T> where T : IComparable<T> { public void QuickSort(T[] arr) { QuickSortInner(arr, 0, arr.Length - 1); } public void QuickSortInner(T[] arr, int left, int right) { do { int i = left; int j = right; var x = arr[i + ((j - i) >> 1)]; do { while (i < arr.Length && x.CompareTo(arr[i]) > 0) i++; while (j >= 0 && x.CompareTo(arr[j]) < 0) j--; if (i > j) { break; } if (i < j) { var temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } i++; j--; } while (i <= j); if (j - left <= right - i) { if (left < j) QuickSortInner(arr, left, j); left = i; } else { if (i < right) QuickSortInner(arr, i, right); right = j; } } while (left < right); } } public interface IQuickSorter<in T> { void QuickSort(T[] arr); } } 

Answer 5

Put the quicksort method on an abstract type and completely get rid of delegate usage.

First create an abstract type. Pay attention to the new method of abstract "comparison" and the absence of a delegate in the QuickSort method:

 public abstract class QuickSort<T> { protected static abstract int compare(T x, T y); public static void QuickSort(T[] arr, int left, int right) { do { int i = left; int j = right; var x = arr[i + ((j - i) >> 1)]; do { while (i 0) i++; while (j >= 0 && compare(x, arr[j]) < 0) j--; if (i > j) { break; } if (i < j) { var temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } i++; j--; } while (i <= j); if (j - left <= right - i) { if (left < j) QuickSort(arr, left, j); left = i; } else { if (i < right) QuickSort(arr, i, right); right = j; } } while (left < right); } } 

Then create a class that inherits from QuickSort and implements the comparison method. We will use ints for our example:

 public class QuickSortInt : QuickSort<int> { protected static override int compare(int x, int y) { if (x < y) return -1; if (x > y) return 1; return 0; } }