性能的C++模板？

Question

我已经在网上看了几次,提到使用模板可以更快地使用C++.

有人可以解释,包括在低级别为什么这是确切的？我总是认为这样一个"好"的功能会像大多数有用的概念一样有开销.

从超低延迟的角度来看,我对此非常感兴趣!

Answer 1

一个常见的例子是排序.

在C中,qsort获取指向比较函数的指针.一般来说,会有一个qsort代码副本,但不会内联.它将通过指向比较例程的指针进行调用 - 这当然也没有内联.

在C++中,它std::sort是一个模板,它可以将一个函子对象作为比较器.std::sort对于用作比较器的每种不同类型,存在不同的副本.假设您使用带有重载的仿函数类operator(),则可以轻松地将对比较器的调用内联到此副本中std::sort.

因此,模板可以为您提供更多内联,因为sort代码的副本更多,每个代码都可以内联不同的比较器.内联是一个非常好的优化,并且排序例程进行了大量的比较,因此您通常可以std::sort比同等的更快地测量运行qsort.这样做的代价是更大代码的可能性 - 如果你的程序使用了很多不同的比较器,那么你会得到很多不同的排序例程副本,每个副本都有一个不同的比较器.

原则上,没有理由为什么C实现不能内联qsort到它被调用的地方.然后,如果使用函数名称调用它,优化器理论上可以观察到在使用它时,函数指针仍然必须指向同一个函数.然后它可以内联对函数的调用,结果将类似于结果std::sort.但在实践中,编译器往往不采取第一步,内联qsort.这是因为(a)它的大,和(b)是在不同的翻译单元,通常编译成一些你的程序是对链接库,以及(c)去做这样,你就会有一个内联拷贝qsort的每次调用它,而不仅仅是每个不同比较器的副本.所以它会比C++更加臃肿,除非在qsort使用相同的比较器在不同的地方调用的情况下,实现也可以找到一种共享代码的方法.

因此,像qsortC中的通用函数往往会因为通过函数指针调用或其他间接[*]而产生一些开销.C++中的模板是保持源代码通用的常用方法,但确保它编译为专用函数(或几个这样的函数).特殊用途代码希望更快.

值得注意的是,模板绝不仅仅与性能有关.std::sort本身比qsort某些方面更具通用性.例如,qsort只对数组std::sort进行排序,而可以对提供随机访问迭代器的任何内容进行排序.它可以例如对a进行排序deque,其中有几个单独分配的不相交数组.因此,模板的使用不一定提供任何性能优势,可能出于其他原因.只是模板确实会影响性能.

[*]另一个带排序的例子 - qsort接受一个整数参数,说明数组的每个元素有多大,当它移动元素时,它必须调用memcpy或类似于该变量的值.std::sort在编译时知道元素的确切类型,因此确切的大小.它可以内联复制构造函数调用,而后者可能会转换为复制该字节数的指令.与内联比较器一样,通常可以通过调用复制可变数量的字节的例程来快速复制4个(或8个或16个或任何其他)字节,并将其传递给值4(或8) ,或16,或其他).和以前一样,如果你qsort用大小的字面值调用,并且调用qsort内联,那么编译器可以在C中执行完全相同的优化.但实际上你没有看到.

Answer 2

"更快"取决于你的比较.

模板由编译器完全评估,因此它们在运行时没有任何开销.呼叫Foo<int>()与呼叫一样有效FooInt().

因此,与依赖于在运行时完成更多工作的方法相比,例如通过调用虚函数,模板确实可以更快.与为该场景精确编写的手写代码相比,没有区别.

所以关于模板的好处并不是它们比你能做到的更"快",而是它们与手写代码"一样快",同时也是通用的和可重用的.

Answer 3

另一个使用模板来提高运行时性能的显着例子是Blitz ++数值库.它开创了所谓的表达模板的使用,使用编译时逻辑将涉及大向量和矩阵的算术表达式转换为更容易编译为高效机器代码的等效表达式.例如,给定以下伪代码:

vector<1000> a = foo(), b = bar(), c = baz(), result;
result = a + b + c;

一个天真的方法会添加每个元素a和b一起,将结果存储在临时向量中,然后执行相同操作c,最后将结果复制到result.使用表达式模板魔术,结果代码将等效于此:

for(int i = 0; i < 1000; ++i) {
    result[i] = a[i] + b[i] + c[i];
}

这是很多更快,更好地利用缓存的区域性和避免沿途不必要的临时.它还避免了别名问题,编译器无法证明两个指针指向不同的内存区域,迫使它产生不理想的代码.表达模板现在通常用于高性能数字,以及其他不涉及性能的用途,例如Boost.Spirit解析库.

Answer 4

我不确定你是否在讨论C++模板元编程:在编译期间进行一些计算,这样你几乎可以在运行时间内获得结果.如果是这样,这是一个例子.

通过使用模板元编程和模板特化来提供递归的结束条件,程序中使用的因子,忽略任何未使用的因子,可以在编译时通过此代码计算

template <int N>
struct Factorial 
{
    enum { value = N * Factorial<N - 1>::value };
};

template <>
struct Factorial<0> 
{
    enum { value = 1 };
};

// Factorial<4>::value == 24
// Factorial<0>::value == 1
void foo()
{
    int x = Factorial<4>::value; // == 24
    int y = Factorial<0>::value; // == 1
}

这里有更多内容可以阅读 http://en.wikipedia.org/wiki/Template_metaprogramming