32

几年前，我参加了一个小组，该小组正在面试一个相对高级的嵌入式 C 程序员职位的候选人。

我问的标准问题之一是关于优化技术。我很惊讶有些候选人没有答案。

所以，为了给后代整理一份清单——在优化 C 程序时，您通常使用哪些技术和结构？

速度和尺寸优化的答案都被接受。

4

23 回答 23

40

第一要务——不要过早优化。花时间仔细优化一段代码却发现它并不是您认为的瓶颈，这种情况并不少见。或者，换一种说法“在你让它快速之前，让它工作”

在优化代码之前调查是否有任何优化算法的选项。通过优化一个糟糕的算法比优化代码更容易找到性能的改进，然后当你改变算法时才把它扔掉。

并首先弄清楚为什么需要优化。你想达到什么目的？例如，如果您正在尝试改善对某些事件的响应时间，请确定是否有机会更改执行顺序以最小化时间关键区域。例如，当试图改善对某些外部中断的响应时，您可以在事件之间的死区时间做任何准备吗？

一旦你决定需要优化代码，你会优化哪一点？使用分析器。将注意力（首先）集中在最常用的区域上。

那么你能对这些领域做些什么呢？

  • 尽量减少条件检查。检查条件（例如循环的终止条件）是没有花在实际处理上的时间。条件检查可以通过循环展开等技术最小化。
  • 在某些情况下，条件检查也可以通过使用函数指针来消除。例如，如果您正在实现一个状态机，您可能会发现将各个状态的处理程序实现为小函数（具有统一的原型）并通过存储下一个处理程序的函数指针来存储“下一个状态”比使用带有在单个 case 语句中实现的处理程序代码的大型 switch 语句。YMMV。
  • 最小化函数调用。函数调用通常会带来上下文保存的负担（例如，将寄存器中包含的局部变量写入堆栈，保存堆栈指针），因此如果您不必进行调用，则可以节省时间。一种选择（如果您正在优化速度而不是空间）是使用内联函数。
  • 如果函数调用是不可避免的，则最小化传递给函数的数据。例如，传递指针可能比传递结构更有效。
  • 在优化速度时，选择适合您平台的本机大小的数据类型。例如，在 32 位处理器上，处理 32 位值可能比 8 位或 16 位值更有效。（旁注 - 值得检查编译器是否正在执行您认为的操作。我曾遇到过一些情况，我发现我的编译器坚持对 8 位值进行 16 位算术运算，并进行所有的 to 和 from 转换和他们一起去）
  • 查找可以预先计算的数据，并在初始化期间或（更好）在编译时计算。例如，在实现 CRC 时，您可以即时计算 CRC 值（直接使用多项式），这对于大小来说非常有用（但对性能来说很糟糕），或者您可以生成所有中间值的表格 - 这是更快的实施，以损害大小。
  • 本地化您的数据。如果您经常处理大量数据，您的处理器可能能够通过将其全部存储在缓存中来加快处理速度。并且您的编译器可能能够使用适合更多本地化数据的较短指令（例如，使用 8 位偏移而不是 32 位的指令）
  • 同样，本地化您的功能。出于同样的原因。
  • 找出您可以对正在执行的操作做出的假设，并找到利用它们的方法。例如，在 8 位平台上，如果您对 32 位值执行的唯一操作是增量，您可能会发现通过专门为此目的内联（或创建宏）可以比编译器做得更好，而不是使用普通的算术运算。
  • 避免昂贵的指令——除法就是一个典型的例子。
  • “register”关键字可以是您的朋友（尽管希望您的编译器对您的寄存器使用有一个很好的了解）。如果您要使用“注册”，您可能必须先声明要“注册”的局部变量。
  • 与您的数据类型保持一致。如果您正在对混合数据类型（例如，shorts 和 ints、double 和 float）进行算术运算，那么编译器将为每个不匹配添加隐式类型转换。这是浪费的 CPU 周期，可能没有必要。

上面列出的大多数选项都可以用作正常练习的一部分，而不会产生任何不良影响。但是，如果您真的想获得最佳性能： - 调查可以（安全地）禁用错误检查的位置。不建议这样做，但它会为您节省一些空间和周期。- 在汇编程序中手工制作部分代码。这当然意味着您的代码不再是可移植的，但如果这不是问题，您可能会在这里找到节省。请注意，将数据移入和移出您可以使用的寄存器可能会浪费时间（即满足编译器的寄存器使用）。另请注意，您的编译器本身应该做得很好。（当然，也有例外）

