Assault by GC

http://marcgravell.blogspot.com/2011/10/assault-by-gc.html

by lnmx • 15 years ago

129 68 15 years ago

marcgravell.blogspot.com

btmorex• 15 years ago

I'm not familiar with .NET at all, but isn't there some way that you can move a group of objects outside of the GC system and manually manage their allocation and deallocation?

Seems like doing that would be far cleaner than what they actually did and it directly addresses the problem.

lcapaldo• 15 years ago

Yes there is, and yes they did to some extent. He addresses this in the comments.

JoeAltmaier• 15 years ago

Then you have to manage their lifetimes 'manually'. Iterate, ultimately you remove GC altogether.

If GC is the future (and it seems it is) of language runtime, then some kind of control will be needed for situations like this. Different pools, explicit tagging of 'long-lived' or 'cache value' or some such during allocation?

mseebach• 15 years ago

That is what Terracotta BigMemory is supposed to do for the JVM. It gives you a way to store Java objects off the heap and thus away from the GC.

http://terracotta.org/products/bigmemory

jerf2• 15 years ago

"Different pools, explicit tagging of 'long-lived' or 'cache value' or some such during allocation?"

The idea that immediately came to my mind is that given that the site is probably load-balanced, the best thing to do would be to take the site out of the load balancer while the big GC runs, then put it back in. I wonder if there's some way to hook that GC event. So, "pools", but at a higher level.

rayiner• 15 years ago

It's possible and practical. The MPS allows you to have manually-managed pools alongside GC'ed pools in the same heap: http://www.ravenbrook.com/project/mps/

Useful for long-lived data that doesn't change frequently.

scott_s• 15 years ago

Iterate, ultimately you remove GC altogether.

I think that's reductio ad absurdum. It's typical in long-running applications to have a class of memory unlike the rest, that will live the entire lifetime of the application. I see no problem with being able to tell the GC "this memory will always be used," or just allocating it outside of the GC entirely, while still wanting all of the benefits of GC elsewhere in the application.

fpgeek3• 15 years ago

I think you've got it exactly backwards. By the time you've dealt with some of the various complexities manual memory management, for example:

  - handling memory with a dynamic lifetime 
    (with cycle detection as an important corner case)

  - improving allocation performance

  - preventing heap fragmentation

  - thread-local allocators (for multi-threaded scalability)

  ...

I think you're approaching a garbage collector. In fact, I'd even go so far as to say there is a memory-management analog for Greenspun's tenth rule:

Any sufficiently complicated, long-lived program that manually manages memory contains an ad hoc, informally-specified, bug-ridden, slow implementation of a garbage collector.

I agree there's a place for some amount of "hinting" to the garbage collector about the lifetime of some special objects, but, to me, the important thing is that you only need it for the extreme cases.

sehugg• 15 years ago

GC is a tricky problem. Even when you have a system that performs GC in the background (like Java has been doing for almost 10 years) you still are susceptible to your heap becoming fragmented and run the risk of requiring a full GC to compact the heap.

Alexey Ragozin's blog is great if you're interested in the murky details of generational GC: http://aragozin.blogspot.com/2011/06/understanding-gc-pauses...

jshen• 15 years ago

I rarely complain about someones english, but that link is very hard to read.

"Key point of generational GC is what it does need to collect entire heap each time, but just portion of it (e.g. young space)."

"This principle is based on hypnotize that most object “die young”, i.e. majority of objects are becoming garbage shortly after being allocated."

eru3• 15 years ago

> you still are susceptible to your heap becoming fragmented and run the risk of requiring a full GC to compact the heap.

But isn't the heap fragmentation a much bigger problem with malloc style memory management?

tedunangst4• 15 years ago

No, because you can allocate from different arenas if you need to. Using plain malloc may lead to fragmentation, but there's no law requiring you to use a single lowest common denominator allocator for your entire program.

moomin• 15 years ago

The most interesting aspect of this from my perspective was the importance of structs in C#. Java doesn't have this construct, making it harder to solve these problems in-memory.

barrkel• 15 years ago

