Межмодульная оптимизация в GHC

Question

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

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

-- 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

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

Если компилятор не знает тип, при котором должен использоваться код, он не может только создавать полиморфный код. И это плохо для производительности - я довольно удивлен, что здесь разница всего в ~2 раза. Полиморфный код означает, что для многих операций необходим поиск в классе типов, и это, по крайней мере, делает невозможным встраивание искомой функции или размеров с постоянным сгибом [например, для распакованного массива / векторного доступа].

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

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

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

Только маркировка

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 это тот, который имеет решающее значение здесь, но другие необходимы, чтобы 1. увидеть, что 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

сносно маленький.