haskell - Curioso sobre los problemas de rendimiento de HashTable

ghc

Question

Leí que las tablas hash en Haskell tenían problemas de rendimiento (en el Haskell-Cafe en 2006 y en el blog de Flying Frog Consultancy en 2009), y como me gusta Haskell, me preocupaba.

Eso fue hace un año, ¿cuál es el estado ahora (junio de 2010)? ¿Se ha corregido el "problema de la tabla hash" en GHC?

Answer 1

El problema era que se requiere que el recolector de basura atraviese matrices mutables de punteros ("matrices en caja") buscando punteros a los datos que podrían estar listos para desasignar. Las matrices encasilladas y mutables son el mecanismo principal para implementar una tabla hash, por lo que esa estructura particular mostró el problema transversal de GC. Esto es común en muchos idiomas. El síntoma es la recolección excesiva de basura (hasta el 95% del tiempo pasado en GC).

La solución fue implementar el "marcado de la tarjeta" en el GC para matrices mutables de punteros, que se produjo a finales de 2009. No debería verse un GC excesivo al usar matrices mutables de punteros en Haskell ahora. En los puntos de referencia simples, la inserción de tablas hash para hashes grandes mejoró en 10x.

Tenga en cuenta que el problema de GC walking no afecta las estructuras puramente funcionales , ni las matrices no compartidas (como la mayoría de las matrices paralelas de datos o las matrices de vector en Haskell. Tampoco afecta las tablas almacenadas en el montón C (como judy ). no afectaba a los Haskellers del día a día que no usaban tablas hash imperativas.

Si está utilizando hashtables en Haskell, no debería observar ningún problema ahora. Aquí, por ejemplo, hay un programa de tabla doble simple que inserta 10 millones de entradas en un hash. Haré la evaluación comparativa, ya que la cita original no presenta ningún código o puntos de referencia.

import Control.Monad
import qualified Data.HashTable as H
import System.Environment

main = do
  [size] <- fmap (fmap read) getArgs
  m <- H.new (==) H.hashInt
  forM_ [1..size] $ /n -> H.insert m n n
  v <- H.lookup m 100
  print v

Con GHC 6.10.2, antes de la corrección, insertando 10M de entrada:

$ time ./A 10000000 +RTS -s
...
47s.

Con GHC 6.13, después de la corrección:

./A 10000000 +RTS -s 
...
8s

Aumentando el área de montón predeterminado:

./A +RTS -s -A2G
...
2.3s

Evitar tablas hash y usar un mapa de privacidad:

import Control.Monad
import Data.List
import qualified Data.IntMap as I
import System.Environment

main = do
  [size] <- fmap (fmap read) getArgs
  let k = foldl'' (/m n -> I.insert n n m) I.empty [1..size]
  print $ I.lookup 100 k

Y obtenemos:

$ time ./A 10000000 +RTS -s        
./A 10000000 +RTS -s
6s

O, alternativamente, usando una matriz Judy (que es una envoltura Haskell que llama al código C a través de la interfaz de función externa):

import Control.Monad
import Data.List
import System.Environment
import qualified Data.Judy as J

main = do
  [size] <- fmap (fmap read) getArgs
  j <- J.new :: IO (J.JudyL Int)
  forM_ [1..size] $ /n -> J.insert (fromIntegral n) n j
  print =<< J.lookup 100 j

Ejecutando esto,

$ time ./A 10000000 +RTS -s
...
2.1s

Entonces, como puede ver, el problema de GC con hashtables es fijo , y siempre ha habido otras bibliotecas y estructuras de datos que eran perfectamente adecuadas. En resumen, esto no es un problema.

Nota: a partir de 2013, probablemente solo deba usar el paquete hashtables , que admite una variedad de hashtables mutables de forma nativa.

Answer 2

En resumen, incluso con la solución en el último GHC, Haskell sigue siendo incapaz de proporcionar un diccionario (mutable o inmutable) que sea competitivo eficientemente.

Las tablas hash de Haskell fueron 32 veces más lentas que las alternativas como C ++ y .NET con GHC 6.10. Eso se debió en parte a un error de rendimiento en el recolector de basura GHC que se corrigió para GHC 6.12.2 . Pero los resultados de Simon Marlow muestran solo una mejora de rendimiento de 5 × que aún deja las tablas hash de Haskell mucho más lentas que la mayoría de las alternativas.

Las alternativas puramente funcionales también son mucho más lentas que una tabla hash decente. Por ejemplo, Haskell''s IntMap es 10 veces más lento que la tabla hash de .NET .

Utilizando F # 2010 y la última Haskell Platform 2010.2.0.0 (¡lanzada ayer!) Con GHC 6.12.3 en este 2.0 GHz E5405 Xeon ejecutando Windows Vista de 32 bits para insertar enlaces de 20M int-> int en una tabla hash vacía, encontramos que Haskell sigue siendo 29 veces más lento que F # en tiempo real y más de 200 veces más lento en términos de tiempo de CPU porque el Haskell quema todos los núcleos:

GHC 6.12.3 Data.HashTable: 42.8s (new!) .NET hash table: 1.47s

Siempre que ejecute solo microbenchmarks de corta duración, puede desactivar el recolector de basura GHC como Don Stewart sugiere más arriba. Al solicitar una generación de viveros tan grande que este programa en particular nunca lo llene, trajo el tiempo para la tabla hash Haskell a solo 1.5s aquí. Sin embargo, esto socava completamente el punto de tener una generación de guardería y degradará masivamente el rendimiento de otro código porque los valores recién asignados ahora siempre estarán fríos en la memoria caché (razón por la cual la generación de vivero es típicamente del tamaño de la caché L2, órdenes de magnitud más pequeñas que esta).

Answer 3

Una pregunta como esta solo puede resolverse solo por experimento. Pero si no tiene tiempo ni dinero para hacer experimentos, debe preguntarle a otras personas qué piensan. Cuando lo haga, es posible que desee considerar la fuente y considerar si la información proporcionada ha sido revisada o verificada de alguna manera.

Jon Harrop ha avanzado algunas afirmaciones interesantes sobre Haskell. Permítanme sugerirles que busquen en Grupos de Google y en otros lugares para encontrar evidencia de la experiencia de Harrop en Haskell, Lisp y otros lenguajes funcionales. También podría leer el trabajo de Chris Okasaki y Andy Gill sobre árboles Patricia en Haskell, ver cómo se considera su experiencia. También puede encontrar las reclamaciones, en su caso, que hayan sido verificadas por un tercero. Entonces puede decidir qué tan serio es tomar las afirmaciones de las diferentes personas sobre el rendimiento de los diferentes lenguajes funcionales.

Ah, y no alimentes al troll.

PD. Sería bastante razonable que hicieras tus propios experimentos, pero tal vez no sean necesarios, ya que el fiel Don Stewart presenta algunas bonitas micromarcaciones en su excelente respuesta. Aquí hay una adición a la respuesta de Don:

Adición: Usando el código de Don Stewart en un AMD Phenom 9850 Black Edition con frecuencia de 2.5GHz con 4GB de RAM, en modo de 32 bits, con ghc -O ,

• Con el montón predeterminado, el IntMap es un 40% más rápido que la tabla hash.
• Con el montón 2G, la tabla hash es un 40% más rápida que la del IntMap .
• Si voy a diez millones de elementos con el montón predeterminado, el IntMap es cuatro veces más rápido que la tabla hash (tiempo de CPU) o el doble de rápido que el reloj de pared.

Estoy un poco sorprendido por este resultado, pero estoy seguro de que las estructuras de datos funcionales funcionan bastante bien. Y confirmado en mi creencia de que realmente vale la pena comparar su código en las condiciones reales en que se va a utilizar.