Wydajność pamięci Haskell - jakie jest lepsze podejście?

Wdrażamy bibliotekę kompresji macierzy opartą na zmodyfikowanej dwuwymiarowej składni gramatycznej. Teraz mamy dwa podejścia do naszych typów danych - które będzie lepsze w przypadku użycia pamięci? (chcemy coś skompresować;)).

Gramatyki zawierają NonTerminals z dokładnie 4 produkcjami lub Terminal po prawej stronie. Będziemy potrzebować nazw Productions do kontroli równości i minimalizacji gramatyki.

Pierwszy:

-- | Type synonym for non-terminal symbols
type NonTerminal = String

-- | Data type for the right hand side of a production
data RightHandSide = DownStep NonTerminal NonTerminal NonTerminal NonTerminal | Terminal Int

-- | Data type for a set of productions
type ProductionMap = Map NonTerminal RightHandSide

data MatrixGrammar = MatrixGrammar {
    -- the start symbol
    startSymbol :: NonTerminal,
    -- productions
    productions :: ProductionMap    
    } 

Tutaj nasze dane RightHandSide zapisują tylko nazwy ciągów, aby określić następne produkcje, a nie wiemy tutaj, w jaki sposób Haskell zapisuje te ciągi. Na przykład macierz [[0, 0], [0, 0]] ma 2 produkcje:

a = Terminal 0
aString = "A"
b = DownStep aString aString aString aString
bString = "B"
productions = Map.FromList [(aString, a), (bString, b)]

Pytanie brzmi więc, jak często naprawdę zapisywany jest ciąg „A”? Raz w aString, 4 razy wb i raz w produkcjach, czy tylko raz w aString, a inni mają tylko „tańsze” referencje?

Drugi:

data Production = NonTerminal String Production Production Production Production
                | Terminal String Int 

type ProductionMap = Map String Production

tutaj termin „Terminal” jest nieco mylący, ponieważ w rzeczywistości jest to produkcja, która ma terminal po prawej stronie. Ta sama matryca:

a = Terminal "A" 0
b = NonTerminal "B" a a a a
productions = Map.fromList [("A", a), ("B", b)]

i podobne pytanie: jak często Haskell oszczędza produkcję wewnętrznie? Być może upuścimy nazwiska w produkcjach, jeśli nie będziemy ich potrzebować, ale nie jesteśmy w tej chwili pewni.

Powiedzmy, że mamy gramatykę z około 1000 produkcji. Które podejście zużyje mniej pamięci?

Na koniec pytanie o liczby całkowite w Haskell: Obecnie planujemy mieć nazwę Strings. Ale moglibyśmy z łatwością zmienić nazwy na liczby całkowite, ponieważ przy 1000 produkcjach będziemy mieli nazwy zawierające więcej niż 4 znaki (które zakładam, że to 32 bity?). Jak Haskell sobie z tym radzi. Czy liczba Int zawsze jest 32-bitowa, a liczba całkowita przydziela pamięć, której tak naprawdę potrzebuje?

Przeczytałem również to: Opracowując test wartości / referencji semantyki Haskella - ale nie mogę zrozumieć, co to dla nas dokładnie znaczy - jestem bardziej imperatywnym dzieckiem Javy niż dobrym programistą: P

Możesz rozwinąć gramatykę macierzy w ADT z doskonałym udostępnianiem z odrobiną sztuczki:

{-# LANGUAGE DeriveFunctor, DeriveFoldable, DeriveTraversable #-}

import Data.Map
import Data.Foldable
import Data.Functor
import Data.Traversable

-- | Type synonym for non-terminal symbols
type NonTerminal = String

-- | Data type for the right hand side of a production
data RHS a = DownStep NonTerminal NonTerminal NonTerminal NonTerminal | Terminal a
  deriving (Eq,Ord,Show,Read,Functor, Foldable, Traversable)

data G a = G NonTerminal (Map NonTerminal (RHS a))
  deriving (Eq,Ord,Show,Read,Functor)

data M a = Q (M a) (M a) (M a) (M a) | T a
  deriving (Functor, Foldable, Traversable)

tabulate :: G a -> M a
tabulate (G s pm) = loeb (expand <$> pm) ! s where
  expand (DownStep a11 a12 a21 a22) m = Q (m!a11) (m!a12) (m!a21) (m!a22)
  expand (Terminal a)               _ = T a

loeb :: Functor f => f (f b -> b) -> f b
loeb x = xs where xs = fmap ($xs) x

Tutaj uogólniłem twoje gramatyki, aby pozwolić na dowolny typ danych, nie tylko Int, i tabulatewezmę gramatykę i rozwinę ją, składając ją na siebie za pomocą loeb.

loebjest opisany w artykule Dana Piponiego

Wynikowe rozszerzenie jako ADT fizycznie nie zajmuje więcej pamięci niż oryginalna gramatyka - w rzeczywistości zajmuje nieco mniej, ponieważ nie potrzebuje dodatkowego współczynnika log dla kręgosłupa mapy i nie musi przechowywać w ogóle struny.

W przeciwieństwie do naiwnego rozszerzenia, użycie loebpozwala mi „związać węzeł” i dzielić się thunkami za wszystkie wystąpienia tego samego nieterminalnego.

Jeśli chcesz pogłębić teorię tego wszystkiego, możemy zobaczyć, że RHSmożna to zmienić w podstawowy funktor:

data RHS t nt = Q nt nt nt nt | L t

a następnie mój typ M jest tylko stałym punktem tego Functor.

M a ~ Mu (RHS a)

podczas gdy G askładałby się z wybranego ciągu i mapy od ciągów do (RHS String a).

Następnie możemy rozwinąć Gsię M, wyszukując leniwie wpis na mapie rozwiniętych ciągów.

Jest to coś w rodzaju dualności tego, co zostało zrobione w data-reifypakiecie, który może wziąć taki bazowy funktor, i coś podobnego Mi odzyskać z niego moralny ekwiwalent G. Używają innego typu dla nazw nieterminalnych, co w zasadzie jest po prostu Int.

data Graph e = Graph [(Unique, e Unique)] Unique

i zapewniają kombinator

reifyGraph :: MuRef s => s -> IO (Graph (DeRef s))

które mogą być użyte z odpowiednią instancją na powyższych typach danych, aby uzyskać wykres (MatrixGrammar) z dowolnej macierzy. Nie dokona deduplikacji identycznych, ale oddzielnie przechowywanych ćwiartek, ale odzyska wszystkie udostępnienia, które są obecne na oryginalnym wykresie.

W Haskell typ String jest aliasem dla [Char], który jest zwykłą listą Haskell Char, a nie wektorem lub tablicą. Char jest typem, który zawiera pojedynczy znak Unicode. Literały łańcuchowe to, o ile nie używasz rozszerzenia języka, wartości typu String.

Myślę, że z powyższego można zgadywać, że String nie jest bardzo zwartą ani wydajną reprezentacją. Typowe alternatywne reprezentacje ciągów obejmują typy dostarczane przez Data.Text i Data.ByteString.

Dla dodatkowej wygody można użyć opcji -XOverloadedStrings, aby można było używać literałów łańcuchowych jako reprezentacji alternatywnego typu łańcucha, takiego jak dostarczany przez Data.ByteString.Char8. Jest to prawdopodobnie najbardziej oszczędny sposób na wygodne używanie ciągów jako identyfikatorów.

Jeśli chodzi o Int, jest to typ o stałej szerokości, ale nie ma gwarancji, że jest on szeroki, z wyjątkiem tego, że musi być wystarczająco szeroki, aby pomieścić wartości [-2 ^ 29 .. 2 ^ 29-1]. Sugeruje to, że ma co najmniej 32 bity, ale nie wyklucza 64 bitów. Data.Int ma kilka bardziej specyficznych typów, Int8-Int64, których możesz użyć, jeśli potrzebujesz określonej szerokości.

Edytuj, aby dodać informacje

Nie sądzę, aby semantyka Haskell w jakikolwiek sposób określała kwestię udostępniania danych. Nie należy oczekiwać, że dwa literały typu String lub dwa dowolne skonstruowane dane będą odnosić się do tego samego „kanonicznego” obiektu w pamięci. Jeśli miałbyś powiązać skonstruowaną wartość z nową nazwą (z let, dopasowaniem wzorca itp.) Obie nazwy najprawdopodobniej odnoszą się do tych samych danych, ale to, czy tak, czy nie, nie jest tak naprawdę widoczne ze względu na niezmienny charakter Dane Haskell.

Ze względu na wydajność pamięci można internować ciągi znaków, które zasadniczo przechowują kanoniczną reprezentację każdego z nich w jakiejś tablicy przeglądowej, zazwyczaj tablicy mieszającej. Kiedy internujesz obiekt, dostajesz deskryptor dla niego z powrotem, i możesz porównać te deskryptory z innymi, aby zobaczyć, czy są one takie same znacznie taniej niż możesz napisać, a także często są znacznie mniejsze.

W przypadku biblioteki zajmującej się internowaniem możesz użyć https://github.com/ekmett/intern/

Jeśli chodzi o decyzję o tym, który rozmiar całkowity zastosować w czasie wykonywania, dość łatwo jest napisać kod, który zależy od klas typu Integral lub Num zamiast konkretnych typów numerycznych. Wnioskowanie typu daje automatycznie najbardziej ogólne typy. Mógłbyś wtedy mieć kilka różnych funkcji z typami wyraźnie zawężonymi do określonych typów liczbowych, które możesz wybrać w środowisku wykonawczym do wykonania konfiguracji początkowej, a następnie wszystkie inne funkcje polimorficzne działałyby tak samo na każdym z nich. Na przykład:

polyConstructor :: Integral a => a -> MyType a
int16Constructor :: Int16 -> MyType Int16
int32Constructor :: Int32 -> MyType Int32

int16Constructor = polyConstructor
int32Constructor = polyConstructor

Edycja : Więcej informacji o internowaniu

Jeśli chcesz tylko internować łańcuchy, możesz utworzyć nowy typ, który zawija łańcuch (najlepiej Text lub ByteString) i małą liczbę całkowitą.

data InternedString = { id :: Int32, str :: Text }
instance Eq InternedString where
    {x, _ } == {y, _ }  =  x == y

intern :: MonadIO m => Text -> m InternedString

To, co robi „intern”, to wyszukiwanie łańcucha w HashMap o słabym odwołaniu, gdzie Teksty są kluczami, a InternedString wartościami. Jeśli zostanie znalezione dopasowanie, „intern” zwraca wartość. Jeśli nie, tworzy nową wartość InternedString z oryginalnym tekstem i unikalnym identyfikatorem całkowitym (dlatego zawarłem ograniczenie MonadIO; zamiast tego mógłby użyć monady stanu lub innej niebezpiecznej operacji, aby uzyskać unikalny identyfikator; istnieje wiele możliwości) i zapisuje go na mapie przed zwróceniem.

Teraz masz szybkie porównanie na podstawie identyfikatora liczby całkowitej i masz tylko jedną kopię każdego unikalnego ciągu.

Biblioteka stażystów Edwarda Kmetta stosuje mniej więcej tę samą zasadę w znacznie bardziej ogólny sposób, tak że całe uporządkowane terminy danych są mieszane, przechowywane w wyjątkowy sposób i poddawane szybkiej operacji porównania. Jest to nieco zniechęcające i niezbyt udokumentowane, ale może być chętny do pomocy, jeśli poprosisz; lub możesz po prostu wypróbować własną implementację internalizacji ciągów, aby sprawdzić, czy to wystarczy.