潛在的長循環並在裏面聲明變量

我最近編寫了一個動態程序，用於計算兩條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

潛在的長循環並在裏面聲明變量

回答

相關問題