Handling and Profiling the Increasingly Large and Complex Memory Allocation Patterns of the 64 Bit Era

The transition from 32 bit to 64 bit processors caused a sudden increase in memory use for a variety of workloads. Additionally, object oriented programs and advanced data structures predominantly use small memory blocks with complex allocation patterns. The increasing size and complexity of allocation patterns has exposed limitations in the scalability and performance of memory allocators. BFM, the allocator presented in this paper, was motivated by such limitations observed in the processing of VLSI designs.

BFM provides low memory overhead (best fit allocation) and competitive performance. Its worst case complexity, O(log(N)) with small constants, holds not only amortized, but for each individual operation. N is the number of heap operations performed in the past. Thus it ensures the absence of pathological cases and is well suited for applications that wish to control response times.

Together with the allocator, a tracing infrastructure is presented that allows to plot memory use over execution time for every call chain. The overhead for tracing is very low such that tracing of multihour and multi-GB runs is feasible without moving to much larger machines.

In addition to the description of the data structures and algorithms of the allocator and tracer, experimental comparisons with the glibc allocator, Hoard and the IBM ® AIX ® ¹ allocator are presented, along with experimental results of tracing.