7

编码时，在性能方面要记住什么好的经验法则？有无数种方法可以针对特定平台和编译器进行优化，但我正在寻找同样适用于（或几乎）跨编译器和平台的答案。

4

26 回答 26

15

想起一句名言：

“我们应该忘记小的效率，比如大约 97% 的时间：过早的优化是万恶之源。” （Knuth, Donald。带 go to Statements 的结构化编程，ACM Journal Computing Surveys，第 6 卷，第 4 期，1974 年 12 月。第 268 页。）

但是也许您无论如何都不应该按值传递大型数据结构... :-)

编辑：也许还可以避免O (N^2) 或更复杂的算法...

于 2008-11-24T20:43:37.237 回答
12

排名第一的性能提示是尽早且经常地分析您的代码。有很多通用的“不要这样做”提示，但很难保证这会影响应用程序的性能。为什么？每个应用程序都是不同的。如果你有很多元素，很容易说按值传递向量是不好的，但你的程序甚至使用向量（你可能应该但是......）？

分析是了解应用程序性能的唯一方法。我遇到过太多的情况，人们“优化”了代码，但从来没有分析过。事实证明，“优化”引入了许多错误，甚至不是代码路径中的热点。浪费大家的时间。

编辑：

有几个人评论了我回答的“早期”部分。我认为您不应该从第一天开始进行分析。但是您也不应该等到发货后的 1 个月。

一旦我有几个明确的端到端场景，或者在一个更大的项目中，一个主要是功能组件，我通常会首先进行概要分析。我需要一两天（通常与 QA 一起工作）来收集一些大型场景并将其扔到代码中。这是一个很好的抽查，可以及早发现明显的性能问题。此时修复它们要容易一些。

在一个典型的项目中，我发现我的代码在整个项目过程中 30%-40% 都符合这个标准（100% 在客户手中）。这次我松散地归类为早。

于 2008-11-24T20:40:28.473 回答
11
  • 尽可能使用if或switch代替通过函数指针调用。澄清：void doit(int m) { switch(m) { case 1: f1(); break; case 2: f2(); break; } }而不是void doit(void(*m)()) { m(); }可以内联调用。
  • 在可能且不造成伤害的情况下，首选 CRTP 而不是虚拟功能
  • 如果可能，请避免使用 C 字符串并使用 String 类。它通常会更快。（恒定时间长度“测量”，附加摊销的恒定时间，...）
  • 始终通过引用 const (T const&) 而不是复制值来传递用户定义的类型值（除了没有意义的地方。例如迭代器）。
  • 对于用户定义的类型，总是首选++t而不是t++
  • const尽早使用，经常使用。最重要的是提高可读性。
  • 尽量保持new在最低限度。如果可能，总是更喜欢自动变量（在堆栈上）
  • 与其自己填充数组，不如使用空的初始化列表进行初始化，就像T t[N] = { };你想要零一样。
  • 尽可能多地使用构造函数初始化器列表，尤其是在初始化用户定义的类型成员时。
  • 利用函子（operator()重载的类型）。它们内联比通过函数指针调用更好。
  • std::vector如果您的std::string数量固定不变，请不要使用此类。使用boost::array<T, Size>或裸数组并正确使用它。

事实上，我差点忘记了：

过早的优化是万恶之源

于 2008-11-24T20:47:29.973 回答
11

有人提到了函数指针（以及为什么你应该使用if）。好吧，甚至更好：改用仿函数，它们被内联并且通常具有零开销。仿函数是一种结构（或类，但通常是前者），它重载了运算符()和实例，可以像普通函数一样使用：

template <typename T>
struct add {
    operator T ()(T const& a, T const& b) const { return a + b; }
};

int result = add<int>()(1, 2);

这些几乎可以在可以使用普通函数或函数指针的所有上下文中使用。它们通常来自std::unary_functionor std::binary_function，但这通常不是必需的（实际上只是为了继承一些有用typedef的 s）。

