现代C ++编译器的有效优化策略
我正在研究对性能至关重要的科学代码。 代码的初始版本已经被编写和testing，现在，使用Profiler，现在是时候从热点开始刮削周期了。
众所周知，一些优化，比如循环展开，现在由编译器处理得比用手工编程的程序员更有效。 哪些技术仍然值得？ 很显然，我会通过一个分析器来运行所有的东西，但是如果有传统的智慧来判断哪些工作可以工作，哪些工作不工作，那将会为我节省很多时间。
我知道，优化是非常依赖于编译器和体系结构的。 我正在使用针对Core 2 Duo的英特尔C ++编译器，但是我也对gcc或者“任何现代编译器”都适用。
以下是我正在考虑的一些具体的想法：
- 用手工卷取代STL容器/algorithm有什么好处吗？ 特别是，我的程序包含一个非常大的优先级队列（目前是一个
std::priority_queue），其操作花费了大量的时间。 这是值得研究的东西，还是STL实现可能是最快的？ - 沿着类似的路线，对于需要的大小未知，但有一个合理的小上限的
std::vectors，用静态分配的数组replace它们是否有利呢？ - 我发现dynamic内存分配通常是一个严重的瓶颈，消除它会导致显着的加速。 因此，我很感兴趣的是，通过值返回大的临时数据结构与通过指针返回与通过引用传递结果的性能权衡。 有没有办法可靠地确定编译器是否将RVO用于给定的方法（当然，假设调用者不需要修改结果）？
- 编译器倾向于如何识别caching？ 例如，是否值得重新sorting嵌套循环？
- 鉴于该计划的科学性，无处不在的浮点数。 我的代码中的一个重要瓶颈曾经是从浮点到整数的转换：编译器会发出代码来保存当前的舍入模式，更改它，执行转换，然后恢复旧的舍入模式 – 即使程序中没有任何内容曾改变舍入模式！ 禁用此行为显着加快了我的代码。 是否有类似的浮点相关陷阱我应该知道？
- 单独编译和链接C ++的一个后果就是编译器无法做到看起来非常简单的优化，比如strlen（）之类的方法调用超出了循环的终止条件。 有没有像这样的优化，我应该看看，因为它们不能由编译器完成，必须手工完成？
- 另一方面，是否有任何技术我应该避免，因为它们可能会干扰编译器自动优化代码的能力？
最后，扼杀某些种类的答案：
- 我知道优化在复杂性，可靠性和可维护性方面有成本。 对于这个特定的应用来说，性能的提高是值得的。
- 我知道最好的优化往往是提高高级algorithm，这已经完成了。
用手工卷取代STL容器/algorithm有什么好处吗？ 特别是，我的程序包含一个非常大的优先级队列（目前是一个std :: priority_queue），其操作花费了大量的时间。 这是值得研究的东西，还是STL实现可能是最快的？
我假设你知道STL容器依赖于复制元素。 在某些情况下，这可能是一个重大的损失。 存储指针，如果你做了很多的容器操作，你可能会看到性能的提高。 另一方面，它可能会减lesscaching的位置并伤害你。 另一个select是使用专门的分配器。
某些容器（如map ， set ， list ）依赖于大量的指针操作。 虽然违反直觉，但通常会导致更快的代码来replace它们。 得到的algorithm可能从O(1)或O(log n)到O(n) ，但是由于caching局部性，在实践中可以快得多。 configuration文件是肯定的。
你提到你正在使用priority_queue ，我想这会花费很多重新安排元素，特别是如果它们很大。 你可以尝试切换底层容器（可能是deque或专用的）。 我几乎肯定会存储指针 – 再一次，configuration文件是肯定的。
沿着类似的路线，对于一个std :: vectors，其所需的大小是未知的，但有一个相当小的上限，用静态分配的数组replace它们是否有利呢？
再次，这可能会帮助一小部分，这取决于用例。 你可以避免堆分配，但是只有当你不需要你的数组超时才能分配堆栈，或者你可以在vector reserve()大小，这样在重新分配时就不需要复制了。
我发现dynamic内存分配通常是一个严重的瓶颈，消除它会导致显着的加速。 因此，我很感兴趣的是，通过值返回大的临时数据结构与通过指针返回与通过引用传递结果的性能权衡。 有没有办法可靠地确定编译器是否将RVO用于给定的方法（当然，假设调用者不需要修改结果）？
您可以查看生成的程序集以查看是否应用了RVO，但是如果返回指针或引用，则可以确定没有副本。 这是否有帮助取决于你在做什么 – 例如不能返回临时对象的引用。 你可以使用舞台来分配和重用对象，所以不要付大量的惩罚。
编译器倾向于如何识别caching？ 例如，是否值得重新sorting嵌套循环？
我已经看到在这个领域里戏剧性的 （严重戏剧性的）加速。 我从后面看到了multithreading处理代码的更多改进。 事情可能在五年以后发生了变化，只有一个方法可以确定。
另一方面，是否有任何技术我应该避免，因为它们可能会干扰编译器自动优化代码的能力？
-
在你的单个参数构造函数中
explicit使用。 临时对象的构造和破坏可能隐藏在你的代码中。 -
请注意大对象上隐藏的复制构造函数调用。 在某些情况下，考虑用指针replace。
-
简介，简介，简介。 调整瓶颈区域。
看看面向对象程序devise幻灯片的优秀缺陷，了解一些有关重构本地代码的信息。 根据我的经验，更好的地方几乎总是最大的胜利。
一般过程：
- 学会在debugging器中爱上反汇编视图 ，或者让你的编译系统尽可能地生成中间汇编文件（.s）。 注意变化或看起来过分的事情 – 即使不熟悉给定的指令集体系结构，您也应该能够清楚地看到一些事情！ （我有时会检查一系列带有相应.cpp / .c变化的.s文件，只是为了利用我的SCM中可爱的工具来观察代码和相应的asm随着时间的变化。）
- 获取一个可以监视CPU性能计数器的分析器，或者至less可以猜测caching未命中。 （AMD CodeAnalyst，cachegrind，vTune等）
其他一些具体的事情：
- 了解严格的别名。 一旦你这样做了，如果你的编译器有这个
restrict，就可以使用restrict。 （也检查这里的不适！） - 检查处理器和编译器上的不同浮点模式 。 如果你不需要非规范化的范围，select一个没有这个的模式可以得到更好的性能。 （听起来你已经在这方面做了一些事情，根据你对舍入模式的讨论。）
- 绝对避免allocs：当你可以调用
std::vectorreserve，或者在编译时知道大小的时候使用std::array。 - 使用内存池来增加局部性并减lessalloc / free开销; 还要确保高速caching线alignment并防止乒乓。
- 如果您按照可预测的模式分配内容，可以使用帧分配器 ，并且可以一次性释放所有内容。
- 请注意不variables 。 你知道的东西是不变的，可能不是编译器，例如在循环中使用struct或class成员。 我发现最简单的方法就是把所有的东西都命名为一个名字，并且喜欢在循环之外命名。 例如
const int threshold = m_currentThreshold;或者也许Thing * const pThing = pStructHoldingThing->pThing;幸运的是，您通常可以在反汇编视图中看到需要这种处理的东西。 这也有助于后期debugging（使得debugging版本中的watch / locals窗口更好地运行）！ - 如果可能的话， 避免在循环中写入 – 先累积，然后写入或批量写入一些写入。 YMMV，当然。
WRT你的std::priority_queue问题：插入东西到一个vector（默认的后端为一个priority_queue）往往会移动很多元素。 如果你可以分成几个阶段，插入数据的地方，然后对它进行分类，然后在分类之后阅读，那么你可能会好很多。 虽然你肯定会失去局部性，但是你可能会发现更多的自我sorting结构，比如std :: map或者std :: set值得开销 – 但是这真的取决于你的使用模式。
用手工卷取代STL容器/algorithm有什么好处吗？
我只会认为这是最后的select。 STL容器和algorithm已经过全面testing。 创造新的开发时间是昂贵的。
沿着类似的路线，对于所需大小未知但具有相当小的上限的std :: vectors，用静态分配的数组replace它们是否有利呢？
首先，尝试为vector保留空间。 检查出std::vector::reserve方法。 一个不断增长或者变大的vector将会浪费dynamic的内存和执行时间。 添加一些代码来确定一个上限的好值。
我发现dynamic内存分配通常是一个严重的瓶颈，消除它会导致显着的加速。 因此，我很感兴趣的是，通过值返回大的临时数据结构与通过指针返回与通过引用传递结果的性能权衡。 有没有办法可靠地确定编译器是否将RVO用于给定的方法（当然，假设调用者不需要修改结果）？
作为一个原则，总是通过引用或指针传递大型结构。 喜欢通过不断的引用传递。 如果您正在使用指针，请考虑使用智能指针。
编译器倾向于如何识别caching？ 例如，是否值得重新sorting嵌套循环？
现代编译器非常了解指令caching（pipe道）并尽量避免重新加载。 你总是可以通过编写使用较less分支的代码（来自if ， switch ， 循环结构和函数调用 ）来协助你的编译器。
通过调整程序来优化数据caching，您可能会看到更显着的性能提升。 在networking上search数据驱动devise 。 关于这个话题有很多优秀的文章。
鉴于该计划的科学性，无处不在的浮点数。 我的代码中的一个重要瓶颈曾经是从浮点到整数的转换：编译器会发出代码来保存当前的舍入模式，更改它，执行转换，然后恢复旧的舍入模式 – 即使程序中没有任何内容曾改变舍入模式！ 禁用此行为显着加快了我的代码。 是否有类似的浮点相关陷阱我应该知道？
为了保证准确性，请将所有内容都保留double 只在必要时或在显示之前调整舍入。 这符合优化规则， 使用更less的代码，消除无关或死木代码 。
另请参阅上文有关在使用容器之前预留容器空间的部分。
一些处理器可以加载和存储浮点数，可以比整数更快或更快。 这需要在优化之前收集configuration文件数据。 然而，如果你知道有最小的分辨率，你可以使用整数，并改变你的基础到最小的分辨率。 例如，在处理美国货币时，整数可以用来代表美元的1/100或1/1000。
单独编译和链接C ++的一个后果就是编译器无法做到看起来非常简单的优化，比如strlen（）之类的方法调用超出了循环的终止条件。 有没有像这样的优化，我应该看看，因为它们不能由编译器完成，必须手工完成？
这是一个错误的假设。 编译器可以根据函数的签名进行优化，特别是在参数正确使用const 。 我总是喜欢通过在循环之外移动常量来协助编译器。 对于上限值（如string长度），请在循环之前将其分配给constvariables。 const修饰符将帮助优化器。
循环中总是有倒计时优化。 对于许多处理器来说，如果寄存器跳转等于零，则比比较 跳转更有效， 如果跳转小于则跳转 。
另一方面，是否有任何技术我应该避免，因为它们可能会干扰编译器自动优化代码的能力？
我会避免“微观优化”。 如果您有任何疑问，请在最高优化设置下打印由编译器生成的汇编代码（用于提问的区域）。 尝试重写代码以表示编译器的汇编代码。 如果可以的话，优化这个代码。 还有什么需要特定平台的指示。
优化理念和概念
计算机更喜欢执行顺序指令。
分支扰乱他们。 一些现代的处理器有足够的指令caching来包含小循环的代码。 如有疑问，请勿引起分支机构。
2.消除要求
更less的代码，更多的性能。
3.在代码之前优化devise通常，通过改变devise而不是改变devise的实现，可以获得更多的性能。 较less的devise可以减less代码，产生更多的性能。
4.考虑数据组织优化数据。
将经常使用的字段组织到substructures 。 设置数据大小以适应数据caching行 。 从数据结构中移除常量数据。
尽可能使用const说明符。
5.考虑页面交换操作系统会将您的程序或任务换成另一个。 经常进入硬盘上的“交换文件”。 将代码分解为包含大量执行代码和较less执行代码的块将有助于操作系统。 此外，将严重使用的代码凝结成更严格的单位。 这个想法是减less硬盘驱动器代码的交换（例如获取“远”function）。 如果代码必须换出，它应该是一个单元。
6.考虑I / O优化 （也包括文件I / O）。
大多数I / O比较less数据块的大块数据。 硬盘喜欢继续旋转。 较大的数据包比较小的数据包开销less。
将数据格式化成缓冲区，然后写入缓冲区。
7.消除竞争
摆脱与您的处理器应用程序竞争的任何程序和任务。 病毒扫描和播放音乐等任务。 即使是I / O驱动程序也需要一些操作（这就是为什么要减less数量或I / O事务）。
这些应该让你忙一会儿。 🙂
-
内存缓冲池的使用与dynamic分配相比可以带来巨大的性能优势。 更重要的是，如果他们减less或防止长时间执行运行的堆碎片。
-
注意数据的位置。 如果你有本地和全局数据的重要组合，你可能会超速caching机制。 尽量保持数据集靠近，以最大限度地利用caching行的有效性。
-
尽pipe编译器在循环中做了很好的工作，但是在性能调优时仍然仔细审视它们。 您可以发现在编译器只能削减百分比的情况下产生数量级的体系结构缺陷。
-
如果单个优先级队列在其操作中使用了大量时间，则可能有利于创build表示优先级桶的一组队列。 在这种情况下，将复杂的速度交易。
-
我注意到你没有提到使用SSEtypes指令。 他们可以适用于你的types的数字处理？
祝你好运。
这是一个很好的论文。
关于STL容器。
这里的大多数人声称STL提供了容器algorithm的最快实现之一。 而我则正好相反：对于大多数现实世界的场景，STL容器被当成是一个真正的灾难性的performance 。
人们争论STL中使用的algorithm的复杂性 。 这里STL是好的：O（1）为map / queue ，vector（amortized）和O（log（N））。 但是这不是典型应用程序性能的真正瓶颈！ 对于许多应用程序来说，真正的瓶颈是堆操作 （ malloc / free ， new / delete等）。
list典型操作仅需要几个CPU周期。 在map – 十几个，可能会更多（这当然取决于caching状态和日志（N））。 而且典型的堆操作是从成本上升到成千上万的CPU周期。 对于multithreading应用程序来说，他们也需要同步（互锁操作）。 另外在一些操作系统上（比如Windows XP），堆函数完全是在内核模式下实现的。
因此，典型场景中STL容器的实际性能主要取决于它们执行的堆操作的数量。 在这里他们是灾难性的。 不是因为他们执行得不好，而是因为他们的devise 。 那就是这是devise的问题。
另一方面有其他容器devise不同。 一旦我为自己的需要devise和编写这样的容器：
http://www.codeproject.com/KB/recipes/Containers.aspx
而且从性能的angular度来看，certificate了我的优越性，而不仅仅是。
但最近我发现我不是唯一一个想到这个的人。 boost::intrusive是以类似于我所做的方式实现的容器库。
我build议你尝试一下（如果你还没有的话）
用手工卷取代STL容器/algorithm有什么好处吗？
一般来说，除非你正在做一个糟糕的实现。 我不会因为您认为您可以编写更紧密的代码而replaceSTL容器或algorithm。 我只会在STL版本比需要解决问题更普遍时才这样做。 如果你可以写一个简单的版本来做你需要的，那么在那里可能会有一些速度。
我所看到的一个例外是将一个不需要线程同步的std :: stringreplace为copy-on-write std :: string。
对于需要大小未知但具有相当小的上限的std :: vectors，用静态分配的数组replace它们是否有利呢？
不太可能。 但是，如果您使用大量时间来分配特定大小，添加reserve（）调用可能是有利的。
性能权衡的价值返回大的临时数据结构与指针返回与传递结果参考。
当使用容器时，我为input和输出迭代器传递迭代器，这仍然非常普遍。
编译器倾向于如何识别caching？ 例如，是否值得重新sorting嵌套循环？
不是特别的。 是。 我发现错过的分支预测和caching恶意的内存访问模式是性能的两个最大的杀手（一旦你得到了合理的algorithm）。 很多旧的代码使用“提前”testing来减less计算。 但在现代处理器上，这往往比做math而忽略结果要昂贵。
我的代码中的一个重要瓶颈曾经是从浮点到整数的转换
对。 我最近发现了同样的问题。
单独编译和链接C ++的一个后果就是编译器无法做到看起来非常简单的优化，比如strlen（）之类的方法调用超出了循环的终止条件。
有些编译器可以处理这个问题。 Visual C ++有一个“链接时代码生成”选项，有效地重新调用编译器进行进一步的优化。 而且，在像strlen这样的函数的情况下，许多编译器会认识到这是一个固有的function。
有没有像这样的优化，我应该看看，因为它们不能由编译器完成，必须手工完成？ 另一方面，是否有任何技术我应该避免，因为它们可能会干扰编译器自动优化代码的能力？
当你在这个低级别进行优化时，几乎没有可靠的经验法则。 编译器会有所不同。 衡量你当前的解决scheme，并决定是否太慢。 如果是这样，就提出一个假设（例如，“如果用查找表来replace内部的if语句怎么办？”）。 这可能有助于（“消除由于分支预测失败导致的停顿”）或者可能会受到伤害（“查找访问模式损害caching一致性”）。 逐步实验和测量。
我经常克隆简单的实现，并使用#ifdef HAND_OPTIMIZED / #else / #endif在参考版本和调整版本之间切换。 这对于以后的代码维护和validation非常有用。 我承诺每个成功的实验都要改变控制，并且保留一个日志（电子表格），包含更改列表号，运行时间和每个优化步骤的解释。 当我更多地了解代码的行为时，日志可以很容易地备份和分支到另一个方向。
您需要一个运行可复制的时序testing的框架，并将结果与参考版本进行比较，以确保您不会无意中引入错误。
如果我正在研究这个问题，我会期待一个末端阶段，像caching区域和vector操作这样的事情将会发挥作用。
但是，在进入最后阶段之前，我希望能find一系列不同大小的问题，而这些问题与编译器级别的优化有关，而且更多的是做一些不可思议的事情，但是一旦发现，很容易修复。 通常他们围绕着类的过度devise和数据结构问题。
这是一个这样的过程的例子。
我发现使用迭代器的泛化容器类，原则上编译器可以优化到最小的周期，但由于某些不明确的原因，通常不会进行优化。 我也听说过这种情况发生的其他案件。
其他人曾经说过，在你做别的事之前，简介。 我同意这种做法，除了我认为有一个更好的方法，并在这个环节中表明。 每当我发现自己在问一些像STL这样的具体事情是否会成为问题时，我可能就是对的 – 但是 – 我在猜测 。 性能调优的基本胜利的想法是发现 ，不要猜测。 很容易找出什么是花时间，所以不要猜测。
这里有一些我用过的东西：
- 模板专门化最内层的循环边界（使他们真的很快）
- 使用
__restrict__关键字来处理别名问题 - 预先向默认值预留向量。
- 避免使用地图（它可以很慢）
- 向量追加/插入可以显着缓慢。 如果是这样的话，原始的操作可能会加快速度
- N字节内存alignment（英特尔的编译指示alignment， http://www.intel.com/software/products/compilers/docs/clin/main_cls/cref_cls/common/cppref_pragma_vector.htm ）
- 试图保持L1 / L2caching内的内存。
- 用NDEBUG编译
- 使用oprofileconfiguration文件，使用opannotate来查找特定的行（stl开销清晰可见）
这里是configuration文件数据的示例部分（所以你知道在哪里寻找问题）
* Output annotated source file with samples * Output all files * * CPU: Core 2, speed 1995 MHz (estimated) -- * Total samples for file : "/home/andrey/gamess/source/blas.f" * * 1020586 14.0896 -- * Total samples for file : "/home/andrey/libqc/rysq/src/fock.cpp" * * 962558 13.2885 -- * Total samples for file : "/usr/include/boost/numeric/ublas/detail/matrix_assign.hpp" * * 748150 10.3285 -- * Total samples for file : "/usr/include/boost/numeric/ublas/functional.hpp" * * 639714 8.8315 -- * Total samples for file : "/home/andrey/gamess/source/eigen.f" * * 429129 5.9243 -- * Total samples for file : "/usr/include/c++/4.3/bits/stl_algobase.h" * * 411725 5.6840 --
来自我的项目的代码示例
template<int ni, int nj, int nk, int nl> inline void eval(const Data::density_type &D, const Data::fock_type &F, const double *__restrict Q, double scale) { const double * __restrict Dij = D[0]; ... double * __restrict Fij = F[0]; ... for (int l = 0, kl = 0, ijkl = 0; l < nl; ++l) { for (int k = 0; k < nk; ++k, ++kl) { for (int j = 0, ij = 0; j < nj; ++j, ++jk, ++jl) { for (int i = 0; i < ni; ++i, ++ij, ++ik, ++il, ++ijkl) {
我认为任何人可以给你的主要提示是： 衡量 ， 衡量 ， 衡量 。 这和改善你的algorithm。
你使用某些语言特性的方式，编译器版本，std lib实现，平台，机器 – 都在性能上扮演着angular色，而且你还没有提到其中的许多特性，而且我们也没有人有过你的确切设置。
关于replacestd::vector ：使用drop-inreplace（例如， 这个 ），只是尝试一下。
编译器倾向于如何识别caching？ 例如，是否值得重新sorting嵌套循环？
我不能说所有的编译器，但是我使用GCC的经验表明，它不会针对caching大量优化代码。 我希望对大多数现代编译器来说这是真实的。 优化如重新sorting嵌套循环肯定会影响性能。 如果您认为自己的内存访问模式可能会导致许多caching未命中，那么调查此问题将对您有利。
用手工卷取代STL容器/algorithm有什么好处吗？ 特别是，我的程序包含一个非常大的优先级队列（目前是一个std :: priority_queue），其操作花费了大量的时间。 这是值得研究的东西，还是STL实现可能是最快的？
STL通常是最快的一般情况。 如果你有一个非常具体的案例，你可能会看到一个手卷的加速。 例如，std :: sort（通常为quicksort）是最快的一般sorting，但是如果事先知道您的元素实际上已经sorting了，那么插入sorting可能是更好的select。
沿着类似的路线，对于所需大小未知但具有相当小的上限的std :: vectors，用静态分配的数组replace它们是否有利呢？
这取决于你在哪里做静态分配。 我沿着这条线尝试的一件事就是静态分配堆栈上的大量内存，然后重新使用。 结果？ 堆内存要快得多。 仅仅因为一个物品在堆栈上并不能使访问速度更快 – 堆栈内存的速度也取决于caching等内容。 静态分配的全局数组可能不会比堆更快。 我假设你已经尝试过只保留上限的技术。 如果有很多具有相同上限的向量，请考虑通过包含数据成员的结构向量来改进caching。
我发现dynamic内存分配通常是一个严重的瓶颈，消除它会导致显着的加速。 因此，我很感兴趣的是，通过值返回大的临时数据结构与通过指针返回与通过引用传递结果的性能权衡。 Is there a way to reliably determine whether or not the compiler will use RVO for a given method (assuming the caller doesn't need to modify the result, of course)?
I personally normally pass the result in by reference in this scenario. It allows for a lot more re-use. Passing large data structures by value and hoping that the compiler uses RVO is not a good idea when you can just manually use RVO yourself.
How cache-aware do compilers tend to be? For example, is it worth looking into reordering nested loops?
I found that they weren't particularly cache-aware. The issue is that the compiler doesn't understand your program and can't predict the vast majority of it's state, especially if you depend heavily on heap. If you have a profiler that ships with your compiler, for example Visual Studio's Profile Guided Optimization, then this can produce excellent speedups.
Given the scientific nature of the program, floating-point numbers are used everywhere. A significant bottleneck in my code used to be conversions from floating point to integers: the compiler would emit code to save the current rounding mode, change it, perform the conversion, then restore the old rounding mode — even though nothing in the program ever changed the rounding mode! Disabling this behavior significantly sped up my code. Are there any similar floating-point-related gotchas I should be aware of?
There are different floating-point models – Visual Studio gives an fp:fast compiler setting. As for the exact effects of doing such, I can't be certain. However, you could try altering the floating point precision or other settings in your compiler and checking the result.
One consequence of C++ being compiled and linked separately is that the compiler is unable to do what would seem to be very simple optimizations, such as move method calls like strlen() out of the termination conditions of loop. Are there any optimization like this one that I should look out for because they can't be done by the compiler and must be done by hand?
I've never come across such a scenario. However, if you're genuinely concerned about such, then the option remains to do it manually. One of the things that you could try is calling a function on a const reference, suggesting to the compiler that the value won't change.
One of the other things that I want to point out is the use of non-standard extensions to the compiler, for example provided by Visual Studio is __assume. http://msdn.microsoft.com/en-us/library/1b3fsfxw(VS.80).aspx
There's also multithread, which I would expect you've gone down that road. You could try some specific opts, like another answer suggested SSE.
Edit: I realized that a lot of the suggestions I posted referenced Visual Studio directly. That's true, but, GCC almost certainly provides alternatives to the majority of them. I just have personal experience with VS most.
The STL priority queue implementation is fairly well-optimized for what it does, but certain kinds of heaps have special properties that can improve your performance on certain algorithms. Fibonacci heaps are one example. Also, if you're storing objects with a small key and a large amount of satellite data, you'll get a major improvement in cache performance if you store that data separately, even if it means storing one extra pointer per object.
As for arrays, I've found std::vector to even slightly out-perform compile-time-constant arrays. That said, its optimizations are general, and specific knowledge of your algorithm's access patterns may allow you to optimize further for cache locality, alignment, coloring, etc. If you find that your performance drops significantly past a certain threshold due to cache effects, hand-optimized arrays may move that problem size threshold by as much as a factor of two in some cases, but it's unlikely to make a huge difference for small inner loops that fit easily within the cache, or large working sets that exceed the size of any CPU cache. Work on the priority queue first.
Most of the overhead of dynamic memory allocation is constant with respect to the size of the object being allocated. Allocating one large object and returning it by a pointer isn't going to hurt much as much as copying it. The threshold for copying vs. dynamic allocation varies greatly between systems, but it should be fairly consistent within a chip generation.
Compilers are quite cache-aware when cpu-specific tuning is turned on, but they don't know the size of the cache. If you're optimizing for cache size, you may want to detect that or have the user specify it at run-time, since that will vary even between processors of the same generation.
As for floating point, you absolutely should be using SSE. This doesn't necessarily require learning SSE yourself, as there are many libraries of highly-optimized SSE code that do all sorts of important scientific computing operations. If you're compiling 64-bit code, the compiler might emit some SSE code automatically, as SSE2 is part of the x86_64 instruction set. SSE will also save you some of the overhead of x87 floating point, since it's not converting back and forth to 80-bit values internally. Those conversions can also be a source of accuracy problems, since you can get different results from the same set of operations depending on how they get compiled, so it's good to be rid of them.
If you work on big matrices for instance, consider tiling your loops to improve the locality. This often leads to dramatic improvements. You can use VTune/PTU to monitor the L2 cache misses.
One consequence of C++ being compiled and linked separately is that the compiler is unable to do what would seem to be very simple optimizations, such as move method calls like strlen() out of the termination conditions of loop. Are there any optimization like this one that I should look out for because they can't be done by the compiler and must be done by hand?
On some compilers this is incorrect. The compiler has perfect knowledge of all code across all translation units (including static libraries) and can optimize the code the same way it would do if it were in a single translation unit. A few ones that support this feature come to my mind:
- Microsoft Visual C++ compilers
- Intel C++ Compiler
- LLVC-GCC
- GCC (I think, not sure)
i'm surprised no one has mentioned these two:
-
Link time optimization clang and g++ from 4.5 on support link time optimizations. I've heard that on g++ case, the heuristics is still pretty inmature but it should improve quickly since the main architecture is laid out.
Benefits range from inter procedural optimizations at object file level, including highly sought stuff like inling of virtual calls (devirtualization)
-
Project inlining this might seem to some like very crude approach, but it is that very crudeness which makes it so powerful: this amounts at dumping all your headers and .cpp files into a single, really big .cpp file and compile that; basically it will give you the same benefits of link-time optimization in your trip back to 1999. Of course, if your project is really big, you'll still need a 2010 machine; this thing will eat your RAM like there is no tomorrow. However, even in that case, you can split it in more than one no-so-damn-huge .cpp file
If you are doing heavy floating point math you should consider using SSE to vectorize your computations if that maps well to your problem.
Google SSE intrinsics for more information about this.
Here is something that worked for me once. I can't say that it will work for you. I had code on the lines of
switch(num) { case 1: result = f1(param); break; case 2: result = f2(param); break; //... }
Then I got a serious performance boost when I changed it to
// init: funcs[N] = {f1, f2 /*...*/}; // later in the code: result = (funcs[num])(param);
Perhaps someone here can explain the reason the latter version is better. I suppose it has something to do with the fact that there are no conditional branches there.
My current project is a media server, with multi thread processing (C++ language). It's a time critical application, once low performance functions could cause bad results on media streaming like lost of sync, high latency, huge delays and so.
The strategy i usually use to grantee the best performance possible is to minimize the amount of heavy operational system calls that allocate or manage resources like memory, files, sockets and so.
At first i wrote my own STL, network and file manage classes.
All my containers classes ("MySTL") manage their own memory blocks to avoid multiple alloc (new) / free (delete) calls. The objects released are enqueued on a memory block pool to be reused when needed. On that way i improve performance and protect my code against memory fragmentation.
The parts of the code that need to access lower performance system resources (like files, databases, script, network write) i use separate threads for them. But not one thread for each unit (like not 1 thread for each socket), if so the operational system would lose performance while managing a high number of threads. So you can group objects of same classes to be processed on a separate thread if possible.
For example, if you have to write data to a network socket, but the socket write buffer is full, i save the data on a sendqueue buffer (which shares memory with all sockets together) to be sent on a separate thread as soon as the sockets become writeable again. At this way your main threads should never stop processing on a blocked state waiting for the operational system frees a specific resource. All the buffers released are saved and reused when needed.
After all a profile tool would be welcome to look for program bottles and shows which algorithms should be improved.
i got succeeded using that strategy once i have servers running like 500+ days on a linux machine without rebooting, with thousands users logging everyday.
[02:01] -alpha.ip.tv- Uptime: 525days 12hrs 43mins 7secs
