The currently common form of generational GC, which typically apply a monolithic copying collectors for the youngest generation, and are supported purely by a store barrier (no barrier needed on load instructions) is generally tracked back to David Ungar's 1984 paper titled "Generation Scavenging: A non-disruptive high per- formance storage reclamation algorithm". AFAIK the real generational thing started with Lieberman & Hewitt's 1983 paper titled "A real-time garbage collector based on the lifetimes of objects" - that one was incremental (interleaves with program execution) and required barriers on load instructions.So the observation that using age to focus collection effort on young objects pays off is now about 30 years old.
On Wednesday, January 30, 2013 6:45:21 PM UTC-8, mikeb01 wrote:
--
You received this message because you are subscribed to the Google Groups "mechanical-sympathy" group.
To unsubscribe from this group and stop receiving emails from it, send an email to mechanical-symp...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
...
Kirk - Nice writeup. Interesting to see that David Ungar's most recent work has been with a subset of Smalltalk-80. The manycore RoarVM they've built for it (http://soft.vub.ac.be/~smarr/renaissance/), is using Cliff Click's pauseless generational GC algorithm (from Gil and Azul's C4).
On Thursday, January 31, 2013 9:58:19 AM UTC-8, jamie...@typesafe.com wrote:Kirk - Nice writeup. Interesting to see that David Ungar's most recent work has been with a subset of Smalltalk-80. The manycore RoarVM they've built for it (http://soft.vub.ac.be/~smarr/renaissance/), is using Cliff Click's pauseless generational GC algorithm (from Gil and Azul's C4).Ahem... It's actually Gil and Michael (Wolf)'s Pauseless GC and generational Pauseless GC (C4) algorithms... With key contributions from Cliff Click and Balaji Iyengar...
To unsubscribe from this group and stop receiving emails from it, send an email to mechanical-sympathy+unsub...@googlegroups.com.
I might be being dumb here but does it matter if objects live less than a GC cycle? We want to track the ones that live longer and for how many new generation cycles to give an idea of what gets promoted and the lifetime we should expect.
From a GC algorithm perspective it seems the right thing to have generational GC. The issues come from the fact that the young generation collection is not concurrent in modern large memory systems combined with issue of copying objects multiple times between survivor spaces as they age rather than straight promotion and have a compacting concurrent collector on the old generation. I think the generational issue is a red herring and more a case of how we better do GC concurrently.
On Saturday, February 2, 2013 7:44:03 AM UTC, Gil Tene wrote:I'm not saying it's impossible to get good data for this from statistical sampling. There may be some clever way around the below, but it's going to be very very tricky. Whenever I've tried this before (get a good feel for lifetime distribution for non-long-lived-obejcts), it basically comes down to this:The challenge with statistical lifetime sampling (e.g. sample only at natural GC frequency without making GC happen virtually all the time) is that you have no knowledge about when an object died within a GC cycle, only that it is dead (or alive) at the end of a cycle. This can give you data on the distribution of objects that survive at least one GC cycle, which we already know have a different behavior that the vast majority of allocations... Most object do die very young, and that would mean that they die without a single lifetime information sample, and before the GC cycle could determine if they are alive or dead. Using only the sample from live-at-end-of-cycle objects would completely skew your data.Without an actual GC cycle, there is no way to tell if an object is still alive or dead. This includes hacked JVMs as well as BCI stuff, JVMTI stuff, and weak or phantom ref based stuff. All of these would only get their information and actions from what a GC cycle figures out, and have nothing to act on without a trace in a mark phase (or a copy phase in the case of most newgens).So lifetime profiling of long-lived objects is fairly straight forward, but that doesn't even take a statistical sampler. Lifetime profiling of short lived (which are dominantly collected by newgen) objects is hard, unless you make newgen happen so frequently that virtually nothing gets collected in the first scan (read: unless you completely thrash your system).-- Gil.
On Friday, February 1, 2013 2:45:38 AM UTC-8, Kirk Pepperdine wrote:Ah, I should have read this before writing my previous email. I'd use some statistical sampling to try to draw down on the drag. You don't need to capture everything.. just a large enough sample size to be significant.On 2013-02-01, at 9:21 AM, Gil Tene <g...@azulsystems.com> wrote:I agree that it would be interesting redraw the graph based on more current profiles, by collecting data to from real world apps (not from benchmarks - they are the worst possible source).Unfortunately, GC logs for actual runs don't really have the data needed to draw the graph. In fact, having the data would in itself contradict the main cause for generational GC efficiency: the fact that newgen collections do not visit or collect any information about dead objects. If they did, their complexity would jump from being linear to the surviving live set to being linear to the newgen heap size, at which point they would be no more efficient than a full gc [they'd still provide a form of incremental GC, with more frequent but smaller pauses than a full GC, but they will spend even more CPU per allocated volume for doing this than a full gc would].Yes. You can get some small amount of information from the optional age distribution reporting avialable in GC logging, but that data is only about the stuff that survives at least one newgen collection. Unless the newgen is dramatically undersized and thrashing, that's a tiny percentage of the overall allocation, and you'd have no information about behavior and lifetime profile within a single newgen collection. As a simple example, there is no visibility or information at all into the lifetime and frequency of temporary (die within a frame or two) objects.It would be fairly straightforward to hack a JVM like OpenJDK into a GC-alot mode, where both newgen and oldgen collections run almost back to back STW cycles, giving the application a millisecond here and there to run between complete GC cycles, and to collect fairly accurate object lifetime distribution information with that technique. I'm not sure how we could entice people to actually run in that mode to give us useful data, since it would be a badly trashing mode...
On Thursday, January 31, 2013 10:02:00 PM UTC-8, Kirk Pepperdine wrote:I've been thinking more about the weak generational hypothesis and that long ago pub'ed graph. Though I'm sure the shape of the curve hasn't changed much I'm wondering about magnitudes. I've got tons of GC logs but they all exhibit some pathological condition so I don't have a good basis for maybe redrawing this map.. but I'm wondering if we could expand my send me your GC log campaign to see if we can redraw that chart with current data?
On 2013-02-02, at 9:26 AM, Martin Thompson <mjp...@gmail.com> wrote:I might be being dumb here but does it matter if objects live less than a GC cycle? We want to track the ones that live longer and for how many new generation cycles to give an idea of what gets promoted and the lifetime we should expect.Ok, stupid question but how long is it between GC cycles?
I might be being dumb here but does it matter if objects live less than a GC cycle? We want to track the ones that live longer and for how many new generation cycles to give an idea of what gets promoted and the lifetime we should expect.Ok, stupid question but how long is it between GC cycles?
I get that in a perfect world we would really know all object life cycles. However I'm thinking that given the constraints, does it really matter when before a new gen GC cycle an object dies.
If the new gen is sized to reasonable level for bytes collected, we could then dig in further to see what actually object are getting promoted as this is likely to be related to the domain model.For me the bytes allocated and collected is too blunt a tool to understand the actual model and for that we need objects by type. The actual types lets us better tune an application rather than guessing then experimenting to see if we can improve things.
The one significant area where I often see generational GC hurting is dealing with large batch jobs or sets of data. For example allocating a large collection of object means individual object allocation and promotion as new gen fills. It would be much better to just allocate a large array of objects/structures in the old gen directly, just like large primitive arrays, and work on them directly. Instead we end up going off heap and memory-mapping such collections into memory.
I might be being dumb here but does it matter if objects live less than a GC cycle? We want to track the ones that live longer and for how many new generation cycles to give an idea of what gets promoted and the lifetime we should expect.
The one significant area where I often see generational GC hurting is dealing with large batch jobs or sets of data. For example allocating a large collection of object means individual object allocation and promotion as new gen fills. It would be much better to just allocate a large array of objects/structures in the old gen directly, just like large primitive arrays, and work on them directly. Instead we end up going off heap and memory-mapping such collections into memory.
And if you use Azul Zing, this extra promotion (once after each minor GC) will likely be cleaned in the background anyway... May be Gil can comment on this?
... No-one (with the exception of Gil) has suggested
that there is a fundamental flaw in the design of those collectors
that have taken the generation hypothesis as an absolute (rather than
the source of an optimisation, to bring C4 back into the picture) and
placed a lower bound on the time taken for a pause for any application
that has some degree of promotion.
--
In short terms, you are right, but if there is longer natural application/business day like daily trading or 24x5 this is not such a big assumption.
I think the problem is not so much that some developers don't have a pretty good idea about the life cycle of their objects (admittedly most Java developers don't care too much, and don't need to) the problem is that the cleanup can *never ever* clean up an object you assume is there later but can allow for a trivial memory leak. e.g. The Java GC allows for short term consumption of memory by objects which are not needed if there is plenty of free memory to reduce overhead.
|
I think we are saying the same thing. |
> It's also with the state of tooling for Java compared to C++ as well as the level of difficulties in moving between Java and C++ tooling.
|
The state of the tooling is important to consider for any language. Some language are easier to write tools for, or have enough mass that they have better tools. This is one of the things which puts me off newer, cooler languages. Better tools and having more time to run them is one reason I have seen Java out perform C++ in real applications. Another reason is that having some protection from the faults of a complex system is something your need whether you have Java or C++ but in the later case you end up having to re-invent what Java supports natively which means Java can be a) more reliable and b) faster in the end.
|
> My concern isn't with leaks, it's with dangling pointers and scan for root activities.I think the problem is not so much that some developers don't have a pretty good idea about the life cycle of their objects (admittedly most Java developers don't care too much, and don't need to) the problem is that the cleanup can *never ever* clean up an object you assume is there later but can allow for a trivial memory leak. e.g. The Java GC allows for short term consumption of memory by objects which are not needed if there is plenty of free memory to reduce overhead.I think we are saying the same thing.
:-)
> It's also with the state of tooling for Java compared to C++ as well as the level of difficulties in moving between Java and C++ tooling.The state of the tooling is important to consider for any language. Some language are easier to write tools for, or have enough mass that they have better tools. This is one of the things which puts me off newer, cooler languages. Better tools and having more time to run them is one reason I have seen Java out perform C++ in real applications. Another reason is that having some protection from the faults of a complex system is something your need whether you have Java or C++ but in the later case you end up having to re-invent what Java supports natively which means Java can be a) more reliable and b) faster in the end.
Well put!!!My only other message is, don't accidentally being writing a garbage collector.. you will regret it :-)
Hi,For some applications the data that is taking up hundreds of gigabytes can be managed with strategies that are simpler than garbage collection.
VoltDB has two strategies based on no holes (de)allocation. Anytime something is deleted an object from the end of the allocator's pool is moved to fill the hole. The pools are fixed size and objects can be something like a red black tree nodes which are fixed size. Every time a tree node is moved to fill a hole the children and parent are updated to reflect the new location. Binary and character blobs are handled by allocating a tombstone that will never move to point to the blob and the blob contains a pointer to the tombstone so the tombstone can be updated if the blob is moved. Tombstones can never be deallocated, but they can be used for any kind of allocation and can be shared across different types of memory pools. Pools can be sized to fit the object type being allocated without any padding or fragmentation.
On Feb 15, 2013, at 7:30 AM, "Peter Lawrey" <peter....@gmail.com> wrote:
> ...
> This allows you to clean up any number of objects at a known point in time. It also uses int or long indecies which avoids SEG/BUS Faults.im
> ...
I'm with you on the "when I know I am allowed to throw objects away, garbage collection becomes simpler" point. E.g. defragmenting a pure-cache memory pool does not require compaction and moving of objects, just aggressive eviction.
However, an int/long index system is never superior to a pointer based system. At most it can hope to be almost-equivalent on speed, and it is never more stable.
"Avoiding" SEGVs by using integer indexes into large pre-allocated regions is not a benefit. SEGV is your friend. Virtual memory protection on pointer access does not create logic bugs; It helps detect them (at times). Without it, the same logic would just silently corrupt or miscompute stuff. 20 times out of 10, you should be much happier to trigger a SEGV, than to have the same logical bug in an int/long index system go undetected.
I'm not saying that index based storage pool management is "wrong", or even that it is "worse", just that it is never better.
-- Gil.