编辑在上面的代码中，显式<int>类型限定是必需的。类型推断仅适用于函数调用，不适用于实例创建。但是，通常可以通过使用make辅助函数来省略它。这是在 STL 中为pairs 完成的：

template <typename T1, typename T2>
pair<T1, T2> make_pair(T1 const& first, T2 const& second) {
    return pair<T1, T2>(first, second);
}

// Implied types:
pair<int, float> pif = make_pair(1, 1.0f);

有人在评论中提到，仿函数有时被称为“functionoids”。是的，但不完全是。事实上，“函子”是“函数对象”的（有点奇怪）缩写。functionoid 在概念上是相似的，但通过使用虚函数来实现（尽管它们有时被同义使用）。例如，functionoid 可能如下所示（连同其必要的接口定义）：

template <typename T, typename R>
struct UnaryFunctionoid {
    virtual R invoke(T const& value) const = 0;
};

struct IsEvenFunction : UnaryFunctionoid<int, bool> {
    bool invoke(int const& value) const { return value % 2 == 0; }
};

// call it, somewhat clumsily:
UnaryFunctionoid const& f = IsEvenFunction();
f.invoke(4); // true

当然，这会失去仿函数由于其虚函数调用而具有的任何性能优势。因此，它用于实际需要多态（有状态）运行时函数的不同上下文中。

C++ FAQ 有更多关于这个主题的内容。

于 2008-11-24T21:01:18.510 回答
8

在需要之前不要费心优化。要了解是否需要，请配置文件。不要猜测；有证据。

此外，算法优化通常比微观优化具有更大的影响。使用 A-star 而不是蛮力寻路会更快，就像 Bresenham 圆比使用 sin/cos 更好一样。当然，这些也有例外，但它们非常（非常）罕见（<0.1%）。如果你有一个好的设计，改变算法只会改变你代码中的一个模块。简单的。

于 2008-11-24T20:45:47.183 回答
7

使用已经使用和重复使用的现有的、经过审查的代码。（例如：STL、提升与滚动您自己的容器和算法）

由于评论而更新：正确使用已使用和重复使用的现有、已审核的代码。

于 2008-11-24T20:50:03.383 回答
4

就性能而言，您能做的最好的事情就是从可靠的架构和线程模型开始。其他一切都将建立在此之上，因此，如果您的基础很糟糕，那么您的成品也只会那么好。分析会晚一点，甚至比微优化更晚（一般来说，这些都是微不足道的，并且比任何东西都更复杂代码。）

这个故事的寓意是：从一个有效的基础开始，建立在不做完全愚蠢和缓慢的事情的认识之上，你应该会没事的。

于 2008-11-24T20:47:13.780 回答
4

还有一点：最快的代码是不存在的代码。这意味着您的项目需要越健壮和功能齐全，它就会越慢。底线：尽可能跳过绒毛，同时确保您仍然满足要求。

于 2008-11-24T21:24:07.420 回答
3

C++ 的两个最佳技巧：

购买由 Scott Meyers 撰写的 Effective C++。

然后购买 Scott Meyers 的《更有效的 C++》。

于 2008-11-24T21:14:21.400 回答
2

尽可能保持代码干净。如今的编译器非常棒。然后，如果您确实有性能问题，请配置文件。

所有这一切都是在为您的问题选择了可用的最佳算法之后。

于 2008-11-24T20:45:56.873 回答
2

Wikibooks 有一些东西。

一件好事是知道你正在使用的东西的效率。乘法的加法速度有多快，向量与普通数组的比较速度或某些算法与更高尺度的比较速度有多快。这使您可以为任务选择最有效的工具

于 2008-11-24T20:55:45.247 回答
2

使用通用算法是一个很好的优化技巧——不是在运行时间方面，而是在编码时间方面。知道您可以排序（开始，结束）并期望范围 - 无论是指向数据库的两个指针或迭代器 - 都会被排序（而且，使用的算法也将是运行时高效的）。泛型编程是 C++ 独特而强大的原因，您应该始终牢记这一点。您不必编写许多算法，因为版本已经存在（并且可能与您编写的任何算法一样快或更快）。如果您有其他考虑，那么您可以专门研究算法。

