1. 12 Apr, 2023 3 commits
    • Piotr Caban's avatar
      e9da35db
    • Piotr Caban's avatar
      5c3b412c
    • 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
  2. 11 Apr, 2023 37 commits