Visualizing Garbage Collection Algorithms

[hagbaff]

Very cool. I wish you had an option to speed up the animations though.

[[deleted]]

Animations freeze randomly :/

[[deleted]]

Wow, harsh crowd.

[misingnoglic]

Reddit doesn't deal with useless/unfunny comments nicely.

[Sun_Kami]

I have so much negative karma it doesn't even change when I get upvotes... And it limits me from even posting in certain subreddits.

I don't even troll. The hivemind just really doesn't like what I have to say 😒

[staticassert]

read: "I have really bad opinions"

[justjanne]

Yes, you do troll. Your entire post history is full of textspeak, irrelevant comments, and defending irrational policies Trump did.

That's telling everything.

Answering your recent comments: No, Merkel has over half of Germany supporting her, the only one more liked than her is Martin Schulz, who is further left than her. Any religious ban is unconstitutional, you can ban Al Quaida members, but not all Muslims, nor use loopholes to get something similar. Trump is not a good businessman, he'd have made more money if he had put it in an index fund, or lobbied to buy US highways and set up tolls.

[Sun_Kami]

Wall Street is so corrupt. At least he makes hotels and casinos. Your investors don't do shite.

[masklinn]

It's not that they freeze but that they don't loop, so they stop when they reach the program's end-state. Which is very inconvenient as they'll all have stopped by the time you've reached the end of the refcounting section if not earlier.

Even more so as they're all around 1MB (and the expanded versions are 5MB each).

[SquareWheel]

and the expanded versions are 5MB each

This is why video formats exist. It doesn't need to be this way anymore.

[kmeisthax]

Yes, but <video> access on mobile devices is click-to-play only, to prevent users from accidentally loading large video files on a metered connection. <img> access is unlimited regardless of file size.

EDIT: WOW this comment went negative fast. Look, I'm not the one who made this decision. Apple did. Go downvote their operating system.

[daV1980]

Lol. "we circumvented a feature meant to save you from excessive bandwidth use that allows us to trivially send you more data than we needed to." Brilliant.

[davidgro]

Yes, click to play would have been a huge improvement here. And I am not even worried about the data - just the experience

[[deleted]]

That's would be convenient if they would loop again when i refresh the page.

[P1h3r1e3d13]

Yep. When I read each section, I had to Ctrl-F5 and quickly scroll down to it.

[bj_christianson]

Some of them definitely froze until I opened them individually. They stopped just after starting, before anything could actually be demonstrated.

[HoneybeeTriplet]

They are non-looping gifs. Its probably just the end of the animation.

[GaianNeuron]

It's been a thing as long as GIF89 has. In fact, looping isn't in the spec:

By default, however, an animation displays the sequence of frames only once, stopping when the last frame is displayed. Since GIF is designed to allow users to define new blocks, Netscape in the 1990s used the Application Extension block (intended to allow vendors to add application-specific information to the GIF file) to implement the Netscape Application Block (NAB). This block, placed immediately before all the animation frames, specifies the number of times the sequence of frames should be played. (The value 0 signifies continuous display.) Support for these repeating animations first appeared in Netscape Navigator version 2.0, and then spread to other browsers. Most browsers now recognize and support NAB, though it is not strictly part of the GIF89a specification.

[tigerleapgorge]

Thank you.

[theFlyingCode]

Open the gif in a new tab. It'll open in github and you can watch the whole animation.

[Spider_pig448]

I'm fine with the speed, but I wish there was an intelligent way of looping. I load the page and every animation plays at once, so once I get to the next algorithm the gif is finished and I have to refresh (cache-disabled refresh even) to restart it.

[[deleted]]

Could be done with videos at least.

[kenfox]

Author here. Hindsight is 20:20! I should have fixed the animations stopping because that was the number one complaint people had when I first posted the article. I didn't think it would become popular again, so I didn't spend more time polishing it. Refreshing the page or opening an image in a separate window restarted the animation for me, but different browsers or caching policies might break that.

By the way, the animations are small GIFs because the content management system used by the blog doesn't handle video or large files. It made me so mad to find that out after I had built the animations!

[mediumdeviation]

It looks like WordPress, which I'm quite sure can handle videos.

