4 ms·

Writing a Simple Garbage Collector in C (2014)

190 points by susam 4y ago

jakearmitage 4y ago
What a well written article. Very didactic.
version_five 4y ago
Stupid question, are there standard GC libraries that are used with C? Alternatively, what is the usual memory management practice? Is it typical just to keep track within the confines of the code you're writing and explicitly free memory when you're done with it?
- mandarax8 4y ago
  Boehm GC is mentioned in the article: https://github.com/ivmai/bdwgc https://github.com/ivmai/bdwgc
- nu11ptr 4y ago
  The Boehm collector exists and is mentioned in the article, but is not part of the standard library. Typical memory management practice is to store on the stack as much as possible reclaming memory as it goes out of scope. Larger chunks of memory or those that outlast scope typically uses manual malloc + free and these are often batched to minimize overhead. It is fairly unusual to use a GC in C. This is likely due to multiple reasons: history/culture, language design (C only allows for conservative collectors), less precise control over runtime overhead and pauses, higher memory utilization, etc.
- deleted 4y ago
  [deleted]
- ritcgab 4y ago
  Manual malloc() + free() is the way. The language design makes it hard (if not impossible) to generate compilation-time GC routine. Runtime GC will be another thing, and you probably will lose raw pointer access, because we need some higher-level struct wrapping around the raw pointer to feed more information to the garbage collector.
- sirwhinesalot 4y ago
  If you want to keep your sanity, you don't want to be manually mallocing and freeing all over the place. The most common patterns I often see are a "context" object of some kind (typically used by libraries) which handles all memory management internally and must be passed to every API call. So you only ever allocate and free that one object. (Internally they might be doing all sorts of crazy things, I've even seen a basic tracing GC!) Applications typically use some combination of bump allocators (aka arenas) and pools. You put temporary allocations in a dedicated temp arena and clear it out when appropriate for the application (i.e. every frame)
- cancerhacker 4y ago
  A common idiom that is no longer as common is to always create a stack buffer up to a certain small bound and then an allocation if it goes beyond: void dwim(unsigned count) { struct Something _buffer[10]; struct Something* buffer; if (count < sizeof(_buffer) / sizeof(_buffer[0])) buffer = _buffer; else { buffer = (struct Something*) malloc(count * sizeof(struct Something)); } doSomething(buffer, count); if (buffer != _buffer) free(buffer); } It used to be really common to write that without considering if it was a necessary optimization or not - nowadays I would just malloc up front.
  - gmueckl 4y ago
    This pattern still exists in C++ in the form of custom containers that implement "small array optimization". The LLVM project is a heavy user of this pattern as far as I know and I have seen it in several proprietary codebases.
    - alpaca128 4y ago
      Same with Rust's smallvec crate.
    - spacechild1 4y ago
      It's also used in std::string (small string optimization).
