Adaptive allocators

Computer Engineering - Sapienza University of Rome

Student: Emilio Coppa - Supervisor: Camil Demetrescu

Experimental comparison of allocators BSA (Bad segregated allocator), developed by Emilio Coppa during the Algorithm Engineering course held in 2009-2010 at the School of Engineering of the Sapienza University of Rome, and TLSF (Two level segregated fit), a general-purpose dynamic memory allocator specifically designed to meet real-time requirements designed by Real Time Research Group of the University of Valencia. The main goal of this work was to study some adaptive allocation techniques to improve BSA(++)'s capabilities based on the analysis of typical allocation traces of applications.

Allocator descriptions:


Benchmarks have been produced with the following working environment: a MacBook 5.1 (Intel Core 2 Duo [email protected], 2GB DDR3, NVIDIA GeForce 9400M). The software configuration used is the following:


Our benchmarks files were created based on the file format of the MallocLab framework developed by R. Bryant and D. O'Hallaron. This platform provides a simple tool to measure performance of an allocator in time and space (only single-process load).

We collected our traces using a combination of different techniques:

  1. Development of a tool based on PIN (a dynamic binary instrumentation software by Intel).
  2. Modified GlibC (added instruction tracing).
  3. Library interpositioning at runtime based on the dlsym() call.
In addition, we created tools to convert the collected traces in the format required by MallocLab and their analysis. This software has been published in the package MallocLabTools.


The benchmarks reproduced were inspired by experiments carried out by the authors of TLSF in order to test their allocator. We ran MallocLab with the following program traces: In conclusion, these are the average behaviour of tested allocators for all programs:
We summarize below the lessons we learned from our experiments: