从一道LeetCode题目得到的十个C++优化Tips

NoiseFloor · 发表于 2022-2-19 08:19

题目分析

LeetCode题目：1005. K 次取反后最大化的数组和
难度：简单
要求：给定int数组nums，取值范围是闭区间[-100, 100]，和一个正整数k，对数组进行k次如下操作：选取一个元素nums，将它改变为-nums ，然后求k次操作后，数组之和的最大值。

如果我们仅需要完成题目交差，那么解决方案很简单：如果数组之和为S，那么将nums变为-nums后，数组之和会变为S- 2* nums。若要使数组之和最大，可选的策略如下：

如果数组存在负数，则先对这些负数从最小值开始进行操作，变负为正，提高数组之和；

如果将数组中的负数全部转为正数后，记此时数组之和为S_max，还有m次操作：

如果数组中有0，则对0进行m次操作，数组之和保持为S_max；

如果数组中没有0，但m为偶数，可以对任一元素操作m次，由于m是偶数，数组之和保持为S_max；

如果数组中没有0且m为奇数，则对任意元素操作m-1次后，仍然需要对最小的正数n进行一次操作，此时数组之和变为S_max - 2*n。

经过以上分析，可以看出解法并不复杂，我们只需要知道数组内部的排序，然后进行一次遍历即可得到答案。使用STL中的sort算法当然可以解决问题（平均复杂度O（NlogN）），如果我们再仔细观察一下，由于nums的取值范围已知，可以使用计数排序的方法来降低排序算法的复杂度（平均复杂度O（N）），实现代码如下（这段代码和官方题解的解法类似）：
int largestSumAfterKNegations(vector<int>& nums, int k) {
      // get the initial sum value
      int ans = accumulate(nums.begin(), nums.end(), 0);
      // count sort
      constexpr int range_lo = -100;
      constexpr int range_hi = 100;
      unordered_map<int, int>freqs;
      for (auto const & num : nums)
      {
         freqs[num]++;
      }
      // traverse the negative numbers
      for (int i = range_lo; i < 0; i++)
      {
         int ops = min(k, freqs);
         ans -= 2 * i * ops;
         k -= ops;
         freqs -= ops;
         freqs[-i] += ops;
         if (k == 0)
         {
            break;
         }
      }
      // if needed, operate once on the smallest positive number
      if (k > 0 && k % 2 == 1 && !freqs[0])
      {
         for (int i = 1; i <= range_hi; i++)
         {
            if (freqs)
            {
                  ans -= 2 * i;
                  return ans;
            }
         }
      }
      return ans;
}
提交结果，运行正确，执行用时为8ms：

我们记上面这段代码为提交1。使用计数排序而不是STL中的排序算法是我们今天得到的第一个优化Tip：

Tip 1 根据输入数据的范围优化算法

优秀的工程师不能只满足于结果的正确，更要注重性能的提升。尤其是在深度学习算法的工程部署上，深度优化的工程版本对算法落地至关重要。而优化本身也是非常有趣的工程实践，考验工程师的计算机体系架构知识基础、逻辑分析能力和动手实践能力。
以上述代码为例，计数排序最方便的实现是用哈希表（unordered_map）。根据CPP Reference，哈希表的插入和查找平均时间复杂度都是常数时间，但无法保证最坏情况下的时间复杂度。本文中题目的输入数据更加特殊，一定是[-100, 100]之间的整数，于是可以直接用连续数组vector实现计数排序，只要事先分配好空间，数据的写入和读取都是常数时间复杂度。实现代码如下：
int largestSumAfterKNegations(vector<int>& nums, int k) {
      // get the initial sum value
      int ans = accumulate(nums.begin(), nums.end(), 0);
      // count sort
      constexpr int range_lo = -100;
      constexpr int range_hi = 100;
      vector<int> freqs(range_hi - range_lo + 1);
      for (auto const & num : nums)
      {
         freqs[num - range_lo]++;
      }
      // traverse the negative numbers
      for (int i = range_lo; i < 0; i++)
      {
         int ops = min(k, freqs[i - range_lo]);
         ans -= 2 * i * ops;
         k -= ops;
         freqs[i - range_lo] -= ops;
         freqs[-i - range_lo] += ops;
         if (k == 0)
         {
            break;
         }
      }
      // if needed, operate once on the smallest positive number
      if (k > 0 && k % 2 == 1 && !freqs[- range_lo])
      {
         for (int i = 1; i <= range_hi; i++)
         {
            if (freqs[i - range_lo])
            {
                  ans -= 2 * i;
                  return ans;
            }
         }
      }
      return ans;
}
提交结果，运行正确，执行用时为0ms：

