Locality Consideration in Memory Allocators

From the above discussion, we know meta-data design matters much with spacial locality. In order to improve spacial locality, vam [FengB:MSP05] allocator moved object headers, i.e. meta-data, to the headers of pages where objects are stored. streamflow [Schneider+:ISMM06] allocator also removed object headers, but stored the meta-data globally in separate space like tcmalloc does. In addition to meta-data, a few other papers tried to explore locality in other ways. Streamflow [Schneider+:ISMM06] allocator favored locality transparently from three folds. First, it favored temporal locality by using LIFO free lists. Second, spacial locality is favored by removing object headers. Last, contiguous allocation within pages in physical memory helped to reduce cache misses, page fault rate and TLB misses, since continuous layout reduces self-interference within a page block and cross-interference (between page blocks) in the cache. Cache-conscious data layout is developed by streamflow for the first time at the user level. To achieve the locality purpose, however, streamflow uses atomics or locks for synchronizations in five design details, which slow down programs much. In particular, three out of five are in critical path. In fact, the meta-data management in streamflow is quite like tcmalloc does. Julia [JulaR:ISMM09] used automatic hints from C++ STL library to improve an application’s spacial locality suppose the target application is using C++ STL library. For example, the parent’s address is used as a hint when allocating a node in a tree. For another instance, the previous element’s address is used as a hint when allocating an element in a list. Provided with hints, Julia defined locality accuracy as the distance in the virtual address space between the hint and the returned object, which actually reflects “closeness” in spacial locality. By dividing pages into regions in a “closeness” scope, the allocator always tried to return an object in the same region with the hint to achieve the locality accuracy. Julia only enhanced spacial locality of applications using C++ STL library. For those applications not using C++ STL library, Julia’s method is not a fit. Pool allocation [Lattner+:PLDI05] incorporates heap objects with the same data structure into the same pool in order to purse a good cache locality. Lattner [Lattner+:PLDI05] analyzed data types of heap slots at compile-time and allocate the heap objects with the same data type in the same pool. To prevent the disambiguity and inaccuracy of compile-time analysis, Wang et al. [Wang+:CGO10] proposed dynamic pool allocation to improve spacial locality of heap objects at runtime by keeping track of affinity of heap objects of the same data structure, which certainly incurs much performance overhead.

One thought on “Locality Consideration in Memory Allocators

  1. K is a tunable parameter. The locality accuracy is measured by the logarithm of the byte-distance of two objects in memory.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s