- mcguire 4y ago
  "The usual memory management practice" in C depends a lot an what you are doing. Malloc/free scattered through your code is...not uncommon. That does require discipline or ugliness ensues. Other common options are not allocating, which is kind of limiting but the only option under very tight memory constraints, and doing specific domain management options. One of the best of the latter is arena management. (https://en.wikipedia.org/wiki/Region-based_memory_management https://en.wikipedia.org/wiki/Region-based_memory_management)
- hsn915 4y ago
  The consensus seems to be Arena allocators. Ryan Fleury has a great write up on the subject: https://www.rfleury.com/p/untangling-lifetimes-the-arena-allocator https://www.rfleury.com/p/untangling-lifetimes-the-arena-all...
- sparkie 4y ago
  > Is it typical just to keep track within the confines of the code you're writing and explicitly free memory when you're done with it? Yes. It's common to write OOP style C by using an opaque pointer in a header file and handle all the allocation and deallocation within the code file. The header file will export a "constructor" and "destructor" function. The constructor and destructor are still called manually, but this method properly encapsulates state to being visible only within a single code file, which prevents some accidental misuses of a type. The destructor should have a free for every allocation in the constructor, but done in reverse order. If you follow this pattern consistently, then `malloc` will only ever appear inside a constructor and `free` will only appear in a destructor. All other object allocation and deallocation is done via the relevant constructor/destructor. .h file: typedef struct my_type_t my_type; my_type* my_type_alloc (type1, size_t); void my_type_free (my_type*); .c file: struct my_type_t { type1 member1; type2* member2; }; my_type* my_type_alloc (type1 m1_copy, size_t m2_size); { my_type result* = (my_type*) malloc (sizeof (my_type)); result->member1 = m1_copy; result->member2 = type2_alloc (m2_size); return result; } void my_type_free (my_type* value) { type2_free (value->member2); free (value); } Another technique is to make use of GCC `constructor` and `destructor` attributes, which are called before `main` and after `main` loses scope (or `exit()` is called). For example, you might have a static container type and only expose methods `add`, `remove` and `get`, then all allocation and deallocation happens solely within the code file and consumers of this API don't need to concern themselves with allocating and deallocating. This is only really useful for singleton-like (process global) data structures, but you could perhaps utilize these for implementing a GC, since an allocator is usually global to the process. (Eg, the `GC_init` function in the article could be given the constructor attribute so that the programmer would not need to manually call it). .h file: void container_add (obj value); void container_remove (obj value); obj container_get (size_t index); .c file: struct container_t { obj* items; size_t num_items; size_t capacity; } static container_t* c; __attribute__((constructor)) void container_initialize(void) { c = malloc (sizeof (struct container_t)); c->num_items = 0; c->capacity = DEFAULT_NUM_ITEMS; c->items = malloc(DEFAULT_NUM_ITEMS * sizeof (obj)); } __attribute__((destructor)) void container_uninitialize(void) { free (c->items); free (c); } void container_resize (size_t new_size) { obj* tmp = c->items; c->capacity = new_size; c->items = malloc (new_size * sizeof (obj)); memcpy (c->items, tmp, c->num_items * sizeof (obj)); free (tmp); } void container_add (obj value) { if (c->num_items == c->capacity) container_resize (c->capacity * 2); ... } void container_remove (obj value) { ... } obj container_get (size_t index) { return c->items[index]; }
webkike 4y ago
Wow! What a blast from the past. I originally submitted this article back in 2014 when it was hosted on my personal page hosted by my university. You can view the thread here: https://news.ycombinator.com/item?id=8222487 https://news.ycombinator.com/item?id=8222487 When I migrated to my own personal domain, I decided I would update the article to address the comments on that thread, and I think the end result was much better (but alas, I never had a reason to re-submit the article here). Obviously I do not recommend using a GC like this in general, but as a learning resource for how memory works and some of the more obscure parts of executables, I think it works pretty well! The compliments I've received from this article have been pretty incredible. Seeing it here, uploaded independently, really warms my heart. Oh, and this article is so old that I'm now a Rust guy. Crazy how that works!
- matheusmoreira 4y ago
  Thank you. Your article helped me understand memory allocation and garbage collection algorithms. I successfully used this knowledge while developing my own language.
jpfr 4y ago
Nice and tight. For comparison, this is the malloc/free implementation of the original UNIX. Also nice and tight C code. https://warsus.github.io/lions-/all.html#line2522 https://warsus.github.io/lions-/all.html#line2522 Although this isn’t very efficient for today’s memory sizes.
lamp987 4y ago
that code is severely broken by using unsigned int instead of uintptr_t to represent addresses.
cyberax 4y ago
Nice! A couple of other classic articles that should be mentioned: "Accurate garbage collection in an uncooperative environment" by Fergus Henderson - https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=db35502708be06db3bfdd26c685400f3e134fdd4 https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&d... "Accurate Garbage Collection in Uncooperative Environments Revisited" - http://www.filpizlo.com/papers/baker-ccpe09-accurate.pdf http://www.filpizlo.com/papers/baker-ccpe09-accurate.pdf
firatsarlar 4y ago
[flagged]
- CJefferson 4y ago
  I can see you are annoyed from getting downvotes. Unfortunately, I do not know the point you are trying to make in your message. I would suggest trying to write out full sentences, so we can understand what you are trying to say.
  - firatsarlar 4y ago
    Thank you. All my heart. This made me understand how I could easily manipulated. And sorry. I would like to chat about language-s- but you - the community you represent - will percieve it as arguing. I would like to to tell my intention but, it will perceived some kind of defense or offence. What I'm trying to is, simply read a book "How to talk anyone" and practise. I'm not a native speaker.I'm tired to this language barrier. I'm just trying to simple enough to make some spark with the words alone. We all know those words, we all know their meaning. And yes. I was not aware that I'm being manipulated - say my ego, say what I perceived or offended - And I understand, this is wrong. ( Not the way I talk, playing karma game and argue ) Again. We - non Eng. speakers - can not communicate with you - I still have hope but sad, -> , bad -> , offended --> defended - Sorry for the shit. Sorry for my language. Sorry for my will to exist or communicate. I'm sorry. I'm sad - not sure - And broken. I do not really know -deeply- why I'm doing that. But sorry. I'll practice to talk anyone somewhere I feel free, accepted, - self petty ( joke lets say) - Peace. My heart long left with place, I'm sorry for all of us. Peace. And thank for another spark of showing me that, I'm not a pro. programmer, I'm just an ametour. The man I know, will forget these and want to express itself. But no. Lets say good by. Have a wonderful life, grow, progress, ...
    - detrites 4y ago
      I believe you have good intentions, so with respect I will try to help. Maybe try write what you would like to say in your native language, into a translation site or app, and then copy/paste the English version here? Then you can do the reverse for replies you receive. Something that may help the translator app work better, is to simplify your native writing, as if communicating with a young person. Doing this regularly may also help you improve your English. Or if you are doing that already, I suggest trying a different translator app/site, as the one you are using is not giving an accurate result. Anyway, best wishes to you.
fmiras 4y ago
congrats! great project
dang 4y ago
Related: Writing a Simple Garbage Collector in C - https://news.ycombinator.com/item?id=21794327 https://news.ycombinator.com/item?id=21794327 - Dec 2019 (23 comments) Writing a Simple Garbage Collector in C - https://news.ycombinator.com/item?id=8222487 https://news.ycombinator.com/item?id=8222487 - Aug 2014 (47 comments)
- nhatcher 4y ago
  And probably yesterday's: _The Garbage Collection Handbook, 2nd Edition_ - https://news.ycombinator.com/item?id=35492307 https://news.ycombinator.com/item?id=35492307
rurban 4y ago
Simple GC's such as this are utterly useless. For such slow stop-the-world GC's use the Boehm-Weiser libgc and nothing else. And for a proper compacting GC there are many options, best being ravenbrook's MPS, but these require lot of source code adaptions.
- matheusmoreira 4y ago
  Useless? These algorithms may be simple but they're not toys. This stuff has been used in production. You can certainly improve it but it's not "useless".
  - rurban 4y ago
    In production such a toy GC, without threading support and without register scanning? Imprecise also. How do you seperate large ints from pointers? Brave.
    - webkike 4y ago
      It’s a learning exercise man. Congratulations, you are very smart. FWIW, all of your questions are addressed in the article
    - matheusmoreira 4y ago
      > In production Did you know Ruby has a garbage collector not unlike this one? People are running it in production right now. > a toy GC It does its job. These algorithms have been working for decades now. > without threading support It can just stop the whole world. > without register scanning Add some inline assembly to spill all the registers. I did this on my own language implementation not even a month ago. If this was a real project I'd submit a patch. The author even acknowledged this limitation and hinted at how to solve it, he just didn't want to get into those gritty details in his article. I'm happy to demonstrate if you want. > Imprecise also. How do you seperate large ints from pointers? You don't. You collect conservatively. It will have false positives but not false negatives. In other words, it will mistake some ints for pointers but it won't collect memory that's in use. Correct if suboptimal behavior.

190 points by susam 4y ago

What a well written article. Very didactic.

Stupid question, are there standard GC libraries that are used with C? Alternatively, what is the usual memory management practice? Is it typical just to keep track within the confines of the code you're writing and explicitly free memory when you're done with it?

mandarax8 4y ago
Boehm GC is mentioned in the article: https://github.com/ivmai/bdwgc https://github.com/ivmai/bdwgc
nu11ptr 4y ago
The Boehm collector exists and is mentioned in the article, but is not part of the standard library. Typical memory management practice is to store on the stack as much as possible reclaming memory as it goes out of scope. Larger chunks of memory or those that outlast scope typically uses manual malloc + free and these are often batched to minimize overhead. It is fairly unusual to use a GC in C. This is likely due to multiple reasons: history/culture, language design (C only allows for conservative collectors), less precise control over runtime overhead and pauses, higher memory utilization, etc.
deleted 4y ago
[deleted]
ritcgab 4y ago
Manual malloc() + free() is the way. The language design makes it hard (if not impossible) to generate compilation-time GC routine. Runtime GC will be another thing, and you probably will lose raw pointer access, because we need some higher-level struct wrapping around the raw pointer to feed more information to the garbage collector.
sirwhinesalot 4y ago
If you want to keep your sanity, you don't want to be manually mallocing and freeing all over the place. The most common patterns I often see are a "context" object of some kind (typically used by libraries) which handles all memory management internally and must be passed to every API call. So you only ever allocate and free that one object. (Internally they might be doing all sorts of crazy things, I've even seen a basic tracing GC!) Applications typically use some combination of bump allocators (aka arenas) and pools. You put temporary allocations in a dedicated temp arena and clear it out when appropriate for the application (i.e. every frame)
cancerhacker 4y ago
A common idiom that is no longer as common is to always create a stack buffer up to a certain small bound and then an allocation if it goes beyond: void dwim(unsigned count) { struct Something _buffer[10]; struct Something* buffer; if (count < sizeof(_buffer) / sizeof(_buffer[0])) buffer = _buffer; else { buffer = (struct Something*) malloc(count * sizeof(struct Something)); } doSomething(buffer, count); if (buffer != _buffer) free(buffer); } It used to be really common to write that without considering if it was a necessary optimization or not - nowadays I would just malloc up front.
- gmueckl 4y ago
  This pattern still exists in C++ in the form of custom containers that implement "small array optimization". The LLVM project is a heavy user of this pattern as far as I know and I have seen it in several proprietary codebases.
  - alpaca128 4y ago
    Same with Rust's smallvec crate.
  - spacechild1 4y ago
    It's also used in std::string (small string optimization).
