How to write generic code while avoiding indirect calls?

Question

Is there any way to call write generic programs and algorithms in C# while avoiding 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);
}

Which you might call as:

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

While seemingly efficient, this benign-looking example performs an indirect (i.e. virtual) call for every comparison.

Obviously, the processor cannot optimize indirect calls, and therefore they perform poorly. On my computer, this translates into a 25% decrease in performance, from about 3,600 items/ms to 2,700 items/ms.

Is there any way to avoid such indirect calls in writing generic code?
No matter how much juggling I do with delegates, DynamicMethod, and the like, it seems like there is always an indirect call between the library code and the user's code, which obviously impacts performance very negatively.

Answer 1

In case of comparing items the answer is no: you cannot put, say, a > between x and arr[j], and expect the compiler to figure out that you meant it to apply its built-in > operator on objects of type T.

However, your solution could be optimized a little, because you are paying for the indirection twice. Since you have declared your T an IComparable<T> already, you could drop the comparator parameter, and call x.CompareTo(arr[j]) without going through the lambda. This would cutting down on the overhead of a second indirection. Of course it would not let you customize the way in which you compare your items, but that would be a routine case of paying for flexibility with CPU cycles.