The GHC Specialization Guarantee
I'm trying to ensure that GHC specializes in recursive function so that everything is unpacked. The complete example code (as well as a GHC core dump) is available at this value . The corresponding function looks like this:
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)
It is an algorithm that looks for a value from any sorted container that can be indexed. The two functions I want to provide are specialized versions:
{-# 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 good news is that, looking at the resettable core , I see that GHC is already implementing specialization, which I That's impressive. However, I would like to be able to count on it. I am concerned that if I add enough specialized options to this file, or that if I call lookupSorted
from another module, GHC may end up leaning towards a small generated executable rather than a fast one.
I understand that pragma SPECIALIZE
does not help in a situation. GHC does not currently allow specialization based on value arguments . I'm sure if I want to write a class for an indexing operation, I can get the job done SPECIALIZE
. I'm trying to avoid this approach, although I don't want to introduce a class unless there is another solution.
Is there a way I can get GHC to create these specialized variants of my function? Also, if anyone has any comments on the dumped main file (if something is not optimal), I would appreciate any feedback on this. Thank.
---- EDIT ----
Thinking about it more, it seems like just putting the pragma INLINE
on is enough lookupSorted
. The GHC docs are not clear about the interaction between INLINE
and recursive binding within sentences let
or where
. Any clarification on this, hopefully with a source to back it up, might be helpful.
source to share
Your final observation is correct: if you put an annotation INLINE
on a function, it will be inlined when there is a call to it with sufficient arguments.
Sufficient arguments mean the number of parameters to your function to the left of =
(as opposed to lambdas to the right). This allows you to do things like
foo op n = \y -> go n y where go acc i = … op … fooSpec1 = foo (+) 0 fooSpec2 = foo (*) 1
and get two specializations foo
that you can then call many times without further code duplication.
For all this, it doesn't matter what happens in where
, and the recursive function will just be inlined in foo
.
(Sorry, you don't have a backup source.)
source to share