Using lifetime predictors to improve memory allocation performance

TLDR

Dynamic storage allocation is widely used in interpreters, simulators, optimizers, and translators. The study proposes using lifetime prediction of short‑lived objects to enhance dynamic storage allocation, aiming to reduce memory overhead, improve reference locality, and sometimes boost CPU performance. The authors develop an algorithm that predicts lifetimes of 42–99% of allocated objects and simulate a storage allocator that leverages these predictions to reduce memory overhead, improve locality, and occasionally enhance CPU performance. In five allocation‑intensive C programs, over 90% of allocated bytes are short‑lived, and the proposed allocator reduces memory overhead, improves locality, and sometimes boosts CPU performance.

Abstract

Dynamic storage allocation is used heavily in many application areas including interpreters, simulators, optimizers, and translators. We describe research that can improve all aspects of the performance of dynamic storage allocation by predicting the lifetimes of short-lived objects when they are allocated. Using five significant, allocation-intensive C programs, we show that a great fraction of all bytes allocated are short-lived (> 90% in all cases). Furthermore, we describe an algorithm for liftetime prediction that accurately predicts the lifetimes of 42–99% of all objects allocated. We describe and simulate a storage allocator that takes adavantage of lifetime prediction of short-lived objects and show that it can significantly improve a program's memory overhead and reference locality, and even, at times, improve CPU performance as well.