可能很长的循环并在内部声明变量

Question

我最近编写了一个动态程序，用于计算两个 DNA 链序列（可能很长）之间的相似性（修改后的编辑距离）。

我的代码如下（不是实际代码，因为它是作业）：

while(!file.eof){
   string line;
   int sizeY, sizeX;

   //get first strand
   getline(db, line)

   //second strand
   getline(db, line)

   double ** ary = new double[sizeY];
   //loop to initialize array

   for(i to sizeY)
   {
      for(i to sizex)
      {
            pair<string,string> p,d;
            p.first = "A";
            p.second = "T";
            d.first = "G";
            d.second = "C";
            //do some comparisons
      }
   }
}

上面的代码大约需要 40 分钟才能完成大约 2400 行的文件。 如果我将 p、d 和赋值对移到嵌套 for 循环之外并运行完全相同的文件，它将在大约 1 分钟内完成。

我在其他线程中读到性能几乎相同。我还用-O2 编译了它。

为什么上面的代码慢这么多？

Answer 1

考虑内部循环的每次迭代中必须发生的各种分配/解除分配。

1. 在堆栈上分配pair对象
2. 分配四个空字符串，每个可能在堆上分配1个字节
3. 四个字符串分配，可能需要4次堆释放和新分配
4. 破坏涉及4次堆释放的字符串
5. 破坏pair对象

忽略堆栈分配（这应该相对便宜）总共 8 次堆分配和另外 8 次释放（或最好的情况是 4/4）。如果这是调试版本，则检查每个堆操作可能会产生额外的开销。

如果您的 sizeX/sizeY 常量为 2400，那么您总共执行了 9200 万 堆操作。如果幸运的话，每个操作将花费大约相同的时间，因为您在每个循环中分配相同大小的对象。如果您不幸运，那么由于堆碎片，某些堆操作可能需要更长的时间才能完成。

正如您所发现的，显而易见的解决方案是将变量定义和赋值放在循环之外。仅当它们在循环中的某个时刻被覆盖时，您才需要重新分配对值。

Answer 2

通用答案：
看来您正在使用 gcc（即 g++）；你总是可以执行 g++ -S [stuff] 来查看 G++ 对你的代码做了什么（假设你可以很好地阅读汇编）。

具体回答：
我很惊讶差异是 40 倍，但在你的代码中，每次完成循环时，它都必须调用 create_new_pair 两次（而且我原以为它必须进行一些清理才能“释放”老对，但考虑到它在堆栈上，我想这并不像我想象的那么难，或者至少我没有看到它......从 Gcc 读取代码曾经比读取 C++ 代码容易得多眼下）

Answer 3

这可能是因为变量是一个对象。由于 p 和 d 不是原始类型，除非编译器内联它的构造函数和析构函数（如果使用 -O3 而不是 -O2 则可能会发生这种情况），否则它将构造和析构两个 std::pair （并因此产生四个 std ::string) 每次迭代。如果它是一个原始变量（如 int），即使您没有启用内联优化，编译器也可以对其进行优化。

编辑：
请注意，由于 std::string 内部使用堆分配，因此即使内联也不会优化这些分配（但您仍然可以通过内联节省一些开销）。对于 int 的 std::pair，使用 -O3，循环内部或外部的性能应该相同。

Answer 4

在具有良好编译器（至少进行中等优化）的编译语言中，在循环内声明变量永远不会成为“失败者”，并且通常（特别是对于仅进行适度优化的编译器）将是“胜利者”。

不过，对于解释性语言来说，情况可能会有所不同。每次通过循环，解释器都需要分配变量位置，这可能会很昂贵。

您还可能会遇到设计不良的编译环境的“失败者”情况，其中在堆栈上分配变量的成本很高。

尽管对于这些场景中的任何一个，我都无法解释 40:1 的差异。我怀疑省略的代码可能包含一些重要的线索。

[啊，在重新阅读时（可能在海报的重新编辑中）我发现这不仅仅是变量声明，而是被移到循环之外的对象创建。]