最佳化程式碼速度/因素最佳化
因素最佳化與複雜度最佳化相反：它們不會改變演算法的整體複雜度，而是透過一定的因素使演算法執行更快。舉一個極端（但並不那麼不切實際）的例子，我可以將程式執行時間的公式從 5 秒乘以 N^2（其中 N 是輸入的長度）增加到 1 秒乘以 N^2。可以看出，我們透過一定的因素提高了最佳化，但仍然沒有處理潛在的可擴充套件性問題。
因素最佳化值得你的時間嗎？有些人似乎不這麼認為。例如，埃裡克·雷蒙德在《Unix 程式設計藝術》中談到 這一點
其中一個是摩爾定律的指數效應——收集效能增益最聰明、最便宜，而且通常也是最快的途徑，就是等待幾個月，讓目標硬體變得更強大。考慮到硬體和程式設計師時間之間的成本比率，幾乎總是有比最佳化一個正在執行的系統更好的事情可做。
我們可以從數學上具體說明這一點。幾乎永遠不值得進行僅將資源使用降低一個常數因子的最佳化；更明智的做法是集中精力處理可以將平均執行時間或空間使用從 O(n^2) 降低到 O(n) 或 O(n log n)[112] 或類似地從更高階降低到更低階的情況。線性效能增益往往會被摩爾定律迅速吞噬[113]。
蘭德爾·海德在 他的 OnLAMP.com 特色文章“為什麼學習組合語言仍然是一個好主意” 中提出了相反的觀點
大多數情況下，你可以透過簡單地改進現有演算法的實現來實現非常好的效能提升。計算機科學家可能會爭辯說，效能的常數改進不如將演算法從 O(n^2) 效能提升到 O(n lg n) 效能那麼好，但事實是，大多數情況下，在整個軟體中應用的二三倍的常數因子改進，可以決定一個實際應用和一個執行速度過慢而無法舒適使用的應用之間的區別。而正是這種型別的最佳化，大多數現代程式設計師都沒有什麼經驗。
那麼，哪種觀點是正確的？我傾向於認為雷蒙德是錯的，而海德是對的。程式執行的因素仍然很重要，可以產生天壤之別。一些因素最佳化可能會帶來巨大的收益，並將使你和你的使用者更快樂。
雷蒙德也誤以為，人們不能指望他們的終端使用者升級他們的機器。此外，似乎我們已經 觸及了基於半導體的 CPU 線性 CPU 速度增長的終點，我們不能指望線性程式碼隨著新硬體而變得更快。高度並行化的程式碼可能會變得更快，但並行化並不總是可能的，或者不可取。
另一個說明性的故事 講述了為什麼不依賴摩爾定律來加速你的程式碼是一個好主意，是由吉爾博阿·達瓦拉釋出到 Linux-IL 郵件列表中的。摘錄自那裡，同時為了連貫性而進行編輯
幾年前，我在一家醫療軟體開發公司工作。我在資料庫開發方面工作。（我們有自己的專有面向物件的資料庫）
我們的資料庫非常酷；它可以在一臺雙奔騰 Pro 機器上處理醫院級別的負載。（這與當時使用的大多數大型機相去甚遠。）
我們的醫療軟體方面使用 PowerBuilder（後來是 VB）來開發醫療應用程式。毫不誇張地說，醫療應用程式本身比它構建的醫療資料庫慢得多，也重得多。當 50 個客戶端可以在一臺奔騰 I 90 MHz 帶 32MB 記憶體的機器上輕鬆執行時，醫療應用程式在一臺奔騰 I 166 MHz 帶 64MB 記憶體的機器上執行非常緩慢！
而且每次我們把這個異常情況指出來時，醫療團隊都聲稱，“新的機器即將推出，新的 CPU；到我們推出的時候，CPU 效能就不是問題了。”
你知道嗎，現在，那個醫療軟體在一臺頂級奔騰 3/奔騰 4/AMD 晶片機器上執行比一條死狗還慢……什麼也沒改變。
我們是否應該投入時間去進行只為我們節省 5 秒（或更少）的最佳化？速度提高 5% 是否可取？有些人可能會對這些問題回答“不”，但答案並非那麼簡單。例如，比爾·雷蒙德寫了一個 FreeCell 求解器，據說 在一臺 733 MHz 的計算機上每小時可以求解 10,000,000 個牌局，並且他 證實了
我透過無數次 1% 的減少來實現我的快速執行時間。
根據我對 我自己求解器（它是開源的，並且有一個公開的版本控制庫）的經驗，我能夠 隨著時間的推移逐漸減少某個基準測試的執行時間，從 224 秒降至 94 秒（提高了 138%），僅僅是每次削減幾秒，並進行許多不同的最佳化。在 一篇博文中，我進一步解釋了我是如何透過應用許多小的最佳化來使“檔案查詢物件”Perl 5 模組的效能提升了四倍。
因此，不應排除即使是“小”最佳化也是微不足道的，也不應追求它們。只需四次 20% 的速度提升，就能將程式的速度提高一倍，雖然每次小的最佳化的收益並不十分顯著，但這種提升會很快累積起來，並最終產生很大影響。另一方面，如果你不應用任何小的最佳化到你的程式碼中，而是等待彩虹盡頭的寶藏，那麼你的程式碼很可能只會像現在一樣快（或者一樣慢）。
如果我們有一個包含許多 C/C++ 結構體（包含可能具有不同資料型別的相鄰數量元素的結構體）的集合，那麼交換兩個這樣的結構體（例如為了重新排序或排序）將需要大量的記憶體訪問。另一方面，如果我們管理指向這些結構體的指標，並且這些指標具有永久地址，那麼交換兩個 32 位或 64 位指標將相對便宜。
FreeCell Solver 的第一個 ANSI C 版本（0.2.0）分配了一個直接的大型 C 結構體陣列，然後對其進行排序並進行二分搜尋。在 0.4.0 版本中，實現了指向單獨 malloc() 的結構體的指標陣列，這帶來了巨大的速度提升。這讓我上了寶貴的一課，瞭解如何使用指標作為最佳化工具。
應用程式或其各個元素消耗的記憶體越多，快取未命中次數就越多，頁面交換次數就越多，資料需要不止一個快取行的可能性就越大。因此，減小程式的大小通常會導致速度優勢。
正如 在 Linux-IL 上的一篇文章中記錄的那樣，當 FreeCell Solver 從將卡片表示為 32 位值轉換為使用 8 位八位位元組表示卡片時，它變得快了很多。這很可能是由於交換次數減少、快取未命中次數減少，以及更多卡片可以放入奔騰的 32 位元組快取行中。
LWN.net 上的“行內函數的代價”文章 也具有說明性。當 Linux 核心中的一個函式被取消內聯時，核心的速度有所提升。原因是它所有內聯例項在每個例項中佔據了（相對）大量的記憶體，因此核心更大，並且出現了更多快取未命中。
在閱讀了這裡的內容之後，你可能會認為這與常見的記憶體-速度權衡“真理”相矛盾。記憶體/速度權衡起源於理論計算機科學，在那裡表明對於某些任務，可以透過增加所使用的記憶體的漸進數量來降低執行時間的漸進複雜度（反之亦然）。例如，我們有時可以透過將記憶體從 O(1) 增加到 O(N) 來將漸進執行時間從 O(N^2) 降低到 O(N)。
這很好，而且是正確的，但它並不與以下事實相矛盾：鑑於當代計算機硬體和作業系統的體系結構，程式使用的記憶體越少（只要演算法的邏輯保持不變）——它執行的速度可能越快。這不是一個漸進的權衡，而是一個雙贏的局面。
透過 並行化 任務，可以將其拆分為多個執行行（程序、執行緒、叢集中不同計算機上的任務等），每個執行行將並行執行。結果，整個任務本身有望更快完成。並行化的一個好例子是對大量輸入執行相同的耗時操作。如果我們為不同的程序分配輸入的子集，那麼它們很可能更快地完成它。
最近，由於多核 CPU 的發展，並行化在使程式碼執行得更快方面變得特別有吸引力。但是，應該注意的是，並行化仍然受到一些因素的限制，例如鎖定、程序間資料的序列化和反序列化、上下文切換、CPU 和作業系統限制，以及任務數量往往超過可用處理器數量的事實。最重要的是，阿姆達爾定律 規定任務的序列部分（根據定義）不能並行化，因此限制了並行化的收益量。
在 Linux 核心中，struct 成員的順序被排序，以便最重要的成員適合 Pentium 架構的 32 位元組快取行大小。這樣，對 struct 的訪問速度總體上會加快，因為它的所有成員大部分時間都保留在快取行中，並且可以更快地訪問。
另一種有用的最佳化被稱為 寫時複製。一個很好的例子是，當為程式語言實現虛擬機器時，以及當我們將一個變數分配給另一個變數時。雖然我們可以在每次操作時複製變數的內容，但只需增加引用計數，並在其中一個變數發生變化之前等待它們分離，這樣做會更便宜。
如果副本的內容很重要，那麼寫時複製可以節省大量的時間。
如果我們執行了許多代價高昂的查詢，那麼將常見發出的查詢及其結果快取到記憶體中很可能會提高程式的整體效能。快取是在各種軟體中實現的——從將最近訪問的檔案系統條目儲存在快取中的作業系統核心，到儲存對它們發出的各種查詢階段的快取的資料庫伺服器。
快取有一個變體叫做 記憶化，在這種情況下，我們永遠不會釋放結果。可以證明，透過記憶化樸素的（樹遞迴的）斐波那契數計算，實際上可以將它的複雜度從指數複雜度降低到線性複雜度。
應該注意的是，在許多情況下無法進行快取或記憶化，例如，如果查詢具有大多數型別的副作用。
這篇文章來自 Hackers-IL 闡述了為了提高效能而避免不必要地複製物件的理由。過度呼叫複製建構函式可能會對效能產生負面影響，而將呼叫次數降至最低限度可以提高效能。僅僅在記憶體中複製一個大型的連續區域多次，可能會對效能產生負面影響，消除它也可能會證明是有益的。
儘管之前提到了，但在減少記憶體消耗的背景下，在 C 或 C++ 等語言中行內函數通常會對效能產生積極影響。函式呼叫是代價高昂的操作，並且有很多開銷，透過在每次使用函式時將程式碼插入到適當位置來避免函式呼叫，可以提高效能。行內函數的長度越短，它們帶來的益處就越大，並且如果內聯呼叫佔用的記憶體小於不內聯時使用的記憶體。
如果你不確定內聯某個函式是會產生積極影響還是消極影響，那麼就進行基準測試並觀察結果。
Schwartzian 變換 是一種最佳化某些型別的基於比較的排序操作的方法。如果我們要比較的函式的鍵需要很長時間來計算（例如，如果它們需要訪問硬碟），那麼我們可以首先準備一個等效的陣列，其中包含輸入及其鍵的配對，然後根據鍵對配對進行排序，最後只從配對中過濾出原始輸入。
應該注意的是，Schwartzian 變換實際上將計算鍵的次數的複雜度從 O(N*log(N)) 降低到 O(N)。但是，排序的總體複雜度仍然是 O(N*log(N))。
我認為，將所有已知的最佳化集中在一個地方，類似於 重構目錄 和 波特蘭模式庫，是一個好主意。這將是一個列表，人們可以完整地閱讀它，瞭解他們的程式碼可以在哪些地方進行改進，以及為了一般啟發和促進交流。
截至撰寫本文時，我不知道有類似的努力，這將非常有用。本節只涵蓋了可能的最佳化策略的一小部分，只是為了讓大家有所瞭解，並不旨在面面俱到。