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

我提出的标准问题之一是关于优化技术。有些候选人没有答案，这让我感到非常惊讶。

因此，为了将后代列表汇总在一起，在优化C程序时通常使用哪些技术和构造？

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

解决方案

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

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

我最喜欢的技术是使用良好的探查器。没有良好的形象可以告诉我们瓶颈所在，没有任何技巧和技术将对我们有所帮助。

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

• 循环展开
• 循环优化以实现更好的缓存预取(即以M个周期执行N次操作，而不是NxM个奇异操作)
• 数据对齐
• 内联函数
• 手工制作的asm片段

至于一般性建议，大多数建议已被采纳：

• 选择更好的算法
• 使用探查器
• 如果不能提供20-30％的性能提升，请不要进行优化

• 首先，请使用更好/更快的算法。没有必要优化设计会很慢的代码。
• 在优化速度时，将内存换为速度：预计算值的查找表，二叉树，编写更快的系统调用自定义实现...
• 交换内存速度时：使用内存压缩

避免使用堆。将obstacks或者pool-allocator用于相同大小的对象。将寿命短的小物件放到堆栈上。 alloca仍然存在。

对于低级优化：

• ffmpeg中的START_TIMER / STOP_TIMER宏(用于测量任何代码的时钟级精度)。
• Oprofile，当然是用于分析。
• 大量的手工编码程序集(只需在x264的/ common / x86目录上执行wc -l，然后记住大多数代码是模板化的)。
• 仔细的编码；较短的代码通常更好。
• 智能低级算法，例如我编写的64位比特流编写器，它仅使用一个if，如果没有，则不使用。
• 显式写合并。
• 考虑到处理器的重要怪异方面，例如英特尔的缓存行拆分问题。
• 寻找可以无损或者几乎无损地进行尽早解雇的情况，尽早解雇检查的费用远低于从中获得的速度。
• 实际上是内联汇编，用于更适合x86 SIMD单元的任务，例如中值计算(需要对MMX支持进行编译时检查)。

过早的优化是万恶之源！
;)

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

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

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

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

PS：请让我们知道清单填写完毕后，我很好奇。 ;)

没有提到的另一件事：

• 了解要求：不要针对不太可能或者永远不会发生的情况进行优化，专注于最大的收益

内联函数！在这里，我受到了性能分析爱好者的启发，介绍了我的一个应用程序，发现了一个小功能，可以对MP3帧进行一些移位。在我的应用程序中，它执行了所有函数调用的90％，因此我将其内联，因此程序现在使用的CPU时间是以前的一半。

首先，第一件事不要太早优化。花时间仔细地优化代码块，以发现它并不是我们认为的瓶颈，这并不少见。或者，换一种方式说："在快速实现之前，先使其工作"

在优化代码之前，调查是否有任何优化算法的选项。通过优化较差的算法来发现性能的提高比优化代码要容易得多，然后要在无论如何更改算法时都将其丢弃。

并弄清楚为什么需要首先进行优化。我们想达到什么目的？如果我们要尝试改善某些事件的响应时间，则可以尝试更改执行顺序以最大程度地减少时间紧迫的区域。例如，当尝试改善对某些外部中断的响应时，我们可以在事件之间的停滞时间内做任何准备吗？

一旦确定需要优化代码，我们会优化哪一点？使用探查器。首先将注意力集中在最常用的区域上。

那么我们可以在那些方面做些什么呢？

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

上面列出的大多数选项都可以用作常规操作的一部分，而不会造成任何不良影响。但是，如果我们确实想获得最佳性能，请执行以下操作：
研究可以(安全)禁用错误检查的位置。不建议这样做，但是这样可以节省一些空间和周期。
在汇编器中手工处理部分代码。当然，这意味着代码不再可移植，但是在没有问题的地方，我们可以在这里找到节省的地方。请注意，将数据移入和移出我们可以使用的寄存器可能会浪费时间(即，满足编译器的寄存器使用率)。还应注意，编译器应独自完成出色的工作。 (当然，也有例外)

在我工作过的大多数嵌入式系统上，没有性能分析工具，因此可以说使用事件探查器很好，但不是很实用。

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

基本/一般：

• 没有问题时不要优化。
• 了解平台/ CPU ...
• ...彻底了解
• 知道你的ABI
• 让编译器进行优化，仅在完成工作时提供帮助。

实际上有帮助的一些事情：

选择大小/内存：

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

选择速度(注意)：

• 尽可能使用预先计算的表
• 将关键功能/数据放置在快速存储器中
• 将专用寄存器用于经常使用的全局变量
• 计数到零，零标志是免费的

难以总结...

