Cadenas de memoria eficiente en Haskell

Question

Los tipos de cadenas Haskell comúnmente recomendados parecen ser ByteString o Text. A menudo trabajo con una gran cantidad de cadenas cortas (tamaño de palabras en inglés), y generalmente 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 ByteStrings. Datos no compartidos. Los vectores de Word8 también son (mucho) más compactos que ByteStrings.

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

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 Inglés, la versión con teclas ByteString estrictas utiliza alrededor de 50 MB memoria, la que tiene vectores de Word8 usa 6MB.

Answer 1

En ausencia de otras respuestas, me voy a quedar en una extremidad aquí.

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

Si las cadenas pequeñas están destinadas a ser legibles por humanos (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 utilizar variantes estrictas o perezosas depende de cómo construyas y uses estas pequeñas cadenas.

No debería necesitar usar su propio Vector s sin contenedor de Word8. Si está experimentando una situación específica en la que String es más rápido que Text o ByteString, agregue los detalles en StackOverflow y trataremos de averiguar por qué. Si realiza un análisis detallado y puede demostrar que un Vector unboxed de Word8 funciona significativamente mejor que Text o ByteString, inicie las conversaciones en las 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 solo estés haciendo algo extraño, como sugieren hammar y shang.

P.S. para su caso de uso particular, en lugar de almacenar muchas cadenas pequeñas, debe considerar una estructura de datos más adecuada para sus necesidades, p. un Trie como sugiere danr.

Answer 2

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

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

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

...

Para cadenas cortas, ByteString simplemente empacar demasiado administración en beneficio de su representación contigua de los datos reales de "cadena".

Para la pregunta original, verificaría una longitud de palabra promedio de su corpus, pero no puedo ver que ByteString sea más eficiente que String aka [Char] que usa 12 bytes por Char (fuente el papel original ByteString) .

Una súplica general a Haskellers (no está dirigido el póster de la pregunta original) - por favor, deje de atacar a String aka [Char] - tiene tanto Cadena como Texto (y ByteString cuando realmente necesita bytes) tiene sentido. O use Limpiar donde la representación de Cadena contigua es más adecuada para cadenas cortas.

Advertencia: puede que haya estado buscando una versión anterior de ByteString en lo que respecta a los tipos de datos que utiliza internamente.

Answer 3

Sé que esta es una publicación de hace 6 años, pero me preguntaba lo mismo recientemente, y encontré esta publicación de blog útil: 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.