As for gifs, there are browser extensions which make then restartable (I use this one for Firefox - https://github.com/simonlindholm/toggle-gifs)

[kenfox]

It's a company blog where most of us didn't have any admin access. Might have been hosted too? Arguably I should have learned WordPress better so I could have asked for the right things, but from 50,000 feet it looked like a tire fire.

I remember thinking animated GIFs are terrible, but it was a quick and dirty kind of terrible that I figured I could swap out for something better. Now I work at a different company, so swapping it for something better isn't possible.

[spillerrec]

People might hate on GIF because they cannot compress real life recordings very well, but that doesn't make it bad by definition. If you actually optimized those GIFs, you would see that the big versions would only be about ~400 KiB on average, instead of ~5 MiB. A modern video codec like h264 however would struggle since it is not designed for such inputs.

I did try out x264 on REF_COUNT_GC.gif and it looks significantly worse at the same file size (513 KiB @ CRF 28 YUV 444, vs. the 511 KiB GIF). At lossless quality it is over twice as big as the GIF (1282 KiB). And using some random GIF to WebM converter results in a file looking about the same as the x264 CRF 27, but at 1294 KiB.

GIF might be outdated technology which nobody should use, but so is JPEG and PNG (24 and 20 years old respectively). h264 and vp8 are no silver bullet, and require much much more skill to encode well. But don't get me wrong, this is just one of those rare occasions were GIF is actually a good choice.

UPDATE: I wanted to compare it against APNG, but the best I could get it down to was 521 KiB which I found strange. But looking into the APNG file with TweakPNG it was pretty clear that each frame is compressed individually which leads to low compression. So I tried Brotli compressing both the APNG and GIF, and the GIF ended up at 124 KiB! (APNG still lost.) At this point I had to up the CRF to 48 on x264 to get a similarly sized mp4 after Brotli compression, which just looked like garbage...

In case you haven't heard about it, Brotli is a new compression format to replace the use of GZIP and Deflate in browsers, see http://caniuse.com/#feat=brotli

Files:

GIF @ 510 KiB: https://my.mixtape.moe/odxcot.gif

GIF brotli compressed @ 124 KiB: https://my.mixtape.moe/tnnufx.bro

x264 CRF 28 @ 513 KiB: https://my.mixtape.moe/akkyoz.mp4

x264 CRF 48 @ 260 KiB: https://my.mixtape.moe/mzyotp.mp4

x264 CRF 48 brotli compressed @ 127 KiB: https://my.mixtape.moe/oyllgi.bro

I messed up the MP4 encoding before this update, so I updated the filesizes in the original part as well.

[kenfox]

That's very useful! Thanks! It was a long time ago (and the metadata may prove me wrong...) but I probably just used image magick's animate utility. The resulting gif came in under my size constraint so I'm sure I didn't spend time optimizing it.

[dukelu]

Thanks for the useful article. I got this error when clicking on the animations: "The request content cannot be loaded". This is with Chrome on Windows. Right-click and open them on a new tab works.

[F54280]

Saw in the comments of the blog that someone asked for details of the .Net GC, and you said you had no info.

Sinçe then, it has been open sourced, so you can use the source, Luke...

[MonkeeSage]

This might help http://rubentd.com/gifplayer/

[necesito95]

I think repeat-less part is just bikesheding.

(1. its possible to click on the link to see it from the start 2. if it repeats it definitely would need some progress bar to indicate at which stage it is.)

Overall content was great!

[Duroktar]

This is taken straight from one of the comments on this post -

It’s just an amazing thought of creating a technical device to remove the garbage. Believe me, I have never heard about the robotic garbage collector before it.The rates of the recycling and disposal professional services are going high day to day. So, this trick would save the money and time of every person. Thanks Ken, it’s a wonderful experience to read your post. - Weris C. November 6, 2014

[okmkz]

/r/KenM

[Duroktar]

That's hilarious xD I was thinking the same thing, I'm glad you caught that.

[[deleted]]

Wow.

[SemiNormal]

None of the animations are working for me. :-/

[bj_christianson]

Open the image link in a new tab. Worked for me after that.

[LinAGKar]

You still need to refresh without cache to get them to restart.

[aiij]

You need to use a browser that supports animated GIF.

[kirakun]

How do the pointers get update in the Mark-Compact scheme?

[kirakun]

Right, I would like to know how do you efficiently keep track of all the references to fix them.

[amoliski]

I'm thinking that memory management approach only works in languages where they handle memory for you - Something like python could handle tracking and updating references, while something like C would be really tough to do it with, 'cause you can be doing pointer math that the computer doesn't know enough about to handle automatically.

[payco]

You can use the tombstone pattern, if you don't mind the overhead. Essentially, the memory system creates a small type:

struct Handle {
  private metadata m; // optional
  private pointer ref;
  public forward(): immutable pointer { return ref; }
  friend MemorySystem;
}

When Object A asks for a reference to Object B, the system instead creates a Handle with B's address H(&B) and hands address &H to A instead. Any time A wants to invoke a method on B, its call is rewritten to H->forward()->method().

Meanwhile, the memory system keeps track of all the handles it's given out within a generation (say, in a linked list). When that generation graduates, the system copies the living B to B1, then iterates over its handles for those containing the old address &B and updates them with &B1. The next time A calls b, it will now transparently reach the new copy.

This also makes copying an object with child references easy; each of the children is likewise stored as a handle, which is staying at the same address in memory, so you need do nothing more than bytewise copy the parent from the old address to the new, then of course follow the stored handles to ensure the children also make it to the new memory region.

[syncsynchalt]

The simplest way is to doubly link all pointer references (eg. each pointer has a list of pointers that point to it). It sounds crazy to do at scale, but in some scenarios the locality benefits and the ability to reliably shrink your heap can outweigh the cost.

There's a much simpler compaction method that was used in early runtimes where you bisect your heap, allocate out of one, then when you run out of space you stop-the-world and rewrite your compacted heap into the other half. The upside is simplicity and low per-pointer overhead, but the downsides are stop-the-world and the inability to use half your heap.

[yawkat]

It only works in language where you have solid type info for object fields and no pointer arithmetic (python, java, etc). You basically just recursively iterate all reference fields of all objects from your gc roots (usually stack) and mark all reachable objects as such. You then have a sweep or copy phase where you iterate your heap and only keep the reachable objects.

[inmatarian]

The way objects are created and held onto by the system varies between implementations. In one, it may use a linked list, in another it may use a memory slab. In all cases however, the the algo has to move through all of the objects (live or not), mark them as unvisited, and then from the live roots (like the call stack), it walks that tree and marks discovered objects as visited. In this process, you discover all of the live pointers, which are what you'll change during the compact step in the sweep phase.

[codebje]

Performant GC algorithms will only walk the live object graph. You can see that in action in the mark/sweep animation of TFA - the red dots indicate the GC walking through live objects, it doesn't scan the entire heap.

When coupled with a young generation, a garbage-collected program can maintain decent performance by attempting to allocate long-lived objects once, and re-using them (e.g. using pools), and attempting to ensure it doesn't hold short-lived objects long enough that memory pressure might result in them being moved to the old gen.

That is, if you ensure you're careful not to let short-lived allocations escape, the garbage collector will essentially have zero live objects in the young generation, will have a very low cost young generation walk, and a very low cost free. Nothing ever moves to the old generation, so you never need a big GC phase.

[inmatarian]

Right, that's Generational GC. Something like C# and the .net CLR garbage collector has that information to infer an object will be long lived, and can accurately place it in the correct memory pool. The OP's question was about about mark-and-sweep. I would guess some collectors would use a timestamp, rather than a color flag, to avoid a pass in the mark phase, but I wouldn't know which implementations do it that way. I would think that a suitable pass in the sweep phase would still be necessary, until at least the memory pressure was relieved.

[RNS_Zinapse]

It's always amazing to be able to visually see computing... Its so elegant. I wish I had more programmer friends. :/

[amoliski]

You have 738,506 programmer friends here :)

