Fixed-Size Allocations For Parrot
02 Aug 2009Parrot has a dirty little secret. Actually, it's not much of a secret because I've mentioned it on my blog here before (although I can't find link right now). The problem is that Parrot, despite the fact that it has an integrated GC mechanism, still relies on malloc/free for most of it's allocations. The only things that aren't allocated this way are the "PObjs": PMC, and STRING structures mostly. However, just about every single PMC allocation involves a malloc anyway to allocate the structure of attribute storage used by that PMC. These structures are typically allocated manually using malloc in the PMC init VTABLE, and manually deallocated in the destroy VTABLE.
In TT #895 NotFound started working on a task that I've been thinking of for a while: Fix the GC so it could automatically allocate and deallocate these attributes structures, to help prevent the myriad of memory leak problems that have arisen from their misuse. Plus, we can get rid of a lot of unnecessary code if we do all the allocations in one place. His idea is to store the necessary size of the attributes structure in the VTABLE structure, and then use that information in the GC to automatically allocate and deallocate these structres. We would allocate the storage directly before the init VTABLE was called, and deallocate the storage directly after the destroy VTABLE was called. Plus, we can flag certain PMC types that use this mechanism, so the transition can be gradual and pain-free. Quite a good plan!
Now I read over that ticket and thought to myself "Self, this would be the perfect opportunity to remove malloc/free from the picture", and so it is! By having all the allocations and deallocations happen in one place, it's painfully easy to abstract that away behind a new GC interface and implement our own fixed-size structure allocator. Last night, this is exactly what I did and Parrot now has an (experimental) fixed-size allocator that's designed to replace many instances of malloc/free not only in the PMC management routines, but also in many other places throughout Parrot. The only requirements that my allocator has that malloc/free doesn't is that you must specify the object size when you free it, and you can't currently resize the buffer once you've allocated it (at least not easily). The new fixed-size allocator isn't currently used anywhere in Parrot, but it's available for testing and should be able to be used in many places on an experimental basis.
The new fixed-size allocator is very simple, and is based in part on our existing PObj allocation routines. We maintain an array of pointers to pools. Each pool contains a linked list of arenas. Each arena contains a large storage space devoted to holding objects of a fixed size. All items in the pool that are free are organized into a linked list called the "free list". When we need a new object of that size, we either take the item on the top of the free list, or else we allocate a new arena, add all the new items to the free list, and then take the item on the top of the free list. On deallocation, we take the deallocated item and simply push it back onto the top of the list.
Using the new allocator is very easy: To allocate a new attributes structure for a PMC, use the new
Parrot_gc_allocate_pmc_attributes function. To free it again, use Parrot_gc_free_pmc_attributes instead. Likewise, to allocate a new arbitrary data structure, use Parrot_gc_allocate_fixed_size_storage and Parrot_gc_free_fixed_size_storage. If you're interested to see how Parrot's memory allocation works in general, these functions and the supporting functions that they call are very instructive.Parrot's interpreter structure maintains an array of pointers to the fixed-sized pools, and the array is resized to support larger allocations. This system works well for small-sized allocations, but does not work well for large allocations. There are some things I think I can do to improve it's efficiency for larger-sized allocations as well, but in general I think it's good right now to limit this mechanism to small structures (as opposed to large buffers).
The GC doesn't do any kind of management for these items, it simply allocates and deallocates them in a very simple manner. It does not compact them, and does not free unused arenas back to the system like it probably should. Of course the primary GC core doesn't do this either with it's PObj storage spaces, so I don't feel so bad. When we finally get Parrot fixed up to support a compacting garbage collector for the PObj stuff, we should also be able to make the fixed-size storage use the same mechanism.
So we've got a new tool to play with in Parrot's memory management toolbox, and I hope that we like it and decide to keep it around for a while. There are plenty of ways to improve this new allocator, make it more efficient, and tune it to behave properly for Parrot's needs. However, I think we're going to see immediate improvements over malloc/free, and I'll start posting benchmark numbers as I get them.
This entry was originally posted on Blogger and was automatically converted. There may be some broken links and other errors due to the conversion. Please let me know about any serious problems.