6 ms·

Rare Are GC Talks

adamnemecek 14y ago
Articles like this are exactly why I come to HN.
- pat_shaughnessy 14y ago
  Agreed! Also, beyond the great tech content there's something charming about this one.
alinajaf 14y ago
Interesting that there's no mention of generational GC in this article. Anyone with a bit more expertise care to comment on why not?
- jimm 14y ago
  Yeah, I noticed that. I first heard of generational GC in association with Smalltalk VMs and I think that's where they made their debut.
  - cwzwarich 14y ago
    The first generational garbage collector was for Lisp: http://web.media.mit.edu/~lieber/Lieberary/GC/Realtime/Realtime.html http://web.media.mit.edu/~lieber/Lieberary/GC/Realtime/Realt...
- msbarnett 14y ago
  It isn't mentioned because the author chose not to include it. Whether that's because this isn't meant to be a complete survey of the field and the author didn't think it fit the introductory nature of the piece, or because it didn't fit within the time limits of the talk this article is based on, or because Ruby doesn't do generational optimizations and the author saw no reason to wander down that path, isn't a question that expertise in gc algorithms gives much insight into.
- maximilianburke 14y ago
  I'm guessing it's either because of scope or because generational collectors are a type of copying collector. Instead of having just from/to spaces that the objects ping-pong between as they fill up, a generational collector will copy objects from one heap generation to the next as they fill. Once the oldest generation (tenured space) reaches capacity it cannot trickle down the live objects to another generation so some other method, like a mark+sweep+compacting method, is used for collecting it. You could probably have a half space tenured generation but half space collectors are not really space-efficient without resorting to a bunch of virtual memory mapping trickery, and the tenured space tends to be large.
- deleted 14y ago
  [deleted]
gue5t 14y ago
The reference counting metaphor leaves out a critical aspect of reference-counting: cyclical structures and how to collect them. Books never write their names in other books so this doesn't appear in his discussion, though it's one of the more important complications for implementations.
- marblar 14y ago
  Extend the metaphor: Mr. B also has to write his name on people who he thinks he will need in the future, lest they be fired.
- electrograv 14y ago
  Honestly, this article is really bad and probably harmful to new programmers. I recommend against taking anything in it to be accurate, much less complete. The author misses vitally key issues (like the inherent dangers of circular references in reference counting "GC"). I wouldn't even call myself slightly knowledgeable in GC, yet blatant holes in the clumsy analogies of this article are obvious to me. As someone who is not even slightly knowledgable in GC, it scares me that people are learning from someone who has massive information holes in the explanation -- holes in topics that every programmer on earth should know. On top of all that, the only "Cons" that are mentioned of RC are absurd: "It's annoying if you forget to release your references." Wow. Profound stuff there - bugs and incorrect code is annoying. This isn't even a problem if your language supports RAII, in which it's impossible to "forget" in the first place.
  - Groxx 14y ago
    I sincerely doubt people are going to read this, and then immediately write and ship a garbage collector. For a square-zero general-idea overview to someone who has zero concept of what a GC does, it's more than accurate enough. It could probably be about 1/2 the size, as it shoots off in weirdly-complex directions for such an introductory text. And it could probably introduce e.g. reference cycles, because they're a real problem with reference counting. But it's a clearer and simpler text by far than I generally see on this topic.
kenmazy 14y ago
Another great GC discussion for LuaJit: http://wiki.luajit.org/New-Garbage-Collector http://wiki.luajit.org/New-Garbage-Collector
kmm 14y ago
I don't see how a Copying GC can be faster than Mark and Sweep. Transferring a book may be easy, but copying an object can be quite costly. I can't imagine copying almost all objects everytime the GC runs.
- tomp 14y ago
  in OCaml, copying GC is used only in the young generation. functional languages allocate lots of shortly lived objects, so copying gc is a good fit, since allocation is the cheapest possible, and as only a few objecta survive a gc, the cost of copying them is low. Since the GC is generational, objecta get copied at most n times, for some n.
  - riffraff 14y ago
    the JVM (HotSpot) also uses this approach, the young generation is handled by a copying GC while the older one(s) use mark & sweep. (to be fair, I believe this _was_ the default GC option, but it's not anymore, and there were at least 3 different young generation GC algorithms that used copying, so it's a bit more nuanced)
- skybrian 14y ago
  Copying is faster if the memory to be collected is mostly garbage. You only copy the good stuff and don't even look at the garbage. Many programs (particularly in scripting languages) allocate memory but only use it for a short time, so they create lots of garbage. Often this is combined with generational garbage collection - new objects live for a short time in a temporary area, and then if they are still in use (not garbage), they get copied to longer-term storage.
  - jeffdavis 14y ago
    Copying also means moving to new addresses. What strategies are used to update the referencing pointers to the new location?
    - 14y ago
