Análise de Desempenho de Hash Tables Não-Bloqueantes na Linguagem C++

  • Douglas Pereira Luiz UFSC
  • Odorico M. Mendizabal UFSC

Resumo


Hash Tables são estruturas de dados que associam chaves de busca a valores e são amplamente utilizadas no desenvolvimento de sistemas. Quando seu uso exigir compartilhamento entre threads podem ser implementadas com travas como método de sincronização ou de maneira não-bloqueante. Neste trabalho foram reunidas e comparadas implementações de hash tables bloqueantes e não-bloqueantes para a linguagem C++.

Referências

Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. (2001). Introduction to Algorithms. The MIT Press, 2nd edition.

Feldman, S., LaBorde, P., and Dechev, D. (2013). Concurrent multi-level arrays: Wait-free extensible hash maps.

Herlihy, M. and Shavit, N. (2012). The Art of Multiprocessor Programming, Revised Reprint. Morgan Kaufmann Publishers Inc., 1st edition.

Laborde, P., Feldman, S., and Dechev, D. (2017). A wait-free hash map. Int. J. Parallel Program., 45(3):421-448.

Michael, M. M. (2002). High performance dynamic lock-free hash tables and list-based sets. In Proceedings of the Fourteenth Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA '02, page 73-82.
Publicado
10/05/2023
LUIZ, Douglas Pereira; MENDIZABAL, Odorico M.. Análise de Desempenho de Hash Tables Não-Bloqueantes na Linguagem C++. In: ESCOLA REGIONAL DE ALTO DESEMPENHO DA REGIÃO SUL (ERAD-RS), 23. , 2023, Porto Alegre/RS. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2023 . p. 73-76. ISSN 2595-4164. DOI: https://doi.org/10.5753/eradrs.2023.229898.