Breadth-first vs. Depth-first
Paul.Hohensee at Sun.COM
Tue Jun 10 18:22:24 UTC 2008
'Ergo writ large' proposes a repository that would contain history of
actual runs, so no explicit training runs would be necessary. No
Tony Printezis wrote:
> Martin Buchholz wrote:
>> Thanks for the reply.
>> I continue to see parallels between code hotspots and data hotspots.
>> In both cases there are few opportunities to rectify previous bad
> Yes, but in the case of code generation, recompiling a method can be
> (generally) done in a quite low-overhead manner. However, re-arranging
> the location of objects is much much more intrusive.
>> There is no way to declare that the initialization phase of
>> the application is over, and the "money phase" is starting.
> Maybe, there should be?
>> Identifying code hotspots pays off better, because code inlining
>> may give rise to further optimizations, unlike data colocation.
>> I imagine that data colocation will increase in value over time,
>> with memory access becoming a more important part of
>> application performance.
> I totally agree with this.
>> I wonder why they y'all never seem to use a technique from the
>> AOT compiler world - provide a profiling mode to allow users
>> to run the app in for a "typical" run, then use that profiling
>> information in future runs.
> I've never been enamored with the idea, I have to say. I just don't
> know how willing customers will be to do training runs. And remember
> to redo the training runs when their code changes. And do the training
> run with a realistic input ("Hey, your GC sucks. I did a training run
> with a 1MB DB input and when I loaded 50GB, the application went
> slower." Well, yeah....).
> Given that some of our customers are lurking here, I'd love to hear
> from them on this, actually...
>> Martin (definitely *not* a hotspot engineer)
>> On Mon, Jun 9, 2008 at 8:51 AM, Tony Printezis
>> <tony.printezis at sun.com> wrote:
>>> I'm personally skeptical on whether we should pursue this further.
>>> There are
>>> a couple of reasons why.
>>> Such profiling could be expensive and I'm not convinced that we will
>>> be able
>>> to reclaim back all the extra cost (the benefit we got from
>>> depth-first was
>>> very dependent on the architecture; some architectures got a lot,
>>> some got
>>> peanuts; the latter might be penalized, instead of benefit, due to
>>> the extra
>>> Additionally, the benefit from depth-first really depends on the GC
>>> For the GCs in HotSpot, the only opportunity we have to re-arrange
>>> is when new objects are copied from the eden to the survivor spaces
>>> and from
>>> the survivor spaces to the old generation. After that, you're stuck
>>> with the
>>> order in which objects moved to the old generation, as the old
>>> typically doesn't re-order objects (UseParallelGC and
>>> UseParallelOldGC do
>>> sliding compaction and they maintain object order, CMS doesn't
>>> typically do
>>> compaction; in fact, due to its in-place de-allocation policy, CMS
>>> even guarantee that two objects that are allocated one after the
>>> other, will
>>> actually be located in the same order in the old gen).
>>> As an aside, Garbage-First:
>>> might have the edge over the other GCs in that respect, as it does
>>> (not sliding) GC in the old generation too and it might have more
>>> opportunities to re-order objects.
>>> Now, think about the following (very realistic!) scenario. An
>>> has a non-trivial initialization phase and a lot of objects created
>>> it will survive the lifetime of that application. After the
>>> phase, the application goes into a steady-state phase (this is the
>>> serving" phase). Now, you would think that the initialization and
>>> steady-state phases will have quite different access patterns (you
>>> see where
>>> this is going, aren't you?). So, the objects created during the
>>> initialization phase will be copied according to the initialization
>>> pattern, which might or might not be what you want during the
>>> phase. I think this is an example that shows that, in some (many?)
>>> when the decision would be made on which objects to cluster
>>> together, it
>>> would be made prematurely.
>>> Now, do I think depth-first was a bad idea? Nope. I think it was a good
>>> idea, not because depth-first is really good, but instead because
>>> breadth-first was pathological in many many cases.
>>> Regarding, the GC times vs. mutator speed trade-off, I was actually
>>> expecting depth-first to have exactly this effect: slower GCs, but
>>> mutator threads. Interestingly, in most tests I ran, GCs didn't slow
>>> much and, in some cases, they actually speeded up. I think this
>>> could have
>>> been due to the new order also benefiting the GC too, as well as the
>>> mutators threads.
>>> My two cents,
>>> Tony, HS GC Group
>>> Martin Buchholz wrote:
>>>> JavaOne 2008 technical session PDFs are now available
>>>> I enjoyed the discussion of breadh-first vs. depth-first GC copying
>>>> in the JavaOne talk
>>>> I'd like to suggest that this is a fruitful avenue for investigation,
>>>> if hotspot engineers go further than simply switching whole-hog
>>>> to depth-first.
>>>> Profiling can find reference fields that are rarely dereferenced,
>>>> and also ones that are likely to be dereferenced soon after the object
>>>> itself is accessed.
>>>> The former can be sequestered by the next copying GC into
>>>> an unloved-object ghetto, while the latter can be stored contiguously
>>>> with its parent object. Tricky to implement, and will certainly
>>>> make GC slower, but might make the runtime of the mutator win big.
>>>> And should be easier to implement than true object inlining.
>>>> This ought to be very similar to the moving of dead or cold code
>>>> fragments inside a method away from the hot code, that hotspot
>>>> already does.
>>> | Tony Printezis, Staff Engineer | Sun Microsystems Inc. |
>>> | | MS BUR02-311 |
>>> | e-mail: tony.printezis at sun.com | 35 Network Drive |
>>> | office: +1 781 442 0998 (x20998) | Burlington, MA01803-0902, USA |
>>> e-mail client: Thunderbird (Solaris)
More information about the hotspot-gc-dev