• 要考虑缓存行大小和预取规则。
• 重新排序结构的成员以从代码中获得对它们的顺序访问
• 了解我们选择的算法的局限性(对10个要排序的元素进行基数排序/快速排序可能不是最佳选择)。
• 信任硬件预取器。当然，如果数据结构设计合理；)
• 关心L2缓存行未命中。
• 尝试尽可能减少应用程序的本地工作集，因为处理器倾向于每个核心使用较小的缓存(C2D享受每个核心最大3MB的内存，其中iCore7将为每个核心提供最大256KB的内存，并为所有核心共享8MB的内存。四芯模具。)。

最重要的是：尽早测量，永远不做任何假设，根据分析器检索的数据进行思考和优化(请使用PTU)。

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

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

我建议我们使用更高效的算法进行优化，而不是事后才想到，而是从一开始就以这种方式进行编码。让编译器解决一些小问题的细节，因为它比我们更了解目标处理器。

首先，我很少使用循环来查找内容，而是将项目添加到哈希表中，然后使用哈希表来查找结果。

例如，我们有一个要查找的字符串，然后有50个可能的值。因此，我们无需执行50 strcmps的操作，而是将所有50个字符串添加到哈希表中，并为每个字符串赋予一个唯一的数字(只需执行一次)。然后，我们在哈希表中查找目标字符串，并对所有50种情况(或者具有函数指针)进行一个大型切换。

在使用通用输入集(例如css规则)查找事物时，我使用快速代码来跟踪唯一可能的孤行，然后反复考虑以找出匹配项。匹配后，将结果保存到哈希表中(作为缓存)，然后在以后得到相同输入集的情况下使用缓存结果。

我的主要工具用于更快的代码是：

哈希表，用于快速查找和缓存结果

qsort这是我使用的唯一排序

bsp用于根据面积查找事物(地图渲染等)

• 衡量效果。
• 使用现实的和不平凡的基准。请记住，"小N一切都很快"。
• 使用探查器查找热点。
• 减少动态内存分配，磁盘访问，数据库访问，网络访问以及用户/内核转换的数量，因为这些通常经常成为热点。
• 衡量效果。

另外，我们应该衡量性能。

如果可能的话，与0进行比较，而不要与任意数字进行比较，尤其是在循环中，因为与0进行比较通常是通过单独的，更快的汇编器命令实现的。

例如，如果可能，写

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

代替

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

正如其他人所说：个人资料，个人资料。

至于实际的技术，我还没有提到：

冷热数据分离：保持在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个字节，因此我们可以在缓存中容纳更多条目。如果可以将其应用于渲染引擎的内部循环之类的情况，这将是一个巨大的胜利。

有时，我们必须决定要追求的是更大的空间还是更快的速度，这将导致几乎相反的优化。例如，要充分利用空间，我们可以打包结构，例如#pragma pack(1)并在结构中使用位字段。为了提高速度，我们打包以使其与处理器首选项保持一致，并避免使用位域。

另一个技巧是为重新分配数组选择正确的大小调整算法，或者最好还是根据特定应用程序编写自己的堆管理器。不要以为编译器随附的解决方案是每种应用程序的最佳解决方案。

这些天，最重要的事情是：

• 尊重缓存-尝试以简单的模式访问内存，不要仅仅出于娱乐目的而展开循环。使用数组代替具有大量指针追踪的数据结构，对于少量数据，它可能会更快。而且不要做任何太大的事情。
• 避免延迟-如果其他计算立即依赖除法和除法，请尽量避免除法和除法慢。依赖于其他内存访问的内存访问(即a [b [c]])是错误的。
• 避免不可预测性-许多if / eles具有不可预测的条件，或者引入更多延迟的条件，确实会使我们感到困惑。这里有很多无分支的数学技巧，但它们会增加延迟，并且仅在我们真正需要它们时才有用。否则，只需编写简单的代码，就不会有疯狂的循环条件。

不要为涉及复制和粘贴代码(例如循环展开)或者手动重新排列循环的优化而烦恼。编译器通常比我们做得更好，但是大多数编译器都不够聪明，无法撤消它。

如果某人对这个问题没有答案，那可能就是他们不太了解。

也可能是他们了解很多。我知道很多(恕我直言：-)，如果有人问我这个问题，我会回头问你：你为什么认为那很重要？

问题是，任何关于性能的先验概念(如果它们没有被特定情况告知)，都是根据定义进行猜测的。

我认为了解性能的编码技术很重要，但是我更重要的是不使用编码技术，直到诊断表明存在问题及其根源。

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

为了给我们一个具体的例子，这是一个经过优化的C应用程序。

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

• 如果我们将某些应用程序分为两个文件(例如main.c和lib.c)，则绕过链接器，在许多情况下，我们只需在main.c中添加\ #include" lib.c"，即可完全绕过链接器和允许对编译器进行更有效的优化。

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

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