Оптимизация перекрестных модулей в GHC

Question

У меня есть нерекурсивная функция для вычисления самой длинной общей подпоследовательности, которая, кажется, хорошо работает (ghc 7.6.1, скомпилирована с флагами -O2 -fllvm), если я измеряю ее с помощью Criterion в том же модуле. С другой стороны, если я преобразую функцию в модуль, экспортируйте именно эту функцию (как рекомендовано here), а затем снова измерьте с помощью Criterion, я получаю спад ~ 2x (который уходит, если я перехожу к критерию теста обратно в модуль где функция определена). Я попытался маркировать функцию с помощьюpragma, которая не имела никакого значения для измерения производительности кросс-модуля.

Мне кажется, что GHC может проводить анализ строгости, который хорошо работает, когда функция и основной (из которых доступна эта функция) находятся в одном модуле, но не тогда, когда они разделены. Я бы очень хотел, чтобы указатели на модульность функции, чтобы она хорошо работала при вызове из других модулей. Этот код слишком большой, чтобы вставить здесь - вы можете увидеть его here, если хотите попробовать. Небольшой пример того, что я пытаюсь сделать, это ниже (с фрагментами кода):

-- Function to find longest common subsequence given unboxed vectors a and b 
-- It returns indices of LCS in a and b 
lcs :: (U.Unbox a, Eq a) => Vector a -> Vector a -> (Vector Int,Vector Int) 
lcs a b | (U.length a > U.length b) = lcsh b a True 
     | otherwise = lcsh a b False 

-- This section below measures performance of lcs function - if I move it to 
-- a different module, performance degrades ~2x - mean goes from ~1.25us to ~2.4us 
-- on my test machine 
{-- 
config :: Config 
config = defaultConfig { cfgSamples = ljust 100 } 

a = U.fromList ['a'..'j'] :: Vector Char 
b = U.fromList ['a'..'k'] :: Vector Char 

suite :: [Benchmark] 
suite = [ 
      bench "lcs 10" $ whnf (lcs a) b 
     ] 

main :: IO() 
main = defaultMainWith config (return()) suite 
--} 

Answer 1

hammaris right, важным вопросом является то, что компилятор может увидеть тип, который lcs используется в одновременно так как он может видеть код, поэтому он может специализировать код для этого конкретного типа.

Если компилятор не знает тип использования кода, он не может не только генерировать полиморфный код. И это плохо для производительности - я довольно удивлен, что это только разница в 2 ×. Полиморфный код означает, что для многих операций требуется поиск типа-типа и, по меньшей мере, делает невозможным встроенную функцию поиска или константные размеры (например, для unboxed array/vector access].

Вы не можете получить сопоставимую производительность с одномодовым корпусом с реализацией и использовать в отдельных модулях, не создавая код, который нуждается в специализации, видимый на используемом сайте (или, если вы знаете необходимые типы на сайте внедрения, специализируясь там , {-# SPECIALISE foo :: Char -> Int, foo :: Bool -> Integer #-} и т.п.).

Создание кода, видимого на рабочем месте, обычно выполняется путем раскрытия разворачивания в файле интерфейса посредством маркировки функции {-# INLINABLE #-}.

Я пробовал обозначать функцию с помощьюpragma, которая не имела никакого значения в измерениях производительности кросс-модуля.

Маркировка только

lcs :: (U.Unbox a, Eq a) => Vector a -> Vector a -> (Vector Int,Vector Int) 
lcs a b | (U.length a > U.length b) = lcsh b a True 
     | otherwise = lcsh a b False 

INLINE или INLINABLE не делает разницы, конечно, эта функция является тривиальным, и компилятор выставляет его разворачивания в любом случае, так как это очень мало. Даже если его разворачивание не было раскрыто, разница не была бы измеримой.

Вы должны разоблачить развертки функций делают фактическую работу тоже, по крайней мере, из полиморфных них, lcsh, findSnakes, gridWalk и cmp (cmp это один, что крайне важно здесь, но другие необходимы- см., что необходимо cmp, 2. вызвать у них специализированный cmp).

Выполнение этих INLINABLE, разница между отдельным-модулем случае

$ ./diffBench 
warming up 
estimating clock resolution... 
mean is 1.573571 us (320001 iterations) 
found 2846 outliers among 319999 samples (0.9%) 
    2182 (0.7%) high severe 
estimating cost of a clock call... 
mean is 40.54233 ns (12 iterations) 

benchmarking lcs 10 
mean: 1.628523 us, lb 1.618721 us, ub 1.638985 us, ci 0.950 
std dev: 51.75533 ns, lb 47.04237 ns, ub 58.45611 ns, ci 0.950 
variance introduced by outliers: 26.787% 
variance is moderately inflated by outliers 

и корпус одномодульного

$ ./oneModule 
warming up 
estimating clock resolution... 
mean is 1.726459 us (320001 iterations) 
found 2092 outliers among 319999 samples (0.7%) 
    1608 (0.5%) high severe 
estimating cost of a clock call... 
mean is 39.98567 ns (14 iterations) 

benchmarking lcs 10 
mean: 1.523183 us, lb 1.514157 us, ub 1.533071 us, ci 0.950 
std dev: 48.48541 ns, lb 44.43230 ns, ub 55.04251 ns, ci 0.950 
variance introduced by outliers: 26.791% 
variance is moderately inflated by outliers 

является bearably мало.