如何更好地優化？

Question

如果問題看起來有些寬泛或奇怪，請事先道歉，我並不是要冒犯任何人，但也許有人可以提出建議。我試圖尋找類似的問題，但冷不。

哪些更好的資源（書籍，博客等），可以教關於優化代碼？

有很多資源讓代碼更易讀（代碼完成可能是第一選擇）。但是如何讓它運行得更快，更具有內存效率？

當然，每種特定語言都有很多書，但是我想知道是否有一些內容覆蓋了操作的記憶/速度問題，並且有些語言無關？

Answer 1

閱讀Structured Programming with go to Statements。儘管它是「不成熟的優化是萬惡之源」的來源，但是現在有人想要做出更快或更小的事情 - 不管它們在過程中多麼重要或遲到 - 它實際上是關於儘可能提高效率。

瞭解有關time complexity，空間複雜性和analysis of algorithms。

想出一些例子，如果您想犧牲空間複雜性更糟的空間以獲得更好的時間複雜性，反之亦然。

瞭解您選擇的語言和框架提供的算法和數據結構的時間和空間複雜性，尤其是您最常使用的語言和框架。

閱讀關於創建一個好的哈希碼的問題，在這個網站上的答案。

研究方法HTTP具有緩存的優點，沒有不適當地使用陳舊數據的缺點。考慮應用於內存緩存的難易程度或難度。想想你什麼時候會說「擰緊它，我可以忍受它爲我提供的速度提升而陳舊」。考慮一下你什麼時候會說「擰緊它，我可以忍受它爲我提供的新鮮度的保證變得緩慢」。

瞭解如何進行多線程。瞭解它何時可以提高性能。瞭解爲什麼它通常不會或甚至使事情變得更糟。

看看很多Joe Duffy's blog，表現是他的寫作經常關注的問題。

瞭解如何將項目處理爲流或迭代，而不是每次都構建和重建每個項目的完整數據結構。瞭解什麼時候你最好不要那樣做。

知道什麼東西的成本。你不能合理地決定「我會工作，所以這是在CPU高速緩存而不是主內存/主內存而不是磁盤/磁盤而不是通過網絡」，除非你有一個好主意，被擊中，以及成本差異是什麼。更糟的是，如果你不知道自己花了多少錢，你不能忽視某些過早的優化 - 不打擾優化某些東西往往是最好的選擇，但如果你甚至不考慮它，你就不會「過早地避免優化「，你會混淆和希望它的工作。

瞭解一下您使用的腳本引擎/ jitter/compiler/etc爲您完成了哪些優化。學習如何與他們合作，而不是反對他們。無論如何，學習不要重新做它會爲你做的工作。在一兩種情況下，您也可以將相同的一般原則應用於您的工作。

搜索，其中一些被斥爲實現細節在本網站的情況下 - 是的，所有這些都是情況下，問題的細節是不是當時最重要的事情，但所有這些的實現細節被選擇因爲某種原因。瞭解他們是什麼。瞭解反駁的論點。

編輯（我會繼續添加更多一些這個，因爲我去）：

不同的書籍，當然在他們把對效率的關注的重點有所不同，但我記得Stroustrup的的C++編程語言爲其中有很多時候他會解釋幾種不同的選擇，如效率關係，以及如何不作出效率的決定，影響班級「從外部」的可用性。

這使我想到另一點。專注於您在不同項目中重複使用的庫代碼的效率。你不想永遠想着「也許我應該在這裏手動推出一個新的更有效率」，除非它是一個非常專業化的案例，你想確保大量工作能夠用於高效使用的課堂在很多情況下，專注於識別熱點。

對於特殊情況，一些比較隱晦的數據結構值得了解。例如，DAWG是一個非常緊湊的結構，用於存儲具有大量通用前綴和後綴的字符串（這些字符在大多數自然語言中都是大多數字詞），您只需在列表中找到匹配模式的列表。如果你需要一個「有效載荷」，那麼一棵樹中的每個字母都有一個隨後每個字母的節點列表（DAWG的推廣，但以「有效載荷」而不是終端節點爲結尾）具有一些但並非全部的優點。他們還發現O(n)時間的結果，其中n是所尋求字符串的長度。

