Skip to content

Defer freeing of mega block groups to avoid quadratic worst case GC performance

Fabian Thorand requested to merge fatho/ghc:deferred-megablock-freeing into master

Fixes #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

If more documentation in the code is required, please let me know!

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