You can simulate it with a bunch of parallel arrays, one array for each field of the "struct". Wrapping up such a construct in a flyweight object (I described this in a comment to the blog post) can then get much of the ease of use back (though you can't override operator== in Java).

RodgerTheGreat• 15 years ago

This is a good point, but I'd wager parallel arrays are slower because the components of a "struct" don't have spatial locality in memory- thus you have poor cache coherence. Of course, this isn't an issue if you're primarily passing the flyweight objects around and not accessing all the fields.

robfig• 15 years ago

What is the distinction between struct and a class with all public members?

msbarnett• 15 years ago

Structs are value types in C#, there's no separate memory overhead for the reference to them.

maximilianburke2• 15 years ago

As with C++, structs in C# can have private members. The big difference between structs and classes, though, is that structs are value types. This means that, for example, function local usage of struct instances can forego allocating them on the heap and instead allocate them in the program's activation records (stack frames).

Because of the semantic differnces you can't just go switching all your classes to structs and realize a significant performance difference. Code like this:

        class Foo
        {
            int bar;
        }

        public static void Func(Foo[] arrayOfFoos)
        {
            Foo f = arrayOfFoos[0];
            f.bar = 10;
        }

will break in subtle ways because you are no longer manipulating the heap allocated instance via a reference but rather a copy that was allocated local to the function.

Arrays of structs also have better cache locality which can improve performance on number crunching workloads and can also make it easier to exchange data between managed code and native code through a P/Invoke interface.

lucisferre• 15 years ago

This solution seems extreme, given the GC is just a reality of working with managed languages which is most of the web these days (.NET, Java, Ruby, etc.). Many, many heavy traffic websites solve these problems without resorting to language magic tricks. Usually with effective use of caching, or separating out the heavily accessed data in a way that is is optimized for those read operations.

This is the second StackExchange article where it feels like square peg, round hole. The first was [their ORM] (http://samsaffron.com/archive/2011/03/30/How+I+learned+to+st...) which isn't really an ORM at all (perhaps micro ORM is fair) in the traditional sense.

ajross3• 15 years ago

More often they do it just by using non-garbage-collected heap strategies. PHP, Perl, Python and (I believe) Ruby all use reference-counted allocators and don't exhibit the kind of latency explosions you see with GC algorithms.

kmontrose5• 15 years ago

Pure reference counting doesn't handle cycles. I believe those languages (and I'm pretty certain Python does) implement a periodic mark-and-sweep GC for those cycles.

So you still periods of high latency collections (in .NET only Gen2 collections are actually noticeable, not sure about other platforms). You also have the overhead of managing reference counts, which can be non-trivial; especially if you're paging as a result.

Of course, comparing GC performance between C# and Python or Ruby is sort of silly. If we were trying to hit our ~40ms Question/Show render targets on them we'd probably have lower hanging fruit than GC.

sams993• 15 years ago

I am really not following your criticism of Dapper? Without Dapper we would both need more servers AND have significantly higher latency.

There is no magic here, it is merely understanding the limitations of the .NET GC and adapting to it. XNA and trading platforms also are aware of these issues and have to follow similar patterns.

maximilianburke2• 15 years ago

Good article! Like his conclusions mention it reminded me a lot of what XNA developers were going through when it was first released in 2007.

In general garbage collectors are sensitive to the volume of objects in the heap and the number of live references, since the collector works by scanning all live objects and following all references contained. If you can't reduce the volume of memory you use explicitly then you can take a stab at reducing the memory used by various language features. Boxing value-types -- such as using a non-generic list of integers, using delegates/events/generators, using specified capacities with System.Collections.List<T>, etc., can all go a long way toward lowering overhead. Reducing the references (by moving to storing indices) can be fairly easy and can be a significant gain as well.

Disposing of IDisposable objects (via using-blocks) when you're done with them rather than waiting for the collector to harvest and/or finalize them also helps considerably.

I think in general more explicit memory usage patterns can benefit even when using a managed language -- you know more about your program and where performance matters than the garbage collector ever will.

dlss• 15 years ago

Why not model GEN-2 GC frequency, then do the following:

1. When a gen-2 is likely to occur (looks like 3 vertical lines on your chart), tell the load balancer to stop forwarding requests.

2. Let any existing connections finish.

3. Run the GC manually.

4. Ask the load balancer to start sending requests again.

This seems cleaner than marring what sounded like already complex code with additional cognitive burdens.

kmontrose5• 15 years ago

While this possible using the profiling interfaces, it's not really much simpler IMO.

What happens if more than 1 server needs to GC at the same time (or overlapping times)? You definitely don't want to pull everything out of rotation, so you'll need some coordination, and how do you determine how many servers are allowed to be pulled out? We know we can limp along on about 1/3 of our servers, but it's not a stellar end user experience; at some point you're not solving the problem, you're spreading the pain.

There are some minor annoyance this would introduce too.

We use "server in/out of rotation" as an at a glance "things are getting ill" check, if a web server has been pulled (due to slow responses to requests) it's almost invariably something that needs fixing right now. We'd lose that if pulling servers out of rotation was normal operating procedure.

This would also be a royal pain in terms of local and dev tier testing, since you've basically made the load balancer and frequent GCs a pre-requisite for thorough testing.

Of course, this remains one of the options when dealing with GC stalls; just think what Marc went with here made more sense.

ww520• 15 years ago

Actually the load balancer approach can be further simplified. Just have a shorter health check on the server, like 3 seconds. When the server is in long GC pause, its health check request from the load balancer will fail. The load balancer automatically takes it off the pool and no traffic reaches it. After GC completed, the server's health check succeeds. Load balancer adds it back to pool automatically.

It's just a simpler solution to have a group of servers with enough capacity accounting for the random GC pauses. Having short health check enables failing fast which is generally better for the users overall - their requests don't stuck in overloaded servers for a long time (GC or otherwise caused).

Roboprog• 15 years ago

As a developer working primarily in Java, I'm jealous that this is an option for the .NET (C#) people. Not jealous enough to want to work on Windows, or have to trust Mono not to get sued, but jealous, nonetheless.

Garbage collection is a wonderful option. It gets old when it's the only hammer you have.

What a joy to be able to maintain a large cache in your program, rather than having to rely on an external service. What a joy for virtual memory to actually work, rather than constantly (every 2 or 3 seconds) swapping back in something that wouldn't otherwise be used for a while, and even more frequently thrashing on L1/L2 caches.

beagle36• 15 years ago

... and everything old is new again.

The solution, which (unsurprisingly, works!) is how you did stuff in Fortran-77, APL (circa 1958). There were no iterators, so all you did was pass around one big array that contained all the data, and indices into it.

In a couple of years, they will realize that even structs are inefficient, and will go to parallel arrays - at which case the transition to Fortran/APL/J/K would be complete.

Sodel• 15 years ago

I always like reading about how people did things back when dinosaurs ruled the data center. Do you know of any web pages that detail this sort of thing?

beagle36• 15 years ago

No, unfortunately.

I'm close to 40, dinosaurish by HN/Reddit standards, but I learned Fortran mostly because back in the late 80s and early 90s essentially all numeric processing code was written either in Assembly or Fortran; and at a later stage, because I was the only one proficient in Fortran, I inherited lots of legacy code at work.

Most people my age, even if they've been programming since age 9, haven't seen any Fortran unless they're doing physics or using LAPACK.

stcredzero2• 15 years ago

GEN-2 is the final lurking place for all your long-lived data..., checking GEN-2 is a “stop the world” event – it (usually briefly) pauses your code, and does what it needs to. Now imagine you have a huge set of objects which will never be available to collect

For many years now, some Smalltalk VMs have had "permspace." You just send a message to a long lived object, and it's moved to a different part of memory considered permanent, and the GC never looks at it. No structs. Just call a function on the permanent objects. Since it's in a different space, this is also very efficient for the VM, since identifying a permanent object is just a comparison of addresses.

JoachimSchipper• 15 years ago

Wouldn't the GC still need to check for references from permspace objects? (It's probably still a noticeable performance boost.)

