• 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
Name
Last commit
Last update
dlls Loading commit data...
documentation Loading commit data...
fonts Loading commit data...
include Loading commit data...
libs Loading commit data...
loader Loading commit data...
nls Loading commit data...
po Loading commit data...
programs Loading commit data...
server Loading commit data...
tools Loading commit data...
.editorconfig Loading commit data...
.gitlab-ci.yml Loading commit data...
.mailmap Loading commit data...
ANNOUNCE Loading commit data...
AUTHORS Loading commit data...
COPYING.LIB Loading commit data...
LICENSE Loading commit data...
LICENSE.OLD Loading commit data...
MAINTAINERS Loading commit data...
README Loading commit data...
VERSION Loading commit data...
aclocal.m4 Loading commit data...
configure Loading commit data...
configure.ac Loading commit data...