Optymalizacje w module krzyżowym w GHC

Question

Mam funkcję nierekurencyjną do obliczania najdłuższego wspólnego podciągu, który wydaje się dobrze działać (ghc 7.6.1, skompilowany z flagami -O2 -fllvm), jeśli zmierzę go z Criterion w tym samym module. Z drugiej strony, jeśli przekonwertuję funkcję na moduł, wyeksportuję właśnie tę funkcję (zgodnie z zaleceniem here), a następnie zmierzę ponownie za pomocą kryterium, otrzymuję ~ 2x spowolnienie (które znika, gdy przeniosę test kryterium z powrotem do modułu gdzie zdefiniowana jest funkcja). Próbowałem zaznaczyć funkcję z pragma INLINE, która nie miała wpływu na pomiary wydajności między modułami.

Wydaje mi się, że GHC może przeprowadzać analizę ścisłości, która działa dobrze, gdy funkcja i główna (z której funkcja jest dostępna) znajdują się w tym samym module, ale nie wtedy, gdy są rozdzielone. Byłbym wdzięczny za wskazówki, jak modularyzować funkcję tak, aby działała dobrze po wywołaniu z innych modułów. Kod, o którym mowa, jest zbyt duży, aby go tu wkleić - możesz go zobaczyć here, jeśli chcesz go wypróbować. Mały przykład tego, co próbuję zrobić, to poniżej (z fragmentów kodu):

-- 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, ważną kwestią jest to, że kompilator widzi typ że lcs jest używany w jednocześnie jak widać kod, dzięki czemu może specjalizować kod do tego konkretnego typu.

Jeśli kompilator nie zna typu, w którym kod ma być używany, może jedynie wygenerować kod polimorficzny. I to jest złe dla wydajności - jestem raczej zaskoczony, że to tylko różnica ~ 2 × tutaj. Kod polimorficzny oznacza, że ​​dla wielu operacji potrzebne jest wyszukiwanie klasy typów, co przynajmniej uniemożliwia wstawienie funkcji sprawdzania lub składanie w stałych rozmiarach [np. do rozpakowanego dostępu do tablicy/wektora].

Nie można uzyskać porównywalnej wydajności w przypadku modułu jednomodułowego z implementacją i używaniem w oddzielnych modułach bez tworzenia kodu wymagającego specjalizacji widocznej na stronie użytkowania (lub, jeśli znasz wymagane typy na stronie wdrożenia, specjalizującej się w tym celu) , {-# SPECIALISE foo :: Char -> Int, foo :: Bool -> Integer #-} itp.).

Dokonywanie kodu widocznego na stronie użytkowania odbywa się zazwyczaj poprzez ujawnienie rozłożenia w pliku interfejsu poprzez oznaczenie funkcji {-# INLINABLE #-}.

Próbowałem oznaczania funkcji z INLINE Pragma, która nie robi żadnej różnicy w pomiarach wydajności cross-modułowych.

Znakowanie tylko

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 lub INLINABLE nie czyni różnicę oczywiście, że funkcja jest trywialne, a kompilator naraża jego rozkładanie i tak, ponieważ jest tak mały. Nawet gdyby jego rozwijanie nie było odsłonięte, różnica nie byłaby mierzalna.

Trzeba wystawiać na dalsze odkrywanie o funkcjach robić rzeczywistej pracy też, przynajmniej z polimorficznych tych, lcsh, findSnakes, gridWalk i cmp (cmp to taka, która jest kluczowa tutaj, ale inni są niezbędne do 1 zobacz, czy potrzebujesz cmp, 2. zadzwoń do wyspecjalizowanego cmp od nich).

Wykonywanie tych INLINABLE różnica pomiędzy przypadku oddzielnego modułu

$ ./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 

i w przypadku pojedynczej modułu

$ ./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 

jest bearably małe.