A high-performance memory allocator for object-oriented systems

doi:10.1109/12.485574

A high-performance memory allocator for object-oriented systems

1996-03-01

36

PRE

AI

DOI：10.1109/12.485574

原文链接

原文求助

摘要

En 中文

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.

Keyword:

buddy system

object-oriented systems

bit-vector allocation

binary tree

dynamic memory management

internal fragmentation

A high-performance memory allocator for object-oriented systems

摘要

期刊

机构

引用论文