Specjalizacja z ograniczeniami

156

Mam problemy ze skonfigurowaniem GHC do specjalizacji funkcji z ograniczeniem klasy. Mam minimalny przykład mój problem tutaj: Foo.hs i Main.hs . Te dwa pliki są kompilowane (GHC 7.6.2 ghc -O3 Main) i uruchamiane.

UWAGA: Foo.hs jest naprawdę okrojona. Jeśli chcesz zobaczyć, dlatego też konieczne jest ograniczenie, można zobaczyć trochę więcej kodu tutaj . Jeśli umieszczę kod w jednym pliku lub wprowadzę wiele innych drobnych zmian, GHC po prostu wstawia wywołanie do plusFastCyc. To się nie stanie w prawdziwym kodzie, ponieważ plusFastCycjest zbyt duży, aby GHC mógł go wbudować, nawet gdy jest oznaczony INLINE. Chodzi o to, aby specjalizować wywołanie plusFastCyc, a nie je wbudować. plusFastCycjest wywoływana w wielu miejscach w rzeczywistym kodzie, więc powielanie tak dużej funkcji nie byłoby pożądane, nawet gdybym mógł do tego zmusić GHC.

Interesujący jest kod plusFastCycin Foo.hs, odtworzony tutaj:

{-# INLINEABLE plusFastCyc #-}
{-# SPECIALIZE plusFastCyc :: 
         forall m . (Factored m Int) => 
              (FastCyc (VT U.Vector m) Int) -> 
                   (FastCyc (VT U.Vector m) Int) -> 
                        (FastCyc (VT U.Vector m) Int) #-}

-- Although the next specialization makes `fcTest` fast,
-- it isn't useful to me in my real program because the phantom type M is reified
-- {-# SPECIALIZE plusFastCyc :: 
--          FastCyc (VT U.Vector M) Int -> 
--               FastCyc (VT U.Vector M) Int -> 
--                    FastCyc (VT U.Vector M) Int #-}

plusFastCyc :: (Num (t r)) => (FastCyc t r) -> (FastCyc t r) -> (FastCyc t r)
plusFastCyc (PowBasis v1) (PowBasis v2) = PowBasis $ v1 + v2

Main.hsPlik ma dwóch kierowców: vtTest, czyli w ~ 3 sekundy, a fcTest, która biegnie w ~ 83 sekund, gdy skompilowany z użyciem -O3 forall„d specjalizacji.

Do podstawowych pokazuje , że w vtTestteście kod dodatek jest specjalistyczne, Unboxedwektory ponad Ints, itp, a rodzajowy kod wektor stosuje fcTest. W linii 10. widać, że GHC pisze wyspecjalizowaną wersję programu plusFastCyc, w porównaniu z wersją ogólną w linii 167. Reguła dla specjalizacji jest w linii 225. Uważam, że ta reguła powinna zostać uruchomiona w linii 270. ( main6wywołania iterate main8 y, więc main8jest gdzie plusFastCycpowinien być wyspecjalizowany.)

Moim celem jest robić fcTesttak szybko, jak vtTestspecjalizując się plusFastCyc. Znalazłem na to dwa sposoby:

  1. Wezwanie explicity inlineod GHC.Extsw fcTest.
  2. Usuń Factored m Intograniczenie na plusFastCyc.

Opcja 1 jest niezadowalająca, ponieważ w rzeczywistej bazie kodu plusFastCycjest często używaną operacją i bardzo dużą funkcją, więc nie powinna być wprowadzana przy każdym użyciu. Zamiast tego GHC powinien wywołać wyspecjalizowaną wersję plusFastCyc. Opcja 2 nie jest tak naprawdę opcją, ponieważ potrzebuję ograniczenia w prawdziwym kodzie.

Próbowałem różnych opcji przy użyciu (a nie przy użyciu) INLINE, INLINABLEoraz SPECIALIZE, ale nic nie wydaje się do pracy. ( EDYCJA : Być może usunąłem zbyt wiele, plusFastCycaby mój przykład był mały, więc INLINEmoże to spowodować wstawienie funkcji. Nie dzieje się tak w moim prawdziwym kodzie, ponieważ plusFastCycjest tak duży). W tym konkretnym przykładzie nie jestem otrzymuję ostrzeżenia match_co: needs more caseslub RULE: LHS too complicated to desugar(i tutaj ), chociaż otrzymywałem wiele match_coostrzeżeń przed zminimalizowaniem przykładu. Przypuszczalnie „problemem” jest Factored m Intograniczenie reguły; jeśli wprowadzę zmiany w tym ograniczeniu, fcTestdziała tak szybko, jak vtTest.

Czy robię coś, czego GHC po prostu nie lubi? Dlaczego GHC nie specjalizuje się w tym plusFastCyci jak mogę to zrobić?

AKTUALIZACJA

Problem występuje nadal w GHC 7.8.2, więc to pytanie jest nadal aktualne.

crockeea
źródło
3
Właśnie spróbowałem specjalizować się w konkretnym m , a mianowicie M. Wykonało to zadanie, ale nie mogę specjalizować się w konkretnych typach fantomów w prawdziwym programie, ponieważ są one reifikowane.
crockeea
Przesłałem również raport o błędzie GHC ghc.haskell.org/trac/ghc/ticket/8668, ale problem jest nadal otwarty. Proces zgłaszania błędów pomógł mi trochę uporządkować pytanie, więc mam nadzieję, że łatwiej będzie mi zrozumieć, co się dzieje.
crockeea
@monojohnny Przykro mi to słyszeć, myślę, że możesz to oznaczyć jako takie. Myślę, że proszę GHC o zrobienie czegoś dość rozsądnego, a to tego nie zrobi. Nie jestem pewien, czy robię to źle, czy też jest to idiosynkrazja z kompilatorem, która może mieć obejście. Widziałem obejścia specjalizacji i reguł w jakiejś konkretnej bibliotece dotyczącej hakowania, które w tej chwili mi umykają, więc mam nadzieję, że ktoś w społeczności z większym doświadczeniem w GHC niż ja może wiedzieć, jak osiągnąć specjalizację.
crockeea
1
Przepraszam za ton mojego komentarza - to nie jest mój najlepszy wkład w tę stronę - naprawdę nie ma nic złego w twoim poście (to mój brak zrozumienia był źródłem mojej irytacji, jak sądzę!)
monojohnny
@monojohnny Przeprosiny przyjęte, ale szkoda, że ​​głos przeciwny jest teraz zablokowany ;-)
crockeea

Odpowiedzi:

5

GHC udostępnia również opcję SPECIALIZEdeklaracji wystąpienia klasy typu. Wypróbowałem to z (rozszerzonym) kodem Foo.hs, wstawiając:

instance (Num r, V.Vector v r, Factored m r) => Num (VT v m r) where 
    {-# SPECIALIZE instance ( Factored m Int => Num (VT U.Vector m Int)) #-}
    VT x + VT y = VT $ V.zipWith (+) x y

Ta zmiana nie przyniosła jednak pożądanego przyspieszenia. To, co pozwoliło osiągnąć tę poprawę wydajności, to ręczne dodanie wyspecjalizowanej instancji dla typu VT U.Vector m Intz tymi samymi definicjami funkcji w następujący sposób:

instance (Factored m Int) => Num (VT U.Vector m Int) where 
    VT x + VT y = VT $ V.zipWith (+) x y

Wymaga to dodawanie OverlappingInstancesi FlexibleInstancesw LANGUAGE.

Co ciekawe, w przykładowym programie przyspieszenie uzyskane z nakładającą się instancją pozostaje, nawet jeśli usuniesz wszystkie SPECIALIZEi INLINABLEpragma.

Diego E. Alonso-Blas
źródło
Zdecydowanie nie optymalne, ale to pierwsze rozwiązanie, które faktycznie osiąga cel, więc myślę, że wezmę to na razie ...
crockeea