Implementación eficiente de cadenas en Haskell

Question

Actualmente me estoy enseñando a mí mismo Haskell, y me pregunto cuáles son las mejores prácticas cuando se trabaja con cadenas en Haskell.

La implementación de cadena predeterminada en Haskell es una lista de Char. Esto es ineficaz para entrada-salida de archivo, según Real World Haskell, ya que cada carácter se asigna por separado (supongo que esto significa que una cadena es básicamente una lista vinculada en Haskell, pero no estoy seguro)

Pero si la implementación de cadena predeterminada es ineficaz para el archivo de E/S, ¿también es ineficaz para trabajar con cadenas en la memoria? ¿Por qué o por qué no? C usa una matriz de caracteres para representar una Cadena, y asumí que esta sería la forma predeterminada de hacer las cosas en la mayoría de los idiomas.

Según lo veo, la implementación de la lista de String ocupará más memoria, ya que cada carácter requerirá sobrecarga, y también más tiempo para iterar, porque se requerirá una desreferenciación del puntero para llegar al siguiente carácter. Pero hasta ahora me ha gustado jugar con Haskell, así que quiero creer que la implementación predeterminada es eficiente.

Answer 1

Las mejores prácticas para trabajar con cadenas de manera performante en Haskell son básicamente: Usar Data.ByteString/Data.ByteString.Lazy.

http://hackage.haskell.org/packages/archive/bytestring/latest/doc/html/

---

En cuanto a la eficacia de la aplicación de cadena por defecto va en Haskell, no lo es. Cada Char representa un punto de código Unicode, lo que significa que necesita al menos 21 bits por Char.

Desde un String es sólo [Char], que es una lista enlazada de Char, significa String s tienen una pobre localidad de referencia, y de nuevo significa que String s son bastante grandes en la memoria, como mínimo es N * (21bits + Mbits) donde N es el longitud de la cadena y M es el tamaño de un puntero (32, 64, lo que tiene) y a diferencia de muchos otros lugares donde Haskell utiliza listas donde otros lenguajes podrían usar estructuras diferentes (estoy pensando específicamente en el flujo de control aquí), String Es mucho menos probable que el compilador pueda optimizar los bucles, etc.

Y mientras que Char corresponde a un punto de código, el informe Haskell 98 no especifica nada sobre la codificación utilizada al hacer el archivo IO, ni siquiera un valor predeterminado y mucho menos una forma de cambiarlo. En la práctica, GHC proporciona extensiones para hacer, p. IO binario, pero vas a salir de la reserva en ese punto de todos modos.

Incluso con operaciones como anteponer a la parte delantera de la cuerda, es poco probable que String supere en la práctica .

Answer 2

La respuesta es un poco más compleja que solo "usar cadenas de bytes perezosas".

• Las cadenas de bytes solo almacenan 8 bits por valor, mientras que String contiene caracteres Unicode reales. Por lo tanto, si desea trabajar con Unicode, debe convertir desde y hacia UTF-8 o UTF-16 todo el tiempo, lo cual es más costoso que el simple uso de cadenas. No cometa el error de asumir que su programa solo necesitará ASCII. A menos que sea solo un código descartable, un día alguien tendrá que poner un símbolo de Euro (U + 20AC) o caracteres acentuados, y su agradable implementación de la cadena de bytes se romperá irremediablemente.
• Las cadenas de bytes hacen que algunas cosas, como anteponer al inicio de una cadena, sean más costosas.

Dicho esto, si necesita rendimiento y puede representar sus datos puramente en cadenas de bytes, hágalo.

Answer 3

Aparte de String/ByteString ahora existe la biblioteca Text que combina lo mejor de ambos mundos: funciona con Unicode mientras que está basado en ByteString internamente, por lo que obtiene cadenas rápidas y correctas.

Answer 4

La respuesta básica dada, use ByteString, es correcta. Dicho eso, todas las tres respuestas anteriores tienen imprecisiones.

En cuanto a UTF-8: si esto será un problema o no depende completamente del tipo de procesamiento que haga con sus cadenas. Si simplemente los trata como trozos únicos de datos (que incluyen operaciones tales como concatenación, aunque no se dividen), o haciendo ciertas operaciones basadas en bytes limitados (por ejemplo, encontrar la longitud de la cadena en bytes, en lugar de la longitud en personajes), no tendrás ningún problema. Si está utilizando I18N, hay suficientes otros problemas que simplemente usar String en lugar de ByteString comenzará a solucionar solo algunos de los problemas que encontrará.

Anular bytes individuales al frente de un ByteString es probablemente más costoso que hacer lo mismo con un String. Sin embargo, si está haciendo mucho de esto, probablemente sea posible encontrar formas de lidiar con su problema particular que sean más baratas.

Pero el resultado final sería, para el póster de la pregunta original: sí, las cadenas son ineficaces en Haskell, aunque bastante prácticas. Si le preocupa la eficiencia, use ByteStrings y visualícelos como matrices de Char8 o Word8, según su finalidad (ASCII/ISO-8859-1 frente a Unicode de algún tipo, o solo datos binarios arbitrarios). En general, usa Lazy ByteStrings (donde anteponer el inicio de una cadena es realmente una operación muy rápida) a menos que sepas por qué quieres las que no son flojas (que generalmente se envuelve en una apreciación de los aspectos de rendimiento de la evaluación perezosa).

Por lo que vale, estoy construyendo un sistema de comercio automatizado completamente en Haskell, y una de las cosas que tenemos que hacer es analizar muy rápidamente un feed de datos de mercado que recibimos a través de una conexión de red. Puedo manejar la lectura y el análisis de 300 mensajes por segundo con una cantidad insignificante de CPU; en lo que respecta al manejo de estos datos, Haskell compilado por GHC se desempeña lo suficientemente cerca de C que no está cerca de ingresar a mi lista de problemas notables.