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.

Phono

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 using

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

with the new version that uses

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

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

Phono

Does it make a difference if you use just static void QuickSort<T>(T[] arr, int left, int right, IComparer<T> cmp) (assuming the comparer is a class, not a struct)? – Senskell

@svick: You should try it and see; I think it should, but I don't have it in front of me right now to test. – Phono

Answer 2

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.

Indignation

But that only works in the (very) special case that the built-in comparator is sufficient. But if you're sorting by a different key (say, a person's age instead of his social security number), then you have to use IComparer<T> -- there is no other way. So it's just a solution tailored to this specific example, not something that you can use generally – Phono

@Mehrdad This is precisely what the last sentence of my answer is about: if you need flexibility (in your case, a way to supply a comparator at run time) you pay with CPU cycles (in your case, an invocation of a virtual function). – Indignation

Answer 3

Your results are going to depend very much on the type of T and on how expensive the comparisons are.

I created custom versions of your QuickSort methods: one that expects an array of int, and one that expects an array of string. The modifications are limited to removing the comparison parameter and changing the two comparisons in the partitioner. I modified them to sort in reverse, like this:

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

I then tested those methods against your generic method, using arrays of 10 million items. 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 comparison is very inexpensive (as it is with int and other native types), then you are going to notice a big difference in performance. If comparison is expensive (strings are pretty expensive to compare), that virtual call overhead is lost in the cost of the comparison.

I know that doesn't provide a solution to your problem; I don't think there is one. Flexibility often comes at a cost.

The people who built the base class libraries understood that. For example, they created special cases for primitive types that use the default IComparer. Compare the difference in running time when calling Array.Sort in these two ways (using an 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 their default IComparer. See Of Comparison and IComparer for a little more info about that.

Speechmaker

Answer 4

I think that dasblinkenlight is right, but I'd venture to guess as to why:

When you pass a Comparer to the QuickSort method the Framework is creating a generic implementation of the System.Comparison delegate (System.Comparison1` for example). Calls to any generic delegates are virtual, which makes sense- how would the compiler be able to statically generate a call to a method on a generic type that is only created at run-time?

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

The closest that I could get was a factory pattern 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);
    }
}

Diplomate

But that only works in the (very) special case that the built-in comparator is sufficient. But if you're sorting by a different key (say, a person's age instead of his social security number), then you have to use IComparer<T> -- there is no other way. So it's just a solution tailored to this specific example, not something that you can use generally. – Phono

Well, you could plug in any arbitrary concrete sorter to the factory method. But you need to do that in advance, yes, so it isn't perfectly generic. – Diplomate

Sorry, I guess I wasn't clear.... the problem here is that you're assuming where T : IComparable<T> actually holds. For many data real-world types, it never does. So unless you expect the user to copy-paste the entire source code for your method just to change a single method call (which is a pretty bad idea, for obvious reasons), I'm confused at how this would actually work. – Phono

I do expect them to copy/paste. As I explain above, there is no way for it to work otherwise. – Diplomate

I hope it's obvious why that's not useful/practical. :\ – Phono

As dasblinkenlight mentioned, it's a flexibility/performance tradeoff. My example just shows how you can provide a "fast special case". – Diplomate

Answer 5

Put the quicksort method in an abstract type and get rid of the use of the delegate completely.

First, create the abstract type. Note the new abstract 'compare' method, and the lack of the delegate on 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);
    }
}

Next, create a class that inherits from QuickSort and implements the compare method. We'll 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;
    }
}

Unavailing

This doesn't compile... You can't have an abstract static method. If you make it an instance method, it results in a callvirt also. – Diplomate

D'oh. I seem to have a hard time getting it into my head that static and abstract methods don't mix. – Unavailing