Designing Allocators that Don't Not Work

Abstract

STL introduced allocators as a stop gap for the now antiquated segmented memory models of the 1990s. Their design was very limited and in many ways wasn't even aiming at helping allocation that much. Because they were there, they simply continued being there, up to the point they became impossible to uproot.

Scalable, high-performance memory allocation is a topic of increasing importance in today's demanding applications. For such, STL's allocators simply don't work. This talk discusses the full design of a memory allocator created from first principles. It is generic, componentized, and very composable for supporting application-specific allocation patterns.

Highlights

• Historical perspective: from malloc to std::allocator
• Differential and comparative design: keep designs that are modular and efficient, eliminate design decisions that lead to costly arcana down the road
• New allocator design built from robust first principles to satisfy demanding allocation traffic
• Collecting allocation statistics efficiently

Attendee Profile

C++ knowledge and an understanding of object models and memory layout are assumed. Library designers and architects of high-performance systems would derive most value from this course. 

Outline

• Allocators: a cyclical business
  • Hand-written allocators have been gainful to implement or not depending on the decade's Zeitgeist
  • Discussion of malloc's fatal mistake that makes it unduly less efficient than it should
  • std::allocator genesis, history, present, obvious mistakes, and subtle issues
• New allocator design
  • Simplest composite allocator: FallbackAllocator
  • Stack allocator
  • Freelist allocator
  • Adding affixes to allocation
  • A simple general-purpose heap
  • Cascading allocators
  • Segregating allocators
  • Bucketizing allocators
• Discussion
  • Approach to copying
  • Granularity
  • Examples
  • Complete API
  • Alignment issues