ctide 14y ago
At the December 2008 Kyushu Ruby 01 Conference, I asked the audience "How many of you here have some interest in garbage collection?" Out of 200 people, only 3 raised their hands Can you imagine how many people would raise their hands if you asked that question NOW at a ruby conference? Crazy how times change.
- notatoad 14y ago
  can you explain a bit why that has changed? I don't really know anything about ruby, but I would have thought that being able to ignore abstractions like garbage collection was the reason that people used high-level languages. Does programming in ruby involve a lot of interaction with the garbage collector, or are you saying that a lot of the ruby community is actually becoming involved with writing and improving low-level language features?
  - suresk 14y ago
    My experience in this regard comes from Java, not Ruby, but I think the basic concepts are the same: You are correct in that, for a lot of uses, ignoring abstractions like GC is just fine. If you are building something that uses a lot of memory, requires high throughput or low latency, or are getting into situations where GC is taking up a decent chunk of your CPU time, then it can pay to have a better understanding of the GC concepts so you can make beneficial changes to your application or to the GC parameters. Plus, stuff like GC is kind of interesting by itself for some people. Some of my favorite sessions at JavaOne were always the GC and JVM internals ones, despite the fact that their immediate utility to me wasn't always obvious.
  - ctide 14y ago
    One of the biggest problems with the 1.8.x versions of MRI (or CRuby as it's referred to in this article) is that the GC is pretty slow and tends to get called a lot. A good explanation of the reasons behind that can be found here: http://www.engineyard.com/blog/2010/mri-memory-allocation-a-primer-for-developers/ http://www.engineyard.com/blog/2010/mri-memory-allocation-a-... As Rails got more popular and sites built on Rails got bigger, people started running into performance issues that could often be rooted down to GC being called over and over during a single web request (due to instantiation of lots of AR objects, causing lots of memory allocations which lead to GC being called.) This lead to people exploring other implementations of Ruby (REE, Rubinius, etc.) and more importantly, becoming a lot more familiar with how GC works in MRI and how to program around it's shortcomings.
deleted 14y ago
[deleted]
drostie 14y ago
One of the most fun discussions of the complications of reference counting and how nuanced you have to be comes from the Python docs: http://docs.python.org/extending/extending.html#reference-counts http://docs.python.org/extending/extending.html#reference-co... It relates "a true story. An older version of Python contained variants of this bug and someone spent a considerable amount of time in a C debugger to figure out why his __del__() methods would fail" in a considerable amount of detail.
grimlck 14y ago
nice introduction, but it seems to be missing some really important concepts - generational GC - concurrent GC, the parts of GC which can be concurrent (which depends on your algorithm), and the tradeoffs needed to let your program run concurrently with the GC without stopping the world.
davnola 14y ago
I recommend Elise Huard's recent talk on Ruby GC: http://skillsmatter.com/podcast/home/ruby-bin-men http://skillsmatter.com/podcast/home/ruby-bin-men (Also, I'd love to see the Hungarian Folk Dance interpretation of different GC approaches http://t.co/l8ADbEQR http://t.co/l8ADbEQR)
silentbicycle 14y ago
Wilson's highly readable "Uniprocessor Garbage Collection Techniques" is a far better overview: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.138.5038 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.138.... You could write a decent GC with just the info in that paper. It doesn't cover parallel or real-time garbage collection (which both get far more complicated); for those, you want Jones et. al's _The Garbage Collection Handbook_ (http://www.amazon.com/The-Garbage-Collection-Handbook-Management/dp/1420082795/ http://www.amazon.com/The-Garbage-Collection-Handbook-Manage...) and plenty of time to explore its bibliography. (His older book is also good, but doesn't cover those topics.)
- mattyb 14y ago
  That is a good paper. Thanks for the pointer!
zem 14y ago
very nice article. given its likely target audience, though, he really needs to explain explicitly why mark-and-sweep can't compact as it goes, rather than leaving a fragmented heap.
cronin101 14y ago
In the article he states "[for Copying] Conservative GC is unable to determine the difference between pointer and integer values. If an integer value was overwritten the result would be disastrous. It is likely that the result of 1+1 would change occasionally." However reading through the RHG, it is shown that Ruby allocates memory for objects in 20 byte blocks and that this results in all pointers therefore being multiples of four. This is handy as it allows the direct usage of literals such as FixNum (an always odd 'pointer' that you shift right by one bit to access the value) and Symbol (a 'pointer' that always has 0xff as the trailing byte that you shift right 1 byte to access the unique ID) without requiring object creation. With this in mind, can someone enlighten me as to why Copying could not be used inside Ruby? It seems as though it would be trivial for the GC to differentiate between literals and pointers as otherwise they would not be much use as literals.