mcguire 4y ago
"The usual memory management practice" in C depends a lot an what you are doing. Malloc/free scattered through your code is...not uncommon. That does require discipline or ugliness ensues. Other common options are not allocating, which is kind of limiting but the only option under very tight memory constraints, and doing specific domain management options. One of the best of the latter is arena management. (https://en.wikipedia.org/wiki/Region-based_memory_management https://en.wikipedia.org/wiki/Region-based_memory_management)
hsn915 4y ago
The consensus seems to be Arena allocators. Ryan Fleury has a great write up on the subject: https://www.rfleury.com/p/untangling-lifetimes-the-arena-allocator https://www.rfleury.com/p/untangling-lifetimes-the-arena-all...
sparkie 4y ago
> Is it typical just to keep track within the confines of the code you're writing and explicitly free memory when you're done with it? Yes. It's common to write OOP style C by using an opaque pointer in a header file and handle all the allocation and deallocation within the code file. The header file will export a "constructor" and "destructor" function. The constructor and destructor are still called manually, but this method properly encapsulates state to being visible only within a single code file, which prevents some accidental misuses of a type. The destructor should have a free for every allocation in the constructor, but done in reverse order. If you follow this pattern consistently, then `malloc` will only ever appear inside a constructor and `free` will only appear in a destructor. All other object allocation and deallocation is done via the relevant constructor/destructor. .h file: typedef struct my_type_t my_type; my_type* my_type_alloc (type1, size_t); void my_type_free (my_type*); .c file: struct my_type_t { type1 member1; type2* member2; }; my_type* my_type_alloc (type1 m1_copy, size_t m2_size); { my_type result* = (my_type*) malloc (sizeof (my_type)); result->member1 = m1_copy; result->member2 = type2_alloc (m2_size); return result; } void my_type_free (my_type* value) { type2_free (value->member2); free (value); } Another technique is to make use of GCC `constructor` and `destructor` attributes, which are called before `main` and after `main` loses scope (or `exit()` is called). For example, you might have a static container type and only expose methods `add`, `remove` and `get`, then all allocation and deallocation happens solely within the code file and consumers of this API don't need to concern themselves with allocating and deallocating. This is only really useful for singleton-like (process global) data structures, but you could perhaps utilize these for implementing a GC, since an allocator is usually global to the process. (Eg, the `GC_init` function in the article could be given the constructor attribute so that the programmer would not need to manually call it). .h file: void container_add (obj value); void container_remove (obj value); obj container_get (size_t index); .c file: struct container_t { obj* items; size_t num_items; size_t capacity; } static container_t* c; __attribute__((constructor)) void container_initialize(void) { c = malloc (sizeof (struct container_t)); c->num_items = 0; c->capacity = DEFAULT_NUM_ITEMS; c->items = malloc(DEFAULT_NUM_ITEMS * sizeof (obj)); } __attribute__((destructor)) void container_uninitialize(void) { free (c->items); free (c); } void container_resize (size_t new_size) { obj* tmp = c->items; c->capacity = new_size; c->items = malloc (new_size * sizeof (obj)); memcpy (c->items, tmp, c->num_items * sizeof (obj)); free (tmp); } void container_add (obj value) { if (c->num_items == c->capacity) container_resize (c->capacity * 2); ... } void container_remove (obj value) { ... } obj container_get (size_t index) { return c->items[index]; }

webkike 4y ago

Wow! What a blast from the past. I originally submitted this article back in 2014 when it was hosted on my personal page hosted by my university. You can view the thread here: https://news.ycombinator.com/item?id=8222487 https://news.ycombinator.com/item?id=8222487 When I migrated to my own personal domain, I decided I would update the article to address the comments on that thread, and I think the end result was much better (but alas, I never had a reason to re-submit the article here). Obviously I do not recommend using a GC like this in general, but as a learning resource for how memory works and some of the more obscure parts of executables, I think it works pretty well! The compliments I've received from this article have been pretty incredible. Seeing it here, uploaded independently, really warms my heart. Oh, and this article is so old that I'm now a Rust guy. Crazy how that works!

matheusmoreira 4y ago
Thank you. Your article helped me understand memory allocation and garbage collection algorithms. I successfully used this knowledge while developing my own language.

jpfr 4y ago

Nice and tight. For comparison, this is the malloc/free implementation of the original UNIX. Also nice and tight C code. https://warsus.github.io/lions-/all.html#line2522 https://warsus.github.io/lions-/all.html#line2522 Although this isn’t very efficient for today’s memory sizes.

lamp987 4y ago

that code is severely broken by using unsigned int instead of uintptr_t to represent addresses.

cyberax 4y ago

Nice! A couple of other classic articles that should be mentioned: "Accurate garbage collection in an uncooperative environment" by Fergus Henderson - https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=db35502708be06db3bfdd26c685400f3e134fdd4 https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&d... "Accurate Garbage Collection in Uncooperative Environments Revisited" - http://www.filpizlo.com/papers/baker-ccpe09-accurate.pdf http://www.filpizlo.com/papers/baker-ccpe09-accurate.pdf

firatsarlar 4y ago

[flagged]

CJefferson 4y ago
I can see you are annoyed from getting downvotes. Unfortunately, I do not know the point you are trying to make in your message. I would suggest trying to write out full sentences, so we can understand what you are trying to say.
- firatsarlar 4y ago
  Thank you. All my heart. This made me understand how I could easily manipulated. And sorry. I would like to chat about language-s- but you - the community you represent - will percieve it as arguing. I would like to to tell my intention but, it will perceived some kind of defense or offence. What I'm trying to is, simply read a book "How to talk anyone" and practise. I'm not a native speaker.I'm tired to this language barrier. I'm just trying to simple enough to make some spark with the words alone. We all know those words, we all know their meaning. And yes. I was not aware that I'm being manipulated - say my ego, say what I perceived or offended - And I understand, this is wrong. ( Not the way I talk, playing karma game and argue ) Again. We - non Eng. speakers - can not communicate with you - I still have hope but sad, -> , bad -> , offended --> defended - Sorry for the shit. Sorry for my language. Sorry for my will to exist or communicate. I'm sorry. I'm sad - not sure - And broken. I do not really know -deeply- why I'm doing that. But sorry. I'll practice to talk anyone somewhere I feel free, accepted, - self petty ( joke lets say) - Peace. My heart long left with place, I'm sorry for all of us. Peace. And thank for another spark of showing me that, I'm not a pro. programmer, I'm just an ametour. The man I know, will forget these and want to express itself. But no. Lets say good by. Have a wonderful life, grow, progress, ...
  - detrites 4y ago
    I believe you have good intentions, so with respect I will try to help. Maybe try write what you would like to say in your native language, into a translation site or app, and then copy/paste the English version here? Then you can do the reverse for replies you receive. Something that may help the translator app work better, is to simplify your native writing, as if communicating with a young person. Doing this regularly may also help you improve your English. Or if you are doing that already, I suggest trying a different translator app/site, as the one you are using is not giving an accurate result. Anyway, best wishes to you.

fmiras 4y ago

congrats! great project

dang 4y ago

Related: Writing a Simple Garbage Collector in C - https://news.ycombinator.com/item?id=21794327 https://news.ycombinator.com/item?id=21794327 - Dec 2019 (23 comments) Writing a Simple Garbage Collector in C - https://news.ycombinator.com/item?id=8222487 https://news.ycombinator.com/item?id=8222487 - Aug 2014 (47 comments)

nhatcher 4y ago
And probably yesterday's: _The Garbage Collection Handbook, 2nd Edition_ - https://news.ycombinator.com/item?id=35492307 https://news.ycombinator.com/item?id=35492307

rurban 4y ago

Simple GC's such as this are utterly useless. For such slow stop-the-world GC's use the Boehm-Weiser libgc and nothing else. And for a proper compacting GC there are many options, best being ravenbrook's MPS, but these require lot of source code adaptions.

matheusmoreira 4y ago
Useless? These algorithms may be simple but they're not toys. This stuff has been used in production. You can certainly improve it but it's not "useless".
- rurban 4y ago
  In production such a toy GC, without threading support and without register scanning? Imprecise also. How do you seperate large ints from pointers? Brave.
  - webkike 4y ago
    It’s a learning exercise man. Congratulations, you are very smart. FWIW, all of your questions are addressed in the article
  - matheusmoreira 4y ago
    > In production Did you know Ruby has a garbage collector not unlike this one? People are running it in production right now. > a toy GC It does its job. These algorithms have been working for decades now. > without threading support It can just stop the whole world. > without register scanning Add some inline assembly to spill all the registers. I did this on my own language implementation not even a month ago. If this was a real project I'd submit a patch. The author even acknowledged this limitation and hinted at how to solve it, he just didn't want to get into those gritty details in his article. I'm happy to demonstrate if you want. > Imprecise also. How do you seperate large ints from pointers? You don't. You collect conservatively. It will have false positives but not false negatives. In other words, it will mistake some ints for pointers but it won't collect memory that's in use. Correct if suboptimal behavior.