提高时间关键代码的技巧

  • 项目

编写快速代码需要了解应用程序的所有方面和它如何与系统交互。 本文建议的方法可替代一些更明显的编码方法，帮助确保代码的时间关键部分满意地执行。

总而言之，提高时间关键代码需要：

  • 知道程序的哪个部分必须快。

  • 知道代码的大小和速度。

  • 知道新功能的成本。

  • 知道完成工作所需的最小工作量。

若要收集有关代码性能的信息，可以使用性能监视器 (perfmon.exe)。

本文章有以下部分

缓存未命中和页错误

缓存未命中不论出现在内部缓存中，还是出现在外部缓存中，都会降低程序的性能；而页错误由于会转到二级存储中获得程序指令和数据，也会降低程序的性能。

CPU 缓存命中可以花费程序 10-20 个时钟周期。 外部缓存命中可以花费 20-40 个时钟周期。 页错误可以花费 1,000,000 个时钟周期（假定处理器每秒处理 500,000,000 个指令并且一个页错误是 2 毫秒）。 因此，编写减少缓存未命中和页错误数的代码对程序执行最重要。

程序慢的一个原因是它们接受的页错误比需要的多，或者未命中缓存的频率比需要的高。 为避免此问题，使用具有良好引用地址的数据结构很重要，这意味着将相关的事物合在一起。 有时看上去很棒的数据结构由于引用地址不好而变得很糟，有时正好相反。 这里是两个示例：

  • 动态分配的链接表可以降低程序性能。 当搜索项或者在表中遍历到末尾时，每个跳过的链接都可能未命中缓存或导致页错误。 基于简单数组的列表实现可能会更快，因为存在更适用的缓存和更少的页面错误。 即使考虑到数组更难增长的事实，该列表实现仍然可能会更快。

  • 使用动态分配的链接表的哈希表可以降低性能。 通过扩展，使用动态分配的链接表存储内容的哈希表的性能可能显著降低。 事实上，在最后的分析中，通过数组的简单线性搜索实际上可能更快（取决于具体的情况）。 使用基于数组的哈希表（所谓的“关闭散列”）是通常具有极佳的性能但却经常被忽略的实现。

排序和搜索

与许多典型的操作相比，排序本身就很耗时。 避免不必要减速的最好办法是避免在关键时间排序。 你可能能够执行以下操作：

  • 将排序推迟到非性能关键时间。

  • 在更早的、非性能关键的时间排序数据。

  • 只排序数据中真正需要排序的部分。

有时，可以按排序顺序生成列表。 注意，因为如果需要按排序顺序插入数据，则可能需要具有较差引用地址的更复杂的数据结构，从而导致缓存未命中和页错误。 没有适用于所有情况的方法。 试用几种方法并测试差异。

这里有一些通用的排序技巧：

  • 使用常用排序将 Bug 减到最少。

  • 任何可以预先减少排序复杂性的工作都是值得做的。 如果一次性经过数据可简化比较和减少从 O(n log n) 到 O(n) 的排序，则几乎可以肯定将先行一步。

  • 考虑排序算法的引用地址和预期其涉及的数据。

与排序相比搜索的选择更少。 如果搜索是时间关键的，二进制搜索或者哈希表查找几乎总是最好的，但是与排序一样，必须记住地址。 如果二进制文件搜索通过的数据结构具有许多导致页错误或缓存未命中的指针，则通过小数组的线性搜索可以比二进制文件搜索快。

MFC 和类库

