Оптимизация кросс-модуля в GHC

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

Мне кажется, что 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
--}

Ответы

Ответ 1

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

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

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

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

Я попытался маркировать функцию с помощью INLINE 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 - это тот, который имеет решающее значение здесь, но остальные необходимы, чтобы 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

имеет малую величину.