Articles like this are exactly why I come to HN.

pat_shaughnessy 14y ago
Agreed! Also, beyond the great tech content there's something charming about this one.

Interesting that there's no mention of generational GC in this article. Anyone with a bit more expertise care to comment on why not?

jimm 14y ago
Yeah, I noticed that. I first heard of generational GC in association with Smalltalk VMs and I think that's where they made their debut.
- cwzwarich 14y ago
  The first generational garbage collector was for Lisp: http://web.media.mit.edu/~lieber/Lieberary/GC/Realtime/Realtime.html http://web.media.mit.edu/~lieber/Lieberary/GC/Realtime/Realt...
msbarnett 14y ago
It isn't mentioned because the author chose not to include it. Whether that's because this isn't meant to be a complete survey of the field and the author didn't think it fit the introductory nature of the piece, or because it didn't fit within the time limits of the talk this article is based on, or because Ruby doesn't do generational optimizations and the author saw no reason to wander down that path, isn't a question that expertise in gc algorithms gives much insight into.
maximilianburke 14y ago
I'm guessing it's either because of scope or because generational collectors are a type of copying collector. Instead of having just from/to spaces that the objects ping-pong between as they fill up, a generational collector will copy objects from one heap generation to the next as they fill. Once the oldest generation (tenured space) reaches capacity it cannot trickle down the live objects to another generation so some other method, like a mark+sweep+compacting method, is used for collecting it. You could probably have a half space tenured generation but half space collectors are not really space-efficient without resorting to a bunch of virtual memory mapping trickery, and the tenured space tends to be large.
deleted 14y ago
[deleted]

gue5t 14y ago

The reference counting metaphor leaves out a critical aspect of reference-counting: cyclical structures and how to collect them. Books never write their names in other books so this doesn't appear in his discussion, though it's one of the more important complications for implementations.

marblar 14y ago
Extend the metaphor: Mr. B also has to write his name on people who he thinks he will need in the future, lest they be fired.
electrograv 14y ago
Honestly, this article is really bad and probably harmful to new programmers. I recommend against taking anything in it to be accurate, much less complete. The author misses vitally key issues (like the inherent dangers of circular references in reference counting "GC"). I wouldn't even call myself slightly knowledgeable in GC, yet blatant holes in the clumsy analogies of this article are obvious to me. As someone who is not even slightly knowledgable in GC, it scares me that people are learning from someone who has massive information holes in the explanation -- holes in topics that every programmer on earth should know. On top of all that, the only "Cons" that are mentioned of RC are absurd: "It's annoying if you forget to release your references." Wow. Profound stuff there - bugs and incorrect code is annoying. This isn't even a problem if your language supports RAII, in which it's impossible to "forget" in the first place.
- Groxx 14y ago
  I sincerely doubt people are going to read this, and then immediately write and ship a garbage collector. For a square-zero general-idea overview to someone who has zero concept of what a GC does, it's more than accurate enough. It could probably be about 1/2 the size, as it shoots off in weirdly-complex directions for such an introductory text. And it could probably introduce e.g. reference cycles, because they're a real problem with reference counting. But it's a clearer and simpler text by far than I generally see on this topic.

kenmazy 14y ago

Another great GC discussion for LuaJit: http://wiki.luajit.org/New-Garbage-Collector http://wiki.luajit.org/New-Garbage-Collector

kmm 14y ago

I don't see how a Copying GC can be faster than Mark and Sweep. Transferring a book may be easy, but copying an object can be quite costly. I can't imagine copying almost all objects everytime the GC runs.

tomp 14y ago
in OCaml, copying GC is used only in the young generation. functional languages allocate lots of shortly lived objects, so copying gc is a good fit, since allocation is the cheapest possible, and as only a few objecta survive a gc, the cost of copying them is low. Since the GC is generational, objecta get copied at most n times, for some n.
- riffraff 14y ago
  the JVM (HotSpot) also uses this approach, the young generation is handled by a copying GC while the older one(s) use mark & sweep. (to be fair, I believe this _was_ the default GC option, but it's not anymore, and there were at least 3 different young generation GC algorithms that used copying, so it's a bit more nuanced)
skybrian 14y ago
Copying is faster if the memory to be collected is mostly garbage. You only copy the good stuff and don't even look at the garbage. Many programs (particularly in scripting languages) allocate memory but only use it for a short time, so they create lots of garbage. Often this is combined with generational garbage collection - new objects live for a short time in a temporary area, and then if they are still in use (not garbage), they get copied to longer-term storage.
- jeffdavis 14y ago
  Copying also means moving to new addresses. What strategies are used to update the referencing pointers to the new location?
  - 14y ago

