• Tatsuyuki Ishi's avatar
    ntdll: Use log-linear bucketing for free lists. · a612ab6f
    Tatsuyuki Ishi authored
    Currently, the free list consists of a "small list" for sizes below 256,
    which are linearly spaced, and a "large list" which is manually split
    into a few chunks.
    
    This patch replaces it with a single log-linear policy, while expanding
    the range the large list covers.
    
    The old implementation had issues when a lot of large allocations
    happened. In this case, all the allocations went in the last catch-all
    bucket in the "large list", and what happens is:
    1. The linked list grew in size over time, causing searching cost to
       skyrocket.
    2. With the first-fit allocation policy, fragmentation was also making
       the problem worse.
    
    The new bucketing covers the entire range up until we start allocating
    large blocks, which will not enter the free list. It also makes the
    allocation policy closer to best-fit (although not exactly), reducing
    fragmentation.
    
    The increase in number of free lists does incur some cost when it needs
    to be skipped over, but the improvement in allocation performance
    outweighs it.
    
    For future work, these ideas (mostly from glibc) might or might not
    benefit performance:
    - Use an exact best-fit allocation policy.
    - Add a bitmap for freelist, allowing empty lists to be skipped with a
      single bit scan.
    Signed-off-by: 's avatarTatsuyuki Ishi <ishitatsuyuki@gmail.com>
    a612ab6f
heap.c 171 KB