File SizeClassAllocator.h

↰ Parent directory (ADS/memory)

An allocator of small blocks by size classes, beyond the book: the scheme of the allocators of today (mimalloc, jemalloc, tcmalloc), for one thread, the size of a block given back by its owner (sized deallocation, as std::allocator does), so that a block needs no header.

Definition (ADS/memory/SizeClassAllocator.h)

Detailed Description

A request of n bytes, :math:` 1 leq n leq 32768 `, goes to the least class not below it: the multiples of 16 up to 128, then four classes per power of 2 (160, 192, 224, 256, 320, …), so that the waste is below 25% of a block past 128 bytes (and below 16 bytes up to it), and the class is found by a shift and a count of the leading zeros, with no table and no loop. Each class has a free list of the blocks given back, the last one first (whose memory is still in the cache), and a page of 64 KB (the size of the largest block, if larger) whose rest is cut a block at a time; a request takes the first free block, or the next one of the page, or a new page, in O( 1 ) time, and a release puts the block at the head of the list of its class, in O( 1 ). The pages go back to the system with the allocator (or by release()): memory is not returned while the allocator lives, as with a pool, but the blocks given back serve any later request of their class. A request of more than 32768 bytes goes to operator new.

The contracts [see File Contract.h]: a request is of at least one byte, and deallocate() gets a block of this allocator with the size of its request. The operations are defined in SizeClassAllocator.tpp.

    1. Knuth, The Art of Computer Programming, vol. 1, 3rd ed., Addison-Wesley, 1997, section 2.5 (the lists of available blocks)

  1. Masmano, I. Ripoll, A. Crespo, J. Real, TLSF: a new dynamic memory allocator for real-time systems, Proceedings of the 16th Euromicro Conference on Real-Time Systems (ECRTS), 79-88, 2004, doi:10.1109/EMRTS.2004.1311009

    1. Berger, B. G. Zorn, K. S. McKinley, Reconsidering custom memory allocation, Proceedings of the 17th ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA), 1-12, 2002, doi:10.1145/582419.582421

  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

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

  • ADS/Contract.h (File Contract.h)

  • ADS/memory/impl/SizeClassAllocator.tpp

  • bit

  • cstddef

  • cstdint

  • new

  • utility

Namespaces

Classes