于 2008-09-21T11:42:37.160 回答
27

正如其他人所说：配置文件，配置文件配置文件。

至于实际技术，我认为尚未提及的一种技术：

冷热数据分离：保持在 CPU 的缓存中非常重要。帮助做到这一点的一种方法是将数据结构拆分为经常访问（“热”）和很少访问（“冷”）的部分。

一个例子：假设你有一个看起来像这样的客户结构：

struct Customer
{
    int ID;
    int AccountNumber;
    char Name[128];
    char Address[256];
};

Customer customers[1000];

现在，让我们假设您想访问很多 ID 和 AccountNumber，但不想访问姓名和地址。你要做的就是把它分成两部分：

struct CustomerAccount
{
    int ID;
    int AccountNumber;
    CustomerData *pData;
};

struct CustomerData
{
    char Name[128];
    char Address[256];
};

CustomerAccount customers[1000];

这样，当您遍历“客户”数组时，每个条目只有 12 个字节，因此您可以在缓存中容纳更多条目。如果您可以将其应用于渲染引擎的内部循环等情况，这将是一个巨大的胜利。

于 2008-09-22T11:49:01.020 回答
20

我最喜欢的技术是使用好的分析器。如果没有一个好的配置文件告诉你瓶颈在哪里，没有任何技巧和技术可以帮助你。

于 2008-09-21T10:07:20.180 回答
15

我遇到的最常见的技术是：

  • 循环展开
  • 循环优化以获得更好的缓存预取（即在 M 个周期中执行 N 次操作，而不是 NxM 单次操作）
  • 数据对齐
  • 内联函数
  • 手工制作的 asm 片段

至于一般性建议，大部分已经响起：

  • 选择更好的算法
  • 使用分析器
  • 如果不能提高 20-30% 的性能，就不要优化
于 2008-09-21T10:07:48.417 回答
8

对于低级优化：

  1. 来自 ffmpeg 的 START_TIMER/STOP_TIMER 宏（用于测量任何代码的时钟级精度）。
  2. Oprofile，当然，用于分析。
  3. 大量手工编码的程序集（只需在 x264 的 /common/x86 目录上执行 wc -l，然后记住大部分代码都是模板化的）。
  4. 仔细编码；更短的代码通常更好。
  5. 智能低级算法，比如我写的 64 位比特流写入器，它只使用一个 if 而不使用 else。
  6. 显式写入组合。
  7. 考虑到处理器的重要怪异方面，例如英特尔的缓存线拆分问题。
  8. 寻找可以无损或几乎无损地进行提前终止的情况，其中提前终止检查的成本远低于人们从中获得的速度。
  9. 实际上内联程序集用于更适合 x86 SIMD 单元的任务，例如中位数计算（需要编译时检查以支持 MMX）。
于 2008-09-21T10:20:55.140 回答
5
  • 首先，使用更好/更快的算法。优化设计缓慢的代码是没有意义的。
  • 在优化速度时，以内存换速度：查找预计算值表、二叉树、编写更快的自定义系统调用实现......
  • 以速度换内存时：使用内存压缩
于 2008-09-21T10:08:34.733 回答
4

避免使用堆。对相同大小的对象使用 obstacks 或 pool-allocator。将生命周期短的小东西放入堆栈。alloca 仍然存在。

于 2008-09-21T10:20:34.657 回答
4

未成熟的优化是万恶之源！;)

于 2008-09-21T10:21:29.883 回答
4

由于我的应用程序在设计上通常不需要太多 CPU 时间，因此我专注于我的二进制文件在磁盘和内存中的大小。我主要做的是寻找静态大小的数组，并用动态分配的内存替换它们，这值得稍后释放内存的额外努力。为了减少二进制文件的大小，我寻找在编译时初始化的大数组并将初始化放到运行时。

char buf[1024] = { 0, };
/* becomes: */
char buf[1024];
memset(buf, 0, sizeof(buf));

这将从二进制文件 .DATA 部分中删除 1024 个零字节，并将在运行时在堆栈上创建缓冲区并用零填充它。

编辑：哦，是的，我喜欢缓存东西。它不是特定于 C 的，但取决于您缓存的内容，它可以极大地提高性能。

PS：请在您的清单完成后告诉我们，我很好奇。;)

于 2008-09-21T10:31:10.747 回答
4

