Эффективные строки памяти в Haskell

Обычно рекомендуемые типы строк Haskell кажутся ByteString или Text. Я часто работаю с очень большим количеством коротких (английских размерных слов) строк и, как правило, должен хранить их в таблице поиска, такой как Data.Map. Во многих случаях я нахожу, что в этом сценарии таблица строк может занимать меньше памяти, чем таблица ByteStrings. Unboxed Data.Vectors of Word8 также (намного) более компактны, чем ByteStrings.

Какова наилучшая практика, когда нужно хранить и сравнивать большое количество небольших строк в Haskell?

Ниже я попытался сконфигурировать конкретный проблемный случай в небольшом примере:

import qualified Data.ByteString.Lazy.Char8 as S
import qualified Data.ByteString as Strict
import qualified Data.Map as Map
import qualified Data.Vector.Unboxed as U
import qualified Data.Serialize as Serialize
import Control.Monad.State

main =   putStr 
  . unlines . map show . flip evalState (0,Map.empty) 
  . mapM toInt 
  . S.words
  =<<
  S.getContents


toInt x = do  
  let x' =   
          U.fromList . Strict.unpack .  -- Comment this line to increase memory usage
           Serialize.encode $ x  
  (i,t) <- get
  case Map.lookup x' t of
    Just j -> return j
    Nothing -> do 
      let i' = i + (1::Int)
      put (i', Map.insert x' i t)
      return i

Когда я запускаю это в файле, содержащем около 400 000 слов текста на английском языке, версия со строгими ключами bytestring использует около 50 МБ памяти, одна с векторами Word8 использует 6 МБ.

Ответ 1

В отсутствие других ответов я собираюсь выйти на конечность здесь.

Какова наилучшая практика, когда нужно хранить и сравнивать большое количество небольших строк в Haskell?

Если маленькие строки предназначены для чтения человеком (например, английское слово), используйте Text. Если они предназначены для чтения только компьютером, используйте ByteString. Решение использовать строгие или ленивые варианты их зависит от того, как вы создаете и используете эти маленькие строки.

Вам не нужно использовать свой собственный unboxed Vector из Word8. Если вы столкнулись с конкретной ситуацией, в которой обычный String быстрее, чем Text или ByteString, затем перетащите детали в StackOverflow, и мы попытаемся выяснить, почему. Если вы выполните подробный анализ и можете доказать, что unboxed Vector of Word8 последовательно работает значительно лучше, чем Text или ByteString, тогда начните беседы в списках рассылки, irc, reddit и т.д.; стандартные библиотеки не установлены в камне, и улучшения всегда приветствуются.

Но я думаю, что очень вероятно, что вы просто делаете что-то странное, как предполагают хаммар и шань.

P.S. для вашего конкретного случая использования вместо хранения большого количества небольших строк вы должны рассмотреть более подходящую структуру данных, удовлетворяющую вашим потребностям, например. "Три" как данр.

Ответ 2

A (строгий) ByteSting - это конструктор над unboxed ForiegnPtr до Word8 и двумя unboxed Ints.

A ForeignPtr является другим конструктором над Addr# (a GHC prim) и a ForeignPtrContents:

data ForeignPtrContents
  = PlainForeignPtr !(IORef (Finalizers, [IO ()]))
  | MallocPtr      (MutableByteArray# RealWorld) !(IORef (Finalizers, [IO ()]))
  | PlainPtr       (MutableByteArray# RealWorld)

...

Для коротких строк ByteStrings просто упаковывают слишком много администрирования, чтобы извлечь выгоду из их непрерывного представления фактических "строковых" данных.

Для исходного вопроса - я проверил бы среднюю длину слова вашего тела, но я не вижу, что ByteString более эффективен, чем String aka [ Char], который использует 12 байт на Char (исходный оригинал ByteString).

Общая просьба к Haskellers (не нацеленная на плакат оригинального вопроса) - пожалуйста, прекратите избивать String aka [ Char] - иметь как String, так и Text (и ByteString, когда вам действительно нужны байты) имеет смысл. Или используйте "Очистить", где смежное строковое представление лучше подходит для коротких строк.

Предостережение. Возможно, я смотрел на старую версию внутренних элементов ByteString относительно того, какие типы данных он использует внутри.