Visualizing Garbage Collection Algorithms

mnemonik 11 years ago |

If you find this interesting, you might also enjoy "A Unified Theory of Garbage Collection" by Bacon et all: http://www.cs.virginia.edu/~cs415/reading/bacon-garbage.pdf

silentbicycle 11 years ago | |

Also, "Uniprocessor Garbage Collection Techniques" (https://ritdml.rit.edu/bitstream/handle/1850/5112/PWilsonPro...) is a great survey paper, and _The Garbage Collection Handbook_ by Jones, et. al (http://gchandbook.org/) is an excellent book covering the field as of pretty recently.

kazinator 11 years ago |

This is useful; I've been puzzled by the actual behavior of a garbage collector. For instance, you might be dismayed, after implementing generational GC, that it benchmarks worse compared to reconfiguring for pure mark and sweep. Some visualization could help explain why. Raw execution profiling isn't all that helpful because it is entangled with the program, so you have to rely on collecting and logging various statistics from the collector.

azmenthe 11 years ago |

Very cool, it would be nice if the animations looped though!

jaredmcateer 11 years ago | |

Yea kinda annoying by the time I finished reading/watching the no-gc and reference count gc the animations were all done. Even better if they were side by side.

aftbit 11 years ago | | |

Paste this into your address bar, and press Ctrl-F5 to make it loop again.

  data:text/html,<img src="http://d37rcl8t6g8sj5.cloudfront.net/wp-content/uploads/NO_GC.gif" /> <img src="http://d37rcl8t6g8sj5.cloudfront.net/wp-content/uploads/REF_COUNT_GC.gif" /> <img src="http://d37rcl8t6g8sj5.cloudfront.net/wp-content/uploads/MARK_SWEEP_GC.gif" /> <img src="http://d37rcl8t6g8sj5.cloudfront.net/wp-content/uploads/MARK_COMPACT_GC.gif" /> <img src="http://d37rcl8t6g8sj5.cloudfront.net/wp-content/uploads/COPY_GC.gif" />

kenfox 11 years ago | | |

Author here. That's a nice trick to put the animations side-by-side. Thanks!

I had looping versions of the images, but changed them to stop because it seemed confusing to not clearly see the initial and ending states. Refreshing the page to replay an image seemed to work ok, but maybe not in all browsers?

The github project has versions animating longer runtime programs. They are linked from the smaller images in the blog post and might be useful to open side-by-side when reading the text.

infogulch 11 years ago | | |

Instead of looping immediately, you could make the last frame last like 6 seconds, and perhaps have a couple seconds of all-black at the beginning.

aftbit 11 years ago | | |

I've found that even in cases where a normal refresh won't restart the animations, a Ctrl-F5 will (forcing the images to be reloaded from the server, instead of cache). This is in Firefox on Arch.

jrapdx3 11 years ago | | |

Though in this particular case, just reloading the page restarted the animations just fine. Even so, I'll try C-F5 to see if that's better.

gridspy 11 years ago | | |

What you should do to fix that is to make the very last frame and very first frame much longer. That would make the loop obvious.

Nice graphics!

esaym 11 years ago | | |

And I assume the gif that finishes first is the fastest?

ygra 11 years ago | | |

That should be the very first one as it has no GC overhead whatsoever. But I guess that was obvious from the beginning.

sriku 11 years ago |

On a total tangent, I've never been satisfied with the analogy of "garbage collection" for what memory managers do ... and tried to come up with something better [1]. Not surprisingly, it came up when I was actually washing dishes :)

[1] http://sriku.org/blog/2014/07/06/dish-washing-versus-garbage...

bengali3 11 years ago |

nice. Shows why forcing GC frequently can be counter productive, esp with the copy collector

aidenn0 11 years ago | |

Pure 2-space copy collectors are very rare. Typically they are generational, so most GCs end up only copying recently allocated data (which is much more likely to be garbage).

In general though, the more frequently you GC, the more time you spend overall doing GC. This is part of why reference counted implementations tend to be slower (amortized) than other GC algorithms.

agersant 11 years ago |

Looks great! Thanks for making this.

molixiaoge 11 years ago |

great

molixiaoge 11 years ago |

ss

frozenport 11 years ago |

Obligatory Quote:

"If Java had true garbage collection, most programs would delete themselves upon execution." -- Robert Sewell

Interestingly, this doesn't apply to Scala.

innguest 11 years ago | |

That's because the road to good code is through the gates of increasingly smarter type systems.

k__ 11 years ago | | |

[Citation needed]

;)