On Wed, 10 Oct 2001, Gavriel State wrote:
Well, after looking at some allocator algorithms, it seems to me there's no reason to change neither the bin sizes nor the data structures. We just have to change the free block selection algorithm - from my reading of the code, right now it seems to always choose the *newest* (most recently added) free block that's big enough. By changing it to always choose the *oldest* free block instead, we'd already have a huge improvement. (That's essentially the effect of Gav's patch, but only for big blocks, but I suspect that could safely be done for *all* block sizes)
Actually, we originally had it pushing all new free blocks (regardless of size) to the end. Our fear though was that doing that would cause slowdowns as it would lengthen the free-block search time. By doing it only for larger blocks, small block allocations should be faster.
But the free list bins Wine's allocator uses (HEAP_freeListSizes) would have taken care of that, wouldn't it?
There are a variety of other issues that are important to consider with an allocator though: locality of reference (memory blocks allocated together are likely to be used together, and we should therefore try to allocate them near one another to reduce paging time); speedy allocation of small blocks; best-fit efficiency (ie: prefer to take a free block that's close to the size we're looking for rather than split a bigger block, etc.
Those issues are all part of the "free block selection algorithm" I talked about above. We just need to change the algorithm used there; its effect would be the same as plugging in a whole new allocator.
I've had a brief look at the code referenced by Adam Moss (found at http://g.oswego.edu/dl/html/malloc.html), and it looks like it would be a vast improvement over Wine's current Heap manager.
Not that much. Wine's allocator already implements the *features* of that allocator (boundary tags, bins), it just doesn't implement all the *strategies* used for selecting which free block to allocate memory from (though the only big things we lack there is "best fit" and "wilderness preservation", the latter of which Alexandre talked about). We just need to make sure Wine's free block selection routine uses the same strategies as this allocator, and we'd get exactly the same performance as that allocator, but without replacing the whole thing and sacrificing the compatibility we have or introducing new bugs.