A Comprehensive Complexity Analysis of User-Level Memory Allocator Algorithms

• Taís Borges Ferreira UFU
• Márcia Aparecida Fernandes UFU
• Rivalino Matias Jr. UFU

Resumo

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.

Palavras-chave: Instruction sets, Arrays, Memory management, Resource management, Complexity theory, Algorithm design and analysis, analysis of algorithm, user-level allocators