Faster Virtual Method Dispatch

[Craig Black]

"James Dunne" <james.jdunne at gmail.com> wrote in message 
news:e2pjk0$96l$1 at digitaldaemon.com...
> Craig Black wrote:
>> Good idea!  I suppose that every time you allocate memory you must always 
>> specify a parent node in the hierarchy.  This requires a little more 
>> thought than GC, because you have to consider how to organize the 
>> hierarchy so that it will be easy to free memory relating to a given task 
>> once the task is done.  Such a system is would be very fast, and with 
>> just a small amount of preparation, memory leaks are completely 
>> eliminated.  It could potentially be faster than traditional memory 
>> management, because you don't necessarily have to call free on every 
>> block of memory.  Rather, one free could free the entire hierarchy, or a 
>> large sub-hierarchy.  Have you experienced any drawbacks?  Does this 
>> approach work well with exceptions? threads?  Also, what kind of data 
>> structure do you use for this hierarchy?
>>
>> -Craig
>
> Holy geez... Yes it is a good idea, but alas I cannot take credit for it. 
> You point out all the benefits that I've gotten from it so far quite 
> accurately. :)
>
> I've only used it with my compiler implementation written in C, so I'll 
> discuss my experience relating to that, if that's okay with you...
>
> Drawbacks?  Only that you have to give it that much more thought about 
> what to parent to what...  There's no serious runtime penalty - it just 
> adds a pointer to the parent's list of children, but that cost is tacked 
> on to allocating memory in general.
>
> Exceptions?  I'm coding in C, and I wrote my own pseudo-exception model, 
> which makes use of that memory model so I don't even leak memory from 
> exceptions... a good thing!
>
> Threads?  Haven't gotten there yet, but I plan to design my threads to be 
> completely independent of each other.  It's easy to do when you're 
> lexing/parsing/analyzing different source files at the same time.  Only 
> need to synchronize when each pass is completed.  I'll look into 
> concurrency issues in the allocator code when I get to it.
>
> The data structure is a simple list of child pointers and a single parent 
> pointer for each memory block.  Linked lists.  The code still relies, of 
> course, on malloc and free to actually get the memory in the first place.

Of coarse it does.  Along those lines ... I've been thinking of an 
optimization for this.  Couldn't you make come of your parent nodes an 
allocators, so that all of their children get their memory from it?  This 
way, you could allocate large blocks of memory, and could cut down on your 
calls to malloc and free by an order of magnitude.  Obviously you would have 
to choose what nodes in the hierarchy become allocators such that the least 
number of CRT calls would be made.

-Craig