James Dunne wrote:
> 
> I should also mention that my compiler implementation makes use of context structures, so every memory block that the compiler will allocate is somehow parented to that context structure.  So when the compile job is complete, free the context structure and all the memory goes away.
> 

What kinda compiler?

James Dunne wrote:

> Your example is having two trees _point_ to data within each other.  The original data is still _owned_ by the original tree which the data resides in.  You wouldn't be swapping ownership of the data like you're talking about.  In this system, when memory is allocated it is assigned an owner and that ownership does not ever change.  So the system resembles a tree (one parent only), not a directed graph.

But when this happens in the general case, I can't delete *any* of the trees.

Dave wrote:
> James Dunne wrote:
> 
>>
>> I should also mention that my compiler implementation makes use of context structures, so every memory block that the compiler will allocate is somehow parented to that context structure.  So when the compile job is complete, free the context structure and all the memory goes away.
>>
> 
> What kinda compiler?

My own research language named Iris.  I'd like to keep it under the radar for now.  You can read about it in my monthly rants on http://iris-design-log.blogspot.com/.

-- 
Regards,
James Dunne

Walter Bright wrote:
> James Dunne wrote:
> 
>> Your example is having two trees _point_ to data within each other.  The original data is still _owned_ by the original tree which the data resides in.  You wouldn't be swapping ownership of the data like you're talking about.  In this system, when memory is allocated it is assigned an owner and that ownership does not ever change.  So the system resembles a tree (one parent only), not a directed graph.
> 
> 
> But when this happens in the general case, I can't delete *any* of the trees.

When are you trying to delete one of these trees?

To which 'tree' are you referring, the data structure tree or the hierarchical memory manager's tree?

-- 
Regards,
James Dunne

Walter Bright wrote:
> James Dunne wrote:
> 
>> Can you provide me a few legitimate examples of when you won't know what to free and when to free it?  I'm having a tough time coming up with examples on my own...
> 
> 
> One example that has plagued me in the past is having two distinct tree data structures, and it becomes necessary for a node in one tree to refer to data in the other.
> 
> Or when you have a third data structure, and you need to point to data in one or the other or both of the first two trees.
> 
> A typical example of that is symbol tables inside the compiler. In the DMD front end (which is garbage collected) the data has all kinds of cross-connections in it.
> 
> I.e. the problem crops up when the data in memory just doesn't fit into a strictly heirarcical format.

If you parent the memory you're creating in the tree data structures to a structure that is higher up the chain than both tree data structures, then the data doesn't get lost simply because you freed the data structure that held references to that memory.

-- 
Regards,
James Dunne

James Dunne wrote:
> Walter Bright wrote:
>> James Dunne wrote:
>>
>>> Your example is having two trees _point_ to data within each other.  The original data is still _owned_ by the original tree which the data resides in.  You wouldn't be swapping ownership of the data like you're talking about.  In this system, when memory is allocated it is assigned an owner and that ownership does not ever change.  So the system resembles a tree (one parent only), not a directed graph.
>>
>>
>> But when this happens in the general case, I can't delete *any* of the trees.
> 
> When are you trying to delete one of these trees?

I could wait until the program finishes before deleting anything, but that isn't memory management.

> To which 'tree' are you referring, the data structure tree or the hierarchical memory manager's tree?

The nested symbol table of the local scope of a function, for example.

James Dunne wrote:
> Walter Bright wrote:
>> I.e. the problem crops up when the data in memory just doesn't fit into a strictly heirarcical format.
> If you parent the memory you're creating in the tree data structures to a structure that is higher up the chain than both tree data structures, then the data doesn't get lost simply because you freed the data structure that held references to that memory.

I've designed data structures around the memory management requirement for keeping a sole 'parent' around for it that can free it. But I'd rather design data structures around how they are used instead.

For example, if I have an associative array of strings, I can stuff any old string into it - even static strings - without having to worry about who 'owns' those strings. It's quite liberating <g>.

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

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.

-- 
Regards,
James Dunne

"James Dunne" <james.jdunne@gmail.com> wrote in message news:e2pjk0$96l$1@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