如何在避免间接调用的同时编写泛型代码
本文关键字：代码 泛型 调用 | 更新日期: 2023-09-27 18:23:55
是否有任何方法可以在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项/毫秒。
在编写泛型代码时，有什么方法可以避免这种间接调用吗
无论我如何处理委托、DynamicMethod等，似乎在库代码和用户代码之间总是存在间接调用，这显然会对性能产生非常负面的影响。
在比较项目的情况下，答案是否定的：例如，不能在x和arr[j]之间放置>，并期望编译器发现您的意思是将其内置的>运算符应用于T类型的对象。
但是，您的解决方案可以进行一点优化，因为您要为间接性支付两次费用。由于您已经将T声明为IComparable<T>，因此可以删除comparator参数，并在不经过lambda的情况下调用x.CompareTo(arr[j])。这将减少第二次间接寻址的开销。当然，它不会让你自定义比较物品的方式，但这将是为CPU周期的灵活性付费的常规情况。
您的结果将在很大程度上取决于T的类型以及比较的成本。
我创建了您的QuickSort方法的自定义版本：一个需要int的数组，另一个则需要string的数组。修改仅限于删除比较参数和更改partitioner中的两个比较。我将它们修改为反向排序，如下所示：
while (i < arr.Length && arr[i].CompareTo(x) > 0) i++;
while (j >= 0 && arr[j].CompareTo(x) < 0) j--;
然后，我使用1000万个项目的数组，针对您的通用方法测试了这些方法。我的结果：
Int: Generic QuickSort - 2,190 ms
Int: Custom QuickSort - 1,252 ms
String: Generic QuickSort - 32,902 ms
String: Custom QuickSort - 31,634 ms
我的结论是，如果比较非常便宜（就像int和其他本机类型一样），那么您将注意到性能上的巨大差异。如果比较很昂贵（字符串比较起来相当昂贵），那么虚拟调用开销就会损失在比较成本中。
我知道这并不能解决你的问题；我认为没有。灵活性往往是有代价的。
构建基类库的人明白这一点。例如，他们为使用默认IComparer的基元类型创建了特殊情况。比较以下两种方式（使用int[10000000]）调用Array.Sort时运行时间的差异：
Array.Sort(a); // 845 ms
Array.Sort(a, (a, b) => a.CompareTo(b)); // 2,339 ms
事实证明，Array.Sort对使用默认IComparer的基元类型有内置的优化。请参阅Of Comparison和IComparer了解更多信息。
我认为dasblinkenlight是对的，但我敢猜测为什么：
将Comparer传递给QuickSort方法时，Framework正在创建System.Comparison委托的通用实现（例如System.Comparison 1`）。对任何泛型委托的调用都是虚拟的，这是有道理的——编译器如何能够静态生成对仅在运行时创建的泛型类型上的方法的调用？
Reed Copsey在这里更深入地描述了这一点：http://social.msdn.microsoft.com/Forums/en-US/csharplanguage/thread/b94c7506-e21f-43b1-be9a-bf88f8f72f36
我能得到的最接近的是一个工厂模式，它返回已知类型的非虚拟调用：
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);
}
}
将quicksort方法放在抽象类型中，并完全取消委托的使用。
首先，创建抽象类型。注意新的抽象"比较"方法，以及QuickSort方法上缺少委托：
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);
}
}接下来，创建一个从QuickSort继承并实现compare方法的类。我们将使用int作为示例：
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;
}
}实际上，我终于意识到解决方案非常简单：
使用泛型+接口而不是委托
示例：
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);
}
在我的电脑上，当我使用比较旧版本时
QuickSort(copy1, 0, copy1.Length - 1, (x, y) => x.CompareTo(y));
使用的新版本
QuickSort(copy1, 0, copy1.Length - 1, comparer);
我的速度提高了（约30%）。