Implikacje wydajności parametrycznych typów GHC - haskell, ghc

Zmotywuję ogólne pytanie bardziej konkretnym:

W GHC Haskell, a Cofree [] a mają taką samą wydajność jak containers-styl Data.Tree a? A może dodatkowy polimorfizm wiąże się z jakimś kosztem czasu wykonywania?

Ogólnie rzecz biorąc, czy istnieją dodatkowe koszty w czasie wykonywania związane ze wzrostem „arity” rodzaju?

Odpowiedzi:

Myślę, że bardziej klasyczny konkretny przykład byłby czymś takim jak wektory lub tablice. The pakiet wektorowy eksportuje zarówno wektory „zapakowane”, jak i „rozpakowane”. Podczas gdy wektory w pudełkach mogą zawierać dowolny typ Haskella (w tym funkcje), wektory w pudełkach wymagają, aby jego elementy były instancją Unbox klasa typu. Chociaż oznacza to bardziej wydajną reprezentację upakowanej pamięci bez pośrednich wskaźników, nie można zdefiniować Functor instancja dla wektorów nieopakowanych, więc wiąże się to z utratą ogólności.

Jeśli skorzystałeś z

fmap :: (a -> b) -> Vector a -> Vector b

w funkcji typu

f :: Functor f => f SomeType -> f SomeOtherType

„Słownik”, czyli rekord z odpowiednim fmap implementacja zostanie przekazana w czasie wykonywania jako dodatkowy niejawny argument. Możesz to zobaczyć, patrząc na dane wyjściowe „Core” produkowane przez GHC, przy użyciu -ddump-simpl flaga. W szczególności arity f powyżej byłyby dwa zamiast jednego.

W niektórych przypadkach GHC może zoptymalizować ten narzut, tworząc specjalistyczne wersje twoich funkcji. Możesz pomóc za pomocą SPECJALIZACJA / WKŁADKA / ... pragmy, używając jawnych list eksportu, może dodając trochę surowości i kilka innych drobnych poprawek, które są również opisane w dokumentacji.

Odnośnie narzutu związanego z używaniem parametrycznymtypy polimorficzne, to oczywiście zależy. Moim najgorszym przypadkiem był czynnik 100 w wewnętrznej pętli numerycznej (który został rozwiązany przez dodanie jednej pragmy SPECIALIZE), więc mogą rzeczywiście cię gryźć. Na szczęście przy użyciu narzędzi do profilowania i pamiętając, że słowniki wpływają na działanie funkcji, śledzenie tych problemów staje się bardzo systematyczne.