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.
For the benchmark, this drastically improves initial shader loading performance in Overwatch 2. In this workload 78k shaders are passed to DXVK for DXBC -> SPIRV translation, and for each shader a few allocation happens in the 4K – 100K range for the staging buffer.
Before this patch, malloc consisted a whooping 43% of overhead. The overhead with log-linear bucketing is drastically lower, resulting in a ~2x improvement in loading time.
Overhead for each `FREE_LIST_LINEAR_BITS` is as below: - 0: 7.7% - 1: 2.9% - 2: 1.3% - 3: 0.6%
Since performance seems to scale linearly with increase in buckets (up to the point I have tested), I've opted for 3 (8 buckets per doubling) in the current revision of patch.
Signed-off-by: Tatsuyuki Ishi ishitatsuyuki@gmail.com
-- v7: ntdll: Use log-linear bucketing for free lists.