A Comprehensive Complexity Analysis of User-Level Memory Allocator Algorithms - Ferreira, Taís Borges; Fernandes, Márcia Aparecida; Matias Jr., Rivalino (Anais do Simpósio Brasileiro de Engenharia de Sistemas Computacionais (SBESC); 2012: Anais do II Simpósio Brasileiro de Engenharia de Sistemas Computacionais, 2012)
Memory allocations are one of the most frequently used operations in computer programs. The performance of memory allocation operations is a critical factor in software design; however, it is very often neglected. In this paper, we present a comprehensive complexity analysis of widely adopted user-level memory allocator algorithms. We consider time and space complexity, as well as the allocator overhead. The results show that the Ptmalloc family of memory allocator algorithms outperformed all other investigated allocators in terms of theoretical time complexity and space overhead. All allocators showed the same space complexity.