Alexandre Julliard wrote:
That's why we have multiple free lists. The code is using the Win95 values now, but there is no reason we couldn't add a few larger values in the HEAP_freeListSizes array, instead of creating a new mechanism.
This still doesn't help us: as Ove points out, we still end up allocating from newly created free blocks even if old blocks would suit us better.
Ove Kaaven wrote:
A new allocator would definitely be a good thing. This one was done the way it is in order to use a compatible memory layout, but it turns out this is not necessary so we could scrap it.
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.
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.
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. It even has Windows code that uses VirtualAlloc to reserve actual memory.
-Gav