8 ms·

Baby's First Garbage Collector

217 points by daw___ 13y ago

mamcx 13y ago
That was actually very easy to understand!. Thanks for that. I'm thinking in build a toy language and this make on magic thing die..
phamilton 13y ago
Not having studied the topic in depth, my first thought is whether true pointers and a garbage collector can coexist (without artificially removing parts of the language). The big condition for knowing if something is still in use is whether any references exist to it. But in a language like C , you could cast a pointer to something else (like a void pointer for some quasi generic linked list), store it somewhere, and then cast it back later after garbage collection has run. That seems like a problematic situation. So is completely giving up on pointers (or just never doing tricky things like casting or pointer arithmetic) a requirement to having a garbage collector?
- city41 13y ago
  I don't know of any language that has pointers and a GC. Are there any? C# lets you use pointers but only if you tell the GC to not move your object and promise to behave.
  - octo_t 13y ago
    Optional GC[1] in a language like C++, and Rust has pointers with task-local GC [1] - http://en.wikipedia.org/wiki/Boehm_GC http://en.wikipedia.org/wiki/Boehm_GC
  - jballanc 13y ago
    The Boehm–Demers–Weiser garbage collector is a fairly famous implementation of a GC for vanilla C, pointers and all: http://en.wikipedia.org/wiki/Boehm_garbage_collector http://en.wikipedia.org/wiki/Boehm_garbage_collector
    - city41 13y ago
      Yeah I'm aware of optional GCs. What I meant was languages that ship with a GC as standard and also have pointers. In the case of Boehm, since you choose to bring it in yourself, it's up to you to make sure you don't abuse it.
      - jballanc 13y ago
        Well, pretty much any language with a GC can abuse the GC, regardless of whether it's optional or designed in from the start. It just happens to be a lot harder to abuse a GC than to forget to free/delete something.
  - Scaevolus 13y ago
    You can have a GC without compaction. Go has a GC and pointers, including internal pointers (e.g. to a field of a struct). Its GC started out fully conservative, then precise for the heap and conservative for the stack, and future versions will be fully precise.
  - cwzwarich 13y ago
    Some languages in the Wirth family have pointers and GC, e.g. Modula-3. It has a module-level notion of safety, so that modules using potentially unsafe pointer manipulation are marked as unsafe and break runtime safety guarantees. It also doesn't guarantee that all pointers will be roots for GC.
  - nicky0 13y ago
    Objective-C has pointers and a GC.
  - wsc981 13y ago
    > "I don't know of any language that has pointers and a GC. Are there any?" Objective-C used to have a garbage collector, though (at least with regards to iOS) Apple removed this capability with the introduction or ARC. On the following URL is some discussion on the Objective-C garbage collector: http://cocoasamurai.blogspot.nl/2010/12/objective-c-memory-management-garbage.html http://cocoasamurai.blogspot.nl/2010/12/objective-c-memory-m...
    - masklinn 13y ago
      iOS never got the GC, only the desktop version got it, and afaik it was deprecated rather than removed entirely.
      - pornel 13y ago
        It's been removed entirely in Xcode 5.1.
  - betterunix 13y ago
    OCaml, though in a very restricted sense: http://www.cs.cornell.edu/courses/cs3110/2011sp/recitations/rec10.htm http://www.cs.cornell.edu/courses/cs3110/2011sp/recitations/...
  - pjmlp 13y ago
    > I don't know of any language that has pointers and a GC. Are there any? C# lets you use pointers but only if you tell the GC to not move your object and promise to behave Oberon, Oberon-2 allows you to use no-GC pointers via the SYSTEM package. Active Oberon additionally adds syntax support for untraced pointers. Modula-3 has unsafe modules which allow you to use untraced pointers. D has unsafe pointers in system blocks. Ada and C++11 have support for optional GC defined on the language standard. However so far, there isn't any compiler vendor that really offers them. In Java you can do a bit of dirty pointer tricks via the com.sun.unsafe package, but it is Oracle's VM specific. Although there are plans to make it part of the official library after Java 8.
  - bitwize 13y ago
    Various Lisp dialects over the years have supported the use of locatives, or pointer-like objects. In general, objects which can be moved or copied around by the runtime behind the programmer's back cannot have indefinite-extent hardware-address pointers taken directly into them. This includes objects managed by most halfway-decent garbage collectors (which tend to be implemented as stop-and-copy, not mark-and-sweep), but also includes such things as drawing surfaces in SDL and DirectDraw. Many runtimes take the C# approach -- provide a memory locking operation that fixes the object in memory while you do some pointer stuff on it and a dual unlocking operation that releases the object so it can be kicked around by the runtime again.
