File ConcurrentPool.h

↰ Parent directory (ADS/memory)

A pool of size classes shared by threads, beyond the book: an object made by one thread may be freed by any other, e.g., a message created by the thread that changes a model and released by the thread of a solver that has read it.

Definition (ADS/memory/ConcurrentPool.h)

Detailed Description

It is a resource of PoolAllocator [see File PoolAllocator.h], with the classes of PoolResource: the multiples of 8 bytes up to M, a request of b bytes aligned to at most 8 taking a slot of :math:` lceil b / 8 rceil 8 ` bytes, one aligned to 16 a slot of :math:` lceil b / 16 rceil 16 ` bytes, and any larger or more aligned one going to operator new.

Each thread that uses the resource has a heap of its own, found by a cache in its thread-local storage (one comparison with the identity of the resource) and, the first time, on a list of the heaps that grows by a compare-and-swap and is read with no lock. A heap is a PageHeap [see File PageHeap.h]: pages of :math:` 2^{16} ` bytes of one class each, cut from segments of :math:` 2^{21} ` bytes, with a free list per page and a header that names the heap owning the page. The free of a pointer p finds its page as :math:` p wedge neg ( 2^{16} - 1 ) `, i.e., by masking the low bits of p, and then:

  • if the page belongs to the heap of the calling thread, the slot goes on the free list of its page, with no atomic operation, so that a thread that frees what it made pays what it pays in PoolResource;

  • otherwise the slot joins the batch of the calling thread for its class, which holds the slots of one owning heap, and the batch goes back to that heap, by one compare-and-swap that links it whole on the top of the list of the returns of the class there (a stack of Treiber), when it has 32 slots, when a slot of another heap arrives, or when the calling thread needs a new page of the class or calls collect(); many threads push, and only the owner takes, the whole stack at once by exchanging its top with nil when the current page of that class is exhausted, and puts each slot back on the list of its page. Since the owner only takes the whole stack, the ABA problem cannot occur.

Thus an allocation costs the pop of the list of the current page or the bump of its pointer, or, when the page is exhausted, one exchange that takes all the returns at once; a free costs a push on the list of a page, or a push on a batch and a compare-and-swap per batch, i.e., per up to 32 frees of a producer and a consumer that work in pairs. The lists of returns of the classes sit on separate lines of cache, so that the threads that free into different classes do not share a line. A slot waits in a batch for at most 31 other frees, so that each thread holds at most 31 slots per class freed and not yet back. A heap is never destroyed before the resource; a thread that ends leaves its heap, whose returns keep coming, to the next thread that has the same identity, and its memory goes back to the system with the resource.

global() is a resource that lives as long as the program, the default one of PoolAllocator< T , ConcurrentPoolResource<> >.

The contracts [see File Contract.h]: a pointer freed was given by the resource and is freed once, with the size and the alignment of its allocation; the resource outlives its objects and its allocators, and heaps() and bytes() are read while no other thread uses it. The operations are defined in ConcurrentPool.tpp.

    1. Treiber, Systems programming: coping with parallelism, Technical Report RJ 5118, IBM Almaden Research Center, 1986

    1. Berger, K. S. McKinley, R. D. Blumofe, P. R. Wilson, Hoard: a scalable memory allocator for multithreaded applications, Proceedings of the Ninth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS IX), 117-128, 2000, doi:10.1145/378993.379232 (the heaps of the threads, the owner of a block)

  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 pages of one class with their local and their thread free lists, the page of a pointer by masking)

  1. Lietar, T. Butler, S. Clebsch, S. Drossopoulou, J. Franco, M. J. Parkinson, A. Shamis, C. M. Wintersteiger, D. Chisnall, snmalloc: a message passing allocator, Proceedings of the 2019 ACM SIGPLAN International Symposium on Memory Management (ISMM 2019), 122-135, 2019, doi:10.1145/3315573.3329980 (the frees of other threads sent back to the owner in batches, which it takes all at once)

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes