Freelists with concurrent allocators

Question

Freelists are a common way to speed up allocation by reusing existing memory that was already allocated. Is there a way to use free-lists in a concurrent allocator, without incurring the overhead of a lock for every allocation (which would neutralize the intended performance gain of the freelist)?

Answer 1

Use a lock-free linked list.

Answer 2

You could have thread-specific free list chunks.

Basically, there is some system which populates the free lists (e.g. a garbage collector). Then each thread could have its own free list chunk, containing a small number of entries. Locking would be used to allocate a new chunk. With chunks with 30 entries, you would lock only once every 30 allocations. Conversely, with thread-specific chunks you may have to run the GC sooner, because the shared list could become empty even if some of the thread-specific chunks still have some free entries.