Curioso acerca de los problemas de rendimiento HashTable

StackOverflow https://stackoverflow.com/questions/3058529

  •  27-09-2019
  •  | 
  •  

Pregunta

He leído que las tablas hash en Haskell tenían problemas de rendimiento (en el Haskell -Cafe en 2006 y volando de la rana Consultancy el blog en 2009), y ya que me gusta Haskell me preocupaba.

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

¿Fue útil?

Solución

El problema es que se requiere que el recolector de basura para atravesar matrices mutables de punteros ( "conjuntos de caja") en busca de punteros a los datos que podrían estar dispuestos a cancelar la asignación. En caja, las matrices mutables son el principal mecanismo para la implementación de una tabla hash, por lo que la estructura particular, se presentó el problema GC recorrido. Esto es común a muchos idiomas. El síntoma es la recolección de basura excesiva (hasta el 95% del tiempo empleado en GC).

La solución fue a implementar "tarjeta de marcado" en el GC para matrices mutables de los punteros, que se produjeron a finales de 2009. no debería ver GC excesivo cuando se usan matrices mutables de punteros en Haskell ahora. En los puntos de referencia simples, la inserción tabla hash para grandes hashes mejorarse 10x.

Tenga en cuenta que el tema GC caminar no afecta estructuras puramente funcionales , ni matrices (sin embalaje como la mayoría de los datos matrices paralelas , o vector -como arrays, en Haskell. Tampoco afecta tablas hash almacenados en el montón de C (como Judy ). lo que significa que no afectó el día a día Haskellers no usar tablas hash imperativas.

Si está utilizando tablas hash en Haskell, no debe observar cualquier tema ahora. Aquí, por ejemplo, es un sencillo programa de tabla hash que las inserciones 10 millones de enteros en un hash. Voy a hacer la evaluación comparativa, ya que la citación 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, la inserción de ints 10M: 

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

Con GHC 6,13, después de la revisión: 

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

El aumento del área montón predeterminado: 

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

Evitar tablas hash y utilizando un IntMap: 

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, utilizando una matriz de Judy (que es un Haskell envoltura llamando código C a través de la interfaz de la función extranjera): 

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

La ejecución de este, 

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

Por lo tanto, como se puede ver, la cuestión GC con tablas hash es fijo , y no tienen siempre ha habido otras bibliotecas y estructuras de datos que estaban perfectamente adecuado. En resumen, este es un no-tema.

Nota: a partir de 2013, se debe, probablemente, sólo tiene que utilizar el paquete, tablas hash cuales soportes < a href = "http://gregorycollins.net/posts/2011/06/11/announcing-hashtables" rel = "noreferrer"> una serie de tablas hash mutables nativa.

Otros consejos

Una pregunta como esto puede realmente ser resuelta únicamente por el experimento. Pero si usted no tiene el tiempo o dinero para hacer experimentos, hay que preguntar a otras personas lo que piensan. Cuando lo hace, es posible que desee considerar la fuente y considerar si la información dada ha sido revisada o investigados de ninguna manera.

Jon Harrop ha avanzado algunas afirmaciones interesantes sobre Haskell. Permítanme sugerir que usted busca en Google Grupos y en otros lugares para la evidencia de la experiencia de Harrop en Haskell, Lisp, y otros lenguajes funcionales. También puede leer la obra de Chris Okasaki y Andy Gill en los árboles Patricia en Haskell, ver cómo se considera su experiencia. También se puede encontrar cuyas reclamaciones, si las hubiere, han sido verificados por un tercero. A continuación, puede hacer su propia mente la seriedad para tomar las reclamaciones de las personas diferentes sobre el rendimiento de los diferentes lenguajes funcionales.

Ah, y no alimentar al troll.

P.S. Sería bastante razonable para que usted pueda hacer sus propios experimentos, pero quizás no es necesario, ya que los Don Stewart presentes algunos fieles microbenchmarks agradables en su excelente respuesta. Aquí está una adición a la respuesta de Don:

Adición: El uso de código de Don Stewart en un AMD Phenom 9850 Negro Edición velocidad de reloj de 2,5 GHz con 4 GB de RAM, en el modo de 32 bits, con ghc -O,

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

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

En resumen, incluso con la corrección en la última GHC, Haskell es todavía incapaz de proporcionar un diccionario (mutable o inmutable) que es competitivo eficiente.

tablas hash de Haskell fueron 32 × más lenta que otras alternativas como C ++ y .NET con GHC 6,10. Eso fue en parte debido a un fallo href="http://hackage.haskell.org/trac/ghc/ticket/650#comment:24" rel="noreferrer"> rendimiento . Pero los resultados de Simon Marlow no sólo muestran una mejora del 5 × prestaciones que todavía deja tablas hash de Haskell muchas veces más lento que la mayoría de las alternativas.

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

El uso de F # 2010 y la última plataforma Haskell 2010.2.0.0 (publicado ayer!) con GHC 6.12.3 en este 2.0GHz Xeon E5405 funcionamiento de 32 bits de Windows Vista para insertar 20M INT> int fijaciones en una tabla hash vacío nos encontramos con que Haskell es todavía 29 × más lento que F # en tiempo real y más de 200 × 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 se ejecuta sólo microbenchmarks vivido corto que puede deshabilitar el recolector de basura GHC como Don Stewart sugiere arriba. Al pedir una generación vivero tan grande que este programa en particular nunca lo llenará, trajo la hora de la tabla hash Haskell hasta aquí solamente 1,5 segundos. Sin embargo, esto socava completamente todo el punto de tener una generación vivero y será masivamente degrade el rendimiento de otro código porque los valores recién asignados ahora siempre será frío en la memoria caché (lo cual es la razón por la generación vivero es típicamente el tamaño de la caché L2, órdenes de magnitud menor que esto).

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top