- jballanc 13y ago
  When you hear talk of "conservative" Garbage Collectors, what the "conservative" refers to is that anything on the stack that looks like a pointer is treated as if it is a pointer. After all, it doesn't matter what you cast a pointer to, it's all just 1s and 0s on the stack...
  - dllthomas 13y ago
    Of course, you can make something look like not a pointer and then make it a pointer again if you actually change the zeros and ones.
    - _delirium 13y ago
      Most languages don't give you any guarantees if you do that, though. In C, for example, pointer arithmetic on a void*, or on a pointer cast to an integer, is not guaranteed to produce sensible results. The standard only provides guarantees for pointer arithmetic if it's performed on a non-void pointer that points within an array, and the results remain within the bounds of the same array (arithmetic that produces a pointer pointing outside the array of the base pointer is undefined, with the exception that pointing to one element past the end of the array is defined).
      - dllthomas 13y ago
        In ordinary C, without a garbage collector, I'd be baffled to find an implementation where one could not: 1) Cast a pointer to an integer of sufficient size. 2) Xor that integer with another value. 3) Xor the result with the same value. 4) Cast back to a pointer. 5) Dereference. It's sufficiently corner-case that I am not certain what the standard says about it. In any event, pointers matter when coding in assembly, where language standards aren't even relevant.
        aidenn0 13y ago
        That is actually allowed in the standard; it specifically says that casting a pointer to an integral type of sufficient size is a reversible operation (though it I'm not sure if this is not well defined: (int i[2]; (int )((int)i)+sizeof(int)
- rayiner 13y ago
  You don't need to give up pointers, or pointer arithmetic, just the ability to obscure what a pointer points to. Casting to void does not do this (and indeed, has no run time effect at all). Metadata is associated with the pointed-to block of memory, so as long as the address is recognizable as a pointer at runtime, you can do GC. Some of the things that break GC aren't even technically valid C code. For example, say I allocate three memory areas with malloc() then hold on only to the area with the lowest address, and reference the other two areas with offsets relative to the first area. This is illegal in C, though it will work on most existing implementations, because it's illegal to dereference a pointer past the end of an allocation. Specific GC algorithms might not be able to handle say pointers into the interiors of objects, but that's not a general limitation for GC.
  - city41 13y ago
    Does this still work if the GC compacts memory? I don't know much about GCs, but it seems like once your GC is advanced enough with generational collecting, compacting, etc, then allowing raw pointers seems at odds with what the GC is trying todo. I'm sure it's possible, but it's probably a heck of a lot easier just to not allow pointers.
    - rayiner 13y ago
      It works fine as long as you have enough type information to know what is and is not a pointer.
  - cperciva 13y ago
    it's illegal to dereference a pointer past the end of an allocation. Yes, but there's a legal way to do this. reference the other two areas with offsets relative to the first area If you cast the pointers to uintptr_t, and perform your arithmetic on uintptr_t and cast your final pointer back (void * ) before using it, what you've done is perfectly legal and safe (albeit weird) since uintptr_t is an unsigned integer type with all the flexibility of unsigned integers, and if x = (uintptr_t)p then it's guaranteed that p == (void * )x. In other words: char * x = malloc(100); char * y = malloc(100); ptrdiff_t yminusx = y - x; x[yminusx] = '\0' is undefined behaviour, but char * x = malloc(100); char * y = malloc(100); uintptr_t yminusx = (uintptr_t)(y) - (uintptr_t)(x); *(char *)(void *)((uintptr_t)(x) + yminusx) = '\0' is valid C (and has the same meaning on a DWIM compiler).
- deleted 13y ago
  [deleted]
- bunderbunder 13y ago
  C# has pointer goodness, in that you can do pointer arithmetic and bypass type safety. However, you have to declare an 'unsafe' context in which you'll do it. Unsafe contexts are tied to a local scope, which means that you can't do anything like having classes with fields of pointer types. Pointers don't outlive the function in which you use them. Also, before you can get a pointer to an object you have to "pin" it, which tells the garbage collector not to move it around. This is necessary, of course, but it can have severe performance implications since it basically torpedoes all the garbage collector's best performance optimizations. So pointers are there when you need them. . . but the language makes them extremely inconvenient to use them more than you absolutely need to. A pretty solid compromise, IMO.
  - MichaelGG 13y ago
    C# can also use managed pointers (type& instead of type*). All out/ref parameters use this type of pointer, and it'll get updated by the runtime, like an object reference - no pinning necessary.
    - kevingadd 13y ago
      Interesting, can you link to an example of their use? I've never seen them in the documentation or examples, but I remember that Managed C++ and C++/CLI have something similar. Or are you just saying that you can 'use' them via out/ref? I interpreted your post to mean that you can store them in fields, which would be stellar but seems like it would break reference lifetime guarantees.
      - MichaelGG 13y ago
        You only use them via out/ref. Section 13.4.2 of the CLI spec says: - Managed pointers can be passed as arguments, stored in local variables, and returned as values. - Managed pointers cannot be stored in static variables, array elements, or fields of objects or value types. So you're right, they have very limited scope as it'd be messy otherwise. It's my understanding that the JVM does not have pointers even at this level, hence Java can't do out/ref parameters. (Sure, tuples are a better way to handle many cases of out params, but sometimes a well chosen ref can really be nicer.) I think C++ also uses the term "managed pointer" but not in the same technical sense (I think it just means reference.) Using "safe" C++/CLI generation limits the scope of pointers just like we'd expect.
- aidenn0 13y ago
  See this: http://www.hpl.hp.com/personal/Hans_Boehm/gc/ http://www.hpl.hp.com/personal/Hans_Boehm/gc/ But also with a very small number of restrictions, you can make C have non-conservative GC. ANSI C forbids aliasing as any type but a character. Furthermore, unions are to be interpreted as the last type they are accessed as. The three places you run into issues are: 1) You can treat two structs that begin with the same values interchangeably so long as you only access the common beginning of the structures. 2) You can freely convert pointers to integers and back. 3) Storage returned by malloc() can be used heterogeneously (however, with strict aliasing rules, you can't switch types of the data once you've accessed it) If you forbid those three things, then you can have a strict gc by adding runtime overhead to accessing data (once malloced data is accessed by a non-character type, you can treat it like that type forever). However, lots and lots of code violates these rules, (the most famous code that does is probably the fast inverse square-root)[1] http://betterexplained.com/articles/understanding-quakes-fast-inverse-square-root/ http://betterexplained.com/articles/understanding-quakes-fas...
recuter 13y ago
So every once in a while I come across old timey C optimizations in the spirit of Duff's device or bit twiddling to swap variables, 'etc 'etc... While they have a certain kind of charm to them they seem to be almost universally bested by increasingly mature compilers and complex (or virtualized) hardware. So I'm kind of coming to the conclusion that clever pointer arithmetic games and even manual malloc/free are increasingly futile unless you're targeting embedded devices. If a young language like Go gets you at least in the same ballpark as C with a relatively immature GC and even toy implementations like the OP take you rather far these days... when is coding without a garbage collector even really defensible anymore? I'm not trolling. I think pointer arithmetic is neat and the aforementioned "optimizations" are magical and possibly my generation has missed out on something wonderful. Seems it just isn't often practical to do that sort of thing anymore. Edit: I'd like to stress that I wasn't talking in absolutes, and asking rather than telling. I'm not sure how to phrase my post better, made some edits nonetheless.
- vinkelhake 13y ago
  What you are asking for is essentially areas of computing where you want to get the most out of the hardware. Non-casual games is one such area. Some parts of finance is another. I'm not sure why you are referring to it as "games". The high-level programming you can enjoy today rely on efficient low-level implementations. You might not see them, but they are still there and still being developed.
- scott_s 13y ago
  Someone has to implement those garbage-collected languages. If you ever want to be one of those someones, you need to learn manual memory management and raw-memory manipulation.
- lelandbatey 13y ago
  I was introduced to programming through python. Now that I'm in school, I've been doing most of my work in C++. I have to say, as much as I like programming in python, my knowledge of programming is made so much better because I've had to write C++. From an educational perspective, I think non-GC languages will always have a place (if only for teaching about computers). In production environments, I don't think that any programming practice should ever need to be "defended." Non-GC languages have their ups and downs, just as GC'ed languages have their ups and downs. Saying "it's indefensible to use one over the other" feels like saying "it's indefensible to fly somewhere instead of driving there." It doesn't make sense, since each is useful for some things and not others. Once again, when asked the question "which tool is better" my answer is "the one that's best for the job."
dysoco 13y ago
Now THIS is the kind of articles I want to see in HN. Saved for later reading, seems very interesting and well explained.
- kerkeslager 13y ago
  Did you see this a few weeks ago? http://patshaughnessy.net/2013/10/24/visualizing-garbage-collection-in-ruby-and-python/ http://patshaughnessy.net/2013/10/24/visualizing-garbage-col...
  - dysoco 13y ago
    Nope, thanks for the link!
deleted 13y ago
[deleted]
kimonos 13y ago
Nice post! It's very precise. I didn't have a hard time understanding it. Thanks for sharing!
robertk 13y ago
I don't understand. When sweep frees an object, it invalidates the "next" object of the previous object in the linked list, breaking the traversal next time a gc() is called. Doesn't the linked list have to be patched? (e.g., keep track of "prev_object" and set its next to unreached->next before freeing unreached)
- bla2 13y ago
  I think `*object = unreached->next;` does that, since it's using a pointer to a pointer.
  - munificent 13y ago
    That's correct. It patches the "next" pointer of the previous object to point past the freed object. It's a pointer to a pointer to handle the case where you're freeing the first object in the list. In that case, it's "firstObject" that needs to be modified, not some Object's "next" pointer. Using a pointer to a pointer (while admittedly harder to read at first) lets you handle both of those cases with the same code.
    - unwind 13y ago
      This technique is talked about in this Stack Overflow answer: http://stackoverflow.com/questions/12914917/using-pointers-to-remove-item-from-singly-linked-list http://stackoverflow.com/questions/12914917/using-pointers-t..., which also references this Slashdot interview (http://meta.slashdot.org/story/12/10/11/0030249/linus-torvalds-answers-your-questions http://meta.slashdot.org/story/12/10/11/0030249/linus-torval...) with Linus Torvalds where he gives this as his "favorite hack".
      - munificent 13y ago
        Yup, I got the idea for this from Linus. Before then, I've always done the uglier "if this is the first node then ..." special case branch instead.
shiraz 13y ago
Interesting, lot to learn from this
signa11 13y ago
storing the 'mark' bit with the objects themselves is not so good for COW semantics, but should be just fine for this toy example i think...
pof33 13y ago
The first paragraph is essentially this: http://www.structuredprocrastination.com/ http://www.structuredprocrastination.com/ I also suffer from this condition ;)

217 points by daw___ 13y ago

mamcx 13y ago

That was actually very easy to understand!. Thanks for that. I'm thinking in build a toy language and this make on magic thing die..

phamilton 13y ago

Not having studied the topic in depth, my first thought is whether true pointers and a garbage collector can coexist (without artificially removing parts of the language). The big condition for knowing if something is still in use is whether any references exist to it. But in a language like C , you could cast a pointer to something else (like a void pointer for some quasi generic linked list), store it somewhere, and then cast it back later after garbage collection has run. That seems like a problematic situation. So is completely giving up on pointers (or just never doing tricky things like casting or pointer arithmetic) a requirement to having a garbage collector?

city41 13y ago
I don't know of any language that has pointers and a GC. Are there any? C# lets you use pointers but only if you tell the GC to not move your object and promise to behave.
- octo_t 13y ago
  Optional GC[1] in a language like C++, and Rust has pointers with task-local GC [1] - http://en.wikipedia.org/wiki/Boehm_GC http://en.wikipedia.org/wiki/Boehm_GC
- jballanc 13y ago
  The Boehm–Demers–Weiser garbage collector is a fairly famous implementation of a GC for vanilla C, pointers and all: http://en.wikipedia.org/wiki/Boehm_garbage_collector http://en.wikipedia.org/wiki/Boehm_garbage_collector
  - city41 13y ago
    Yeah I'm aware of optional GCs. What I meant was languages that ship with a GC as standard and also have pointers. In the case of Boehm, since you choose to bring it in yourself, it's up to you to make sure you don't abuse it.
    - jballanc 13y ago
      Well, pretty much any language with a GC can abuse the GC, regardless of whether it's optional or designed in from the start. It just happens to be a lot harder to abuse a GC than to forget to free/delete something.
- Scaevolus 13y ago
  You can have a GC without compaction. Go has a GC and pointers, including internal pointers (e.g. to a field of a struct). Its GC started out fully conservative, then precise for the heap and conservative for the stack, and future versions will be fully precise.
- cwzwarich 13y ago
  Some languages in the Wirth family have pointers and GC, e.g. Modula-3. It has a module-level notion of safety, so that modules using potentially unsafe pointer manipulation are marked as unsafe and break runtime safety guarantees. It also doesn't guarantee that all pointers will be roots for GC.
- nicky0 13y ago
  Objective-C has pointers and a GC.
- wsc981 13y ago
  > "I don't know of any language that has pointers and a GC. Are there any?" Objective-C used to have a garbage collector, though (at least with regards to iOS) Apple removed this capability with the introduction or ARC. On the following URL is some discussion on the Objective-C garbage collector: http://cocoasamurai.blogspot.nl/2010/12/objective-c-memory-management-garbage.html http://cocoasamurai.blogspot.nl/2010/12/objective-c-memory-m...
  - masklinn 13y ago
    iOS never got the GC, only the desktop version got it, and afaik it was deprecated rather than removed entirely.
    - pornel 13y ago
      It's been removed entirely in Xcode 5.1.
- betterunix 13y ago
  OCaml, though in a very restricted sense: http://www.cs.cornell.edu/courses/cs3110/2011sp/recitations/rec10.htm http://www.cs.cornell.edu/courses/cs3110/2011sp/recitations/...
- pjmlp 13y ago
  > I don't know of any language that has pointers and a GC. Are there any? C# lets you use pointers but only if you tell the GC to not move your object and promise to behave Oberon, Oberon-2 allows you to use no-GC pointers via the SYSTEM package. Active Oberon additionally adds syntax support for untraced pointers. Modula-3 has unsafe modules which allow you to use untraced pointers. D has unsafe pointers in system blocks. Ada and C++11 have support for optional GC defined on the language standard. However so far, there isn't any compiler vendor that really offers them. In Java you can do a bit of dirty pointer tricks via the com.sun.unsafe package, but it is Oracle's VM specific. Although there are plans to make it part of the official library after Java 8.
- bitwize 13y ago
  Various Lisp dialects over the years have supported the use of locatives, or pointer-like objects. In general, objects which can be moved or copied around by the runtime behind the programmer's back cannot have indefinite-extent hardware-address pointers taken directly into them. This includes objects managed by most halfway-decent garbage collectors (which tend to be implemented as stop-and-copy, not mark-and-sweep), but also includes such things as drawing surfaces in SDL and DirectDraw. Many runtimes take the C# approach -- provide a memory locking operation that fixes the object in memory while you do some pointer stuff on it and a dual unlocking operation that releases the object so it can be kicked around by the runtime again.
jballanc 13y ago
When you hear talk of "conservative" Garbage Collectors, what the "conservative" refers to is that anything on the stack that looks like a pointer is treated as if it is a pointer. After all, it doesn't matter what you cast a pointer to, it's all just 1s and 0s on the stack...
- dllthomas 13y ago
  Of course, you can make something look like not a pointer and then make it a pointer again if you actually change the zeros and ones.
  - _delirium 13y ago
    Most languages don't give you any guarantees if you do that, though. In C, for example, pointer arithmetic on a void*, or on a pointer cast to an integer, is not guaranteed to produce sensible results. The standard only provides guarantees for pointer arithmetic if it's performed on a non-void pointer that points within an array, and the results remain within the bounds of the same array (arithmetic that produces a pointer pointing outside the array of the base pointer is undefined, with the exception that pointing to one element past the end of the array is defined).
    - dllthomas 13y ago
      In ordinary C, without a garbage collector, I'd be baffled to find an implementation where one could not: 1) Cast a pointer to an integer of sufficient size. 2) Xor that integer with another value. 3) Xor the result with the same value. 4) Cast back to a pointer. 5) Dereference. It's sufficiently corner-case that I am not certain what the standard says about it. In any event, pointers matter when coding in assembly, where language standards aren't even relevant.
      - aidenn0 13y ago
        That is actually allowed in the standard; it specifically says that casting a pointer to an integral type of sufficient size is a reversible operation (though it I'm not sure if this is not well defined: (int i[2]; (int )((int)i)+sizeof(int)
rayiner 13y ago
You don't need to give up pointers, or pointer arithmetic, just the ability to obscure what a pointer points to. Casting to void does not do this (and indeed, has no run time effect at all). Metadata is associated with the pointed-to block of memory, so as long as the address is recognizable as a pointer at runtime, you can do GC. Some of the things that break GC aren't even technically valid C code. For example, say I allocate three memory areas with malloc() then hold on only to the area with the lowest address, and reference the other two areas with offsets relative to the first area. This is illegal in C, though it will work on most existing implementations, because it's illegal to dereference a pointer past the end of an allocation. Specific GC algorithms might not be able to handle say pointers into the interiors of objects, but that's not a general limitation for GC.
- city41 13y ago
  Does this still work if the GC compacts memory? I don't know much about GCs, but it seems like once your GC is advanced enough with generational collecting, compacting, etc, then allowing raw pointers seems at odds with what the GC is trying todo. I'm sure it's possible, but it's probably a heck of a lot easier just to not allow pointers.
  - rayiner 13y ago
    It works fine as long as you have enough type information to know what is and is not a pointer.
- cperciva 13y ago
  it's illegal to dereference a pointer past the end of an allocation. Yes, but there's a legal way to do this. reference the other two areas with offsets relative to the first area If you cast the pointers to uintptr_t, and perform your arithmetic on uintptr_t and cast your final pointer back (void * ) before using it, what you've done is perfectly legal and safe (albeit weird) since uintptr_t is an unsigned integer type with all the flexibility of unsigned integers, and if x = (uintptr_t)p then it's guaranteed that p == (void * )x. In other words: char * x = malloc(100); char * y = malloc(100); ptrdiff_t yminusx = y - x; x[yminusx] = '\0' is undefined behaviour, but char * x = malloc(100); char * y = malloc(100); uintptr_t yminusx = (uintptr_t)(y) - (uintptr_t)(x); *(char *)(void *)((uintptr_t)(x) + yminusx) = '\0' is valid C (and has the same meaning on a DWIM compiler).
deleted 13y ago
[deleted]
bunderbunder 13y ago
C# has pointer goodness, in that you can do pointer arithmetic and bypass type safety. However, you have to declare an 'unsafe' context in which you'll do it. Unsafe contexts are tied to a local scope, which means that you can't do anything like having classes with fields of pointer types. Pointers don't outlive the function in which you use them. Also, before you can get a pointer to an object you have to "pin" it, which tells the garbage collector not to move it around. This is necessary, of course, but it can have severe performance implications since it basically torpedoes all the garbage collector's best performance optimizations. So pointers are there when you need them. . . but the language makes them extremely inconvenient to use them more than you absolutely need to. A pretty solid compromise, IMO.
- MichaelGG 13y ago
  C# can also use managed pointers (type& instead of type*). All out/ref parameters use this type of pointer, and it'll get updated by the runtime, like an object reference - no pinning necessary.
  - kevingadd 13y ago
    Interesting, can you link to an example of their use? I've never seen them in the documentation or examples, but I remember that Managed C++ and C++/CLI have something similar. Or are you just saying that you can 'use' them via out/ref? I interpreted your post to mean that you can store them in fields, which would be stellar but seems like it would break reference lifetime guarantees.
    - MichaelGG 13y ago
      You only use them via out/ref. Section 13.4.2 of the CLI spec says: - Managed pointers can be passed as arguments, stored in local variables, and returned as values. - Managed pointers cannot be stored in static variables, array elements, or fields of objects or value types. So you're right, they have very limited scope as it'd be messy otherwise. It's my understanding that the JVM does not have pointers even at this level, hence Java can't do out/ref parameters. (Sure, tuples are a better way to handle many cases of out params, but sometimes a well chosen ref can really be nicer.) I think C++ also uses the term "managed pointer" but not in the same technical sense (I think it just means reference.) Using "safe" C++/CLI generation limits the scope of pointers just like we'd expect.
aidenn0 13y ago
See this: http://www.hpl.hp.com/personal/Hans_Boehm/gc/ http://www.hpl.hp.com/personal/Hans_Boehm/gc/ But also with a very small number of restrictions, you can make C have non-conservative GC. ANSI C forbids aliasing as any type but a character. Furthermore, unions are to be interpreted as the last type they are accessed as. The three places you run into issues are: 1) You can treat two structs that begin with the same values interchangeably so long as you only access the common beginning of the structures. 2) You can freely convert pointers to integers and back. 3) Storage returned by malloc() can be used heterogeneously (however, with strict aliasing rules, you can't switch types of the data once you've accessed it) If you forbid those three things, then you can have a strict gc by adding runtime overhead to accessing data (once malloced data is accessed by a non-character type, you can treat it like that type forever). However, lots and lots of code violates these rules, (the most famous code that does is probably the fast inverse square-root)[1] http://betterexplained.com/articles/understanding-quakes-fast-inverse-square-root/ http://betterexplained.com/articles/understanding-quakes-fas...

recuter 13y ago

So every once in a while I come across old timey C optimizations in the spirit of Duff's device or bit twiddling to swap variables, 'etc 'etc... While they have a certain kind of charm to them they seem to be almost universally bested by increasingly mature compilers and complex (or virtualized) hardware. So I'm kind of coming to the conclusion that clever pointer arithmetic games and even manual malloc/free are increasingly futile unless you're targeting embedded devices. If a young language like Go gets you at least in the same ballpark as C with a relatively immature GC and even toy implementations like the OP take you rather far these days... when is coding without a garbage collector even really defensible anymore? I'm not trolling. I think pointer arithmetic is neat and the aforementioned "optimizations" are magical and possibly my generation has missed out on something wonderful. Seems it just isn't often practical to do that sort of thing anymore. Edit: I'd like to stress that I wasn't talking in absolutes, and asking rather than telling. I'm not sure how to phrase my post better, made some edits nonetheless.

vinkelhake 13y ago
What you are asking for is essentially areas of computing where you want to get the most out of the hardware. Non-casual games is one such area. Some parts of finance is another. I'm not sure why you are referring to it as "games". The high-level programming you can enjoy today rely on efficient low-level implementations. You might not see them, but they are still there and still being developed.
scott_s 13y ago
Someone has to implement those garbage-collected languages. If you ever want to be one of those someones, you need to learn manual memory management and raw-memory manipulation.
lelandbatey 13y ago
I was introduced to programming through python. Now that I'm in school, I've been doing most of my work in C++. I have to say, as much as I like programming in python, my knowledge of programming is made so much better because I've had to write C++. From an educational perspective, I think non-GC languages will always have a place (if only for teaching about computers). In production environments, I don't think that any programming practice should ever need to be "defended." Non-GC languages have their ups and downs, just as GC'ed languages have their ups and downs. Saying "it's indefensible to use one over the other" feels like saying "it's indefensible to fly somewhere instead of driving there." It doesn't make sense, since each is useful for some things and not others. Once again, when asked the question "which tool is better" my answer is "the one that's best for the job."

dysoco 13y ago

Now THIS is the kind of articles I want to see in HN. Saved for later reading, seems very interesting and well explained.

kerkeslager 13y ago
Did you see this a few weeks ago? http://patshaughnessy.net/2013/10/24/visualizing-garbage-collection-in-ruby-and-python/ http://patshaughnessy.net/2013/10/24/visualizing-garbage-col...
- dysoco 13y ago
  Nope, thanks for the link!

deleted 13y ago

[deleted]

kimonos 13y ago

Nice post! It's very precise. I didn't have a hard time understanding it. Thanks for sharing!

robertk 13y ago

I don't understand. When sweep frees an object, it invalidates the "next" object of the previous object in the linked list, breaking the traversal next time a gc() is called. Doesn't the linked list have to be patched? (e.g., keep track of "prev_object" and set its next to unreached->next before freeing unreached)

bla2 13y ago
I think `*object = unreached->next;` does that, since it's using a pointer to a pointer.
- munificent 13y ago
  That's correct. It patches the "next" pointer of the previous object to point past the freed object. It's a pointer to a pointer to handle the case where you're freeing the first object in the list. In that case, it's "firstObject" that needs to be modified, not some Object's "next" pointer. Using a pointer to a pointer (while admittedly harder to read at first) lets you handle both of those cases with the same code.
  - unwind 13y ago
    This technique is talked about in this Stack Overflow answer: http://stackoverflow.com/questions/12914917/using-pointers-to-remove-item-from-singly-linked-list http://stackoverflow.com/questions/12914917/using-pointers-t..., which also references this Slashdot interview (http://meta.slashdot.org/story/12/10/11/0030249/linus-torvalds-answers-your-questions http://meta.slashdot.org/story/12/10/11/0030249/linus-torval...) with Linus Torvalds where he gives this as his "favorite hack".
    - munificent 13y ago
      Yup, I got the idea for this from Linus. Before then, I've always done the uglier "if this is the first node then ..." special case branch instead.

shiraz 13y ago

Interesting, lot to learn from this

signa11 13y ago

storing the 'mark' bit with the objects themselves is not so good for COW semantics, but should be just fine for this toy example i think...

pof33 13y ago

The first paragraph is essentially this: http://www.structuredprocrastination.com/ http://www.structuredprocrastination.com/ I also suffer from this condition ;)