Comparando o Desempenho de Implementações de Tabelas Hash Concorrentes em Haskell
Abstract
An algorithm which explores performance on concurrent hash tables is far from being trivial. This paper presents seven hash table Haskell implementations, which include low level synchronism models to high level ones such as transactional memories. The result of the comparison between the algorithms showed that the implementation using the STM Haskell transactional memory library presented the best performance.References
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.
Published
2015-10-18
How to Cite
DUARTE, Rodrigo; DU BOIS, André; PILLA, Maurício; REISER, Renata.
Comparando o Desempenho de Implementações de Tabelas Hash Concorrentes em Haskell. In: BRAZILIAN SYMPOSIUM ON HIGH PERFORMANCE COMPUTING SYSTEMS (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.
