Skip to content

Defer megablock freeing to avoid repeated linear search on free list

Fabian Thorand requested to merge deferred-megablock-freeing into master

Fixes ghc/ghc#19897 (closed) in the following way:

  • The megablock free list remains sorted and coalesced, but during GCs, we will use a secondary free list that is neither sorted nor coalesced.
  • At the end of a GC run, we can then sort the secondary free list once (O(n log n)) and perform a single merge pass to merge it into the actual free list (O(n))

That way, we are asymptotically faster compared to the situation explained in the above issue, where every individual free call incurs a linear search on the free list, resulting in O(n^2) runtime in the worst case.

You can see the difference in runtime of the final measured GC of the reproducer from the original issue in the following graph:

image

The overall runtime of the reproducer also slightly improved:

image

I also added a comment about another potential case of "accidentally quadratic" that I didn't tackle in this PR, because it didn't occur (yet) in practice.

Merge request reports