保證與GHC專業化

我試圖確保GHC專門遞歸函數，以便所有的東西都被拆箱。完整的示例代碼（以及GHC核心轉儲）可在this gist中找到。有問題的功能如下：保證與GHC專業化

import Data.Bits          
import qualified Data.Vector.Unboxed as UV 

lookupSorted :: Ord a => (Int -> a) -> Int -> a -> Maybe Int 
lookupSorted lookupIx len needle =     
    let !r = go 0 (len - 1)     
    in if r < 0 then Nothing else Just r      
    where          
    go :: Int -> Int -> Int     
    go !lo !hi = if lo <= hi 
    then             
     let !mid = lo + (unsafeShiftR (hi - lo) 1)    
      !val = lookupIx mid      
     in case compare val needle of       
      EQ -> mid            
      LT -> go (mid + 1) hi            
      GT -> go lo (mid - 1)         
    else (-1)

這是從任何排序容器查找的數值相比，可以索引到的算法。我想，以確保這兩個功能是本專業版本是：

{-# NOINLINE lookupUnboxedWord #-} 
lookupUnboxedWord :: UV.Vector Word -> Word -> Maybe Int 
lookupUnboxedWord v w = lookupSorted (UV.unsafeIndex v) (UV.length v) w 

{-# NOINLINE lookupUnboxedDouble #-}   
lookupUnboxedDouble :: UV.Vector Double -> Double -> Maybe Int 
lookupUnboxedDouble v w = lookupSorted (UV.unsafeIndex v) (UV.length v) w

好消息是，從看the dumped core，我可以看到，GHC已經執行，我很感興趣的專業化。這非常令人印象深刻。不過，我希望能夠指望它發生。我擔心，如果我爲該文件添加足夠多的專用變體，或者如果我從另一個模塊中調用lookupSorted，GHC可能最終傾向於生成一個小型可執行文件而不是一個快速文件。

我的理解是SPECIALIZE編譯在這種情況下不起作用。 GHC目前does not allow specialization based on value arguments。我很確定，如果我願意爲索引操作編寫類型類型，那麼我可以使SPECIALIZE工作。我試圖避免這種方法，因爲除非沒有其他解決方案，否則我不想引入類型類。

有沒有辦法強制GHC創建我的函數的這些專門變體？此外，如果任何人對轉儲的核心文件有任何評論（如果有什麼不是最佳的），我將不勝感激任何反饋。謝謝。

---- ----編輯

更多這方面的思考，好像它可能是足夠簡單地把一個INLINE編譯上lookupSorted。 GHC文檔不清楚INLINE和let或where子句中的遞歸綁定之間的相互作用。任何關於此的澄清，希望有一個支持來源，可能會有所幫助。

來源

2017-04-12 Andrew Thaddeus Martin

你最後的觀察是正確的：如果你在一個函數上加了一個INLINE註解，當它有足夠的參數調用時，它將被內聯。

足夠的參數意味着=左邊的函數的參數個數（與右邊的lambda表達式相反）。這允許你做這樣的事情

foo op n = \y -> go n y 
    where go acc i = … op … 

fooSpec1 = foo (+) 0 
fooSpec2 = foo (*) 1

，並得到foo兩個專業，你則可以調用很多次都沒有進一步的代碼重複。

對於所有這些，where中發生的事情並不重要，遞歸函數只會與foo內聯。

（對不起，沒有資料可以支持。）

來源

2017-04-13 00:06:37

保證與GHC專業化

回答

相關問題