如果可能，请与 0 进行比较，而不是与任意数字进行比较，尤其是在循环中，因为与 0 的比较通常使用单独的、更快的汇编程序命令来实现。

例如，如果可能，写

for (i=n; i!=0; --i) { ... }

代替

for (i=0; i!=n; ++i) { ... }
于 2008-09-22T10:55:01.103 回答
3

这些天来，优化中最重要的事情是：

  • 尊重缓存 - 尝试以简单的模式访问内存，不要为了好玩而展开循环。使用数组而不是具有大量指针追逐的数据结构，对于少量数据可能会更快。并且不要做太大的事情。
  • 避免延迟 - 如果其他计算立即依赖于它们，请尽量避免分裂和缓慢的东西。依赖于其他内存访问（即 a[b[c]]）的内存访问是不好的。
  • 避免不可预测性 - 许多具有不可预测条件或引入更多延迟的条件的 if/else 真的会让您感到困惑。这里有很多有用的无分支数学技巧，但它们会增加延迟，并且只有在你真的需要它们时才有用。否则，只需编写简单的代码，不要有疯狂的循环条件。

不要为涉及复制和粘贴代码（如循环展开）或手动重新排序循环的优化而烦恼。编译器在这方面通常比你做得更好，但它们中的大多数都不够聪明，无法撤消它。

于 2008-10-16T21:44:16.553 回答
3

基础/一般：

  • 没有问题时不要优化。
  • 了解您的平台/CPU...
  • ...彻底了解
  • 了解您的 ABI
  • 让编译器进行优化，只是帮助它完成这项工作。

一些实际有帮助的事情：

选择大小/内存：

  • 使用位域存储布尔值
  • 通过覆盖联合重用大型全局数组（小心）

选择速度（小心）：

  • 尽可能使用预先计算好的表
  • 将关键功能/数据放在快速存储器中
  • 为常用的全局变量使用专用寄存器
  • 计数为零，零标志是免费的
于 2008-09-21T12:20:24.590 回答
3

很难概括...

  • 数据结构：

    • 根据使用情况拆分数据结构非常重要。常见的结构是保存基于流控制访问的数据。这种情况可以显着降低缓存使用率。
    • 考虑缓存行大小和预取规则。
    • 重新排序结构的成员以从您的代码中获得对它们的顺序访问

  • 算法：

    • 花时间思考您的问题并找到正确的算法。
    • 了解您选择的算法的局限性（对 10 个要排序的元素进行基数排序/快速排序可能不是最佳选择）。

  • 低级：

    • 至于最新的处理器，不建议展开体积​​较小的循环。处理器为此提供了自己的检测机制，并将使其流水线的整个部分短路。
    • 相信硬件预取器。当然，如果您的数据结构设计良好；）
    • 关心您的 L2 缓存行未命中。
    • 尽量减少应用程序的本地工作集，因为处理器倾向于每个内核的缓存更小（C2D 享受每个内核最大 3MB，而 iCore7 将提供每个内核最大 256KB + 8MB 共享给所有内核四核芯片。）。

最重要的是：尽早测量，经常测量并且永远不会做出假设，将您的思考和优化基于分析器检索到的数据（请使用PTU）。

另一个提示，性能是应用程序成功的关键，应该在设计时考虑，并且应该有明确的性能目标。

这远非详尽无遗，但应该提供一个有趣的基础。

于 2008-09-21T12:36:12.600 回答
3

还有一点没有提到：

  • 了解您的需求：不要针对不太可能或永远不会发生的情况进行优化，专注于最大的收益
于 2008-09-21T10:35:19.227 回答
2

在我工作的大多数嵌入式系统上，没有分析工具，所以说使用分析器很好，但不是很实用。

速度优化的第一条规则是—— 找到你的关键路径。
通常你会发现这条路并没有那么长，也没有那么复杂。很难以通用的方式说如何优化它，这取决于你在做什么以及你有能力做什么。例如，您通常希望避免在关键路径上使用 memcpy，因此您需要使用 DMA 或优化，但是如果您的硬件没有 DMA 怎么办？如果不重写它，请检查 memcpy 实现是否是最好的。
根本不要在嵌入式中使用动态分配，但如果出于某种原因这样做，请不要在关键路径中使用。
正确组织您的线程优先级，正确的是真正的问题，并且显然是系统特定的。
我们使用非常简单的工具来分析瓶颈，存储时间戳和索引的简单宏。在 90% 的情况下，很少 (2-3) 次运行会找到您花费时间的地方。
最后一个是代码审查 ，非常重要。在大多数情况下，我们在代码审查期间避免性能问题是非常有效的方法:)

