Эффективность памяти Haskell - какой подход лучше?

11

Мы реализуем библиотеку сжатия матрицы на основе модифицированного синтаксиса двумерной грамматики. Теперь у нас есть два подхода к нашим типам данных - какой из них будет лучше в случае использования памяти? (мы хотим что-то сжать;)).

Грамматики содержат нетерминалы с ровно 4 продукцией или терминалом с правой стороны. Нам понадобятся имена Productions для проверки равенства и минимизации грамматики.

Первое:

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

Здесь наши данные RightHandSide сохраняют только строковые имена для определения следующих производств, и здесь мы не знаем, как Haskell сохраняет эти строки. Например, матрица [[0, 0], [0, 0]] имеет 2 произведения:

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

Итак, вопрос здесь в том, как часто действительно сохраняется строка «А»? Один раз в aString, 4 раза в b и один раз в спектаклях или только один раз в aString, а остальные просто содержат «более дешевые» ссылки?

Секунда:

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

type ProductionMap = Map String Production

здесь термин «Терминал» немного вводит в заблуждение, потому что это фактически производство, которое имеет терминал с правой стороны. Та же матрица:

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

и аналогичный вопрос: как часто продукция сохраняется внутри Haskell? Возможно, мы будем отбрасывать имена внутри производств, если они нам не нужны, но сейчас мы не уверены в этом.

Допустим, у нас есть грамматика с около 1000 произведений. Какой подход потребляет меньше памяти?

Наконец, вопрос о целых числах в Haskell: в настоящее время мы планируем иметь имя как Strings. Но мы могли бы легко переключиться на целочисленные имена, потому что с 1000 продукций у нас будут имена с более чем 4 символами (который я предполагаю, является 32-разрядным?). Как Хаскелл справляется с этим? Всегда ли Int 32-разрядный, а Integer выделяет память, которая ему действительно нужна?

Я также прочитал это: Разработка теста семантики значения / ссылки в Haskell - но я не могу понять, что именно это означает для нас - я скорее обязательный ребенок java, чем хороший функциональный программист: P

Деннис Ич
источник

Ответы:

7

Вы можете расширить свою матричную грамматику в ADT с идеальным совместным использованием с небольшим количеством хитрости:

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

Здесь я обобщил ваши грамматики, чтобы учесть любой тип данных, не только Int, и tabulateвозьму грамматику и расширим ее, сложив ее на себя, используя loeb.

loebописывается в статье Дэна Пипони

Результирующее расширение как ADT физически занимает не больше памяти, чем исходная грамматика - на самом деле это занимает немного меньше, потому что ему не нужен дополнительный лог-фактор для корешка Map, и ему не нужно хранить струны вообще.

В отличие от наивного расширения, использование loebпозволяет мне «связать себя узами брака» и делиться пухом для всех случаев одного и того же нетерминала.

Если вы хотите углубиться в теорию всего этого, мы можем увидеть, что это RHSможно превратить в базовый функтор:

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

и тогда мой тип М - это просто фиксированная точка этого Functor.

M a ~ Mu (RHS a)

while G aбудет состоять из выбранной строки и карты из строк в (RHS String a).

Затем мы можем расширить Gв Mпо LookUp до записи в карте расширенных строк Лениво.

Это своего рода двойственное из того, что делается в data-reifyпакете, которое может взять такой базовый функтор, и что-то вроде Mи восстановить из него моральный эквивалент вашего G. Они используют другой тип для нетерминальных имен, который в основном просто Int.

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

и предоставить комбинатор

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

который может использоваться с соответствующим экземпляром для указанных выше типов данных, чтобы получить график (MatrixGrammar) из произвольной матрицы. Он не будет выполнять дедупликацию идентичных, но отдельно хранимых квадрантов, но восстановит весь общий доступ, присутствующий в исходном графике.

Эдвард КМЕТТ
источник
8

В Haskell тип String - это псевдоним для [Char], который является обычным списком Char в Haskell , а не вектором или массивом. Char - это тип, который содержит один символ Unicode. Строковые литералы являются, если вы не используете расширение языка, значениями типа String.

Я думаю, вы можете догадаться из вышесказанного, что String не очень компактное или иным образом эффективное представление. Общие альтернативные представления для строк включают типы, предоставляемые Data.Text и Data.ByteString.

Для дополнительного удобства вы можете использовать -XOverloadedStrings, чтобы вы могли использовать строковые литералы как представления альтернативного строкового типа, такого как предоставляемый Data.ByteString.Char8. Это, вероятно, самый экономичный способ удобно использовать строки в качестве идентификаторов.