這會出現多久？不多。它曾經爲我提供過一次（真的有幾次，但是它們是同一案例的變種），因此，直到那時我才瞭解所有關於DAWG的知識。但我足夠清楚知道這是我以後需要研究的，並且它爲我節省了幾千兆字節（實際上，對於需要處理16GB內存的計算機來說，這太少了，至少少於1.5GB）。直接進行手動滾動的DAWG完全是過早的優化，而不是將字符串放在哈希集合中，但通過彈出the NIST datastructure site意味着當它出現時我就可以。

考慮：「在DAWG中查找字符串是O（n）」「在Hashset中查找字符串是O（1）」這兩個語句都是真實的，但兩者的速度往往是可比較的。爲什麼？因爲DAWG就字符串的長度而言是O（n），並且就DAWG的大小而言實際上是O（1）。就散列集的大小而言，散列集的大小爲O（1），但根據字符串的長度計算散列值通常爲O（n），並且就該長度而言，相等性檢查也是O（n） 。兩個陳述都是正確的，但他們正在考慮一個不同的n！在任何時間和空間複雜性的討論中，你總是需要知道什麼是 - 通常它是結構的大小，但並非總是如此。

不要忘記恆定效應：對於足夠低的n值，O（n²）與O（1）相同！請記住，O（n2）這樣的類似的翻譯爲n2 * k + n * k 1 + k 2，假設k 1 & k 2足夠低並且k和我們比較的另一種算法或結構的k足夠接近，他們並不重要，我們關心的只是n²。這不是一直如此，我們有時可以發現k，k 1或k 2足夠高，以至於我們陷入困境。當n很小以至於不同方法的不變成本差異很重要時，也不是這樣。當然，當n很小時，我們沒有很大的效率問題，但是如果我們在平均n的結構上進行m次操作，而m很大。如果我們在O（1）和O（n²）之間進行選擇，我們在O（m）和O（n 2m）方法之間進行選擇。對於前者來說，它看起來似乎毫不費力，但是它的本質是在兩種不同的O（m）方法之間進行選擇，而常數因子更重要。

瞭解無鎖多線程。或者也許不。就我個人而言，我有兩個我自己的代碼，我專業使用，除了最簡單的無鎖技術。一種是基於衆所周知的方法，現在我不打擾了（它是.NET 2.0第一次爲.NET 2.0編寫的代碼，.NET4.0庫提供了一個完成相同功能的類）。另一個我第一次寫作是爲了好玩，並且只是在那段爲了樂趣而給了我一些可靠的東西之後才被使用（在很多情況下它仍然被4.0庫中的某些東西毆打，但對於我關心的其他人關於）。我不願意在寫作期限和客戶時寫下類似的文章。所有這一切說，如果你編寫的興趣不大，所涉及的挑戰是有趣的，當你有自由放棄失敗的計劃時，這是一件令人愉快的事情，你正在爲付費客戶做些事情，而且你通常會對效率問題有所瞭解。 （如果你想看看我已經完成了一些工作，請看https://github.com/hackcraft/Ariadne）。

爲例

其實包含的一些上述原則一個比較好的例子。看看目前在511行的方法https://github.com/hackcraft/Ariadne/blob/master/Collections/ThreadSafeDictionary.cs（我在這裏開玩笑說它是引用Dijkstra的人的火焰誘餌，我們用它作爲案例研究：

該方法首先寫入使用遞歸，因爲這是一個自然遞歸的問題 - 在對當前表執行操作之後，如果存在「下一個」表，我們希望對其執行完全相同的操作，依此類推，直到沒有其他表爲止。

