A lock-free memory allocator with delayed coalescing

Abstract

A method is disclosed for dynamic memory allocation in computer programs. The invention uses free-lists stored in a table. A method of delayed coalescing is disclosed, whereby blocks are not coalesced immediately they are deallocated. Coalescing is performed by storing block-pointers in an array, sorting the array, and scanning the array for adjacent blocks. The memory allocator can operate in a completely lock-free way using atomic lists. The invention also contains thread-local caches of memory blocks, allowing it to operate mostly lock-free, and specific methods for allocating data and transferring data in between tables are disclosed. A method for automatic memory management (“garbage collection”) based on this allocator is also disclosed. The realisation of this algorithm is a faster memory allocation system for use by computer programs requiring either automatic or manual memory management.

Dependencies are inferred from the claim text.