Please see below ...
Joe.
[Joe da Silva]
Yes, I seem to recall this matter being discussed in Pemberton and Martin, wrt. the P4 compiler, although I can't recall the details ( I'm trying to learn this stuff, but it's "heavy going" and spare time is scarce :-/ ).
[Joe da Silva]
An interesting idea - I like your approach.
[Joe da Silva]
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);
da Silva, Joe wrote:
I think Joe is right. Maintaining the pool of free memory is another (and I think much easier) step.
But you have the extra cost of an additional pointer (memory) and indirection (runtime).
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.
Frank
On Wed, 13 Feb 2002, Frank Heckenbach wrote:
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.
Very true. It looks like what you might gain isn't worth the added complexity.
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
Russell Whitaker wrote:
Indeed -- and inefficient (in the worst case, it adds a factor of O(n) with n being the number of fragments). I remember that BP's memory manager worked this way and you could see the slowdown with a suitable test program.
However, modern memory managers (as found on most systems) are a little more clever. E.g., they sort the fragments by size to find a best match without long searching. Surely they use balanced trees rather than linked lists if necessary (i.e., if searching might occur). Another common technique is to divide a page of memory into fragments of a size that is a power of 2 and manage them using an allocation table much like a file system does (well, a modern file system, not exactly Dos FAT).
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?
For the compiler itself. GPC applications by default use the normal libc memory manager, but there are in fact several ways to replace it. The GPC unit provides some hooks. Furthermore, the libc routines can be overriden, e.g. by alternative memory management libraries. Such libraries exist (some of them doing GC, some for other purposes), and generally they can be used in GPC programs by just linking them. But that's up to the programmer's choice, of course.
As I said, the fragmentation is not the main issue for GPC, but in fact the memory leaking problem. I.e., with such complex structures it's difficult to ensure that all memory is deallocated at the correct time, and if it turns out to be more difficult than doing a GC, it might be advantegeous to let the memory "leak" intentionally and let the GC clean up.
Frank
-
da Silva, Joe -
Frank Heckenbach -
Russell Whitaker