Customalloc: Efficient synthesized memory allocators
Dirk C. Grunwald, Benjamin G. Zorn · Software Practice and Experience · 1993
Abstract The allocation and disposal of memory is a ubiquitous operation in most programs. Rarely do programmers concern themselves with details of memory allocators; most assume that memory allocators provided by the system perform well. Yet, in some applications, programmers use domain‐specific knowledge in an attempt to improve the speed or memory utilization of memory allocators. In this paper, we describe a program (CustoMalloc) that synthesizes a memory allocator customized for a specific application. Our experiments show that the synthesized allocators are uniformly faster and more space efficient than the Berkeley UNIX allocator. Constructing a custom allocator requires little programmer effort, usually taking only a few minutes. Experience has shown that the synthesized allocators are not overly sensitive to properties of input sets and the resulting allocators are superior even to domain‐specific allocators designed by programmers. Measurements show that synthesized allocators are from two to ten times faster than widely‐used allocators.
Cited by 74 works. doi:10.1002/spe.4380230804
Authors
References
- The Art of Computer Programming. Volume 1: Fundamental Algorithms.
- Optimally profiling and tracing programs
- A unifying look at data structures
- The measured cost of conservative garbage collection
- Improving the cache locality of memory allocation
- Analysis of free-storage algorithms
- Measurements of segment size
- An efficient algorithm for heap storage allocation
- New methods for dynamic storage allocation (Fast Fits)
- Evaluating models of memory allocation