20

Google tells me that John McCarthy invented garbage collection, for Lisp in 1959. However, a video on C that I was watching (‘Learn C Programming with Dr. Chuck’, c. 6:40) mentions the lack of a garbage collector and says that when Dennis Richie invented C in 1972, computers were decades away from a garbage collector.

Why would a C video say this if Lisp had one in '59?

3
  • Comments are not for extended discussion; this conversation has been moved to chat.
    – Chenmunka
    Jan 21, 2023 at 9:01
  • I have reverted the edit. I don’t like it either that the question was based on a misreading of what the source said, but distorting the content of the question is even worse. Better just close it. Jan 21, 2023 at 12:32
  • 1
    I don't know why you suppress this edit, @user3840170, because, it was a transcription of the video and helped understand the problem without having to watch it. It didn't distort the question at all. By the way it wasn't a misreading : The text is clear : There are two problems caused by dynamic memory allocation, and cleaning both can be placed under the vocable "garbage collection".
    – Camion
    Feb 1, 2023 at 11:27

4 Answers 4

34

TL;DR:

  • Garbage collection is not a standalone entity, but part of a storage management system.
  • Only languages having dynamic storage objects needs management to handle them.
  • C is neither a storage management system nor does it have dynamic storage objects.
  • Languages like LISP or BASIC do need it.
  • Both of those had it years before C was developed.

Garbage collection is never a standalone 'invention'. It's always tightly coupled with the structures it optimizes and part of the software that manages those structures. Thus it can not be 'invented' as an entity in itself, but only developed as a part of a management of dynamic storage structures. Which means that a language that does not provide such a memory management does not need such a provision.

  • LISP, as a language that is constantly creating, manipulating and destroying (lists of) atoms, does need such management and garbage collection as part of it. Thus it had one almost from the start in 1959.
  • BASIC got dynamic strings (and GC) in 1967 with Dartmouth Fourth Edition
  • C in turn was intended as a very basic, minimalist language, geared toward handling data close to its physical representation. Dynamic storage objects would have been way out of scope. Without them, there was no need for dynamic management and thus of course no need for garbage collection as part of that management either.
24
  • 2
    BBC BASIC had dynamic strings without garbage collection - reassignment used the original memory block if possible and good practice was to allocate the maximum anticipated length to each variable at program startup.
    – grahamj42
    Jan 21, 2023 at 15:08
  • 1
    I disagree. I must be a purist. It is 'manual' memory management in the sense that, at the point at which a reference is overwritten, it can be determined instantly whether the previous referent is still referenced.
    – dave
    Jan 22, 2023 at 14:00
  • 1
    Wut? reference counting definitely is GC - there's nothing "manual" about it in the sense that the programmer does anything. It's got a chapter in the GC handbook. Etc.
    – davidbak
    Jan 22, 2023 at 17:18
  • 4
    BTW, this thread is a good example of why the SE "chat" feature is useless and why it is annoying that moderators here on Retrocomputing where we use comments a lot with a local culture that allows discussion in comments move comments to chat. Nobody looks in chat to see what was discussed already; nobody goes to chat to add additional discussion. Some of the points in this thread were already made in the comments that were moved to chat - some just a few hours after the earlier ones were moved to chat.
    – davidbak
    Jan 22, 2023 at 17:20
  • 1
    @supercat - ok, but I don't exactly get what point you're arguing in favor of?? (though to be honest I'm not sure how bad a problem it is - presumably in a multithreaded code the code author is already providing those memory fences that are required by the language semantics (i.e., memory model) - and then what the GC library needs to provide is hard fences whenever it is about to start screwing around - certainly easier for a stop-the-world collector (maybe only possible for a stop-the-world collector I dunno) and GC is already expensive relative to manual mem mgmt ...)
    – davidbak
    Jan 22, 2023 at 22:25
24

Part of the problem here is the definition of "garbage collection". This is what the video says:

The more difficult problem [than forgetting to free memory] is after a series of calls to malloc() and free() the heap space becomes fragmented and some cleanup is needed. This clean up is called "garbage collection". Efficient memory allocation and garbage collection has been the subject of decades of computer science research. The Java language has build a number of increasingly effective garbage collection approaches over the years.

Kernighan and Ritchie in one simple paragraph define most of the problem as out of scope for the C language. Which makes it a bit challenging for us to make good use of dynamic memory allocation in C - but when we do it properly - it performs very well.

If you are using a language like Java, Python, or PHP, every time you create a new string through concatenation without thinking about memory allocation, remember to appreciate the decades of work by computer scientists that made it easy for you. Kernighan and Ritchie knew "garbage collection" was difficult. So they left it out of the C language and put it into a run-time library.

I think this is a mischaracterisation of what garbage collection is. It's not just the problem of defragmenting the heap, it's also the problem of making sure that memory that is no longer used is returned to the heap. It's true that there has been decades of research into making both of these problems more tractable and making garbage collection faster, but it is not as if there weren't adequate solutions at the time C was invented and it's not as if the defragmentation issue was a new problem even then.

tl;dr I think the video is wrong.

10
  • 3
    Thanks for putting in the effort to actually listen to the video/transcribe it. You're right: the video is on the wrong track - possibly the guy who wrote it was confused. In fact there are plenty of heap algorithms that "defragment" the heap coalescing returned items (using various techniques). (Up to a point since they can't move allocated things around.) "Buddy allocation" was definitely known when C was invented, probably others as well.
    – davidbak
    Jan 20, 2023 at 15:27
  • 6
    The video seems to be just a recording of someone reading from <cc4e.com/book/chap00.md> (the password is 42; yay for gratuitously breaking the Wayback Machine!) Jan 20, 2023 at 15:27
  • Certainly for nearly 30 years the gnu libc implementation of malloc and free have been defragmenting by coalescing and allocating smartly. The difficulty presented by C is at the sweep stage: C doesn't mandate how references are stored or flag cells as containing pointers or type except very loosely. There is also a very common possibility of uninitialised junk (especially historically). This means you can never really know in C if something is a reference or if you have all the references. With well-behaved programmers you can use Boehm, etc, but it's not perfect.
    – Dan
    Jan 21, 2023 at 2:09
  • 2
    I think garbage collection is not about defragmenting the heap at all. Garbage collection is what it says on the tin: collecting (freeing) garbage (unreachable objects). Many garbage collection methods also defragment the surviving objects, but many don't (e.g. refcounting GC, the Boehm GC, and CPython's cycle collector) and they still count as garbage collection.
    – benrg
    Jan 21, 2023 at 16:49
  • 1
    @benrg - are you implying the 'expert' in the video isn't? ;-)
    – dave
    Jan 21, 2023 at 18:01