ctide 14y ago

At the December 2008 Kyushu Ruby 01 Conference, I asked the audience "How many of you here have some interest in garbage collection?" Out of 200 people, only 3 raised their hands Can you imagine how many people would raise their hands if you asked that question NOW at a ruby conference? Crazy how times change.

notatoad 14y ago
can you explain a bit why that has changed? I don't really know anything about ruby, but I would have thought that being able to ignore abstractions like garbage collection was the reason that people used high-level languages. Does programming in ruby involve a lot of interaction with the garbage collector, or are you saying that a lot of the ruby community is actually becoming involved with writing and improving low-level language features?
- suresk 14y ago
  My experience in this regard comes from Java, not Ruby, but I think the basic concepts are the same: You are correct in that, for a lot of uses, ignoring abstractions like GC is just fine. If you are building something that uses a lot of memory, requires high throughput or low latency, or are getting into situations where GC is taking up a decent chunk of your CPU time, then it can pay to have a better understanding of the GC concepts so you can make beneficial changes to your application or to the GC parameters. Plus, stuff like GC is kind of interesting by itself for some people. Some of my favorite sessions at JavaOne were always the GC and JVM internals ones, despite the fact that their immediate utility to me wasn't always obvious.
- ctide 14y ago
  One of the biggest problems with the 1.8.x versions of MRI (or CRuby as it's referred to in this article) is that the GC is pretty slow and tends to get called a lot. A good explanation of the reasons behind that can be found here: http://www.engineyard.com/blog/2010/mri-memory-allocation-a-primer-for-developers/ http://www.engineyard.com/blog/2010/mri-memory-allocation-a-... As Rails got more popular and sites built on Rails got bigger, people started running into performance issues that could often be rooted down to GC being called over and over during a single web request (due to instantiation of lots of AR objects, causing lots of memory allocations which lead to GC being called.) This lead to people exploring other implementations of Ruby (REE, Rubinius, etc.) and more importantly, becoming a lot more familiar with how GC works in MRI and how to program around it's shortcomings.

deleted 14y ago

[deleted]

drostie 14y ago

One of the most fun discussions of the complications of reference counting and how nuanced you have to be comes from the Python docs: http://docs.python.org/extending/extending.html#reference-counts http://docs.python.org/extending/extending.html#reference-co... It relates "a true story. An older version of Python contained variants of this bug and someone spent a considerable amount of time in a C debugger to figure out why his __del__() methods would fail" in a considerable amount of detail.

grimlck 14y ago

nice introduction, but it seems to be missing some really important concepts - generational GC - concurrent GC, the parts of GC which can be concurrent (which depends on your algorithm), and the tradeoffs needed to let your program run concurrently with the GC without stopping the world.

davnola 14y ago

I recommend Elise Huard's recent talk on Ruby GC: http://skillsmatter.com/podcast/home/ruby-bin-men http://skillsmatter.com/podcast/home/ruby-bin-men (Also, I'd love to see the Hungarian Folk Dance interpretation of different GC approaches http://t.co/l8ADbEQR http://t.co/l8ADbEQR)

silentbicycle 14y ago

Wilson's highly readable "Uniprocessor Garbage Collection Techniques" is a far better overview: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.138.5038 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.138.... You could write a decent GC with just the info in that paper. It doesn't cover parallel or real-time garbage collection (which both get far more complicated); for those, you want Jones et. al's _The Garbage Collection Handbook_ (http://www.amazon.com/The-Garbage-Collection-Handbook-Management/dp/1420082795/ http://www.amazon.com/The-Garbage-Collection-Handbook-Manage...) and plenty of time to explore its bibliography. (His older book is also good, but doesn't cover those topics.)

mattyb 14y ago
That is a good paper. Thanks for the pointer!

zem 14y ago

very nice article. given its likely target audience, though, he really needs to explain explicitly why mark-and-sweep can't compact as it goes, rather than leaving a fragmented heap.

cronin101 14y ago

In the article he states "[for Copying] Conservative GC is unable to determine the difference between pointer and integer values. If an integer value was overwritten the result would be disastrous. It is likely that the result of 1+1 would change occasionally." However reading through the RHG, it is shown that Ruby allocates memory for objects in 20 byte blocks and that this results in all pointers therefore being multiples of four. This is handy as it allows the direct usage of literals such as FixNum (an always odd 'pointer' that you shift right by one bit to access the value) and Symbol (a 'pointer' that always has 0xff as the trailing byte that you shift right 1 byte to access the unique ID) without requiring object creation. With this in mind, can someone enlighten me as to why Copying could not be used inside Ruby? It seems as though it would be trivial for the GC to differentiate between literals and pointers as otherwise they would not be much use as literals.