保证与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专业化

回答

相关问题