0

我最近编写了一个动态程序来计算两条 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
      }
   }
}

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

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

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

4

4 回答 4

2

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

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

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

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

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

于 2011-06-02T02:22:12.600 回答
0

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

具体答案：我很惊讶差异是 40 倍，但是在您的代码中，每次完成循环时，它都必须调用 create_new_pair 两次（我原以为它必须做一些清理工作才能“ free”旧的一对，但考虑到它在堆栈上，我想这并不像我想象的那么难，或者至少我没有看到它......从 Gcc 读取代码过去比阅读要容易得多目前 C++ 代码）

于 2011-06-02T01:55:09.497 回答
0

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

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

于 2011-06-02T02:57:21.107 回答
-1

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

但是，对于解释型语言，它可能会有所不同。每次通过循环，解释器都需要分配变量位置，这可能会很昂贵。

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

尽管在任何这些情况下，我都无法解释 40:1 的差异。我怀疑省略的代码可能包含一些重要的线索。

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

于 2011-06-02T01:49:31.503 回答