于 2008-11-24T20:58:46.347 回答
1

一个简单的建议是养成做 ++i 而不是 i++ 的习惯。i++ 制作一个副本，这可能很昂贵。

于 2008-11-24T20:45:48.883 回答
1

这里有几个：

此外，避免使用虚函数，只在需要使用它们时创建对象。

如果您有心情，请查看Efficient C++。我上学的时候家里有一本。

于 2008-11-24T20:47:21.737 回答
1

考虑使用内存池。

于 2008-11-24T21:03:33.310 回答
1

  1. 始终尝试考虑您的内存的外观 - 例如，数组是大小为 numOfObjects X 的连续内存行sizeof(object)。一个二维数组是 n X m Xsizeof(object)并且每个对象都在 n + m X n 的索引中，所以

    for(int i = 0 ; i < n ; i++){
    for(int j = 0 ; j < m ; j++){
        arr[i,j] = f();

    比（在单个进程上）要好得多： 

    for(int i = 0 ; i < n ; i++){
    for(int j = 0 ; j < m ; j++){
        arr[j,i] = f();

    因为数组是以连续块的形式进入缓存的，所以第一个片段在缓存中的所有单元格上运行，然后再获取其余部分，而第二个片段需要一遍又一遍地将新的数组单元格提取到单元格中

  2. 当您的应用程序开始变慢时，使用性能基准来找到确切的瓶颈，甚至GetTickCount可以使用简单的调用来确定组件运行所需的时间。在较大的项目上，在开始优化之前使用适当的分析器，这样您就可以在重要的地方花费最多的优化工作。

于 2008-11-24T21:56:00.850 回答
1

不要使用效率极低的算法，在编译器中打开优化，不要优化任何东西，除非分析器显示它是一个瓶颈，当你尝试改进事情时，测试看看你做得好还是坏。还要记住，库函数通常是由比你更擅长的人优化的。

与这些相比，几乎所有其他事情都是次要的。

于 2008-11-24T22:50:21.427 回答
1

基本上，您最大的性能提升将来自算法改进。这意味着使用最高效的算法，进而使用最高效的数据项容器。

有时很难知道最好的权衡是什么，但幸运的是，STL 的设计者正是考虑到了这个用例，因此 STL 容器通常足够灵活，可以根据需要混合和匹配容器的应用程序。

但是，要充分实现好处，您需要确保不会将内部设计选择作为类/模块/其他接口的一部分公开。您的任何客户都不应依赖于您对std::vector. 至少提供他们（和您）可以使用的 typedef，这应该允许根据您的需要将向量更改为列表（或其他）。

同样，请确保您拥有尽可能多的已调试算法和容器供您使用。如今，Boost 和/或 TR1 几乎是必需品。

于 2008-11-25T03:39:02.623 回答
1

来自我参考的一本 C++ 书籍（Bulka 和 Mayhew 的 Efficient C++ performance Techniques），其中明确谈到了 C++ 性能方面。其中之一是；

在定义构造函数时..也初始化其他构造函数；就像是;

class x {

x::x(char *str):m_x(str) {} // and not as x::x(char *str) { m_str(str); }

private:
std::string m_x;

};

以上是一些引起我注意并帮助我改进编码风格的事情......这本书有更多关于这个有趣的性能主题的分享。

于 2008-12-23T10:38:50.140 回答
1

粗略设计

在对性能至关重要的领域中，将您的类和数据结构设计保持在较粗略的方面，而不是细粒度的方面。通过性能关键，我的意思是要么这样测量，要么你可以肯定地预期大量输入被重复处理（例如：每一帧）。这样做的目的是在未来为任何必要的优化留出足够的喘息空间。否则，我们可能会看到需要对代码库的中心区域进行大量重新设计/重写的瓶颈，这需要对所有依赖项进行级联重写。

让我们来看几个我从其他遇到热点的人那里遇到的粒度设计示例。

一大堆弦乐

// Stores millions of strings.
std::vector<std::string> boatload_of_strings;

这是一个细粒度的设计，因为我们通过数百万个实例存储了一个成熟的字符串容器/类。数百万存储的每一个很小的字符串都使用一个成熟的、可变大小的内存管理std::string容器来表示。这最终会导致内存使用爆炸，需要比必要更多的内存，或者使用比必要更多的堆分配，或者两者兼而有之。通过最近的小字符串优化，最小值sizeof(std::string)可以达到 24 字节，如果我们的大多数字符串只有几个字符长，这将是相当爆炸性的内存使用。如果字符串是中等长度的，你仍然可以为每个字符串分配一个单独的堆。无论哪种方式，它都会转化为大量缓存未命中。相反，如果您像这样使设计更粗糙：

class BoatloadOfStrings
{
public:
     // Returns the nth string.
     const char* operator[](int n) const
     {
         return buffer.data() + string_start[n];
     }

     // Inserts a string.
     void insert(const char* str)
     {
         string_start.push_back(buffer.size());
         buffer.insert(buffer.end(), str, str + strlen(str)+1);
     }

private:
     // Stores all the characters of all null-terminated
     // strings in one giant buffer.
     std::vector<char> buffer;

     // Stores the starting position of each null-terminated
     // string.
     std::vector<size_t> string_start;
};

...现在我们最终使用更少的内存，并且仅在这两个向量之一超过容量（摊销成本）时才面临堆分配。即使我们从使用std::vector存储数百万个实例的上述解决方案开始std::string，使用这种更粗略的BoatloadOfStrings类设计也比我们对前一种表示具有大量依赖项的情况有更多的优化空间。

大量抽象像素

class IPixel
{
public:
     virtual ~IPixel() {}

     // Abstract pixel operations.
     ...
};

在这里，如果我们正在设计一个图像/视频处理应用程序，它必须重复循环遍历像素以执行自定义视频过滤器等操作，那么上述设计非常浪费，但也给我们没有喘息的空间来进一步优化它如果整个系统都依赖于这样的接口。

通常情况下，动态调度和虚拟指针之类的成本是几美分，但如果每帧多次支付数百万次，那么便士就会变得昂贵。为每个像素支付虚拟调度的成本确实变得相对非常昂贵，而且虚拟指针的大小，尽管在 64 位系统上只有 8 个字节，却使32 位系统的内存使用量增加了四倍。位 RGBA 图像，当我们考虑其大小时，考虑到其 64 位对齐要求（64 位 vptr + 32 位像素数据 + 32 位对齐 vptr 的填充），它将添加到结构中的填充。

在这种情况下，我推荐的解决方案相同。在更粗略的水平上进行设计。如果你需要多态，看看你是否可以在更粗略的图像级别进行抽象：

class IImage
{
public:
     virtual ~IImage() {}

     // Abstract image operations.
     ...
};

突然之间，虚拟指针和虚拟调度的成本变得非常便宜，因为它们只需为整个图像支付一次，整个图像很可能包含数百万像素作为像素容器。现在您有空间做一些事情，例如在中央级别将 SIMD 内在函数应用于并行循环中的图像操作，而无需重写大部分代码库。

一大堆生物

class Creature
{
public:
     virtual ~Creature() {}

     // Abstract creature operations.
     ...
};

class Human: public Creature
{
     ...
};

class Orc: public Creature
{
     ...
};

class Undead: public Creature
{
     ...
};

假设我们有一个实时战争模拟，其中包括在单个游戏会话中具有大量单位的一大堆抽象生物，指环王风格。这些生物可以在任何给定时刻被移除，因为它们可能会死亡，例如，我们每帧应用的大多数关键循环实际上是顺序循环，它们只是做一些事情，比如沿着给定路径移动所有生物。

在这种情况下，上述表示可能会成为瓶颈，几乎没有进一步优化的空间，因为代码使用指向 的多态基指针Creature*，迫使我们一次处理一个生物。最重要的是，每个生物可能有不同的大小和对齐要求，这意味着它们通常不能连续存储在内存中（例如：我们可能无法将兽人的数据与人类的数据交错存储在内存中，即使我们想要处理一个兽人，然后是一个人类）。

在这些情况下，您可以通过为每个生物子类型使用单独的分配器来稍微提高性能，例如每个生物子类型的单独空闲列表，它将特定类型的生物分配到连续的块中，以及对多态基础进行基数排序用于改进引用局部性的地址指针（例如，相同类型的相邻生物的空间局部性和 vtable 上的时间局部性）。但是，在有限的空间内进行优化需要付出很多努力。同时，如果您只使用这样的粗略设计：

class CreatureHorde
{
public:
     virtual ~CreatureHorde() {}

     // Abstract creature horde operations.
     ...
};

class HumanHorde: public CreatureHorde
{
     ...
};

class OrcHorde: public CreatureHorde
{
     ...
};

class UndeadHorde: public CreatureHorde
{
     ...
};

...现在我们在整个生物群的水平上进行设计，就像我们将抽象像素界面变成抽象图像界面一样。现在我们有各种空间可以轻松优化，因为我们的多态基指针 ( CreatureHorde*) 将指向要处理的整个生物群，而不是一次处理一个生物。在每个部落中，我们可能对缓存友好的顺序处理，例如，在一个连续的向量/数组中顺序存储和处理的一群人类中的人类单位的所有数据。

结论

所以无论如何，这是我的第一条建议，它与设计有关，而不是与实施有关。当您预计系统中有较大的、对性能至关重要的循环区域时，请在较粗略的级别进行设计。使用更粗略的数据结构、更粗略的类接口和更粗略的抽象。不要将一大堆小东西单独表示为单独的类和独立的数据结构，或者至少不要将其表示为更粗略设计的私有实现细节。

在您获得足够粗略的设计以给您优化的喘息空间之后，您可能会考虑让自己获得一些不错的分析工具，提高您对内存层次结构的理解，并行化您的代码（使用更粗略的设计也变得更容易），矢量化它（粗糙的设计也变得更容易）等。

但是，当我们预先考虑效率时，对我来说最重要的是设计效率，因为缺乏这一点，即使我们分析并准确地发现我们的热点，我们也无法在事后有效地优化我们的实现。设计效率通常归结为有足够的喘息空间来优化设计，而这实际上归结为更粗略的设计，不尝试对最小的对象和数据结构进行建模。

于 2018-01-15T23:50:50.623 回答
0

“过早的优化是万恶之源”（Knuth，Donald）

这实际上取决于您编写的代码类型及其典型用法。

于 2008-11-24T20:42:55.130 回答
0

无论您采取什么措施来节省几个周期，请记住这一点：不要试图比编译器更聪明 - 测量以验证增益。

于 2008-11-25T07:12:23.207 回答
0

虽然没有解决确切的问题，但一些建议是：

总是为接口编码（当涉及到算法时），这样你就可以用高效的接口（通过任何 req 方式）平滑地替换它们。

于 2008-11-25T08:19:48.763 回答
0

我同意关于过早优化的建议。但是，我喜欢在设计过程中遵循一些准则，因为它们以后可能难以优化：

  • 尝试在启动时分配所有对象，new在运行时尽量减少使用。
  • 设计你的数据结构，使你的算法在 O(1) 时有很好的机会。
  • 像往常一样，模块化，以便您以后可以拆掉和更换。这意味着您拥有一套全面的单元测试，可以让您确信您的新解决方案是正确的。
  • 将性能测试添加到您的单元测试套件中，以确保您不会无意中得到一些 O(n*n) 代码:-)
于 2008-12-18T17:28:54.373 回答
0
  • 规则 1：不要
  • 规则 2：测量
于 2008-12-18T17:34:33.363 回答
0

选择性能最好的算法，使用更少的内存，使用更少的分支，使用快速操作，使用少量的迭代。

于 2009-06-17T07:25:38.740 回答