On Wed, 13 Feb 2002, Frank Heckenbach wrote:
da Silva, Joe wrote:
Russell Whitaker wrote:
Perhaps I'm missing something. I thought the purpose of GC was to maintain a list of free memory. Thus GC doesn't care how you access a block, it cares only if it is free or not. A simple GC would recognize adjacent free blocks and combine them into a larger single block.
Well, I though that's what "new" and "dispose" do. As I understand it, GC's purpose is to de-allocate memory blocks that no longer are referenced by pointers but that the programmer has forgotten to de-allocate himself (or herself). For example,
new(apointertosomething); ..... {no dispose} new(apointertosomething);
That's a memory leak. Suppose you don't have a leak but you do have a simple memory allocation scheme where new always allocates from the end of the heap. Say the program allocates ten items, 1 thru 10, and then disposes nos. 7 and 10. Since 10 is at the end of the heap it gets added back to the heap but not 7 at this time because 8 and 9 are in the way. This is not a memory leak. Now if the program asks new for a block of memory it passes up 7 because its not at the end of the heap. ( I'm using "end of heap" here to mean "the end of the unallocated portion of the heap").
Well it works but you could design an application that stair-steps its way from one end of the heap to the other and crashes.
The next level of complexity is a linked list of free memory. Now new traverses the list looking for a suitable block. If what it finds is too big then it takes what it needs and leaves the rest on the list.
This gets rid of the stair-step problem. However if a program runs long enough there is a tendency to have an allocated bock, a free block, an allocated block, etc., which is a tad wasteful.
I think Joe is right. Maintaining the pool of free memory is another (and I think much easier) step.
A more complex scheme could move already allocated blocks to make a large free block when one is needed. This last might be implemented by adding a transparent level of indirection. Programmer thinks his pointer p is pointing to something when in reality it is pointing to an internal pointer pointing to the something. Thus when the block gets moved only one pointer needs to be changed.
But you have the extra cost of an additional pointer (memory) and indirection (runtime).
Very true. It looks like what you might gain isn't worth the added complexity.
However, I don't think that's a major issue for GCC at all since most of the allocations are done for "tree nodes" which have a small number of different constant sizes, so the storage of most of the deallocated nodes can later be re-used for nodes of exactly the same size.
True for gcc (& gpc) itself, most likely not true for the programs it creates. So is the GC intended for the compiler, the applications, or both?
Russ