On Sunday 04 November 2001 03:36 pm, Benoit Cerrina wrote: > > While the PMC structures themselves don't move (no real need--there of > > fixed size so you can't fragment your allocation pool, though it makes > > Sorry can you expand on this. I don't see the relation between the data > being fixed size and the memory not becomming fragmented.
Fixed sized memory objects can be "records" of an array. Thus you can use an "arena" scheme (also known as a slab, or indexed chunks). You store a linked list of free'd elements as with most memory allocators, but: a) You're garunteed a "best fit algorithm"; all requests are of the exactly needed size. b) When you free, you don't have to consolidate, since subsequent memory requests will also need this exact same size. Fragmentation is when you mix big and small allocations, while the life-times of the objects are random. When you alloc something big, then another thing big, then free the first, then alloc something small (which fragments the original big chunk into a small chunk and a remainder), then you can't allocate another big chunk without growing the heap, even though 99% of what you need is available - The fragmentation makes this region useless. And this is just with two memory sizes. Real memory systems have an infinite number of memory sizes. Theoretically you reuse the medium sized chunk, but then you develop non-optimal fitting strategies which are O(n) (and you regularly achieve millions of objects). In general, good algorithms don't allow arbitrary sized allocations, and do at least SOME rounding up to minimize fragmentation. Most additionally use some sort of arena as with the above. > > > generational collection easier to some extent) the data pointed to by the > > PMC can. That's the bit that moves. > > > > Dan > > Well one of the reasons of moving the data is so you can use a trivial > stack like > allocator. If you don't move the PMC you won't be able to. > Benoit Yeah, I'm writing something up on that. -Michael
