Friday, 4 May 2012

How can garbage collection be faster than malloc?

  • GCs can pointer-bump allocate into a thread-local generation and then rely upon copying collection to handle the (relatively) uncommon case of evacuating the survivors. Traditional allocators like malloc often compete for global locks and search trees.
  • GCs can deallocate many dead blocks simultaneously by resetting the thread-local allocation buffer instead of calling free on each block in turn, i.e. O(1) instead of O(n).
  • By compacting old blocks so more of them fit into each cache line. The improved locality increases cache efficiency.
  • By taking advantage of extra static information such as immutable types.
  • By taking advantage of extra dynamic information such as the changing topology of the heap via the data recorded by the write barrier.
  • By making more efficient techniques tractable, e.g. by removing the headache of manual memory management from wait free algorithms.
  • By making more efficient techniques tractable, e.g. by removing the headache of manual memory management from wait free algorithms.
  • By facilitating concurrency and parallelism, i.e. collection can be performed on a separate core.