Efficacité de la mémoire Haskell - quelle est la meilleure approche?

Nous mettons en œuvre une bibliothèque de compression matricielle basée sur une syntaxe de grammaire bidimensionnelle modifiée. Nous avons maintenant deux approches pour nos types de données - laquelle sera la meilleure en cas d'utilisation de la mémoire? (nous voulons compresser quelque chose;)).

Les grammaires contiennent des non terminaux avec exactement 4 productions ou un terminal sur le côté droit. Nous aurons besoin des noms de Productions pour les contrôles d'égalité et la minimisation de la grammaire.

La première:

-- | 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    
    } 

Ici, nos données RightHandSide enregistrent uniquement les noms de chaîne pour déterminer les prochaines productions, et ce que nous ne savons pas ici, c'est comment Haskell enregistre ces chaînes. Par exemple, la matrice [[0, 0], [0, 0]] a 2 productions:

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

La question ici est donc de savoir à quelle fréquence la chaîne "A" est-elle vraiment enregistrée? Une fois dans aString, 4 fois en b et une fois dans les productions ou juste une fois dans aString et les autres détiennent simplement des références "moins chères"?

La deuxième:

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

type ProductionMap = Map String Production

ici le terme "Terminal" est un peu trompeur car c'est en fait la production qui a un terminal comme côté droit. La même matrice:

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

et la question similaire: à quelle fréquence la production est-elle sauvegardée en interne par Haskell? Peut-être que nous supprimerons les noms dans les productions si nous n'en avons pas besoin, mais nous ne sommes pas sûrs pour le moment.

Disons donc que nous avons une grammaire avec environ 1000 productions. Quelle approche consommera moins de mémoire?

Enfin une question sur les entiers dans Haskell: Actuellement, nous prévoyons d'avoir un nom en tant que chaînes. Mais nous pourrions facilement passer aux noms entiers, car avec 1000 productions, nous aurons des noms avec plus de 4 caractères (ce qui, je suppose, est de 32 bits?). Comment Haskell gère-t-il cela. Un Int est-il toujours 32 bits et Integer alloue la mémoire dont il a vraiment besoin?

J'ai également lu ceci: Conception d'un test de la sémantique de valeur / référence de Haskell - mais je ne peux pas comprendre ce que cela signifie exactement pour nous - Je suis plus un enfant java impératif qu'un bon programmeur fonctionnel: P

Vous pouvez étendre votre grammaire matricielle en ADT avec un partage parfait avec un peu de ruse:

