Skip to content
  • Simon Marlow's avatar
    optimisation to freeGroup() to avoid an O(N^2) pathalogical case · fec956d1
    Simon Marlow authored
    In the free list, we don't strictly speaking need to have every block
    in a coalesced group point to the head block, although this is an
    invariant for non-free blocks.  Dropping this invariant for the free
    list means that coalesce() is O(1) rather than O(N), and freeGroup()
    is therefore O(N) not O(N^2).
    
    The bad case probably didn't happen most of the time, indeed it has
    never shown up in a profile that I've seen.  I had a report from a
    while back that this was a problem with really large heaps, though.
    Fortunately the fix is easy.
    fec956d1