Parallel dynamic memory allocation using a lock-free FIFO

摘要

One embodiment of the present invention sets forth a technique for dynamically allocating memory using one or more lock-free FIFOs. One or more lock-free FIFOs are populated with FIFO nodes, where each FIFO node represents a memory allocation of a predetermined size. Each particular lock-free FIFO includes memory allocations of a single size. Different lock-free FIFOs may include memory allocations for different sizes to service allocation requests for different size memory allocations. A lock-free mechanism is used to pop FIFO nodes from the FIFO. The use of the lock-free FIFO allows multiple consumers to simultaneously attempt to pop the head FIFO node without first obtaining a lock to ensure exclusive access of the FIFO.

主权项

1. A method of allocating memory, the method comprising:
receiving a plurality of memory allocation requests from a plurality of threads, wherein each memory allocation request specifies an amount of memory; identifying a first-in first-out sub-system (FIFO) node size based on the amounts of memory associated with the plurality of memory allocation requests; selecting a first FIFO included in a plurality of FIFOs and populated with FIFO nodes of the FIFO node size; popping a first FIFO head node from the first FIFO to satisfy the memory allocation request associated with a first thread included in the plurality of threads; determining that all of the FIFO nodes that populate the first FIFO have been freed; and in response, retiring the first FIFO.