{-# 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

Ici, j'ai généralisé vos grammaires pour permettre tout type de données, pas seulement Int, et tabulateje prendrai la grammaire et la développerai en la repliant sur elle-même en utilisant loeb.

loebest décrit dans un article de Dan Piponi

L'extension résultante en tant qu'ADT ne prend physiquement pas plus de mémoire que la grammaire d'origine - en fait, elle en prend un peu moins, car elle n'a pas besoin du facteur de journalisation supplémentaire pour la colonne Map, et elle n'a pas besoin de stocker les cordes du tout.

Contrairement à l'expansion naïve, l'utilisation loebme permet de «faire le noeud» et de partager les thunks pour toutes les occurrences du même non-terminal.

Si vous voulez vous plonger davantage dans la théorie de tout cela, nous pouvons voir que cela RHSpourrait être transformé en un foncteur de base:

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

puis mon type M est juste le point fixe de cela Functor.

M a ~ Mu (RHS a)

tandis G aque consisterait en une chaîne choisie et une carte des chaînes vers (RHS String a).

Nous pouvons ensuite développer Gen Mrecherchant l'entrée dans une carte de chaînes développées paresseusement.

C'est en quelque sorte le double de ce qui est fait dans le data-reifypackage, qui peut prendre un tel foncteur de base, et quelque chose comme Met en récupérer l'équivalent moral G. Ils utilisent un type différent pour les noms non terminaux, qui est fondamentalement juste un Int.

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

et fournir un combinateur

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

qui peut être utilisé avec une instance appropriée sur les types de données ci-dessus pour extraire un graphique (MatrixGrammar) d'une matrice arbitraire. Il ne fera pas de déduplication de quadrants identiques mais stockés séparément, mais il récupérera tout le partage présent dans le graphique d'origine.

Dans Haskell, le type String est un alias pour [Char], qui est une liste Haskell régulière de Char, pas un vecteur ou un tableau. Char est un type qui contient un seul caractère Unicode. Les littéraux de chaîne sont, sauf si vous utilisez une extension de langage, des valeurs de type String.

Je pense que vous pouvez deviner d'après ce qui précède que String n'est pas une représentation très compacte ou autrement efficace. Les représentations alternatives courantes pour les chaînes incluent les types fournis par Data.Text et Data.ByteString.

Pour plus de commodité, vous pouvez utiliser -XOverloadedStrings afin d'utiliser des littéraux de chaîne comme représentations d'un autre type de chaîne, tel que fourni par Data.ByteString.Char8. C'est probablement le moyen le plus économe en espace pour utiliser facilement les chaînes comme identificateurs.

En ce qui concerne Int, c'est un type à largeur fixe, mais il n'y a aucune garantie quant à sa largeur, sauf qu'il doit être suffisamment large pour contenir les valeurs [-2 ^ 29 .. 2 ^ 29-1]. Cela suggère que c'est au moins 32 bits, mais n'exclut pas d'être 64 bits. Data.Int a des types plus spécifiques, Int8-Int64, que vous pouvez utiliser si vous avez besoin d'une largeur spécifique.

Modifier pour ajouter des informations

Je ne crois pas que la sémantique de Haskell spécifie quoi que ce soit sur le partage de données de toute façon. Vous ne devez pas vous attendre à ce que deux littéraux String, ou deux des données construites, fassent référence au même objet «canonique» en mémoire. Si vous deviez lier une valeur construite à un nouveau nom (avec let, une correspondance de modèle, etc.), les deux noms feraient probablement référence aux mêmes données, mais s'ils le font ou non, ils ne sont pas vraiment visibles en raison de la nature immuable de Données Haskell.

Pour des raisons d'efficacité de stockage, vous pouvez interner les chaînes, qui stockent essentiellement une représentation canonique de chacune dans une table de recherche quelconque, généralement une table de hachage. Lorsque vous internez un objet, vous obtenez un descripteur pour celui-ci, et vous pouvez comparer ces descripteurs avec d'autres pour voir s'ils sont les mêmes beaucoup moins cher que vous ne pourriez les chaînes, et ils sont également souvent beaucoup plus petits.

Pour une bibliothèque qui fait de l'internat, vous pouvez utiliser https://github.com/ekmett/intern/

En ce qui concerne la décision de la taille entière à utiliser au moment de l'exécution, il est assez facile d'écrire du code qui dépend des classes de type Integral ou Num au lieu de types numériques concrets. L'inférence de type vous donnera automatiquement les types les plus généraux possibles. Vous pouvez alors avoir quelques fonctions différentes avec des types explicitement restreints à des types numériques spécifiques dont vous pouvez choisir une au moment de l'exécution pour effectuer la configuration initiale, et par la suite toutes les autres fonctions polymorphes fonctionneront de la même manière sur chacune d'entre elles. Par exemple:

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

int16Constructor = polyConstructor
int32Constructor = polyConstructor

Edit : Plus d'informations sur les stages

Si vous souhaitez uniquement interner des chaînes, vous pouvez créer un nouveau type qui encapsule une chaîne (de préférence un texte ou une chaîne d'octets) et un petit entier ensemble.

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

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

Ce que «stagiaire» fait est de rechercher la chaîne dans un HashMap de référence faible où les textes sont des clés et les chaînes internes sont des valeurs. Si une correspondance est trouvée, 'intern' renvoie la valeur. Sinon, il crée une nouvelle valeur InternedString avec le texte d'origine et un identifiant entier unique (c'est pourquoi j'ai inclus la contrainte MonadIO; il pourrait utiliser une monade d'état ou une opération non sécurisée à la place pour obtenir l'identifiant unique; il existe de nombreuses possibilités) et le stocke dans la carte avant de le renvoyer.

Vous obtenez maintenant une comparaison rapide basée sur l'id entier et n'avez qu'une seule copie de chaque chaîne unique.

La bibliothèque interne d'Edward Kmett applique le même principe, plus ou moins, d'une manière beaucoup plus générale afin que les termes de données structurées entières soient hachés, stockés de manière unique et bénéficient d'une opération de comparaison rapide. C'est un peu intimidant et pas particulièrement documenté, mais il pourrait être prêt à vous aider si vous le demandez; ou vous pouvez d'abord essayer votre propre implémentation de l'internement de chaîne pour voir si cela aide suffisamment.