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 ® 1 allocator are presented, along with experimental results of tracing.
By: Ulrich Finkler
Published in: RC23377 in 2004
LIMITED DISTRIBUTION NOTICE:
This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.
Questions about this service can be mailed to reports@us.ibm.com .