Gavriel State gav@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.
On 10 Oct 2001, Alexandre Julliard wrote:
Gavriel State gav@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.)
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
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.
-
Alexandre Julliard -
Gavriel State -
Ove Kaaven