對於一些不同的方法，遞歸幾乎總是慢於迭代，我們是否應該使所有遞歸調用迭代？不，它通常不值得，而遞歸是編寫清楚它正在做什麼的代碼的好方法。應用上面的原則，因爲這個我這個圖書館可能會被稱爲性能至關重要的地方，應該對此加以特別的努力。

爲了提高速度，我做的下一件事就是進行測量。我不依賴於「我知道迭代比遞歸更快，所以在更改以避免遞歸時它必須更快」。這是不正確的 - 一個寫得不好的迭代版本可能不如一個寫得很好的遞歸版本。

接下來的問題是，如何重新編寫它。我有一種經過測試的方法，我知道它的工作原理，我將用不同的版本替換它。我不想用一個不起作用的版本來取代它，顯然，如何重新編寫，同時充分利用已有的版本？

那麼，我知道關於尾巴消除;通常由編譯器完成的優化改變了堆棧的管理方式，使得遞歸函數的屬性更接近於迭代的屬性（它仍然是從源代碼的角度遞歸的，但是它的編譯代碼實際上是迭代的使用堆棧）。

這給了我兩件事情要考慮：1.也許編譯器已經這樣做了，在這種情況下，我的額外工作不會做任何事情來幫助。 2。如果編譯器還沒有這樣做，我可以手動採用相同的基本方法。

做出了這個決定，我替換了方法自己調用的所有點，並更改了下一個調用的不同參數，然後返回到開頭。即而不是有：

CurrentMethod(param0.next, param1, param2, /*...*/); 

我們：

param0 = param0.next; 
goto startOfMethod; 

也正在做，我再次測量。貫穿整個單元測試的課程現在一直比以前快13％。如果距離更近，我會嘗試更多的細節度量，但運行時的一致性爲13％，其中包括甚至不稱此方法的代碼，這是我非常滿意的。 （它也告訴我，編譯器沒有進行相同的優化，或者我沒有獲得任何東西）。

然後我清理該方法以進行更多有關新代碼的更改。他們中的大多數讓我拿出goto，因爲goto確實令人討厭（還有其他地方進行了相同的優化，因爲goto完全被重構，所以不那麼明顯）。在某些情況下，我將它留下了，因爲13％是值得打破我的腦海中的不規則規則！

所以上面給出了一個例子：

1. 決定在哪裏集中優化工作（基於多久它可能被擊中，我無法預測該庫的所有使用）
2. 使用的知識一般成本（大多數情況下遞歸成本大於迭代成本）。
3. 測量而不是取決於假設上述始終適用。
4. 學習編譯器的工作。
5. 瞭解到，因爲我可能無法獲得任何東西 - 也許編譯器已經爲我做了。
6. 避免導致不可讀代碼的優化（重構大部分goto是第一次通過）。

一些是輿論和樣式的決定（在某些goto離開也不是沒有爭議）的問題，它肯定沒事跟我決定不同意，但知識點在這個迄今募集職位將使其成爲消息靈通的分歧，而不是一個下意識的分歧。

Answer 2

這裏有一些鏈接，可能一般是有益的內存優化的主題

What Every Programmer Should Know About Memory by Ulrich Drepper

Herb Sutter: The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software

Slides: Herb Sutter: Machine Architecture (Things Your Programming Language Never Told You)

Video: Herb Sutter @ NWCPP: Machine Architecture: Things Your Programming Language Never Told You

The microarchitecture of Intel, AMD and VIA CPUs An optimization guide for assembly programmers and compiler makers, by Agner Fog

Answer 3

除了其他答案中提到的資源之外，Michael Abrash的Graphics Programming Black Book是瞭解優化的最佳解讀。雖然具體細節有點過時，但它仍然是學習如何進行優化的極好資源。

任何時候你想優化代碼，它是絕對必要的措施，措施，措施。學習優化的最佳途徑之一就是通過這樣做 - 獲取一些您想要優化的代碼，學習如何使用分析器來衡量其性能，然後進行更改並測量結果。