A high performance memory allocator for object-oriented systems

JM Chang, EF Gehringer - IEEE Transactions on Computers, 1996 - ieeexplore.ieee.org
JM Chang, EF Gehringer
IEEE Transactions on Computers, 1996ieeexplore.ieee.org
Object-oriented programming languages tend to allocate and deallocate blocks of memory
very frequently. The growing popularity of these languages increases the importance of high-
performance memory allocation. For speed and simplicity in memory allocation, the buddy
system has been the method of choice for nearly three decades. A software realization
incurs the overhead of internal fragmentation and of memory traffic due to splitting and
coalescing memory blocks. This paper presents a simple hardware design for buddy-system …
Object-oriented programming languages tend to allocate and deallocate blocks of memory very frequently. The growing popularity of these languages increases the importance of high-performance memory allocation. For speed and simplicity in memory allocation, the buddy system has been the method of choice for nearly three decades. A software realization incurs the overhead of internal fragmentation and of memory traffic due to splitting and coalescing memory blocks. This paper presents a simple hardware design for buddy-system allocation that takes advantage of the speed of a pure combinational-logic implementation. Two binary trees formed by anding and oring propagate information about the allocation status of blocks and subblocks. They implement a nonbacktracking search for the address of the first free block that is large enough to satisfy a request. Although the buddy system may allocate a block that is much larger than the requested size, the logic that finds a free block can be augmented by a "bit-flipper" to relinquish the unused portion at the end of the block. This effectively eliminates internal fragmentation. Simulation results show that the buddy system modified in this way uses less memory in most, though not all, programs than the unmodified buddy. Hence, the hardware buddy-system allocator is faster and uses memory more efficiently than the standard software approach.
ieeexplore.ieee.org