Garbage Collection

A fascinating subject. Any particularly good garbage collectors lains? Suggestions on best strategies for particular use-cases?

Mercury is supposed to be one of the first languages with a static garbage collector. (I'm not sure if it's in the current implementation.) I didn't have the background to understand the paper or the perseverance to gain that background, but it might be interesting for someone else here to look at. https://mercurylang.org/documentation/papers/CW2004_03_mazur.pdf

>>914 here, I've been meaning to read this

I know the trend these days is for parallel & concurrent non-blocking super-low-latency garbage collectors, but I do have a soft spot for the nice and simple collectors of yore. "One pass real-time generational mark-sweep garbage collection" (attached) is a really nice collector that was once used in Erlang, making use of the immutability of Erlang objects to greatly simplify the algorithm. The paper is a delight to read, and it's so simple to implement.

http://journal.stuffwithstuff.com/2013/12/08/babys-first-garbage-collector/ Implement a garbage collector today! I'm playing with the mark-and-sweep garbage collector above. I want to allow my language to bootstrap without relying on any system calls such as mmap, so I allocated a huge object array statically and had the collector manage it. This way, the kernel will lay out the memory when it's loading the implementation program. The allocation can't fail, but I can't ever free that memory either. I think this is acceptable. It also means there's an upper bound on available memory during language bootstrapping. 1st thing my language will do is lift that limitation by implementing system calls within the language itself. I'm in the process of designing an interface to the garbage collector so that I can mmap pages from within the language and tell it to use that memory for object allocation in addition to the static object array. My goal is to make a language implementation with zero C dependencies; not even libc.

The luaJIT GC is fantastically complex. http://wiki.luajit.org/New-Garbage-Collector

>>1702 Very interesting, do you have a repo ?

>>914 Total noob here. What is even garbage collection ?

>>3196 The way one of my professors described it. Probably not the best example, but one that helped me understand it a bit: >Have you ever used the new keyword in C++? Yes >How about Java? Yes >Have you used the delete operator in C++? Yes >How about in Java? Nope And that's essentially garbage collection; allowing you to not focus on memory allocation/de-allocation. Here's an article that might clear things up further: http://www.geeksforgeeks.org/garbage-collection-java/

>>914 Real time garbage collection is an interesting topic, but I don't have any resources on this to contribute. >>3196 >>3197 Garbage collection is distinct from automatic memory management. When variables local to a function are created and destroyed automatically, that simply frees some effort and clearly follows a stack discipline. Garbage collection generally permits the illusion that memory is infinite; early garbage collection algorithms merely allowed allocations until this failed due to a filled memory and then simply used rules to determine what was considered still in use and so would be kept, allowing the remaining space to be used for further allocations. Alternatively, garbage collection allows the programmer to entirely ignore the memory requirements of the program being written, in all or many cases. Automatic memory management can handle complex behaviors without qualifying as garbage collection. It seems sufficient to tell you that when objects are being traversed and those are being traversed as well, until bedrock is hit, in order to determine memory recollection, then that is closer to garbage collection than basic automatic memory management. It also seems important to mention that a good garbage collection scheme prevents memory leaks from being created, although this also applies to automatic memory management, but to do so for behaviors garbage collectors must handle is far more intense. With this written, it's noteworthy than garbage collection schemes can and do make good use of automatic memory management schemes, such as stacks for local variables, as this is far more efficient than treating such as any other object. I do have a resource related to this; it's a very pleasant read written by RMS and is attached to my post; the title is Phantom Stacks: If You Look Too Hard, They Aren't There . The gist is that stacks are, of course, useful for local data, but Lisp allows local data to escape and persist, violating the stack discipline, but stacks are necessary for efficiency and so phantom stacks are a solution to this problem. Here's, perhaps, the most important and interesting paragraph: >In addition, since the stack's contents look like part of the heap, we have the option of deciding at any time to call it part of the heap. We can use the stack area as a stack for as long as it is convenient. If we run into a snag and can't see how to keep using it as a stack, we can do what the CIA does when its agent is caught: we can pretend it was never a stack at all, and say that all or part of what used to be a stack is now just part of the heap. This is how we deal with the embarassing infrequent call to FUNCTION that requires us to save all the data in the stack indefinitely. For an interesting and exemplary case of automatic memory management, I'll mention the APL language, where a great deal of potentially large array data is created and destroyed often. There are many schemes I've considered and have read of that allow this to be mitigated, but it's not entirely avoidable. All data in an APL system is either immediately discarded as intermediate garbage after an operation, saved to a variable, displayed to the user, or explicitly created or destroyed, although this last operation is very uncommon and unnecessary. It's notable that APL doesn't have closures, functions as manipulated data, and other aspects Lisp has; programs can be manipulated, but must be manipulated as a text array that can later be turned into a function. This automatic memory management scheme is simple and I don't believe I've done its beauty justice here, so I encourage you to do your own investigation. The case of circular structures keeping themselves alive, along with cases such as hash tables stored in closures storing functions storing other functions and so on simply doesn't exist in this language, which is a useful heuristic for distinguishing these schemes from garbage collection.

