The most efficient way to deallocate memory that has been allocated on distinct threads is to not deallocate it at all. The most efficient way to allocate on independent threads is to allocate once for a full block, on each thread separately, and reuse the allocation for each block in order on that thread. So I started with this...
(edited)