Russell Whitaker 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.
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