This might sound naive, but when do we run garbage collection? How do we make sure that the stack isn't in an inconsistent state (e.g. only half of an object was copied over) when the garbage collector kicks in? Of course we can just always run the collector from within the allocation function but that wouldn't work for real-time collectors that need to keep a constant rhythm of collection. >>1702 >The allocation can't fail, but I can't ever free that memory either. Did you take look at compacting garbage collectors? Cheney's two-space collector is particularly easy to implement. You split your heap in two and each gc run copy all objects you can reach from one side to the other while updating pointers. A cool thing about it is that the heap you are moving your objects to acts as a queue so the algorithm doesn't need recursion. And if instead of moving objects back and forth you move them to another, less rarely collected heap, you've got a generational gc (watch our for intergenerational pointers though). >>1291 It's crazy how immutability can make things so simple.

http://journal.stuffwithstuff.com/2013/12/08/babys-first-garbage-collector/ Really simple garbage collector tutorial for those who like to learn by doing. For my language, I started with this and it worked very nicely. I'm now customizing it, making jt accept memory blocks for use as additional space instead of allocating memory by itself. This allows me to boot the language with a static array of objects pre-allocated in the program image; the GC even reuses that space.

I have aspirations to create my own language someday, yet can't justify garbage collection. Does anyone else feel similarly? It's true that more advanced garbage collectors enable configuration, manual memory management that doesn't violate semantics, exclusion for immortal data, and other very nice features, but no language I use offers quite this and I'm inclined to believe that a combination of manual, automated, and garbage collecting memory management would be best for a language that doesn't want to inherently tie itself to a specific algorithm for any of this. Garbage collection is certainly nice, but I'm supposing I'm describing more customizability and play than I'm used to. I use Common Lisp and, unfortunately, the garbage collector is an opaque design that portable programs have no control over and more control over management is mostly reduced to declarations of object lifespan that can be ignored and allocating collections of objects to use like a free list, yet exclusion and other nice features are not available to the portable Common Lisper. I suppose there's simply a perverse obsession with control over minute details.

>>7029 D's handling of the GC is quite nice with respect to managing when it runs and such.

>>7029 >portable Found your problem. In many ways, Common Lisp is like C: poorly-defined by some standards body, plenty of people utterly obsessed with standards compliance as if it mattered or made life easier for anyone and lots of implementations that set themselves apart through their non-standard features. Your post is full of contradictions: you want to use the shiny garbage collectors that do exactly what you want but then you realize it's not standardized and therefore you can't rely on it. That's complete and utter rubbish. Just forget about portability, it's overrated. Choose your platform and use it to the fullest. If no implementation exists, patch it or make your own.

>>7032 >Found your problem. In many ways, Common Lisp is like C: poorly-defined by some standards body, plenty of people utterly obsessed with standards compliance as if it mattered or made life easier for anyone and lots of implementations that set themselves apart through their non-standard features. Common Lisp is much better defined than C. Much of what is undefined amounts to whether structures are copied or not when being returned and there's not much that isn't specified that can't be implemented in the language. Many libraries, including one I've written, simply collect functionality that's not standard under a consistent interface. >Your post is full of contradictions: you want to use the shiny garbage collectors that do exactly what you want but then you realize it's not standardized and therefore you can't rely on it. That's complete and utter rubbish. Just forget about portability, it's overrated. Choose your platform and use it to the fullest. If no implementation exists, patch it or make your own. I agree, in part, but that's simply not how I prefer to write Common Lisp; I always try to write my programs as portably as possible, if perfectly portable isn't possible.

>>7032 >people utterly obsessed with standards compliance as if it mattered or made life easier for anyone Imagine Python being used to control a satellite.

>>7047 >"standards make my program fool proof!" >compiler optimizes away safety checks because undefined behavior can't happen

>>7048 People choose compilers based on different criteria and choose compiler options based on their needs. This isn't that hard to understand.

Personally, one thing I'd like to do eventually is designing a language that is garbage collected by default, but also powerful enough to implement a GC in itself with fairly standard code. I'm hoping that this goal will force the language to be inherently powerful. I want the design to fall out naturally from having custom allocators and whatever kind of polymorphism and/or metaprogramming features I adopt.

