harmony-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Egor Pasko <egor.pa...@gmail.com>
Subject Re: [drlvm] interface call devirtualization
Date Mon, 24 Jul 2006 05:17:18 GMT
On the 0x1AD day of Apache Harmony Mikhail Fursov wrote:
> I promised to start to investigate devirtualization techniques and here is
> the first result:
> I hacked the entry-backedge profiler in DRLVM and added the dump of virtual
> methods call frequencies when VM is about to be shutted down.
> The goal is to test that the last method in class hierarchy is the most
> probable one.
> 
> The numbers I've got for different runtimes:
> 
> Eclipse startup (with a couple of opened projects):
> Number of methods compiled: 18136
> Number of virtual methods with multiple dispatches: 4676
> Percent of the top methods frequency: 76%
> 
> DeCapo bloat:
> Number of methods compiled: 1635
> Number of virtual methods with multiple dispatches: 401
> Percent of the top methods frequency: 88%
> 
> DeCapo hsqldb:
> Number of methods compiled: 2322
> Number of virtual methods with multiple dispatches: 512
> Percent of the top methods frequency: 64%
> 
> DeCapo xalan:
> Number of methods compiled: 2857
> Number of virtual methods with multiple dispatches: 824
> Percent of the top methods frequency: 59%
> 
> The results show that the heuristics to devirtualize the top  method in
> hierarchy is practical, but the frequency of 'middle' methods is too high
> and more advanced methods should be used.

Interesting results! QuickQuestions: 
* did you include interface calls in your investigations. Or is it
  just invokevirtual that you tried? 
* Why do you count number of methods with mult-dispatches? I would
  count only interface calls having multiple dispatches.

> Could I ask you or someone else to review my patch? It's a pity if I had an
> errors in it :)

Sure, I'll gratefully look at your patch and dig into understanding
your ideas, hoping to be successful :) For me it is interesting if
the patch handles the situations when classes are loaded from time to
time. We need to check each interface call for having multiple
dispatches (at runtime).

I created HARMONY-957 for the issue and attached my benchmark. You can
put your patch there, please.

> As the next task I will modify devirtualizer to select a method to
> devirtualize by the hottest frequency and will compare the results.

OK, see you soon :)

> On 20 Jul 2006 09:41:37 +0700, Egor Pasko <egor.pasko@gmail.com> wrote:
> >
> > On the 0x1AB day of Apache Harmony Mikhail Fursov wrote:
> > > > Seems like the best choice is to start from a couple of easy
> > heuristics:
> > > > * if there is only one loaded class to implement the interface, choose
> > it
> > > > * if there are more, choose the one with it's method invoked earlier
> > > > (compiled
> > > >   by some JIT, possibly, some other JIT),
> > > > * if we have many candidate methods that are compiled, choose the most
> > > > frequent
> > > >   one (need a method-entry profile, the feature is likely to stay
> > > > untouched for
> > > >   a while, I guess)
> > > >
> > > >
> > > > 1. Does anybody have some additional elegant ideas?
> > > >
> > > >
> > > Egor,  I'm interested in devirtualizer improvement too.
> >
> > Great!
> >
> > > IMO the profile based devirtualization will probably have the best
> > results
> > > and is easy to implement and to check: infrastructure in Jitrino is
> > ready to
> > > do it right now with a help of entry-backedge profile collected for OPT
> > by
> > > JET.
> >
> > OK, if it is not so difficult to use the profile. BTW, if I have a
> > backedge in my HIR, how do I identify it with JET's backedge? Or is
> > this done automatically in some way I should not care about?
> >
> > > + more ideas I have:
> > > 1) to use edge profiler as value based one if initial compilation
> > > devirtualize all possible dispatches and count their edge frequencies.
> >
> > Oh, that's a real code bloater!:) IMHO, inlining of these 'possible
> > dispatches' should be disabled. Needs to make a hint for inliner. Not
> > a difficult task though. Just an extra flag in call instruction.
> >
> > > 2) implement a real value profiler - this is not an easy task, but may
> > be
> > > reused in other optimizations
> >
> > Yes, sure. This is a big item for ongoing development.
> >
> > > 3) Add special annotations to classlib code about the most probable
> > > dispatch. E.g. if the variable type does not depend on user's
> > environment
> > > and developer can prove that 90% of time the variable is of specific
> > class -
> > > JIT can read this annotation from method during the compilation and to
> > > devirtualize it.
> >
> > Okay, waiting for 1.5 support here. I like the idea of writing
> > annotations for devirtualization, parallelization, and other. They can
> > provide hints without changing program semantics. I think, they should
> > be available not only in classlib, but for user code too.
> >
> > > I will read more about other devirtualization techniques we can use and
> > will
> > > reply in a several days with results.
> >
> > That would be great! Thanks for ideas!
> >
> > --
> > Egor Pasko, Intel Managed Runtime Division
> >
> >
> > ---------------------------------------------------------------------
> > Terms of use : http://incubator.apache.org/harmony/mailing.html
> > To unsubscribe, e-mail: harmony-dev-unsubscribe@incubator.apache.org
> > For additional commands, e-mail: harmony-dev-help@incubator.apache.org
> >
> >
> 
> 
> -- 
> Mikhail Fursov
> 
> ---------------------------------------------------------------------
> Terms of use : http://incubator.apache.org/harmony/mailing.html
> To unsubscribe, e-mail: harmony-dev-unsubscribe@incubator.apache.org
> For additional commands, e-mail: harmony-dev-help@incubator.apache.org

-- 
Egor Pasko, Intel Managed Runtime Division


---------------------------------------------------------------------
Terms of use : http://incubator.apache.org/harmony/mailing.html
To unsubscribe, e-mail: harmony-dev-unsubscribe@incubator.apache.org
For additional commands, e-mail: harmony-dev-help@incubator.apache.org


Mime
View raw message