于 2008-09-21T11:44:02.913 回答
2
  1. 衡量绩效。
  2. 使用现实和重要的基准。请记住“对于小 N 来说一切都很快”。
  3. 使用分析器查找热点。
  4. 减少动态内存分配、磁盘访问、数据库访问、网络访问和用户/内核转换的数量，因为这些往往是热点。
  5. 衡量绩效。

此外，您应该衡量性能。

于 2008-09-21T16:42:30.793 回答
2

收集代码执行的配置文件可以让你完成 50% 的工作。其他 50% 负责分析这些报告。

此外，如果您使用 GCC 或 VisualC++，您可以使用“配置文件引导优化”，编译器将从以前的执行中获取信息并重新安排指令以使 CPU 更快乐。

于 2008-09-21T10:06:52.443 回答
2

内联函数！受到分析爱好者的启发，我分析了我的一个应用程序，发现了一个小函数，可以对 MP3 帧进行一些位移。它在我的应用程序中进行了大约 90% 的函数调用，因此我将其设为内联，瞧——该程序现在使用的 CPU 时间是以前的一半。

于 2008-09-21T11:24:23.583 回答
2

有时你必须决定你追求的是更多的空间还是更快的速度，这将导致几乎相反的优化。例如，为了充分利用空间，您可以打包结构，例如#pragma pack(1)，并在结构中使用位字段。为了获得更高的速度，您可以打包以符合处理器偏好并避免位域。

另一个技巧是通过 realloc 为增长的数组选择正确的大小调整算法，或者更好地根据您的特定应用程序编写自己的堆管理器。不要假设编译器附带的那个是每个应用程序的最佳解决方案。

于 2008-10-02T12:17:14.900 回答
2

如果有人对这个问题没有答案，那可能是他们知道的不多。

也可能是他们知道很多。我知道很多（恕我直言：-），如果我被问到这个问题，我会问你：你为什么认为这很重要？

问题是，任何关于性能的先验概念，如果它们没有受到特定情况的影响，那么根据定义，它们都是猜测。

我认为了解编码技术以提高性能很重要，但我认为知道不使用它们更重要，直到诊断表明存在问题以及问题是什么。

现在我要自相矛盾地说，如果你这样做，你将学习如何识别导致麻烦的设计方法，以便避免它们，对于新手来说，这听起来像是过早的优化。

举一个具体的例子，这是一个经过优化的 C 应用程序。

于 2009-09-17T21:21:02.203 回答
1

有时谷歌是最好的算法优化工具。当我遇到一个复杂的问题时，稍微搜索一下就会发现一些拥有博士学位的人已经找到了这个问题和一个众所周知的问题之间的映射，并且已经完成了大部分工作。

于 2009-11-04T12:32:27.357 回答
1

很棒的清单。我将添加一个我在上面列表中没有看到的提示，在某些情况下可以以最小的成本产生巨大的优化。

  • 绕过链接器

    如果您有一些应用程序分为两个文件，比如 main.c 和 lib.c，在许多情况下，您只需\#include "lib.c"在 main.c 中添加一个，这将完全绕过链接器并允许对编译器进行更有效的优化。

优化文件之间的依赖关系可以达到同样的效果，但更改的成本通常更高。

于 2009-09-18T12:06:29.457 回答
0

I would recommend optimizing using more efficient algorithms and not do it as an afterthought but code it that way from the start. Let the compiler work out the details on the small things as it knows more about the target processor than you do.

For one, I rarely use loops to look things up, I add items to a hashtable and then use the hashtable to lookup the results.

For example you have a string to lookup and then 50 possible values. So instead of doing 50 strcmps, you add all 50 strings to a hashtable and give each a unique number ( you only have to do this once ). Then you lookup the target string in the hashtable and have one large switch with all 50 cases ( or have functions pointers ).

When looking up things with common sets of input ( like css rules ), I use fast code to keep track of the only possible solitions and then iterate thought those to find a match. Once I have a match I save the results into a hashtable ( as a cache ) and then use the cache results if I get that same input set later.

My main tools for faster code are:

hashtable - for quick lookups and for caching results

qsort - it's the only sort I use

bsp - for looking up things based on area ( map rendering etc )

于 2008-09-21T15:07:20.630 回答