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
pragma가 도움이되지 않습니다. 현재 GHC는 does not allow specialization based on value arguments입니다. 꽤 인덱스 작업을위한 typeclass를 쓰고 싶다면 SPECIALIZE
을 만들 수 있다고 확신합니다. 나는 다른 접근법이 없다면 typeclass를 도입하고 싶지 않기 때문에이 접근법을 피하려고 노력하고있다.
GHC가 이러한 특수 기능의 변형을 생성하도록 강제 할 수있는 방법이 있습니까? 또한 누군가가 덤프 된 코어 파일에 대한 해설이있는 경우 (뭔가 최적이 아닌 경우), 이에 대한 의견을 보내 주시면 감사하겠습니다. 감사. 단순히 lookupSorted
상의 INLINE
프라그를 넣어에 충분한 수 있습니다처럼
---- 편집 ----
이 더에 대해 생각하는 것 같습니다. GHC 문서는 INLINE
과 let
또는 where
절 내의 재귀 바인딩 사이의 상호 작용에 명확하지 않습니다. 이것에 대한 모든 설명이 도움이 될 것입니다.