eru3• 15 years ago

Your language could disallow references from permspace to normal space. Or even make permspace objects immutable.

dmpk2k2• 15 years ago

Some Schemes have this too. I'd be surprised if an industrial VM, like the CLR, didn't support this.

alok-g• 15 years ago

A big problem I faced with this approach is that value types in C# are significantly restricted as compared to reference types.

See here for details: http://social.msdn.microsoft.com/Forums/en/csharplanguage/th...

They got lucky that their Customer type was simple enough.

Nitramp• 15 years ago

Structs seem like a very pragmatic solution to the truly hard problem of writing a really good GC algorithm.

Java has a whole selection of very advanced GC algorithms, and from what I hear, it's possible to mitigate most long-pause problems by careful tuning (e.g. incremental+parallel might help here). But JVM tuning is such a black art that really nobody knows how to do it ...

TL;DR worse is better.

mkilling• 15 years ago

XNA doesn't even have a generational GC, which makes writing games feel like a constant exercise in tricking the GC.

The GC's marking phase is very slow because it has to traverse the whole object graph each time, meaning you want to make the object graph as simple as possible. Arrays of structs are very efficient for the GC to scan (it can either collect the whole array or not), but working with structs is a nightmare because there's no polymorphism.

For Fluffy[1] we just used classes and tried to optimize the hotspots as an afterthought. I'm not quite satisfied with how it turned out, there's still a periodical 20-40ms lag in the game.

There is a great article about keeping heap complexity low: http://blogs.msdn.com/b/shawnhar/archive/2007/07/02/twin-pat...

[1] http://marketplace.xbox.com/en-US/Product/Fluffy-Operation-O...

elisee• 15 years ago

On Xbox 360, XNA comes with the .NET Compact Framework which indeed includes a pared-down, non-generational GC (http://msdn.microsoft.com/en-us/library/bb203912.aspx). (On Windows though you get a full .NET framework.)

As a developer for Xbox 360, I found your best bet is to:

- monitor the amount of memory allocated (print out GC.GetTotalMemory(false))

- allocate everything during loading and force a GC when you're done loading stuff.

- ensure you're not creating any garbage at all during your main loop, which will prevent the GC from kicking in at all.

Assault by GC

Related Stories