Что касается Int, то это тип с фиксированной шириной, но нет никакой гарантии, насколько он широк, за исключением того, что он должен быть достаточно широким, чтобы содержать значения [-2 ^ 29 .. 2 ^ 29-1]. Это говорит о том, что это как минимум 32 бита, но не исключает, что он будет 64-битным Data.Int имеет несколько более специфических типов, Int8-Int64, которые вы можете использовать, если вам нужна конкретная ширина.

Изменить, чтобы добавить информацию

Я не верю, что семантика Haskell так или иначе указывает на обмен данными. Не следует ожидать, что два строковых литерала или два любых сконструированных данных ссылаются на один и тот же «канонический» объект в памяти. Если бы вы связали созданное значение с новым именем (с помощью let, сопоставления с образцом и т. Д.), Оба имени, скорее всего, ссылались бы на одни и те же данные, но на самом деле они не видны из-за неизменности их характера. Данные на Haskell.

Ради эффективности хранения вы можете интернировать строки, которые по существу хранят каноническое представление каждого в таблице поиска некоторого вида, обычно хеш-таблице. Когда вы интернируете объект, вы возвращаете его дескриптор, и вы можете сравнить эти дескрипторы с другими, чтобы увидеть, являются ли они одинаковыми намного дешевле, чем строки, и они также часто намного меньше.

Для библиотеки, которая занимается интернированием, вы можете использовать https://github.com/ekmett/intern/

Что касается решения, какой целочисленный размер использовать во время выполнения, довольно просто написать код, который зависит от классов Integral или Num, а не от конкретных числовых типов. Вывод типа даст вам наиболее общие типы, которые он может автоматически. После этого вы могли бы иметь несколько различных функций с типами, явно суженными к конкретным числовым типам, которые вы могли бы выбрать одну из во время выполнения, чтобы выполнить первоначальную настройку, и после этого все другие полиморфные функции работали бы одинаково для любого из них. Например:

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

int16Constructor = polyConstructor
int32Constructor = polyConstructor

Изменить : Больше информации о стажировке

Если вы хотите только интернировать строки, вы можете создать новый тип, который обернет строку (предпочтительно Text или ByteString) и небольшое целое число вместе.

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

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

То, что делает 'intern', это поиск строки в HashMap со слабой ссылкой, где Texts - это ключи, а InternedStrings - это значения. Если совпадение найдено, 'intern' возвращает значение. Если нет, он создает новое значение InternedString с исходным текстом и уникальным целочисленным идентификатором (именно поэтому я включил ограничение MonadIO; вместо этого он мог бы использовать монаду состояния или некоторую небезопасную операцию для получения уникального идентификатора; существует много возможностей) и сохраняет его на карте перед возвратом.

Теперь вы получаете быстрое сравнение на основе целочисленного идентификатора и имеете только одну копию каждой уникальной строки.

Библиотека стажеров Эдварда Кметта применяет тот же принцип, более или менее, в гораздо более общем смысле, так что все термины структурированных данных хешируются, хранятся уникальным образом и выполняются операции быстрого сравнения. Это немного устрашающе и не особо задокументировано, но он может быть готов помочь, если вы попросите; или вы могли бы просто попробовать свою собственную реализацию интернирования строк, чтобы посмотреть, достаточно ли это поможет.

Леви Пирсон
источник
Спасибо за ваш ответ. Можно ли определить, какой размер int мы должны использовать во время выполнения? Я надеюсь, что кто-то еще может дать некоторую информацию о проблеме с копиями :)
Деннис Ич
Спасибо за добавленную информацию. Я посмотрю там. Просто чтобы сделать это правильно, дескрипторы, о которых вы говорите, являются чем-то вроде ссылки, которая хэшируется и может сравниваться? Вы работали с этим сами? Можете ли вы сказать, насколько «сложнее» это происходит с этим, потому что на первый взгляд кажется, что мне нужно быть очень осторожным с определением грамматики;)
Деннис Ич
1
Автор этой библиотеки - очень продвинутый пользователь Haskell, известный качественной работой, но я не использовал эту конкретную библиотеку. Это очень универсальная реализация "hash cons", которая будет хранить и разрешать совместное использование представлений в любом построенном типе данных, а не только в строках. Посмотрите в его каталоге примеров проблему, подобную вашей, и вы увидите, как реализованы функции равенства.
Леви Пирсон