Comparando o Desempenho de Implementações de Tabelas Hash Concorrentes em Haskell
Resumo
Implementar um algoritmo de tabela hash concorrente que extraia desempenho está longe de ser trivial. Neste artigo apresentamos sete diferentes implementações de tabelas hash em Haskell, explorando desde modelos de sincronização de baixo nível até os de mais alta abstração como memórias transacionais. Nos testes realizados a implementação usando a biblioteca STM Haskell de memória transacional foi a que apresentou melhor desempenho.Referências
Data.CAS (2015). http://hackage.haskell.org/package/IORefCAS-0.1.0.1/docs/src/Data-CAS.html.
Harris, T., Marlow, S., Jones, S. P., and Herlihy, M. (2008). Composable memory transactions. Commun. ACM, 51:91–100.
Herlihy, M. and Shavit, N. (2012). The Art of Multiprocessor Programming, Revised Reprint. Elsevier.
Leiserson, C. E., Rivest, R. L., Stein, C., and Cormen, T. H. (2001). Introduction to algorithms. The MIT press.
Marlow, S. (2013). Parallel and Concurrent Programming in Haskell: Techniques for Multicore and Multithreaded Programming. "O'Reilly Media, Inc.".
Newton, R., Chen, C.-P., Marlow, S., et al. (2011). Intel concurrent collections for haskell.
O'Sullivan, B., Goerzen, J., and Stewart, D. B. (2008). Real World Haskell. O'Reilly.
Rigo, S., Centoducatte, P., and Baldassin, A. (2007). Memórias transacionais: Uma nova alternativa para programação concorrente. In Minicursos do VIII Workshop em Sistemas Computacionais de Alto Desempenho, WSCAD 2007.
Shalev, O. and Shavit, N. (2006). Split-ordered lists: Lock-free extensible hash tables. Journal of the ACM (JACM), 53(3):379–405.
Sönmez, N., Perfumo, C., Stipic, S., Cristal, A., Unsal, O. S., and Valero, M. (2007). unreadtvar: Extending haskell software transactional memory for performance. Trends in Functional Programming, 8:89–114.
Sulzmann, M., Lam, E. S., and Marlow, S. (2009). Comparing the performance of concurrent linked-list implementations in haskell. In Proceedings of the 4th workshop on Declarative aspects of multicore programming, pages 37–46. ACM.
Harris, T., Marlow, S., Jones, S. P., and Herlihy, M. (2008). Composable memory transactions. Commun. ACM, 51:91–100.
Herlihy, M. and Shavit, N. (2012). The Art of Multiprocessor Programming, Revised Reprint. Elsevier.
Leiserson, C. E., Rivest, R. L., Stein, C., and Cormen, T. H. (2001). Introduction to algorithms. The MIT press.
Marlow, S. (2013). Parallel and Concurrent Programming in Haskell: Techniques for Multicore and Multithreaded Programming. "O'Reilly Media, Inc.".
Newton, R., Chen, C.-P., Marlow, S., et al. (2011). Intel concurrent collections for haskell.
O'Sullivan, B., Goerzen, J., and Stewart, D. B. (2008). Real World Haskell. O'Reilly.
Rigo, S., Centoducatte, P., and Baldassin, A. (2007). Memórias transacionais: Uma nova alternativa para programação concorrente. In Minicursos do VIII Workshop em Sistemas Computacionais de Alto Desempenho, WSCAD 2007.
Shalev, O. and Shavit, N. (2006). Split-ordered lists: Lock-free extensible hash tables. Journal of the ACM (JACM), 53(3):379–405.
Sönmez, N., Perfumo, C., Stipic, S., Cristal, A., Unsal, O. S., and Valero, M. (2007). unreadtvar: Extending haskell software transactional memory for performance. Trends in Functional Programming, 8:89–114.
Sulzmann, M., Lam, E. S., and Marlow, S. (2009). Comparing the performance of concurrent linked-list implementations in haskell. In Proceedings of the 4th workshop on Declarative aspects of multicore programming, pages 37–46. ACM.
Publicado
18/10/2015
Como Citar
DUARTE, Rodrigo; DU BOIS, André; PILLA, Maurício; REISER, Renata.
Comparando o Desempenho de Implementações de Tabelas Hash Concorrentes em Haskell. In: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 16. , 2015, Florianópolis.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2015
.
p. 180-191.
DOI: https://doi.org/10.5753/wscad.2015.14282.
