測算一個算法的實際運行時間

Question

大約，MIPS的多少條物理指令做一個抽象算法運算緩衝？至於抽象算法操作，I表示的基本操作，如添加，除法等

我看到這不是嚴格的測量技術:-)

克加

Answer 1

有一個基本的MIPS指令列表here。您提到的大多數「基本操作」都是單個MIPS指令或者兩個，這在大多數當前CPU系列中可能都適用。

但是，這並沒有考慮到在所有任何現代CPU的架構和性能特點。不同的指令通常有不同的完成時間。目前的CPU通常實現分支預測，指令流水線，內存緩存，並行化和其他技術的完整列表，以使代碼執行更快。

因此，只要有一個算法的彙編代碼實現沒有說明它的執行速度。您必須在實際硬件上測量並剖析代碼以獲得可比較的結果。事實上，即使在相同的CPU系列中，某些算法在某些CPU上的效率也會更高。

一個常見而頗爲理解的例子是指令緩存的效果。展開一個循環將消除許多分支操作，這直觀地使代碼更快。但是，如果您在具有非常小的指令緩存內存的同一系列的CPU上運行該代碼，添加到主內存的訪問可能會使其比簡單的基於分支的循環慢得多。

Answer 2

電腦很複雜。如果你想要達到這個水平，你需要開始考慮你正在使用什麼類型的CPU，你的編譯器可以如何使用這個CPU的指令集，什麼變量保存在什麼寄存器中，它們的比特級表示是什麼，即使如此，指令的數量並不總是很容易映射到實際的運行時間。不同的指令可能需要不同的時鐘週期執行，這甚至不考慮操作系統線程和程序的緩存缺失率。

最後，還有我們在第一時間:)

---

使用大O notatoin BTW一個很好的理由，最簡單的操作（加，減）的整數應映射到一臺機器指導，以防你擔心。

Answer 3

這取決於CPU架構。一些處理器需要幾個週期來執行單個指令，例如divivide，而其他處理器則需要每個單週期執行所有機器代碼指令。

有時需要測量一個算法需要多少個浮點運算。但是，這不會考慮I/O（如讀取內存）。

CPU的速度有時在FLOPS（浮點運算每秒）中提供，這有助於給您一個時間估計。同樣，不考慮I/O - 而不是多線程問題（也是非常重要的測量因素）。

Answer 4

Donald Knuth在寫作「計算機程序設計藝術」第1卷中解決了這個問題。 在序言中，他給出了在彙編代碼中呈現算法的虛機一個漫長的理由 -

......爲了避免這種困境，我已經 試圖設計一個「理想」 計算機被稱爲「MIX，的算法將循環‘取「與操作非常簡單 規則...

這樣一來，就可以有多少理智地談’，而不必在意之間的機器，高速緩存，延遲差異，管道，或任何其他方式計算技術人員已經進行了優化以節省時間，但知道需要多長時間。