string - Cadenas eficientes de memoria en Haskell

Question

Los tipos de cadena de Haskell comúnmente recomendados parecen ser ByteString o Text. A menudo trabajo con un gran número de cadenas cortas (del tamaño de una palabra en inglés), y normalmente necesito almacenarlas en una tabla de búsqueda como Data.Map En muchos casos, encuentro que en este escenario, una tabla de cadenas puede ocupar menos memoria que una tabla de bytes. Los Data.Vectors de Word8 sin caja también son (mucho) más compactos que los ByteStrings.

¿Cuál es la mejor práctica cuando se necesita almacenar y comparar grandes cantidades de cadenas pequeñas en Haskell?

A continuación, he tratado de condensar un caso problemático particular en un pequeño ejemplo:

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

Cuando ejecuto esto en un archivo que contiene alrededor de 400.000 palabras de texto en inglés, la versión con claves de bytring estrictas usa alrededor de 50 MB de memoria, la de vectores de Word8 usa 6 MB.

Answer 1

A falta de otras respuestas, voy a arriesgarme aquí.

¿Cuál es la mejor práctica cuando se necesita almacenar y comparar grandes cantidades de cadenas pequeñas en Haskell?

Si las cadenas pequeñas están destinadas a ser legibles para el ser humano (por ejemplo, una palabra en inglés), utilice Text . Si están destinados a ser leídos solo por la computadora, use ByteString . La decisión de usar variantes estrictas o perezosas de estos depende de cómo construya y use estas cadenas pequeñas.

No debería tener que usar sus propios Vector Word8 de Word8 . Si experimenta una situación específica en la que la String normal es más rápida que la de Text o ByteString , ByteString los detalles en StackOverflow e intentaremos averiguar por qué. Si realiza un análisis detallado y puede probar que un Vector caja de Word8 funciona de Word8 consistente y significativamente mejor que Text o ByteString , entonces inicie conversaciones en listas de correo, irc, reddit, etc .; Las bibliotecas estándar no están escritas en piedra, y las mejoras siempre son bienvenidas.

Pero creo que es muy probable que estés haciendo algo raro, como sugieren hammar y shang.

PD: para su caso de uso particular, en lugar de almacenar una gran cantidad de cadenas pequeñas, debe considerar una estructura de datos más adecuada que se adapte a sus necesidades, por ejemplo, un Trie como sugiere danr.

Answer 2

Sé que esta es una publicación de 6 años, pero me preguntaba lo mismo recientemente, y encontré esta útil entrada de blog: https://markkarpov.com/post/short-bs-and-text.html . Parece que sí, este es un problema reconocido, y Short (Text / ByteString) es la solución.

Answer 3

Un ByteSting (estricto) es un constructor sobre un ForiegnPtr sin ForiegnPtr a Word8 y dos Ints sin caja.

Un ForeignPtr es otro constructor sobre un Addr# (un prim de GHC) y un ForeignPtrContents :

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

...

Para cadenas cortas, ByteStrings simplemente empaqueta demasiada administración para beneficiar su representación contigua de los datos reales de "cadena".

Para la pregunta original: revisaría la longitud promedio de una palabra de su cuerpo, pero no puedo ver que ByteString sea más eficiente que Stria aka [Char] que usa 12 bytes por Char (fuente del documento original de ByteString).

Una súplica general a los Haskellers (no dirigida al póster de la pregunta original) - por favor, deje de golpear a String aka [Char] - tener sentido tanto String como Text (y ByteString cuando realmente necesita bytes). O use Limpiar donde la representación de cadena contigua se adapte mejor a cadenas cortas.

Advertencia: es posible que haya estado viendo una versión anterior de los elementos internos de ByteString con respecto a los tipos de datos que utiliza internamente.