0

It is possible and in fact not particularly hard to have a fully conformant C implementation that has defragmentable heap. Many implementations are possible, and some were even supported by widely available consumer hardware.

On x86, 16-bit C code built in large mode (multiple code and data segments, objects limited to 64kb length) could be made to run in 286 protected mode directly.

With changes only to the C runtime library, but not compiler itself, the segments could be used as identifiers either for memory arenas (for small objects), or for objects themselves (for larger objects that each had their own "arena"). The allocator maintained a couple arenas for "small" objects, and anything that didn't fit in those got its own segment descriptor.

Windows 3.x couldn't quite do it that way, since there was no segment descriptor indirection on 8086. Thus, Windows heap required explicit handles and object pinning in place of indirection. In any case, the segment descriptor cache misses and churn were expensive enough that it was better that Windows did it this way back then, as the performance hit in some cases was substantial.

If you could trade off some performance for not running out of heap due to fragmentation, then using segment descriptors as an indirection layer to allow moving objects around in the heap was a reasonable idea. It also facilitated paging infrequently used objects to disk, even on 286. There was a small software shop somewhere that made a substitute runtime for Borland products (Pascal and C) that did memory allocation this way on 286, paging included. It was a niche product as far as I remember, and I have no recollection of how it was called, who made it, etc. :(

1
  • This is true, but I don't think it answers the question, since everything you mentioned is from the 80s.
    – benrg
    Jan 21, 2023 at 16:50
0

This is not an answer but complementary information :

There are two different concept which get called "garbage collection".

  • The one we are used in languages like java which means automatic release of unreferenced dynamically allocated zones. This was invented because people tend to forget to manually released, and because in very complex programs, it might be hard to figure out what is not used anymore.
  • And The defragmentation of the heap which was already needed in language like basic which had no explicit dynamic allocation, but used resizable objects.

The point is that fragmentation occurred in manual dynamic allocation too, which lead the designers of mac OSes, to use what they called handlers instead of pointers, in which what was given in allocation was not the address of a memory space, but the address of a system managed unique pointer. That way, the system was able to defragment the memory by moving the data without the program having to know it.

2
  • Does anyone apart from the author of that book refer to heap defragmentation alone as ‘garbage collection’? Jan 25, 2023 at 19:16
  • I don't know what book you're talking about, but for reference, in the old "Locomotive Basic" used in Amstrad CPC464/664/6128, the massive use of string could cause the start of a process which was called garbage collection in the documentation (it was the first time in my life I met this vocable), and could freeze the machine for a very long time (could take more than 10-20 minutes).
    – Camion
    Feb 1, 2023 at 10:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .