9 ms·

Assault by GC

129 points by lnmx 15y ago

sehugg 15y 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-in-jvm-hotspots.html http://aragozin.blogspot.com/2011/06/understanding-gc-pauses...
- jshen 15y 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."
- eru 15y 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?
  - tedunangst 15y 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.
    - fpgeek 15y ago
      That doesn't contradict his observation. Changing your program to use custom memory allocators can solve fragmentation issues, but that's a much bigger step than the changes required to avoid too many (or too expensive ) full GCs (i.e. tuning the garbage collector directly, gettting "permanent" data out of the garbage-collected heap, minimizing mutations so there's less to scan...).
      - tedunangst 15y ago
        The only times I've had difficulty solving a fragmentation problem was because a GC was involved, and rewriting the code in an effort to trick some enormous black box into doing what I wanted was a lot more difficult than just writing code that did what I wanted in the first place. ymmv.
        eru 15y ago
        I guess in theory fpgeek is right, and his great-grandparent post is in the vein of what I thought of answering. But I guess in practice tedunangst is more right at the moment. I'll welcome better garbage collection.
btmorex 15y 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 15y ago
  Yes there is, and yes they did to some extent. He addresses this in the comments.
- JoeAltmaier 15y 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 15y 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 http://terracotta.org/products/bigmemory
    - oconnor0 15y ago
      Are you aware of any other solutions for the JVM? Preferably open source.
      - elefont2 15y ago
        There is an apache incubator project http://raffaeleguidi.wordpress.com/ http://raffaeleguidi.wordpress.com/
  - jerf 15y 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.
deleted 15y ago
[deleted]
moomin 15y 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 15y 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 15y 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.
    - beagle3 15y ago
      > I'd wager parallel arrays are slower because the components of a "struct" don't have spatial locality in memory How much would you wager? I'm willing to take your money :) > Of course, this isn't an issue if you're primarily passing the flyweight objects around and not accessing all the fields. If you examine codebases, you see that this is actually the prevalent use case for objects in general. It turns out that in practice, parallel arrays are often significantly faster, because more often than not you _do_ access a lot of (memory consecutive) records, and you _don't_ access all the fields. Assume e.g. your structure has student names and numeric grades. For display purposes, you are likely to read both name and grade. However, for just about every other purpose, you are likely to scan/process grades without ever looking at the name (e.g., to compute grade statistics; or to sort by grade). And in this case, you actually have much _better_ cache locality than you would have otherwise -- and also much better memory usage compared to individual allocation of objects. Furthermore, if you take this approach, you find that your functions become type-concrete but use-generic, reducing your code footprint (both LOC and I-cache), because e.g. instead of "calcAverageGrade(student[] x)", you can just use a routine called "calcAverage(float[] x)", and call it ont he grade vector. APL, J and K take this approach to its logical conclusion. The result is programs that are 10-1000 times shorter than the idiomatically comparable Python, Java, C#, C++ etc., and that have runtimes the compare favorably with C and C++.
lucisferre 15y 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+stop+worrying+and+write+my+own+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.
- thepointyhat 15y ago
  This is usual in the .Net culture. People use "Not Invented Here" rather than leverage existing stuff because it makes them look all clever plus Microsoft give people no guidance at all that is worthless. In both the .Net and Java arenas which I've been heavily involved in since they both hit the market, I've never had to piddle around with hacks like this and I've chucked out very public stuff that handles 10 million requests an hour. Stackoverflow is an engineering misnomer.
- ajross 15y 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.
  - kmontrose 15y 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.
maximilianburke 15y 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 15y 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.
- kmontrose 15y 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 15y 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 15y 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.
beagle3 15y 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 15y 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?
  - beagle3 15y 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.
    - true_religion 15y ago
      As a 20something who has been unfortunately intimate with Fortran, I can see why people in the past would have been fanatical about C, and heck even talked about the virtues of diving into assembly rather than deal with Fortran.
stcredzero 15y 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 15y ago
  Wouldn't the GC still need to check for references from permspace objects? (It's probably still a noticeable performance boost.)
  - eru 15y ago
    Your language could disallow references from permspace to normal space. Or even make permspace objects immutable.
    - fpgeek 15y ago
      Or just track the (presumably few) mutations of permspace objects for special handling. In that case, permspace effectively becomes an infinitely long-lived generation that is never collected, only used as a source of roots.
      - stcredzero 15y ago
        Bingo. I should have written "GC only uses it as a source of roots."
- dmpk2k 15y ago
  Some Schemes have this too. I'd be surprised if an industrial VM, like the CLR, didn't support this.
alok-g 15y 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/thread/47d10fcb-2d69-451a-bb97-023f1f9113f3 http://social.msdn.microsoft.com/Forums/en/csharplanguage/th... They got lucky that their Customer type was simple enough.
Nitramp 15y 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 15y 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-paths-to-garbage-collector-nirvana.aspx http://blogs.msdn.com/b/shawnhar/archive/2007/07/02/twin-pat... [1] http://marketplace.xbox.com/en-US/Product/Fluffy-Operation-Overkill/66acd000-77fe-1000-9115-d802585508be http://marketplace.xbox.com/en-US/Product/Fluffy-Operation-O...
- elisee 15y 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 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.

129 points by lnmx 15y 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-in-jvm-hotspots.html http://aragozin.blogspot.com/2011/06/understanding-gc-pauses...

jshen 15y 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."
eru 15y 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?
- tedunangst 15y 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.
  - fpgeek 15y ago
    That doesn't contradict his observation. Changing your program to use custom memory allocators can solve fragmentation issues, but that's a much bigger step than the changes required to avoid too many (or too expensive ) full GCs (i.e. tuning the garbage collector directly, gettting "permanent" data out of the garbage-collected heap, minimizing mutations so there's less to scan...).
    - tedunangst 15y ago
      The only times I've had difficulty solving a fragmentation problem was because a GC was involved, and rewriting the code in an effort to trick some enormous black box into doing what I wanted was a lot more difficult than just writing code that did what I wanted in the first place. ymmv.
      - eru 15y ago
        I guess in theory fpgeek is right, and his great-grandparent post is in the vein of what I thought of answering. But I guess in practice tedunangst is more right at the moment. I'll welcome better garbage collection.

btmorex 15y 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 15y ago
Yes there is, and yes they did to some extent. He addresses this in the comments.
JoeAltmaier 15y 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 15y 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 http://terracotta.org/products/bigmemory
  - oconnor0 15y ago
    Are you aware of any other solutions for the JVM? Preferably open source.
    - elefont2 15y ago
      There is an apache incubator project http://raffaeleguidi.wordpress.com/ http://raffaeleguidi.wordpress.com/
- jerf 15y 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.

deleted 15y ago

[deleted]

moomin 15y 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 15y 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 15y 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.
  - beagle3 15y ago
    > I'd wager parallel arrays are slower because the components of a "struct" don't have spatial locality in memory How much would you wager? I'm willing to take your money :) > Of course, this isn't an issue if you're primarily passing the flyweight objects around and not accessing all the fields. If you examine codebases, you see that this is actually the prevalent use case for objects in general. It turns out that in practice, parallel arrays are often significantly faster, because more often than not you _do_ access a lot of (memory consecutive) records, and you _don't_ access all the fields. Assume e.g. your structure has student names and numeric grades. For display purposes, you are likely to read both name and grade. However, for just about every other purpose, you are likely to scan/process grades without ever looking at the name (e.g., to compute grade statistics; or to sort by grade). And in this case, you actually have much _better_ cache locality than you would have otherwise -- and also much better memory usage compared to individual allocation of objects. Furthermore, if you take this approach, you find that your functions become type-concrete but use-generic, reducing your code footprint (both LOC and I-cache), because e.g. instead of "calcAverageGrade(student[] x)", you can just use a routine called "calcAverage(float[] x)", and call it ont he grade vector. APL, J and K take this approach to its logical conclusion. The result is programs that are 10-1000 times shorter than the idiomatically comparable Python, Java, C#, C++ etc., and that have runtimes the compare favorably with C and C++.

lucisferre 15y 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+stop+worrying+and+write+my+own+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.

thepointyhat 15y ago
This is usual in the .Net culture. People use "Not Invented Here" rather than leverage existing stuff because it makes them look all clever plus Microsoft give people no guidance at all that is worthless. In both the .Net and Java arenas which I've been heavily involved in since they both hit the market, I've never had to piddle around with hacks like this and I've chucked out very public stuff that handles 10 million requests an hour. Stackoverflow is an engineering misnomer.
ajross 15y 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.
- kmontrose 15y 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.

maximilianburke 15y 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 15y 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.

kmontrose 15y 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 15y 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 15y 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.

beagle3 15y 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 15y 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?
- beagle3 15y 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.
  - true_religion 15y ago
    As a 20something who has been unfortunately intimate with Fortran, I can see why people in the past would have been fanatical about C, and heck even talked about the virtues of diving into assembly rather than deal with Fortran.

stcredzero 15y 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 15y ago
Wouldn't the GC still need to check for references from permspace objects? (It's probably still a noticeable performance boost.)
- eru 15y ago
  Your language could disallow references from permspace to normal space. Or even make permspace objects immutable.
  - fpgeek 15y ago
    Or just track the (presumably few) mutations of permspace objects for special handling. In that case, permspace effectively becomes an infinitely long-lived generation that is never collected, only used as a source of roots.
    - stcredzero 15y ago
      Bingo. I should have written "GC only uses it as a source of roots."
dmpk2k 15y ago
Some Schemes have this too. I'd be surprised if an industrial VM, like the CLR, didn't support this.

alok-g 15y 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/thread/47d10fcb-2d69-451a-bb97-023f1f9113f3 http://social.msdn.microsoft.com/Forums/en/csharplanguage/th... They got lucky that their Customer type was simple enough.

Nitramp 15y 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 15y 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-paths-to-garbage-collector-nirvana.aspx http://blogs.msdn.com/b/shawnhar/archive/2007/07/02/twin-pat... [1] http://marketplace.xbox.com/en-US/Product/Fluffy-Operation-Overkill/66acd000-77fe-1000-9115-d802585508be http://marketplace.xbox.com/en-US/Product/Fluffy-Operation-O...

elisee 15y 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 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.