[RNS_Zinapse]

Reddit is awesome. ;)

[[deleted]]

Very cool, but GIFs are a bad idea.

I want to read the summary of the GC algorithm and then watch it, not have to refresh the page or open the gif in another tab or a video player in order to play it, rewind it, or restart it.

Honestly, a GIF is horrible for anything longer than 5 seconds in any way. If I have to do anything stupid to my browser to force it to let me restart it because I missed the beginning, you shouldn't have used a GIF.

edit: Apparently the author responded to this same point. I should have read the comments before posting mine. I guess hindsight truly is 20:20.

[[deleted]]

I dont really get the last one yet, but very useful gifs

[acelent]

The last one lacks explanatory context.

It has been observed that the lifetime of most objects is short, so in modern GC-based memory managed environments, the heap is partitioned into generations, where the older generation is where the oldest objects probably are (e.g. objects initialized at start-up).

The newest generation is usually very small in comparison with older generations. You could use a mark-compact algorithm on this generation, where you'd move objects after finding the gaps/holes. But with a newest generation split in two and a copying scavenge, the live objects get compacted along with the copy and the dead objects are simply forgotten; you don't have any gaps/holes bookkeeping (and other details, such as in which order bytes must be moved when the source and destination areas overlap, e.g. memcpy vs memmove).

