Curioso sobre os problemas de desempenho do HashTable

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

  •  27-09-2019
  •  | 
  •  

Pergunta

Eu li que as tabelas hash em Haskell tinham problemas de desempenho (no Haskell-Café em 2006 e Blog da Flying Frog Consultoria em 2009), e como gosto de Haskell isso me preocupou.

Isso foi há um ano, qual é a situação agora (junho de 2010)?O "problema da tabela hash" foi corrigido no GHC?

Foi útil?

Solução

O problema era que o coletor de lixo era obrigado a percorrer arrays mutáveis ​​de ponteiros ("matrizes em caixa") em busca de ponteiros para dados que pudessem estar prontos para serem desalocados.Matrizes mutáveis ​​​​em caixa são o principal mecanismo para implementar uma tabela hash, de modo que essa estrutura específica mostrou o problema de travessia do GC.Isso é comum em muitos idiomas.O sintoma é a coleta excessiva de lixo (até 95% do tempo gasto em GC).

A correção foi implementar "marcação de cartão" no GC para matrizes mutáveis ​​de ponteiros, que ocorreu no final de 2009.Você não deve ver GC excessivo ao usar matrizes mutáveis ​​de ponteiros em Haskell agora.Nos benchmarks simples, a inserção de hashtable para hashes grandes melhorou em 10x.

Observe que o problema de caminhada do GC não afeta estruturas puramente funcionais, nem arrays unboxed (como a maioria dos dados matrizes paralelas, ou vetormatrizes semelhantes a, em Haskell.Nem afeta hashtables armazenados no heap C (como Judy).O que significa que isso não afetou os Haskellers do dia-a-dia que não usavam tabelas hash imperativas.

Se você estiver usando hashtables em Haskell, não deverá observar nenhum problema agora.Aqui, por exemplo, está um programa hashtable simples que insere 10 milhões de ints em um hash.Farei o benchmarking, pois a citação original não apresenta nenhum código ou benchmark.

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

Com GHC 6.10.2, antes da correção, inserindo 10M ints:

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

Com GHC 6.13, após a correção:

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

Aumentando a área de heap padrão:

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

Evitando hashtables e usando um 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

E obtemos:

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

Ou, alternativamente, usando um array judy (que é um wrapper Haskell chamando código C através da interface de função estrangeira):

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

Executando isso,

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

Então, como você pode ver, o problema do GC com hashtables é fixo, e tem sempre foram outras bibliotecas e estruturas de dados que eram perfeitamente adequados.Em resumo, isso não é problema.

Observação:a partir de 2013, você provavelmente deveria usar apenas o tabelas hash pacote, que suporta uma variedade de hashtables mutáveis nativamente.

Outras dicas

Uma pergunta como essa pode realmente ser resolvida apenas pelo experimento. Mas se você não tiver tempo ou dinheiro para fazer experimentos, precisa perguntar a outras pessoas o que elas pensam. Quando você faz isso, considere a fonte e considere se as informações fornecidas foram revisadas ou examinadas de alguma forma.

Jon Harrop avançou algumas reivindicações interessantes sobre Haskell. Deixe -me sugerir que você pesquise nos grupos do Google e em outros lugares por evidências da experiência de Harrop em Haskell, Lisp e outros idiomas funcionais. Você também pode ler o trabalho de Chris Okasaki e Andy Gill nas árvores de Patricia em Haskell, ver como seus conhecimentos são considerados. Você também pode encontrar quais reivindicações, se houver, foram verificadas por terceiros. Então você pode se decidir com o quão a seriamente levar as reivindicações de pessoas diferentes sobre o desempenho de diferentes idiomas funcionais.

Ah, e não alimente o troll.

PS seria bastante razoável para você fazer seus próprios experimentos, mas talvez não seja necessário, já que o confiável Don Stewart apresenta alguns microbenchmarks agradáveis em sua boa resposta. Aqui está um adendo à resposta de Don:

Adendo: Usando o código de Don Stewart em um Phenom 9850 Black Edition da AMD, com um clock de 2,5 GHz com 4 GB de RAM, no modo de 32 bits, com ghc -O,

  • Com a pilha padrão, o IntMap é 40% mais rápido que a tabela de hash.
  • Com a pilha 2G, a tabela de hash é 40% mais rápida que o IntMap.
  • Se eu for para dez milhões de elementos com a pilha padrão, o IntMap é quatro vezes mais rápido do que a tabela de hash (tempo da CPU) ou duas vezes mais rápido no tempo do relógio de parede.

Estou um pouco surpreso com esse resultado, mas tranquilizei que as estruturas de dados funcionais têm um desempenho muito bom. E confirmou na minha crença de que realmente paga para comparar seu código nas condições reais em que ele será usado.

Em suma, mesmo com a correção no mais recente GHC, a Haskell ainda é incapaz de fornecer um dicionário (mutável ou imutável) que é competitivo.

As mesas de hash de Haskell eram 32 × mais lento que alternativas como C ++ e .NET com GHC 6.10. Isso foi em parte devido a um Bug de desempenho no coletor de lixo GHC que foi corrigido para GHC 6.12.2. Mas os resultados de Simon Marlow mostram apenas uma melhoria de desempenho 5 × que ainda deixa as mesas de hash de Haskell muitas vezes mais lentas que a maioria das alternativas.

Alternativas puramente funcionais também são muito mais lentas que uma tabela de hash decente. Por exemplo, Haskell's IntMap é 10 × mais lento que a tabela de hash do .NET.

Usando F# 2010 e A mais recente plataforma Haskell 2010.2.0.0 (Lançado ontem!) Com o GHC 6.12.3 nesta vista de 2,0 GHz E5405, executando o Windows Vista de 32 bits para inserir 20m Int-> int ligações em uma tabela de hash vazio que descobrimos que Haskell ainda é 29 × mais lento que F# em tempo real e Mais de 200 × mais lento em termos de tempo da CPU, porque o Haskell queima todos os núcleos:

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

Desde que você execute apenas Microbenchmarks de curta duração, você pode desativar o coletor de lixo do GHC, como sugere Don Stewart acima. Ao pedir uma geração de berçário tão grande que esse programa em particular nunca o preencha, ele levou tempo para a tabela Haskell Hash para apenas 1,5s aqui. No entanto, isso prejudica completamente todo o ponto de ter uma geração de viveiro e degradará maciçamente o desempenho de outro código, porque os valores recém -alocados agora sempre estarão frios no cache (e é por isso que a geração do berçário é tipicamente do tamanho do cache L2, ordens de magnitude menores que isso).

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top