注意：LeetCode显示的执行用时都是4的倍数，这里的0只能说明平均执行用时比4ms更小。
我们记上面这段代码为提交2。从提交1到提交2，我们得到了第二个优化Tip：

Tip 2 了解STL底层实现并选择最适合的容器

永远不会满足是优秀工程师成长的动力。得到提交1、提交2两个版本后，我们可以下结论说，因为提交2使用了更为合适的容器，它的运行速度就一定快于提交1吗？使用提交1提交多次，系统返回的最快执行用时为4ms；而使用提交2提交多次，系统返回的最慢执行用时为8ms。这种波动在优化过程中很常见：由于硬件状态、系统状态等原因，同一段代码每次执行的耗时是不同的。在实际生产中更要考虑诸如连续长时间运行导致CPU发热降频、程序初次加载的开销等因素。
显然我们需要公平测试来说明哪种实现方案更好，例如在相同的硬件、相同的前置条件下，连续运行提交1、提交2若干次，并比较它们的平均运行时长。这里我们可以得到第三个优化Tip:

Tip 3 不要只测试一次，通过公平测试确保优化结果的可靠性和可信度

提交2的执行速度已经比较快了，不过我们还可以通过这一道题目尝试其他的优化思路。不断review代码、不断思考，就可能不断产生新的收获。例如，通过在线系统的显示结果可以看出，系统测试用例有80个。系统执行用时也就是这80个测试用例的执行时间。在真实的生产环境中，不同输入数据出现的概率也影响了我们如何选择优化方案。例如，如果我们获知这段程序执行过程中，80%的情况下输入数据都没有负数，那么原方案中的第一段从-100到-1的遍历在大部分情况下都是浪费的。如果是这样，我们可以采用针对性优化的手段，如添加以下代码：
      int negative_sum = accumulate(freqs.begin(), freqs.begin() - range_lo, 0);
      if (negative_sum > 0)
      {
         // traverse the negative numbers
         .....
这里我们可以得到第四个Tip：

Tip 4 根据真实生产环境中输入数据的出现概率添加控制逻辑，做针对性优化

我们再构想另一种场景，如果输入数据在[-100, 100]中分布非常均匀，而且输入数组很长，在这种场景下，这段代码的优化方向可以在哪里？  在提交2中可以看到多个循环，优化工程师看到循环是非常敏感的，因为循环条件的每次判断、以及循环里的分支造成的性能开销都是常见的优化点。在多核CPU环境下，最简单的一个优化点是利用OpenMP多线程循环展开（如果对编译器的循环展开、手动循环展开等细节感兴趣，同学们可以去查找资料了解）。对于第一个循环，后面的循环体运算依赖于之前的循环体结果，这种有前后数据依赖的情况不是优化的第一选择：
      for (auto const & num : nums)
      {
         freqs[num - range_lo]++;
      }
对于第二个循环体，它的数据依赖体现在每个循环体都要对k进行操作。对于原题的要求来说，这种情况也不便做循环展开。
      for (int i = range_lo; i < 0; i++)
      {
         ...
         if (k == 0)
         {
            break;
         }
      }
对于第三个循环体，同样在循环中存在跳出逻辑（return），不适合做循环展开：
         for (int i = 1; i <= range_hi; i++)
         {
            if (freqs[i - range_lo])
            {
                  ans -= 2 * i;
                  return ans;
经过分析，在已有的提交2的基础上，现有题目不适合用循环展开的优化策略。这一次失效的优化策略让我们得到的启示是：

Tip 5 分析实现中的循环体，看有没有循环展开的优化可能

可以看到上文提到的优化策略主要都是在阅读代码时边读边想出来的。实际的优化工作与此有什么不同呢？是否有常规的测试手段可以帮助工程师寻找优化的方向呢？答案是肯定的，在真实的生产优化中，往往会选择一个典型场景和典型硬件，用专门的profiler工具去分析提交2中哪一步骤是耗时的核心。试想，如果一段逻辑在这个程序运行耗时中只占1%，那么即使把它优化到极致，对程序的整体耗时影响也是很小的（感兴趣的同学可以查询Amdahl定律）。在之前的优化测试中，我们并没有定位代码中具体哪段逻辑可能成为程序耗时的热点。这源于测试用例的不透明（虽然也可以用暴力试错的方式把所有测试用例试出来，但是这么做性价比不高），也是因为我们不想把硬件平台差异性的讨论引入本篇文章。这里我们想讨论的Tip是：

Tip 6 先定位热点，再采取行动优化

有一句话叫“不喜欢偷懒的程序员不是好程序员”。在性能优化上，同样有很多自动化的工具可以帮助工程师们快速、准确地取得一定的优化加速比，如利用编译器的优化选项，又如利用Halide等通用调优框架。自动化加速的效果因场景而异，它的威力在产品需求需要快速响应时尤其能够体现。而如果手写代码的优化结果还不如自动化调优，那么这段手写代码也值得深刻剖析一番。由此我们分享下一个Tip：

Tip 7 利用自动化工具调优或者作为手动优化结果的性能基线

除了时间上的优化外，根据实际需要，优化工作还有许多其他维度，如内存优化、功耗优化等。以内存优化为例，提交2在LeetCode系统中返回的内存是8.9MB，而所用的freqs计数数组只有201个int值，存储数据所用内存为802个字节，即使编译器预留2倍的空间，也只有1.6MB，可见当前题目条件下，内存占用主要不是在数据上，而是在代码上。可以参考系统提供的内存占用最小的一个代码范例，在牺牲运行时间的前提下，在一次循环内往复寻找最小的负数，最大化地节省代码占用的内存。如果我们放宽条件，在输入值范围很大且需要用vector存储时，也可以考虑优化freqs占用的内存，根据题意，其实只需要存储输入数组中每个负数出现的次数、最大的负数和最小的正数，对其他的正数出现的次数并不需要统计和存储。因此，可以给出如下实现：
int largestSumAfterKNegations(vector<int>& nums, int k) {
      // get the initial sum value
      int ans = accumulate(nums.begin(), nums.end(), 0);
      // count sort
      constexpr int range_lo = -100;
      constexpr int range_hi = 100;
      vector<int> freqs(-range_lo + 1);
      int smallest_positive = INT_MAX;
      for (auto const & num : nums)
      {
         if (num <= 0)
         {
            freqs[num - range_lo]++;
         }
         else if (num < smallest_positive)
         {
            smallest_positive = num;
         }
      }
      // traverse the negative numbers
      int i = range_lo;
      for (i = range_lo; i < 0; i++)
      {
         int ops = min(k, freqs[i - range_lo]);
         ans -= 2 * i * ops;
         k -= ops;
         freqs[i - range_lo] -= ops;
         if (ops > 0 && -i < smallest_positive)
         {
            smallest_positive = -i;
         }
         if (k == 0)
         {
            break;
         }
      }
      // if needed, operate once on the smallest positive number
      if (k > 0 && k % 2 == 1 && !freqs[- range_lo])
      {
         ans -= 2 * smallest_positive;
      }
      return ans;
}
记以上实现为提交3，和提交2相比，它的vector只占用了一半的空间。实际测试时，系统返回的占用内存仍为8.9MB，这是因为题目规定的数字范围比较小，所以内存峰值并不来自于vector的存储。不过我们还是可以从这次提交中得到两点Tips：

Tip 8 除了时间优化以外，还要关注内存优化、功耗优化等其他性能维度

Tip 9 不断实践、试错，积累一手经验

就这样，从一道难度为简单的LeetCode题目中，我们可以延伸出很多优化领域的知识。在工作中，我们实现的每一个功能解决的每一个bug，都可以积跬步至千里，逐步打造我们自己的知识大厦。与此同时，你也将从新手一步步迈向资深。本篇文章最后分享的一个Tip是：

Tip 10 在开发过程中积累技术心得文档，写文档的过程也是技术沉淀的过程

以上只是C++优化中的一小部分，而C++优化又是整个高性能优化知识海洋中的一叶扁舟。做好优化工作，需要个人的思考和努力，同时也需要好的团队、硬件设施和业务支撑。祝各位对高性能计算领域感兴趣的同学都能找到合适的平台激发自己的潜力，不断成长^_^
JD链接

各位校招同学们，思谋科技高性能计算团队整体素质高、团队氛围好、技术兴趣浓厚，致力于CPU/GPU/NPU等硬件平台的并行计算优化和系统优化，感兴趣的同学欢迎戳下方链接扫码了解我们的校招岗位需求。

fwalker · 发表于 2022-2-19 08:20

[赞]

七彩极 · 发表于 2022-2-19 08:25

有空研究下

fwalker · 发表于 2022-2-19 08:30

[赞同]

c0d3n4m · 发表于 2022-2-19 08:33

[酷]

		自动登录	找回密码
密码			立即注册

从一道LeetCode题目得到的十个C++优化Tips

本帖子中包含更多资源