避免动态解决方案的开销的同时,有什么方法可以用C#调用编写通用程序和算法?

考虑一个简单的例子:

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);
}

您可以这样称呼它:
QuickSort(buffer, 0, buffer.Length - 1, (a, b) => a.CompareTo(b))

这个看似良性的示例虽然看似高效,但为每个比较执行了间接(即虚拟)调用。

显然,处理器无法优化间接调用,因此它们的性能很差。在我的计算机上,这意味着性能下降了25%,从大约3600个项目/毫秒降低到了2700个项目/毫秒。

有什么方法可以避免在编写通用代码时进行此类间接调用?
无论我对委托(delegate),DynamicMethod之类的东西进行多大的处理,似乎总是在库代码与用户代码之间存在间接调用,这显然会对性能产生负面影响。

最佳答案

如果比较项目,答案是否定的:例如,您不能在>x之间放置一个arr[j],并且希望编译器弄清楚您的意思是它打算将其内置的>运算符应用于T类型的对象。

但是,您的解决方案可能会有所优化,因为您要为间接支付两次。由于您已经将T声明为IComparable<T>,因此可以删除comparator参数,然后调用x.CompareTo(arr[j]),而无需经过lambda。这将减少第二个间接的开销。当然,它不会让您自定义比较项目的方式,但这是在CPU周期上付出灵活性的常规情况。

关于c# - 如何在避免间接调用的同时编写通用代码?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/9204884/

10-10 10:42