Performance e escalabilidade – Hash Map em AdvPL

O que é um Hash Map ( ou Hash Table ) ?

Em computação, uma tabela de hash (Hash Table) ou mapa de hash (Hash Map) é uma estrutura de dados que implementa um array associativo, também conhecido por chave-valor, onde um determinado valor é acessado por uma determinada chave. Em muitas situações, esta estrutura é muito mais eficiente do que utilizar uma árvore de busca, array ordenado, ou qualquer outra estrutura de dados ou mecanismo de pesquisa.

A partir do TOTVS Application Server, build 7.00.131227A, foram disponibilizadas um grupo de funções para a criação e manutenção de um Hash Map, inclusive a criação de um Hash Map a partir dos dados contidos em um array multi-dimensional em AdvPL.

Vantagens

A vantagem da utilização do Hash Map em relação a outras estruturas é a velocidade de localização de um valor a partir da chave fornecida. Esta diferença de desempenho é mais perceptível quando temos um número maior de entradas ou elementos no Array.

Desvantagens

Porém, a manutenção de um Hash Map (acrescentar ou remover elementos) pode ter um custo maior, inclusive dependendo da estrutura interna da implementação do algoritmo de hash, este custo de manutenção pode aumentar proporcionalmente de acordo com a quantidade de elementos no mapa.

Melhor cenário

Logo, o melhor cenário para uso de um Hash Map parte da utilização em um Array de dados na memória, onde durante o processamento haverá pouca ou nenhuma manutenção neste mapa (acrescentar ou remover elementos), e a quantidade de buscas realizadas neste mapa seja a parte significativa do processamento.

Programa de exemplo

Para ilustrar um caso simples de uso do Hash Map em Advpl, vamos a um programa de exemplo, onde será criado um array com relativamente poucos elementos ( 17 ), onde a primeira coluna será a chave de busca, e vamos realizar 50 mil buscas para cada uma das 17 chaves, mais 50 mil buscas por uma chave não existente.

Na primeira parte do programa, as buscas sobre o Array serão feitas com ASCAN(), e na segunda parte do programa, vamos criar um Objeto de Hash Map a partir do Array, usando a função aToHM(), e depois realizar as mesmas buscas usando o objeto de Hash Map.

Ao todo, cada teste vai realizar 900000 (novecentas mil) buscas, onde serão contabilizados os tempos das 50 mil buscas para cada valor por cada método, e o tempo total de todas as buscas por método utilizado.

Segue o programa Advpl abaixo. Após compilado, ele pode ser executado diretamente a partir do SmartClient, através da função U_TSTHASH

Fonte

#include “protheus.ch”

USER Function TstHash()

Local aDados := {}
Local nI , nJ 
Local nTimer, nTotal
Local cBusca 
Local nPos , xValue
Local oHash

// Cria um array de duas colunas, com 17 elementos

aadd(aDados , { "BC","Branco" } )
aadd(aDados , { "AZ","Azul" } )
aadd(aDados , { "VM","Vermelho" } )
aadd(aDados , { "VD","Verde" } )
aadd(aDados , { "RX","Roxo" } )
aadd(aDados , { "AM","Amarelo" } )
aadd(aDados , { "MA","Marrom" } )
aadd(aDados , { "AM","Azul Marinho" } )
aadd(aDados , { "AC","Azul Céu" } )
aadd(aDados , { "AQ","Amarelo Queimado" } )
aadd(aDados , { "AT","Azul Turquesa" } )
aadd(aDados , { "SA","Salmão" } )
aadd(aDados , { "VO","Verde Oliva" } )
aadd(aDados , { "VI","Violeta" } )
aadd(aDados , { "GR","Cinza" } )
aadd(aDados , { "PB","Chumbo" } )
aadd(aDados , { "PT","Preto" } )

// Faz um teste de desempenho buscando pelos elementos usando ASCAN()
// Faz 50 mil buscas para cada um dos elementos cadastrados
// O ultimo loop busca por um elemento que nao existe

nTotal := seconds()

For nI := 1 to len(aDados)+1
  If nI > len(aDados)
    // Busca por um elemento que nao existe 
    cBusca := "NE"
  Else
    // Busca por um elemento que existe na lista 
    cBusca := aDados[nI][1]
  Endif
  nTimer := seconds()
  For nJ := 1 to 50000
    // Realiza 50 mil buscas 
    nPos := ascan( aDados , {|x| x[1] == cBusca })
  Next
  nTimer := seconds()-nTimer
  conout("Busca por ["+cBusca+"] demorou "+cValToChar(nTimer)+" s.")
Next

nTotal := seconds() - nTotal
conout("Tempo Total (ASCAN) = "+cValToChar(nTotal)+" s.")
conout("")

// Agora usando o HASH
nTotal := seconds()

// Cria o Objeto de HASH a partir do Array
oHash := aToHM(aDados)

For nI := 1 to len(aDados)+1
  If nI > len(aDados)
    // Busca por um elemento que nao existe 
    cBusca := "NE"
  Else
    // Busca por um elemento que existe na lista 
    cBusca := aDados[nI][1]
  Endif
  nTimer := seconds()
  For nJ := 1 to 50000
    // Realiza 50 mil buscas 
    lFound := HMGet( oHash , cBusca , @xValue )
  Next
  nTimer := seconds()-nTimer
  conout("Busca por ["+cBusca+"] demorou "+cValToChar(nTimer)+" s.")