Microsoft 基础类 (MFC) 可以在很大程度上简化代码的编写。 当编写时间关键代码时，应该注意一些类中的固有系统开销。 检查时间关键代码使用的 MFC 代码，查看它是否满足性能需求。 下面的列表标识了应该注意的 MFC 类和函数：

  • CString MFC 调用 C 运行时库以为 CString 动态分配内存。 一般而言，CString 与其他任何动态分配的字符串一样有效。 与任何动态分配的字符串一样，它也有动态分配和释放的系统开销。 通常，堆栈上的简单 char 数组可以达到同样的目的，而且速度更快。 不要使用 CString 存储常数字符串。 请改用 const char *。 使用 CString 对象执行的任何操作都有一些系统开销。 使用运行时库字符串函数可能更快。

  • CArrayCArray 提供了规则数组不具备的灵活性，但是程序可能不需要它。 如果知道数组的特定限制，反而可以使用全局固定数组。 如果使用 CArray，当需要重新分配时，使用 CArray::SetSize 建立它的大小并指定增长的元素数。 否则，添加元素可能导致数组经常重新分配和复制，这样做效率很低而且可能产生内存碎片。 此外，如果将一项插入数组中，则 CArray 移动内存中后面的项并且可能需要增长数组。 这些操作可能导致缓存未命中和页错误。 如果浏览 MFC 使用的代码，你可能会发现可编写一些更特定于方案的内容以提高性能。 例如，由于 CArray 是一个模板，可以提供特定类型的 CArray 专用化。

  • CListCList 是双向链接列表，因此在列表的头、尾和已知位置 (POSITION) 可以很快地插入元素。 按值或索引查找需要顺序搜索，但是，如果列表很长，则搜索速度可能会较慢。 如果代码不要求双向链接列表，则可能需要重新考虑使用 CList。 使用单向链接表可省去更新所有操作的附加指针以及该指针的内存的系统开销。 这种额外内存并不大，但却是解决缓存未命中或页错误的另一种可能的方法。

  • IsKindOf 该函数可以在不同的数据区域中生成许多调用和访问内存，从而导致极差的引用地址。 它对于调试版本是有用的（例如，在 ASSERT 调用中），但应尽量避免在发布版本中使用它。

  • PreTranslateMessage 当特定的窗口目录树需要不同的键盘快捷键或者必须将消息处理插入到消息泵中时，可使用 PreTranslateMessage。 PreTranslateMessage 更改 MFC 调度消息。 如果重写 PreTranslateMessage，只在需要的级别上这样做。 例如，如果只对转到特定视图子级的消息感兴趣，则不必替代 CMainFrame::PreTranslateMessage。 而应重写视图类的 PreTranslateMessage。

    不要为了规避正常调度路径而使用 PreTranslateMessage 处理发送到任何窗口的任何消息。 为实现此目的，应使用窗口过程和 MFC 消息映射。

  • OnIdle 空闲事件可能在预期外的时候发生，例如在 WM_KEYDOWN 和 WM_KEYUP 事件之间。 计时器可能是触发代码的更有效方法。 不要强制 OnIdle 通过生成错误信息或者总是从 TRUE 的替代返回 OnIdle 被反复调用，它从来都不允许线程休眠。 同样，计时器或者单独的线程可能更合适。

共享库

代码重用是需要的。 然而，如果打算使用他人的代码，则应确保完全知道此代码在那些性能对你很重要的情况中的作用。 了解这一点的最好方法是通过单步执行源代码，或者用 PView 或性能监视器这类工具测量。

堆

使用多个堆来做出判断。 使用 HeapCreate 和 HeapAlloc 创建的附加堆使你可以管理并因而释放一组相关分配。 不要分配出太多内存。 如果使用多个堆，特别注意开始时分配出的内存量。

作为替代使用多个堆的方法，可以使用 Helper 函数在代码和默认堆之间建立连接。 Helper 函数有利于可以提高应用程序性能的自定义分配策略。 例如，如果经常执行小的分配，可能需要将这些分配固定在默认堆的一部分内。 可以分配大的内存块，然后使用 Helper 函数从该块子分配。 然后，由于分配出自默认堆，所以没有包含未用内存的附加堆。

然而，在某些情况下，使用默认堆可以减少引用地址。 使用 Process Viewer、Spy++ 或性能监视器测量在堆之间移动对象的效果。

测量堆以便可以解决堆上的每个分配。 使用 C 运行时调试堆例程对堆执行检查点并转储它。 可以将输出读入像 Microsoft Excel 这样的电子表格程序并使用数据透视表查看结果。 注意分配的总数、大小和分布。 将这些结果同工作集的大小进行比较。 还要注意相关大小对象的群集。

还可以使用性能计数器监视内存使用。

线程

对于后台任务，有效的事件空闲处理可能比使用线程更快。 了解单线程程序中的引用地址更容易。

好的经验法则是仅当阻止的操作系统通知是后台工作的根本时才使用线程。 在这种情况下，线程是最好的解决方法，因为阻止事件的主线程是不实际的。

线程也提出了通信问题。 必须用消息列表或者通过分配和使用共享内存，管理线程间的通信链接。 管理通信链接通常需要同步以避免争用条件和死锁问题。 此复杂性可以很容易转变为 Bug 和性能问题。

有关详细信息，请参阅空闲循环处理和多线程。

小工作集

较小的工作集意味着更好的引用地址、更少的页错误和更多的缓存命中。 进程工作集是操作系统为测量引用地址直接提供的最接近的尺度。

另请参阅

优化代码