>>7050 I think that might not be the best idea. IMO, a language with garbage collection shouldn't have pointers, and a language with pointers shouldn't have garbage collection. When people have pointers, they tend to do dumb things, like write the pointers out to disk and read them back again, xor two pointers together, xor their pointers with a magic number, or read pointers over the network. This is why D has so many problems with garbage collection. C# has pointers and pointer arithmetic, but you must tell the garbage collector not to relocate your memory using a fixed block, and you can only use pointers in an unsafe block. This is an ok compromise, but you still can't free things and have to rely on the garbage collector, and it has the previous restrictions as well. Go has pointers but no pointer arithmetic, IIRC. Sounds pretty useless to me.

>>7057 I'm thinking of having raw unsafe pointers and GCed smart pointers that are implemented in terms of the former, roughly like in Rust. The default GCed pointers should not allow pointer arithmetic, but my main design goal is that it should be easy to add your own smart pointers with custom behaviour. In particular, vectors should be allowed to just free themselves preemptively.

>>7057 >IMO, a language with garbage collection shouldn't have pointers, and a language with pointers shouldn't have garbage collection. Why can't one track the pointers themselves and leave it to the programmer to manage whatever data is pointed to? This is how it works with languages that have FFIs; the GC can't and won't get involved. I don't think it's a bad thing at all, in fact integrating this into the language could give it low level programming capabilities. https://github.com/ffi/ffi/wiki/Pointers >When people have pointers, they tend to do dumb things, like write the pointers out to disk and read them back again >read pointers over the network Obviously you shouldn't serialize pointers. This is pretty much the reason people convert data structures into a format like JSON before output. >xor two pointers together, xor their pointers with a magic number There's nothing inherently wrong with this.

>>7057 >This is why D has so many problems with garbage collection. D is a systems language; therefore it has to permit its users to be able to do what they will with pointers. The fact the users can shoot themselves in the foot with bad practices is merely a consequence. Of all the issues I've read concerning D's adaption of a GC as its primary memory management technique, this is the first time I've read an assertion like this.

Thinking a bit more about it, I think that reflection is probably the way to go, with Smalltalk being a great example. In Smalltalk, the stack and all stack frames are objects, and ordinary code can pull it up and take it apart easily. I can also use a (cheap) reflection primitive to iterate over the fields of any given object. I can use this to trace over all elements in the stack. I'll probably just do a relatively simple mark-trace GC and build the whole thing on top of a low-fragmentation allocator like jemalloc to avoid dealing with pointers directly. I'm planning to do it for a very simple smalltalk-inspired language with very few primitives and a minimal bytecode interpreter. Performance is a non-goal at this point, I just want a prototype that I can learn from.

>>7139 >the stack and all stack frames are objects How is that implemented? How to reify concepts of the language implementation into things the language can access and manipulate?

>>7191 You... just do it, and design the rest of the language to play nicely with it. In the case of Smalltalk, it's essential in order to have a proper debugger. If an exception occurs, the debugger lets you find the spot further down in the call stack that caused the error, change the code that caused that error, and then unwind the stack to go back to the program state at the point where you changed the code, and it'll be back to running properly. That's the beauty of Smalltalk and how it lets you modify running programs.

>>7192 Also, at the risk of going off topic but expanding on this, Smalltalk was also the origin of test-driven development. It's a rather surreal feeling when you run a test, see it throw an exception, enter the debugger, look through the stack and all scopes, find the spot where the values begin, change the code there, restart the execution from that method call, and see the execution path continue and pass the unit tests. At that point, you're not even writing code to pass the nth run of your unit test. You end up running it once and changing code so that this one run of your unit tests passes (after repeatedly unwinding the stack and resuming manually from a given point). You can also debug interactive programs like games or GUI's where reproducing bugs automatically in a unit test is difficult and you can't restart the program. You trigger the bug once, and then repeatedly unwind the stack in the debugger and trigger it again while modifying the code until you've fixed it. Doing that for the first time and realizing how it worked was the one thing that completely changed my mind about Smalltalk, from disliking it to being extremely impressed by it. I still feel that classes are a suboptimal abstraction, but Smalltalk's live environment ends up being mind-blowing once you really get into it.

>>3159 One of the few implementations of a tracing jit, which is feasible because Lua is such a simple language. It's quite nice.

>>3196 Garbage collection makes more sense when you come from a background like C where you have to explicitly allocate memory of a certain size, keep up with it, and then give it back to the OS at a later time. A garbage collector is just an algorithm devised to let you allocate memory and not care about keeping up with it. The algorithm determines what memory is still being used and what memory isn't being used -- or the garbage being collected -- and frees that memory.

>>7228 >allocate memory of a certain size, keep up with it, and then give it back to the OS at a later time Indeed, it's a lot easier to understand GC when one is familiar with manual memory management disciplines. The time unused memory is freed is implementation-defined, and selecting such a time seems to be central to the performance of the algorithm. Some free based on memory pressure, others free continuously in parallel, yet others try to leak memory as much as possible and only free when it's exhausted.

