Nasty Evil Memory Fragmentation fix

[Gavriel State]

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

-- 
Gavriel State, CEO
TransGaming Technologies Inc.
http://www.transgaming.com
gav at transgaming.com