確定在什麼情況下什麼變量是常數

Question

這個想法有點類似於Apple has done in the OpenGL stack。我想要更一般一點。

基本上，我想對某些特定情況有一些代碼的專門和優化的變體。

換句話說：我已給定了算法/代碼的函數（讓B = {0,1}）

f : B^n -> B^m 

現在，我通過特殊的功能的特定情況（其預先定義的一部分的˚F輸入）

preset : {1..n} -> {0,1,unset} 

predefinitions（∈的量{0..N}）然後通過

pn := |preset⁻¹({0,1})| 

給定

規範地，我們現在得到一個專業功能

f_preset : B^(n-pn) -> B^m 

同時規範地，我們得到這個特殊函數的代碼/算法。當然，f_preset的代碼將比pk> 0的f更快。然後，您還可以進一步優化此代碼（現在可能會有一些死代碼，現在可能會有一些循環解壓縮，一些計算可以預先計算等）。在某些情況下，它可以有顯着的改進。

蘋果公司爲他們的OpenGL堆棧做了大致的工作（從我已經閱讀/瞭解的內容）：他們試圖在運行時找到一個好的預設，然後爲不會改變的變量設置一個優化版本專門的功能，只使用那個而不是原來的功能。

最初，我想到了一種方法來優化一些自己的遊戲的物理模擬。在那裏我有很多粒子對象和一組粒子類型（這在編譯時是未知的）。粒子類型是一組屬性。一旦它們被加載，粒子類型是固定的並且是恆定的。每個粒子對象都是其中一種粒子類型。粒子對象的物理模擬是許多分支代碼的非常重要的和平，並且非常依賴於粒子類型。我的想法是現在爲每個粒子類型都有一個優化的物理模擬功能。

思考了一下這個之後，我想去遠一點：

我希望在運行時自動計算一組這樣的預設和維護每個優化的代碼。我想在環境發生變化時自動添加或刪除預設。

現在有幾個問題：

• 有一種簡單的方法來計算一個好的預置？我怎麼知道哪些變量對於一個給定的情況是不變的？
• 有沒有簡單的方法來檢查一個預設有多好？ 「好」是指所得優化代碼的性能。
• 如何比較兩種算法/代碼的性能？通過一些啓發式？或通過隨機輸入測試？
• 應該有多少預設（和優化的代碼變體）？所有功能的固定限制？或者每個功能都有所不同？它甚至可能取決於當前的計算機狀態？
• 如何維護不同的優化代碼變體？一個包裝函數大約f它自動選擇最佳優化變體似乎不是很好，因爲這可能不是那麼容易檢查將需要每一個電話。這個問題的解決方案也可能與如何找到好的預設集合/數量有關。 （在粒子類型的情況下，優化的代碼將與粒子類型一起附加/保存，粒子類型的數量也定義了預設的數量。）

對於我的第一種情況，大多數這些問題有點過時了，但我現在對如何以更一般的方式做到這一點非常感興趣。當然，大多數/所有這些問題都是不可計算的，但我想知道你在多大程度上仍然可以獲得好的結果。

這整個主題對於JIT編譯器的優化也非常重要。他們是否已經進行了這種優化？到什麼程度？

有沒有很好的最近的研究工作，回答我的一些問題？或者，也許還有一些結果表明，以這種普遍的方式做這件事實在太難了？

Answer 1

在我看來，你在問關於partial evaluation。

我實際上對這個概念有點問題，因爲它通常是過度學術和過度困難的術語。

它通常表達的方式是，你有一些通用函數F(Islow, Ifast)具有可以在不同時間取不同值的參數。參數Islow很少發生變化，並且Ifast參數在每次調用時都會有所不同。

那麼問題是寫某種局部評估函數G(F, Islow) -> F1(Ifast)的該取功能F和Islow參數，併產生一個新的（簡單的）函數F1即只在該Ifast參數。

問題在於：1）有人必須編寫一般功能F，以及2）有人必須編寫通用部分評估程序G。

什麼更有意義，我是從頭功能H(Islow) -> F1(Ifast)寫，就是寫具體代碼生成器爲F1，而不是寫兩個功能F和G，特別是在G是很難寫。

H通常比F更容易編寫，而G也不需要寫！結果函數F1通常比F更小，性能更高，所以這是一個雙贏的局面。

當人們編寫代碼生成器時，這就是他們正在做的事情，它是一種非常有效的編程技術。