潜在的长循环并在里面声明变量

我最近编写了一个动态程序，用于计算两条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行的文件。如果我移动嵌套for循环外的p，d和赋值对并运行完全相同的文件，它将在大约1分钟内完成。

我读过其他线程的表现几乎相同。我也用-O2编译了它。

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

来源

2011-06-02 acmrk

这是什么语言？如果你不用一种语言标记它，它可能不会获得很多观点 – 2011-06-02 01:34:51

它似乎比任何东西，但它的缺失C++更多;并不会编译。循环是伪代码虽然:) – 2011-06-02 01:38:04

你为什么使用字符串？好像你想要一对字符。这将摆脱大部分uesp指出的问题。 – Michael 2011-06-02 02:41:29

-1

在一个编译好的编译器语言中，如果一个编译器（至少具有普通优化）在循环中声明变量永远不会是一个“失败者”，并且经常（特别是对于只有适度优化的编译器）将是一个“优胜者”。

虽然解释型语言可能会有所不同。每次通过循环时，解释器都需要分配变量位置，并且这可能是昂贵的。

你也可能有一个“失败者”的情况，设计不佳的编译环境，在堆栈上分配变量很昂贵。

虽然有了这些场景，但我仍然无法解释40：1的差异。我怀疑省略的代码可能包含一些重要的线索。

[嗯，在重新阅读（也可能在海报上的重新编辑）我看到，它不是简单的变量声明，但是这被移动的循环之外创建对象。]

来源

2011-06-02 01:49:31

通用的答案：看起来你使用的是gcc（也就是说g ++）;你总是可以用g ++ -S [stuff]来看看G ++对你的代码做了什么（假设你可以很好地阅读程序集）。

具体的回答：我很惊讶，差异是40倍，但在你的代码中，每当你完成一个循环时，它必须调用create_new_pair两次（并且我会认为它将不得不做一点一点点的清理“免费”的旧对，但考虑到它在堆栈上，我想这不像我想象的那么难，或者至少我没有看到它......从Gcc读代码曾经是比阅读C++代码更容易）

来源

2011-06-02 01:55:09 Foon

想要添加：您可以执行g ++ -O2（或其他选项）-S yourfile.cpp（这将导致文件yourfile.s），但是一些优化使得程序集，umm ...读取的乐趣更少。 – Foon 2011-06-02 01:56:04

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

分配一对对象堆栈上
分配4个空字符串，每一个可能是1个字节分配在堆上
四串分配可能需要4分解除分配，新的分配
销毁涉及4分解除分配

忽略堆人的

销毁串位置（应该相对便宜），即总共8个堆分配和另外8个释放（或4/4的最佳情况）。如果这是一个调试版本，那么在检查每个堆操作时可能会有额外的开销。

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

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

来源

2011-06-02 02:22:12 uesp

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

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

来源

2011-06-02 02:57:21 fbafelipe

潜在的长循环并在里面声明变量

回答

相关问题