>>959 That was a very enjoyable read, thanks for posting. I've been looking into a garbage collector for my language stdlib and macro facility. While I plan to make the main language utilize manual memory management, GC would be nice for macros and as an optional plugin to libraries.

>>7139 OK, same guy. I've experimented a bit with various designs. I think it's actually very feasible to write the full shebang including both allocator and GC in the language that it operates on, without ever compromising memory safety. The key is to have an object table for all objects along with a concept of dynamic borrowing like Rust's cell type. The nice thing with an object table is that it can guarentee safety. The actual space of an object in memory is uniquely owned by its header in the object table and other objects only hold the id of the header in the object table, and defining object references as null if the corresponding id is not in the object table If you have that kind of system, you can't have dangling object references as long as each id in the table is only assigned to once, because when you remove an object and its header in the object table, all references to that object immediately become null. A simple way to maintain decent performance without too many levels of indirection is to also have value types (primitives and structs) in the language that are passed by value and can't have references to them unless wrapped as an object field, so that objects are big enough that the object table won't create too much overhead. That covers memory safety. The way to write the allocator itself is to have support for memory region objects which can be split into subregions and have other objects allocated in those subregions. The subregions borrow the original region, so that it can't be deallocated unless it is empty. With this kind of system, you can build a buddy allocator fairly easily. You can also move an object from one region to another by putting a write barrier on its header, copying it, changing the header pointer to the new location, and removing the write barrier. With this kind of system, you can write a fairly sophisticated defragmenting memory allocator & GC in the language itself without ever compromising safety. The headers in the object table can still be fragmented, but since they all have the same size they can be pool allocated. To do a garbage collection, you use a mark sweep algorithm which starts from the roots and marks all reachable headers, and then deletes all headers in the object table which are not reachable. This can be done separately from the actual allocator & defragmentation algorithm.

It would be interesting to get some discussion and resources concerning hardware garbage collection. I can see how it would work well enough. If the hardware had a notion of a pair type and enforced, say, a marking bit, it would be easy enough to see how hardware could even asynchronously go through the pairs from a designated root pair, constantly marking whatever is connected. You could then tie this up in software by scanning through memory collecting unmarked chunks. I could also see support for reference counting with hardware-enforced objects, with interrupts upon becoming garbage, and software support for resolving mutually-linking objects that reference counting can't collect. There are of course other ways to do it. Seeing how previous hardware has done it would be nice.

I also want to learn of any O(1) memory consumption garbage collection routines. For the easy case, I can simply see time costs as being O(n!), effectively mark and sweep without the mark, but I can't currently see a way to solve this problem when dealing with mutually referencing structures. Mutually referencing structures defeat this and I don't see a solution, but I've only given this topic light thought. It's perhaps impossible to have a garbage collection algorithm that consumes constant memory no matter how much it's collecting. A single bit per object is a rather small n for O(n) memory consumption, but it would be so interesting to eliminate it entirely.

Do you believe Lisp systems still have the most advanced garbage collection systems? Comparing to other languages, Python seems to have a relatively primitive generational system, including a generation zero for very fresh objects that are likely to die, but has a system that fails to detect circularities and only occasionally checks for circularities, although I may have an old understanding. Ruby also comes to mind, but I'm not aware of anything novel it does. As for Go, it's my impression that it has an advanced garbage collector, but is primarily concerned with throughput and that Go aggressively analyzes a program so that garbage collection is used as little as possible; it is interesting that it now seems to have a garbage collector that runs in tandem with the main program, however; other systems certainly lack that and I'm not aware of a Common Lisp that has this, but I've not checked much. Moving on to some recent thoughts, I've been concerned with memory exhaustion and how to cope with it. One idea I had for a system is that the underlying runtime should have a buffer of memory and allocate more when a certain percentage is used; if more couldn't be obtained, it would tell the underlying language that memory has been exhausted, yet there would still be some leftover that this language could use for handling the memory exhaustion case in its own way. This is in all likelihood an unoriginal thought, but I like it in any case and find it clearly better than waiting until the underlying system truly can't allocate anything else to let the higher language know, given that such a buffer is feasible. I'll certainly employ this little trick when I implement a garbage collected language.

>>14066 Furthermore, if a user hits that memory limit, the system should spit out a warning and issue a "yellow flag". If a single user acquires more than 3 "yellow flags", the system should reformat all of its storage. That'll teach em.

Are there any garbage collection algorithms suitable for gamedev? I want to write my own game but I friggin hate dealing with manual memory management.

I wonder how feasible it would be to do reference counting at compile time.

>>17602 >Are there any garbage collection algorithms suitable for gamedev? Any language with a GC is suitable for game development. Use object pooling to avoid thrashing the GC. https://gameprogrammingpatterns.com/object-pool.html