內聯如何比遞歸定義更高效？

我的編程範式教科書，Essential of Programming Languages (3rd ed)，第1章有一個練習：內聯如何比遞歸定義更高效？

練習1.12

消除一個呼叫通過其定義替換它，並簡化爲subst式-S-EXP在SUBST由此產生的程序。結果將是不需要 subst-in-s-exp的子版本。這種技術被稱爲內聯，並被優化編譯器使用。

原始代碼將有兩個功能：subst和subst-in-sexp基本上代替舊符號與輸入列表中的新符號的所有事件。

(define subst 
    (lambda (new old slist) 
    (if (null? slist) '() 
     (cons 
     (subst-in-s-exp new old (car slist)) 
     (subst new old (cdr slist)))))) 

(define subst-in-s-exp 
    (lambda (new old sexp) 
    (if (symbol? sexp) 
     (if (eqv? sexp old) new sexp) 
     (subst new old sexp))))

回答這個問題是消除subst-in-sexp，成爲這個

(define subst 
    (lambda (slist old new) 
    (cond 
     [ (null? slist) '()] 
     [ (eqv? (car slist) old) (cons new (subst (cdr slist) old new))] 
     [ else (cons (car slist) (subst (cdr slist) old new))])))

爲什麼在襯裏之外的更好，可能很多短（更少的空間）？遞歸的大小是否改變？換句話說，這種內聯是否會創建更少的堆棧元素？

此外，我怎樣才能使用這個想法使我的C++，Python和Java代碼更快？我可以輕鬆地擴展這個想法嗎？謝謝。

我在Scheme中標記了它（實際上是Racket），因爲這是書中語言的選擇。

來源

2012-02-13 CppLearner

是的，它應該減少少量堆棧幀的開銷，但是現在這不是真正的問題，代碼可讀性更重要，編譯器可能會將其優化爲完全不同的東西。 – AoeAoe 2012-02-13 08:25:41

內聯是一種非常標準的編譯器優化，但正如AoeAoe所說，編寫代碼通常更好，因此它的可讀性讓編譯器爲你做了所有內聯。

內聯的直接好處是它消除了代碼中的分支。這意味着您的CPU可以持續讀取代碼，而不必花費幾個時鐘週期來查找要執行的代碼的下一部分。

但是，內聯還有其他一些好處。你最終會得到更多的代碼塊，這意味着編譯器有更多的代碼和數據可供使用。它可能能夠在寄存器中粘貼更多的東西，或者不斷摺疊以消除更多的計算。編譯器也可以更好地執行指令調度，因爲它有更多的指令可以移動。

缺點是內聯增加了你的結果代碼的大小。特別是在現代CPU運行速度比內存快得多的情況下，爲了保留L1高速緩存中所有熱門代碼，通常最好少插入一些代碼。

來源

2012-02-13 20:28:51

爲Eric的答案增加了一點，內聯可以是動態類型語言的一個重大勝利，內聯調用可能使編譯器可以將實現專門化爲出現的各種數據。

舉例來說：假設我有一個函數調用F：

(define (f x) (+ (* x x) 3.0))

...我在線稱之爲：

(+ (f 3.2) (g 3.9))

在這種情況下，內聯代碼清楚地表明乘法和加法不能與非數字被調用，所以這個錯誤檢查可以省略。

來源

2012-02-13 22:51:19

回答：「我怎樣才能使用這個想法讓我的C++，Python和Java代碼更快？」

我不認爲Python運行庫會自動內聯小方法。（如果這是錯誤的，請有人糾正我！）所以在Python中，如果你有一段代碼，它對性能非常敏感，可能在內部循環中運行數萬甚至數百萬次，你可以嘗試內聯手動。只有這樣做，如果代碼確實是一個瓶頸，並且它確實需要儘可能快，並且總是測量以查看這樣的優化是否實際上有助於任何事情。（如果嘗試插入內容並且沒有幫助，最好撤消優化，因爲內聯通常會使代碼難以閱讀。）

在Java和C++中，任何優秀的編譯器都會爲您內聯小型方法。可以（有時）做的事情，是幫助編譯器看到一個方法可以被內聯。如果調用的確切方法取決於對象的運行時類型（如在C++中使用virtual方法），編譯器將無法內聯該調用。 Java中的方法可以很容易地內聯，並且聲明方法爲final（如果這樣做有道理）也可以使編譯器內聯。

如果您將來了解了編譯器及其工作方式的更多信息，您最好能夠看到如何編寫性能敏感的代碼，以便編譯器能夠爲您優化。

來源

2012-02-13 23:32:26

內聯如何比遞歸定義更高效？

回答

相關問題