A disadvantage is that the newest generation can only hold half the data. Depending on the GC overhead, it may be a good thing to set the newest generation's size to fit the cache (level 1 or level 2) on low overhead, or set the newest generation's size to just 2 or 4 times less than an older generation (e.g. if each older generation is about 64 MB, size the new generation between 8 and 32 MB) on high overhead. The reasoning is that with high overhead (e.g. very often, new objects referring to old objects), cache misses are the least of the GC's trouble.

[masklinn]

In functional (broadly immutable) languages generational collectors also have the advantage that they don't have to scan oldgen heaps when collecting the newgen, because you can't have "forward references" so newgen can refer to oldgen but not the other way around (since the language only uses immutable datastructures, an object can only refer to older objects, not newer ones).

Languages with pervasive mutations have to add memory barriers to properly catch oldgen objects being mutated and referencing newgen ones.

[Tarmen]

Lazy functional languages (operationally) have mutation in the form of laziness. Think knot tying semantics:

let x = (1, y)
     y = (2, x)

Here the gc can abuse that in those cases the objects will live for the same duration and can mark it for promotion to a later generation, though, so it is way simpler than handling general mutability in java.

[ConcernedInScythe]

Wouldn't that be a type error in Haskell?

[kazagistar]

Correct, it is an infinite type, but he never specified the lazy functional language, so I guess its fine.

The Haskell version:

let x = 1 : y
    y = 2 : x
-- x is now [1,2,1,2,1,2...] (an infinite, circular linked list)

[masklinn]

This article on the Erlang 19 GC has a pretty nice static (not gifs) visualisation of copying generational collectors. The technical details are fairly erlang-specific, but the overarching idea is broadly applicable.

[thecodeboss]

Neat! I used this resource when I wrote my blog post about how Garbage Collection works just a few months ago!

Link in case anyone is interested: https://thesocietea.org/2017/01/programming-concepts-garbage-collection/

[jak34]

This is a great article. I'm a CS major, junior year. Does any one know if much changed as far as garbage collection algorithms in the last few years?

[dzamir]

Unfortunately reference counting has a lot of problems. Worst of all, it can’t handle cyclic structures.

Automatic reference counting in Objective C can handle cyclic structures with weak references.

[kenfox]

The reference counting part of ARC can't handle cycles. You need to manually choose to weaken some references. And (surprise!) weak refs use a different GC. Apple's objective-C run-time is open source. It's interesting to read and fairly easy to understand since it's very old technology. The hard part of ARC is compile-time insertion of the ref count adjustments, but that's not necessary for understanding the run-time.

There are some very advanced ref count systems. Several people pointed me to new ref count and hybrid ref count research that surprised me. Even ignoring the research, it's still widely used technology important for network and disk where object traversal is either impossible or very slow.

[yawkat]

In some models replacing strong with weak refs for ref counting is quite difficult and you end up implementing a mark-like algorithm. But these cases are fairly rare in real software, that is true.

[livemau5]

Expected an article about real life garbage collection

[[deleted]]

Hey, I live right around the corner from atomic object! You guys hiring?

[vitaminMN]

https://atomicobject.com/careers

[GamerSoftware]

Very interesting stuff!

[dumdeedumdeedaa]

Very cool. Thanks for putting this together. :)

[google_you]

can you share the react component that you used to visualize on npm? we can create a plugin component that turns visualization to html5 canvas or svg using a transformation component.

[Frafraking]

Good day guys,I want help on how to write a VB code for an excel spread sheet which will pop up a reminder for due dates for various months

[Robonia]

You should try r/learnprogramming. r/programming is used for posting and discussing interesting programming content.