Next

nTotal := seconds() - nTotal
conout("Tempo Total (HASH) = "+cValToChar(nTotal)+" s.")

Return

Resultados obtidos

Para visualizar o resultado do programa, verifique o LOG de console do Application Server. Segue abaixo um exemplo do log gerado:

Busca por [BC] demorou 0.359 s.
Busca por [AZ] demorou 0.406 s.
Busca por [VM] demorou 0.421 s.
Busca por [VD] demorou 0.483 s.
Busca por [RX] demorou 0.53 s.
Busca por [AM] demorou 0.593 s.
Busca por [MA] demorou 0.624 s.
Busca por [AM] demorou 0.577 s.
Busca por [AC] demorou 0.702 s.
Busca por [AQ] demorou 0.78 s.
Busca por [AT] demorou 0.796 s.
Busca por [SA] demorou 0.826 s.
Busca por [VO] demorou 0.874 s.
Busca por [VI] demorou 0.92 s.
Busca por [GR] demorou 0.969 s.
Busca por [PB] demorou 1.014 s.
Busca por [PT] demorou 1.061 s.
Busca por [NE] demorou 1.061 s.
Tempo Total (ASCAN) = 13.075 s.

Busca por [BC] demorou 0.094 s.
Busca por [AZ] demorou 0.094 s.
Busca por [VM] demorou 0.093 s.
Busca por [VD] demorou 0.094 s.
Busca por [RX] demorou 0.093 s.
Busca por [AM] demorou 0.094 s.
Busca por [MA] demorou 0.093 s.
Busca por [AM] demorou 0.094 s.
Busca por [AC] demorou 0.093 s.
Busca por [AQ] demorou 0.094 s.
Busca por [AT] demorou 0.109 s.
Busca por [SA] demorou 0.094 s.
Busca por [VO] demorou 0.093 s.
Busca por [VI] demorou 0.094 s.
Busca por [GR] demorou 0.094 s.
Busca por [PB] demorou 0.109 s.
Busca por [PT] demorou 0.093 s.
Busca por [NE] demorou 0.078 s.
Tempo Total (HASH) = 1.716 s.

Reparem que, ao buscar com ASCAN(), como a busca é feita sequencialmente, quanto mais elementos precisam ser comparados até que seja encontrado o nó do array que satisfaz a condição, maior o tempo de busca. O pior cenário é a busca por um elemento que não existe, pois neste caso o ASCAN() varreu todos os elementos do Array para determinar que o valor não existe. No melhor cenário, 50 mil buscas do primeiro valor do array demoraram 0,359 segundos, e no pior cenário, quando o valor buscado era o último valor do array ou quando o valor não existia no array, 50 mil buscas demoraram 1,061 segundos.

Já com o uso do objeto de hash, criado a partir deste mesmo array, o desempenho das buscas foi aproximadamente 7,6 vezes mais rápido, e cada uma das buscas, não importa se a chave de busca estava no início ou no final do mapa, demoraram em média 1/10 de segundo.

Conclusão

Como mencionado no tópico “Mellhor Cenário”, em um processamento onde usamos um Array em memória com baixa ou nenhuma manutenção, e um volume muito grande de buscas, o Hash Map é uma alternativa excelente em custo x benefício.

Porém, lembre-se também da Lei de Amdahl : “O ganho de desempenho que pode ser obtido melhorando uma determinada parte do sistema é limitado pela fração de tempo que essa parte é utilizada pelo sistema durante a sua operação.” Isto é, se o seu caso de uso cria arrays pequenos e para poucas consultas, tomando um tempo ínfimo de processamento, criar um Hash Map só vai te dar trabalho de refatorar seu código, e você não terá um ganho perceptível, ou ainda, no pior cenário, apresentar uma piora no desempenho. Neste exemplo foi usado um array muito pequeno, logo foram necessárias muitas buscas para mostrar a diferença de desempenho. Cada teste completo fez 900 mil buscas no Array e 900 mil usando Hash Map.

As funções para lidar com Hash Map em AdvPL estão documentadas na TDN, a partir do link http://tdn.totvs.com/pages/viewpage.action?pageId=77300615

Let’s Share

Espero que vocês tenham gostado da linha de raciocínio e conteúdo disponibilizados aqui no Blog. Não se acanhe em comentar se ficou alguma dúvida ou se alguma parte do texto ficou sem pé nem cabeça. Se você gostou, e achou este conteúdo útil, compartilhe , e se este lhe for útil, use-o. No próximo post sobre Hash Map, o fonte de exemplo vai utilizar todas as funções de manutenção, e um índice de busca composto.

“A essência do conhecimento consiste em aplicá-lo, uma vez possuído.” — Confúcio

Até o próximo post, pessoal 😉

Referências

Wikipedia contributors. Hash table. Wikipedia, The Free Encyclopedia. December 11, 2014, 06:10 UTC. Available at: http://en.wikipedia.org/w/index.php?title=Hash_table&oldid=637586906. Accessed December 17, 2014.