File PoolAllocator.h

↰ Parent directory (ADS/memory)

A standard allocator over pools of size classes, beyond the book, so that the containers of the standard library and std::allocate_shared take their nodes from pages of slots of one size instead of the general allocator.

Definition (ADS/memory/PoolAllocator.h)

Detailed Description

PoolResource< M > keeps the size classes of :math:` g = 8 ` bytes up to M: a request of b bytes, :math:` 1 le b le M , aligned to :math: a le 8 , takes a slot of :math: lceil b / 8 rceil 8 ` bytes, and one aligned to 16 a slot of :math:` lceil b / 16 rceil 16 ` bytes, whose class has its slots aligned to 16, so that the internal waste is below a bytes per object and the nodes of the containers, aligned to 8, waste nothing when their size is a multiple of 8; any other request, larger or more aligned, goes to operator new. The slots come from the pages of PageHeap [see File PageHeap.h], whose free lists are kept by page: a class allocates from one page at a time, so that the nodes of a container that is emptied in a scrambled order and filled again are given back a page at a time, close to each other, which a single free list (as that of ObjectPool [see File ObjectPool.h]) does not do. The memory goes back to the system only with the resource: a structure that shrinks keeps the memory of its largest size, which it takes again at no cost.

PoolAllocator< T , R > is the allocator of the standard (the requirements Allocator of [allocator.requirements]): it holds a pointer to its resource R, the PoolResource above or the ConcurrentPoolResource of the threads [see File ConcurrentPool.h], it is rebound to any type by std::allocator_traits (a node of std::list, std::map or std::unordered_map, the control block of std::allocate_shared, which then holds the counts and the object in one slot), and two allocators are equal when they share their resource. A container copies, moves and swaps its allocator with its contents (the three propagate_on_container traits are true), so that a node always goes back to the pool it came from. A request of one object, the case of the node containers, finds its class at compile time and costs the pop of a free list; a request of n objects, e.g., the buckets of std::unordered_map, finds it from n.

Neither the resource nor its allocators synchronize: one thread at a time uses a PoolResource, and an object made by one thread and freed by another needs ConcurrentPoolResource. The resource must outlive every object and every allocator made from it.

The contracts [see File Contract.h]: a pointer freed was given by the same resource, and its deallocation gets the size and the alignment of its allocation. The operations are defined in PoolAllocator.tpp.

  1. Leijen, B. Zorn, L. de Moura, Mimalloc: free list sharding in action, Programming Languages and Systems (APLAS 2019), Lecture Notes in Computer Science 11893, 244-265, 2019, doi:10.1007/978-3-030-34175-6_13 (the free lists by page)

  1. Bonwick, The slab allocator: an object-caching kernel memory allocator, Proceedings of the USENIX Summer 1994 Technical Conference, 1994, www.usenix.org/publications/library/proceedings/bos94/bonwick.html (the slabs of one size)

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Classes

Functions