Nasty Evil Memory Fragmentation fix

[Ove Kaaven]

On 10 Oct 2001, Alexandre Julliard wrote:

> Gavriel State <gav at transgaming.com> writes:
> 
> > We ended up creating a new subheap every time one of these larger 
> > blocks came along.  The new space from the subheap then went to 
> > the top of the freelist, so all the small allocations then filled 
> > it up until the next large block allocation.  IE: We never got a 
> > chance to reuse freed blocks in older subheaps - at least not 
> > very well.  
> 
> 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.
> 
> > Despite the workaround, we're still not too pleased with the current
> > heap allocator.  It's quite slow, and still not as efficient as 
> > it could be.  It would probably be worth the effort to integrate
> > a new allocator - anyone know if there's a high-quality Wine-license-
> > compatible allocator out there?
> 
> 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)

(Another improvement could be to search for a free block of the exact
requested size before deciding on a much bigger free block, but I don't
think that's quite as important as making sure we use up old free blocks
before abusing new ones.)