GHC专业化保证

Question

我正在尝试确保 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 pragma 在这种情况下没有帮助。 GHC 当前 does not allow specialization based on value arguments。我很确定，如果我愿意为索引操作编写一个类型类，那么我可以使 SPECIALIZE 工作。我试图避免这种方法，因为除非没有其他解决方案，否则我不想引入类型类。

有没有办法强制 GHC 创建我的函数的这些特殊变体？此外，如果有人对转储的核心文件有任何评论（如果某些内容不是最佳的），我将不胜感激。谢谢。

----编辑----

再考虑一下，似乎在 lookupSorted 上简单地放置一个 INLINE pragma 似乎就足够了。 GHC 文档不清楚 INLINE 和 let 或 where 子句中的递归绑定之间的交互。对此的任何澄清，希望有支持它的来源，可能会有所帮助。

Answer 1

你最后的观察是正确的：如果你在一个函数上放置一个 INLINE 注释，只要有足够的参数调用它，它就会被内联。

足够的参数意味着 = 左侧的函数参数数量（相对于右侧的 lambda）。这使您可以执行

之类的操作

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

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

并获得 foo 的两个特化，然后您可以多次调用它们而无需进一步的代码重复。

尽管如此，where 中发生的事情并不重要，递归函数将仅内联 foo。

（抱歉，没有任何来源可以支持这一点。）

GHC专业化保证

Guarantee of Specialization with GHC

haskell

ghc