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

• Douglas Pereira Luiz UFSC
• Odorico M. Mendizabal UFSC

DOI: https://doi.org/10.5753/eradrs.2023.229898

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.