By: Wilco (Wilco.Dijkstra.delete@this.ntlworld.com), November 7, 2006 4:34 pm
Room: Moderated Discussions
Gabriele Svelto (gabriele.svelto@gmail.com) on 11/7/06 wrote:
---------------------------
>Wilco (Wilco.Dijkstra@ntlworld.com) on 11/6/06 wrote:
>---------------------------
>Fragmentation is bounded BTW, objects
>are allocated on a per-page basis up to a maximum threshold of 256-bytes per object,
>this guarantees a maximum per-page internal fragementation of 1/16 with 4 KiB page-size
>and the largest sizes, for the average case internal fragmentation is very low.
>Larger objects are allocated with traditional free-list based methods.
There is also external fragmentation. Suppose you allocate 10000 4-byte blocks. Free them, and allocate 5000 8-byte blocks. Do you reuse the pages that were used for the 4-byte blocks? My guess is not. It takes only one allocated block in a page to keep it from being used for any other size. Ie. worst case fragmentation is in the order of 1000 times overhead...
You always have some form of fragmentation of course, the goal is to minimise it as much as possible. Some freelist implementations suffer from the same issue - merging freed blocks with adjacent free blocks is essential in a traditional heap implementation.
>>GCC uses a similar scheme (with GC) and it turned out to be a performance disaster.
>
>I didn't knew that GCC used a segregated allocation scheme, can you point me to some info?
GCC uses a conservative garbage collector. I think it actually has 2 of them - as if just one is not complex enough :-). To be less conservative they allocate structures of the same type together so that GC can find the pointers. However the allocation policy means that different sized structures are allocated all over the place causing a slowdown due to extra cache and TLB misses. I believe the future goal is to use a region based allocator and get rid of GC (it makes no sense in a compiler).
There is little documentation about it, most info is in the discussion lists, but Google found this: http://gcc.gnu.org/onlinedocs/gcc/Garbage-Collection.html
>>The thing is with a small change in the malloc interface you could avoid the per-block
>>overhead without extra complexity.
>
>Yeah, segregated allocators can do wonders on VMs were you have full type/alignment
>information and you can segregate by type instead of size with significantly less tricks.
What I was referring to was using free(p, size) rather than free(p) which would allow to avoid the per-block overhead in existing heap implementations. An even better interface uses type and alignment indeed. In my region based allocator you write Type *p = ALLOC(region, Type) and it allocates a correctly aligned block using pointer increment (its all inlined of course, so we're talking a few cycles per allocation).
Segregation is a very bad idea, the key is to allocate objects which are used together next to each other, not separate them. Often that means you can free them all in one go as well, making deallocation a nop.
Wilco
---------------------------
>Wilco (Wilco.Dijkstra@ntlworld.com) on 11/6/06 wrote:
>---------------------------
>Fragmentation is bounded BTW, objects
>are allocated on a per-page basis up to a maximum threshold of 256-bytes per object,
>this guarantees a maximum per-page internal fragementation of 1/16 with 4 KiB page-size
>and the largest sizes, for the average case internal fragmentation is very low.
>Larger objects are allocated with traditional free-list based methods.
There is also external fragmentation. Suppose you allocate 10000 4-byte blocks. Free them, and allocate 5000 8-byte blocks. Do you reuse the pages that were used for the 4-byte blocks? My guess is not. It takes only one allocated block in a page to keep it from being used for any other size. Ie. worst case fragmentation is in the order of 1000 times overhead...
You always have some form of fragmentation of course, the goal is to minimise it as much as possible. Some freelist implementations suffer from the same issue - merging freed blocks with adjacent free blocks is essential in a traditional heap implementation.
>>GCC uses a similar scheme (with GC) and it turned out to be a performance disaster.
>
>I didn't knew that GCC used a segregated allocation scheme, can you point me to some info?
GCC uses a conservative garbage collector. I think it actually has 2 of them - as if just one is not complex enough :-). To be less conservative they allocate structures of the same type together so that GC can find the pointers. However the allocation policy means that different sized structures are allocated all over the place causing a slowdown due to extra cache and TLB misses. I believe the future goal is to use a region based allocator and get rid of GC (it makes no sense in a compiler).
There is little documentation about it, most info is in the discussion lists, but Google found this: http://gcc.gnu.org/onlinedocs/gcc/Garbage-Collection.html
>>The thing is with a small change in the malloc interface you could avoid the per-block
>>overhead without extra complexity.
>
>Yeah, segregated allocators can do wonders on VMs were you have full type/alignment
>information and you can segregate by type instead of size with significantly less tricks.
What I was referring to was using free(p, size) rather than free(p) which would allow to avoid the per-block overhead in existing heap implementations. An even better interface uses type and alignment indeed. In my region based allocator you write Type *p = ALLOC(region, Type) and it allocates a correctly aligned block using pointer increment (its all inlined of course, so we're talking a few cycles per allocation).
Segregation is a very bad idea, the key is to allocate objects which are used together next to each other, not separate them. Often that means you can free them all in one go as well, making deallocation a nop.
Wilco
