One embodiment of the present invention sets forth a technique for dynamically allocating memory using a nested hierarchical heap. A lock-free mechanism is used to access to a hierarchical heap data structure for allocating and deallocating memory from the heap. The heap is organized as a series of levels of fixed-size blocks, where all blocks at given level are the same size. At each lower level of the hierarchy, a collection of N blocks in the lower level equals the size of a single block at the level above. When a thread requests an allocation, one or more blocks at only one level are allocated to the thread. When threads are finished using an allocation, each thread deallocates the respective allocated blocks. When all of the blocks for a level have been deallocated, defragmentation is performed at that level.