C尾呼叫優化

我經常聽到有人說C不執行尾呼叫消除。儘管標準沒有保證它，但是它在任何體面實施中都不是在實踐中執行的嗎？假設你只針對成熟，實現良好的編譯器，並且不關心針對爲不明顯平臺編寫的原始編譯器的絕對最大可移植性，那麼依靠C中的tail call消除是否合理？C尾呼叫優化

此外，將尾部呼叫優化離開標準的原因是什麼？

來源

2010-08-18 dsimcha

相關：http://stackoverflow.com/questions/2250727/regarding-stack-reuse-of-a-function-calling-itself – 2010-08-18 16:28:24

像「C不執行尾呼叫消除」這樣的語句沒有任何意義。正如你正確地指出自己，這樣的事情完全取決於實施。是的，任何體面的實現都可以很容易地將尾遞歸轉化爲[相當於]一個循環。當然，C編譯器通常不會保證什麼優化，哪些優化不會發生在每個特定的代碼中。你必須編譯它並親自查看。

來源

2010-08-18 16:27:51 AnT

回答你最後一個問題：標準絕對不應該對優化做任何說明。可能存在實施起來或多或少困難的環境。

來源

2010-08-18 16:28:16 Frank

+11

標準要求while循環運行在常量內存中是否是錯誤的？（除了while循環中的分配）標準要求尾遞歸函數在常量內存中運行會是錯誤的嗎？ – Jules 2010-08-18 16:55:12

我認爲Scheme需要tail-call優化，但Scheme是一種主要的函數式語言，大量使用遞歸作爲控制結構。 C程序往往遞歸較少，並且有不斷使用的迭代結構。 – 2010-08-18 17:04:25

語言標準定義了語言的行爲方式，而不是如何實現編譯器。優化不是強制性的，因爲它並不總是想要的。編譯器提供選項，以便用戶可以啓用優化，如果他們願意的話，也可以關閉它們。編譯器優化會影響調試代碼的能力（將C逐行匹配到程序集中變得更加困難），所以只根據用戶的請求執行優化是有意義的。

來源

2010-08-18 16:35:48 bta

只需要滿足特定要求的調用模式使用恆定的內存空間就會非常容易。這是語言如何行爲的一部分，以及如果您可以在程序中調用數百萬次而無需返回（如我編寫的一個依賴於編譯器TCO的程序那樣）的效果。 – 2014-05-30 15:39:40

我認爲只有在很多的遞歸是預期或需要的時候才需要保證尾部呼叫優化;也就是說，鼓勵或強化函數式編程風格的語言。（使用這些語言，您可能會發現for或while循環要麼強烈地被阻止，要麼被認爲不雅，要麼可能完全不在語言中，所以您會因爲所有這些原因而採用遞歸，可能更多。）

C編程語言（恕我直言）顯然是而不是考慮到功能編程的設計。有各種通常用於遞歸的循環結構：for,do .. while,while。在這樣的語言中，在標準中規定tail call優化沒有多大意義，因爲它不是嚴格要求保證工作程序。

再次與沒有while循環的函數式編程語言進行對比：這意味着您需要需要遞歸;這又意味着語言必須確保在迭代過程中堆棧溢出不會成爲問題;因此官方對這種語言的標準可能會選擇開尾通話優化。

P.S：注意，在我的論點爲尾調用優化的輕微缺陷。接近尾聲時，我提到堆棧溢出。但是誰說函數調用總是需要堆棧？在某些平臺上，函數調用可能以完全不同的方式實現，堆棧溢出甚至不會成爲問題。這將是另一個反對在標準中規定尾部呼叫優化的論點。（但是不要誤解我的意思，我可以看到這種優化的優點，即使沒有堆棧！）

來源

2010-08-18 16:46:56 stakx

然而，實現函數調用的一般情況將始終需要保存和恢復某個狀態。因此，總會有這樣的函數，使得嵌套的函數調用過多以填充可用內存來存儲這個狀態。傳統的數據結構是固定存儲器模塊中的一個堆棧，但它可以以不同的方式完成。尾部調用消除可以避免對某些函數進行保存和恢復，但調用兩次的非平凡函數將需要爲第二次調用存儲狀態。 – jilles 2010-08-18 22:22:26

@jilles：確切地說，無論函數調用如何工作，尾部調用優化都應該有助於保留內存。然而，CPU堆棧的一個特點是它的容量通常相對有限;比例如堆內存。這就是爲什麼我提到堆棧溢出，但不是更普遍的內存不足的原因;我認爲你需要一個幾乎難以置信的遞歸來耗盡例如2 GB的內存。 – stakx 2010-08-19 08:17:09

雖然現代編譯器可以在開啓優化的情況下進行尾部優化，但是您的調試版本可能會在沒有它的情況下運行，這樣您就可以獲取堆棧跟蹤並進入/退出代碼以及類似的美妙事物。在這種情況下，尾巴呼叫優化是不希望的。

由於尾調用優化並不總是可取的，因此將其委託給編譯器編寫者是沒有意義的。

來源

2014-05-01 17:34:55

有些情況下，尾部調用優化可能會破壞ABI，或者至少很難以語義保留的方式實現。例如，考慮共享庫中與位置無關的代碼：某些平臺允許程序根據庫動態鏈接，以便在各種不同應用程序都依賴於相同功能時節省主內存。在這種情況下，庫會加載一次並映射到每個程序的虛擬內存中，就像它是系統上唯一的應用程序一樣。在UNIX上和其他一些系統上，這是通過使用庫的位置無關代碼來實現的，因此尋址與偏移相關，而不是絕對地址到固定地址空間。然而，在許多平臺上，位置獨立代碼不能被尾調用優化。所涉及的問題是，導航程序的偏移必須保存在寄存器中;在Intel 32位上，使用%ebx這是一個被調用者保存的寄存器;其他平臺遵循這個概念。與使用普通調用的函數不同，部署尾調用的函數必須在分支到子例程之前恢復被調用者保存的寄存器，而不是在它們返回自己時。通常情況下，這沒有問題，因爲在這一點上，最頂級的調用函數並不關心存儲在%ebx中的值，但獨立於代碼的代碼依賴於每個跳轉，調用或分支命令時的該值。

其他問題可能是未完成的面嚮對象語言（C++）清理工作，這意味着函數中的最後一次調用實際上並不是最後一次調用 - 清理工作。因此，在這種情況下，編譯器通常不會優化。

另外setjmp和longjmp是有問題的，當然，因爲這實際上意味着函數可以在實際完成之前多次完成執行。編譯時難以或不可能優化！

人們可能會想到更多的技術原因。這些只是一些考慮因素。

來源

2018-02-17 10:04:27 nondeterministic

回答

相關問題