#7 Fixes to allow parallel boot image creation - RFE 1147315

closed
None
5
2012-09-21
2005-04-25
Ian Rogers
No

RFE 1147315 details how the opt compiler isn't
re-entrant. This patch solves this problem by fixing
problems, in most compiler phases, caused by cloning. A
cloned objects references reference the same object as
the thing that is being cloned. This has the property
of making local copies of things like the IR object
shared across all threads. As well as fixing this the
patch adds synchronization to the BURS and GlobalCSE
phases to ensure correct access to shared objects. A
number of other objects and methods are synchronized to
allow appropriate access to their static fields. The
boot image writer is modified to correctly accept the
-parallelize option. Some extra debug code to identify
where/when compiler phases throw exceptions has been
added, but this is commented out in case of performance
implications. The VM_BootImageCompiler has been
modified so that optimization plan elements and options
aren't shared.

This patch has been tested with builds using the Sun
JDK 1.4.2 client & server on a multiprocessor Pentium
4. It is expected that extra clone methods will be
required to make this patch work on the PowerPC.

To build, run jconfigure like:
./jconfigure -DOPT_ARGS="-parallelize=2" development
or to see what's happening:
./jconfigure -DOPT_ARGS="-parallelize=2 -trace" development
then run jbuild as normal.

It is noted that my current experience shows that
parallel builds are slower than serial. E.g. on a dual
pentium 4 xeon hyperthread enabled system:

Time for 1 thread:
real 13m2.977s
user 15m32.786s
sys 0m17.863s

Time for 2 threads:
real 15m23.949s
user 30m25.662s
sys 0m19.302s

Time for 3 threads:
real 16m39.713s
user 43m32.840s
sys 0m20.383s

Discussion

  • Ian Rogers

    Ian Rogers - 2005-04-25

    CVS diff of a local CVS repository showing changes made against the sourceforge CVS repository of 20/04/05 16:57

     
  • Dave Grove

    Dave Grove - 2005-04-25

    Logged In: YES
    user_id=1215435

    A couple of comments:
    (1) We need a statement of origin before we can incorporate
    a patch.

    (2) I'm not convinced that banning clone on compiler phase
    is the right solution. The way it is supposed to work (and
    maybe this is broken on some phase right now) is that the
    OptimizatonPlan holds a set of phase objects, we call
    newExecution().perform() on each phase object. So, the IR
    fields of the template objects should never get a chance to
    hold on to or share an IR object.

     
  • Ian Rogers

    Ian Rogers - 2005-04-25

    Logged In: YES
    user_id=308843

        STATEMENT OF ORIGIN FOR A SINGLE CONTRIBUTOR
    

    I, Ian Rogers__:

    (a) represent that either:

    (i) I am the only author and owner of the contributed
    software
    (described as/entitled ____),
    which was neither derived nor copied from any other
    software,
    or

    (ii) that any exception to (i) is software which was
    obtained under the
    CPL (Common Public License),

    and

    (b) hereby agree to license this contributed software under
    the CPL.

     
  • Ian Rogers

    Ian Rogers - 2005-04-25

    Logged In: YES
    user_id=308843

    I am happy for the patch to go in with the unnecessary
    clones (e.g. the ones with an overriden newExecution or
    where the behaviour matches Object.clone). The patch
    over-rides all in an attempt to find all concurrency
    problems - no small task. The problem with using
    Object.clone is it is terribly (and very commonly in the
    current code base) for two compilation threads to reference
    the same IR. You will find the code in the patch over-rides
    clone and newExecution where appropriate. This in itself
    represents an improvement.

     
  • Ian Rogers

    Ian Rogers - 2005-04-25

    Logged In: YES
    user_id=308843

    btw: the reason for over-riding clone is that newExecution
    uses clone when newExecution isn't implemented. It may be
    better to make compiler phases not implement Cloneable as
    this is where this undesired behaviour has crept in.

     
  • Dave Grove

    Dave Grove - 2005-04-25

    Logged In: YES
    user_id=1215435

    I'm still not seeing where the current design is broken and
    a compiler phase object with mutable instance state actually
    gets shared by 2 compilation threads. The main loop of the
    compiler bottoms out into a call of newExecution().perform()
    on the "global" phase objects.

    How does an IR object ever leak back into the global
    objects, or how does the clone become shared between
    compilation threads?

     
  • Ian Rogers

    Ian Rogers - 2005-04-25

    Logged In: YES
    user_id=308843

    The problem comes from the use of Object.clone, which only
    performs shallow cloning. Deep cloning is necessary when
    objects reference other objects, unless you want all
    references to be to the same object. Some odd chains of
    references exist in the Jikes RVM, for example:

    OPT_ExpandRuntimeServices references
    - OPT_Simple
    - OPT_BranchOptimizations

    OPT_Simple references
    - OPT_BranchOptimizations

    Given these chains it is possible to end up in the same
    compiler phase on separate threads without newExecution
    being called.

    To solve this problem there are 3 solutions:

    1) compiler phase has no fields - use myExecution to return
    this. The
    patch also over-rides the clone method to ensure its not
    being called.

    2) compiler phase has object fields - deep cloning should be
    performed in this circumstance to avoid potential
    concurrency problems.

    3) compiler phase has primitive type fields - shallow
    cloning is acceptable (i.e. using Object.clone) in this
    circumstance.

    Solution 3 (which was previously the default for most
    compiler phases) hasn't been used in the patch causing a
    possible inefficiency. However, I have no objections to
    future improvements making more use of shallow cloning. We
    should work toward that situation though, from a situation
    that works concurrently. This is because concurrency/clone
    bugs often mean you die seemingly randomly in compiler
    phases and the cause is difficult to repeat given the
    threaded nature of the compilation.

    The following website provides an argument against using clone:
    http://www.javapractices.com/Topic71.cjp
    if the design of compiler phases were to change then
    possibly getting rid of clone would be a good idea.

    Obviously the patch also deals with some other concurrency
    issues.

     
  • Ian Rogers

    Ian Rogers - 2005-04-25

    Logged In: YES
    user_id=308843

    In most cases the patch is concerned with newExecution
    returning this and clone throwing an exception to make sure
    it isn't used. Deep cloning fixes are more seldom.

     
  • Dave Grove

    Dave Grove - 2005-04-25

    Logged In: YES
    user_id=1215435

    ok, I'd forgotten about the places where phases keep direct
    references to other phases. I can see that those are
    fragile. Those are mostly places where the "right" thing to
    do is to rewrite the compiler phase into an explicit
    compound phase that optionally runs the "contained" phase.

    Would it be possible to break this into some smaller
    patches? For example all of the non-cloning, non-BURS
    changes in one patch. The change to BURS in a second patch.

    That would make it easier to check in the non-cloning
    changes right away while we think about whether it would be
    better to check in the cloning changes or to restructure the
    top-level design to avoid the need for cloning entirely.

    The newExecution returning 'this' is a fairly silly
    optimization I put in years ago. I strongly suspect it
    doesn't actually buy us very much in terms of compilation
    time, so it might make more sense to get rid of it then to
    add code to support it.

    My guess is that any phase that needed deep cloning is
    actually pointing to some place where the current code is
    broken (eg represents a memory leak) and should be fixed by
    rewriting it, not by implementing a deep clone.

     
  • Ian Rogers

    Ian Rogers - 2005-04-26

    Logged In: YES
    user_id=308843

    My motivation for getting this patch in is we're hoping to
    parallelise the runtime compiler. Parallel boot image
    compiles is the first step in this. It strikes me that the
    IR and compiler phases could do with a tidy up. A particular
    problem I found was that there's compilation state held
    OPT_Options (SSA), HIRInfo, SSAOptions and the IR itself. It
    means that the compiler phases aren't robust. By this I mean
    that re-ordering compiler phases causes compilation to fail.
    This robustness is linked to the concurrent compile problems
    as usually it was these objects being shared that caused the
    build to die. Being able to verify the compilation state
    meets, for example, SSA requirements aids writing and debugging.

    I think it is safe to use the patch but to remove any
    changes where I've made "newExecution" return "this". This
    should substantially reduce the number of compiler phases
    modified. I've attached a second patch which is an edited
    version of the first with these methods removed. I've
    attached a new patch which does this. This patch is 1298
    lines long instead of 2459.

    A lot of the remaining differences are caused by altering
    the indentation when a "synchronized(){...}" is inserted.
    The actual difference in the code is small.

     
  • Ian Rogers

    Ian Rogers - 2005-04-26

    An edited version of the first patch with the "return this" compiler phase optimization removed.

     
  • Dave Grove

    Dave Grove - 2005-05-13

    Logged In: YES
    user_id=1215435

    I was looking through the patch this morning.

    What do you think about changing
    OPT_OptimizationPlanAtomicElement so that instead of holding
    onto a OPT_CompilerPhase object it retains a
    java.lang.reflect.Constructor object and an Object[] of the
    parameters for that constructor.

    We also should rework all of the phases that are holding
    onto private OPT_CompilerPhase objects to be
    OPT_OptimizationPlanComposite elements. In a few cases, the
    subphases may need to communicate with each other, so we may
    need to extend OPT_OptimizationPlanCompositeElement with a
    protocol to allow inter-phase communication in a safe way.

    I think this would make it safe to share
    OPT_OptimizationPlans between threads (modulo tweaking the
    timing/stats code to make that thread safe).

    Would remove all of your concerns about clone, since we
    could remove newExecution() entirely.

    If you agree that this would work, then I'll hold off on
    commiting this patch, we'll do a separate patch just to
    change from cloning to reflection, and then do subsequent
    patches to deal with remaining issues.

    I'll have to take a closer look at BURS. I think it can be
    made thread safe by moving some static fields into instance
    fields.

     
  • Ian Rogers

    Ian Rogers - 2005-06-21

    Logged In: YES
    user_id=308843

    Hi,

    what are the plans for this patch?

    Thanks,

    Ian

     
  • Dave Grove

    Dave Grove - 2005-06-24

    Logged In: YES
    user_id=1215435

    Sorry for the slow processing. It's currently #3 on my list
    of things to deal with, but #1 is defect 1213816 which may
    take a while to clear.

    My general plan is to (1) get rid of clone as discussed
    before and then (2) incorporate non-clone related stuff from
    this patch as necessary to make the opt compiler re-entrant.

     
  • Ian Rogers

    Ian Rogers - 2005-08-17

    Logged In: YES
    user_id=308843

    Hi,

    I'm still hoping to make use of this patch. Is there any
    chance it can be committed and a more idealised solution
    worked upon when there aren't more pressing bugs.

    Apologies for nagging,

    Ian

     
  • Ian Rogers

    Ian Rogers - 2005-12-20

    Logged In: YES
    user_id=308843

    Hi Dave, what's the progress on this? I can draw up a new
    patch if you let me know how you want things re-working.
    Many thanks, Ian

     
  • Ian Rogers

    Ian Rogers - 2006-06-29

    Logged In: YES
    user_id=308843

    This patch had been stalled awaiting a change from using
    cloning to reflection. This latest diff shows the changes
    using reflection, although a small verification error needs
    resolving. I will fix this and commit if no problems are raised.

    Ian

     
  • Dave Grove

    Dave Grove - 2006-06-30

    Logged In: YES
    user_id=1215435

    (1) Let's open a defect for the BURS lock. That could
    should be made thread safe by ditching the static variables
    in favor of instance fields on the BURS object (or some
    releated object). It isn't a blocker for commiting this
    patch, but I don't want to leave the code like that.

    (2) Class.forName("...").getConstructors()[0] is a fairly
    expensive operation. Could we cache the results (check
    against instance field being null, then do the forName &
    store the results. This should also handle bootimagewriting
    ==> runtime probelms, since I believe we null out
    java.lang.Class objects (if we don't, we should in the
    bootimage writer, and that's a trivial change).

    (3) I'm nervous about code that assumes the constructors
    returned by getConstructors() are in some particular order.
    I don't think this is specified. Eg in OPT_Simple where it
    pulls constructors[4]. Would be better to look for a
    constructor with the right type signature. If we're going
    to cache the answer (#2), then I don't think we have to care
    about using a slower but safe lookup to find the constructor
    we want.

     
  • Ian Rogers

    Ian Rogers - 2006-07-03

    Logged In: YES
    user_id=308843

    Hi Dave,

    I agree with (1).

    There's been problems whenever we use (2) that the j.l.Class
    that is cached isn't correctly loaded from the bootimage (it
    needs reconstructing). In Java 1.5 the fact that this is a
    class literal saves us, with Java 1.4.2 JVMs an extra fix is
    necessary - hence using forName that avoids the problem. We
    could write an opt compiler phase that turns "t1=call
    Class.forName(StringLiteral)" to "t1=ClassLiteral". I agree
    it's a mess, hence my initial use of clone!

    I agree with (3) and will fix it, but again it will slow
    things down.

    I also need to:

    (4) resolve a runtime bug in the opt compiler
    (5) test this on PPC 32/64

    Feedback, particularly on point (2), appreciated! Thanks,

    Ian and Christos

     
  • Dave Grove

    Dave Grove - 2006-07-07

    Logged In: YES
    user_id=1215435

    (2) is a fairly localized issue, so if you measure compile
    time and we aren't adversely impacted we can live with it in
    the short run I guess. But, I think the caching should be
    pretty easy to work. Have a j.l.Class (or better,
    j.l.r.Constructor) field on the phase object. If it is
    null, look it up and cache it. Modify bootimage writer to
    always write null for instances of classes we know we can't
    carry forward (j.l.Class, j.l.r.Constructor, etc). The fact
    that it isn't doing this already is a bug we've had for a
    long time (better to get a NPE than a unusable object when
    it gets referenced at runtime).

    Sorry for the slow response; long weekend in the US for the
    4th, and I've gotten behind on things.

     
  • Ian Rogers

    Ian Rogers - 2006-09-02

    Another patch, the first that's non-functional, needs a fix to the boot image writer. Improved constructor searching and caching, unfortunately it's to caching that causes the writer problems as we can't correctly write or nullify JVM's internal classes.

     
  • Ian Rogers

    Ian Rogers - 2006-09-02

    Logged In: YES
    user_id=308843

    Hi Dave,

    I understand Mike is interested in this patch so I think
    it's important to get what I've done out of the door. I've
    done the tidy up we've said as well as ported the patch to
    svn. I've attached a new patch that should be all singing
    and dancing, except I haven't caught the following bug that
    you posted earlier in your messages:

    <Dave>
    Modify bootimage writer to always write null for instances
    of classes we know we can't carry forward (j.l.Class,
    j.l.r.Constructor, etc). The fact that it isn't doing this
    already is a bug we've had for a long time (better to get a
    NPE than a unusable object when it gets referenced at runtime).
    </Dave>

    I did a quick approximation of this, it didn't work and then
    I thought it was going to take me a while to fix - so I left
    it (other patches to get written and people waiting). So
    currently a development build will die with the
    j.l.r.Constructor bug we predicted, with the stack trace
    looking like:

    java.lang.NullPointerException
    at
    java.lang.Throwable.fillInStackTrace(Throwable.java:109)
    at java.lang.Throwable.<init>(Throwable.java:53)
    at java.lang.Exception.<init>(Exception.java:67)
    at
    java.lang.RuntimeException.<init>(RuntimeException.java:65)
    at
    java.lang.NullPointerException.<init>(NullPointerException.java:70)
    at
    com.ibm.JikesRVM.VM_Runtime.deliverHardwareException(VM_Runtime.java:643)
    at <hardware trap="">
    at
    com.ibm.JikesRVM.classloader.VM_Member.getModifiers(VM_Member.java:163)
    at
    java.lang.reflect.Constructor.getModifiers(Constructor.java:65)
    at
    java.lang.reflect.Constructor.toString(Constructor.java:139)
    at java.lang.StringBuffer.append(StringBuffer.java:348)
    at
    com.ibm.JikesRVM.opt.OPT_CompilerPhase.newExecution(OPT_CompilerPhase.java:132)
    at
    com.ibm.JikesRVM.opt.OPT_OptimizationPlanAtomicElement.perform(OPT_OptimizationPlanAtomicElement.java:79)
    at
    com.ibm.JikesRVM.opt.OPT_OptimizationPlanCompositeElement.perform(OPT_OptimizationPlanCompositeElement.java:141)
    at
    com.ibm.JikesRVM.opt.OPT_CompilationPlan.execute(OPT_CompilationPlan.java:105)
    at
    com.ibm.JikesRVM.opt.OPT_Compiler.compile(OPT_Compiler.java:217)
    at
    com.ibm.JikesRVM.VM_RuntimeCompiler.optCompile(VM_RuntimeCompiler.java:377)
    at
    com.ibm.JikesRVM.VM_RuntimeCompiler.recompileWithOpt(VM_RuntimeCompiler.java:519)
    at
    com.ibm.JikesRVM.adaptive.VM_ControllerPlan.doRecompile(VM_ControllerPlan.java:179)
    at
    com.ibm.JikesRVM.adaptive.VM_CompilationThread.run(VM_CompilationThread.java:54)

    Anyway, it's some kind of progress. If no progresses happens
    shortly we should probably file the boot image writer bug
    into the bug tracking system and I'll try to pick it up if I
    get a few spare cycles.

    Regards,
    Ian

     
  • Dave Grove

    Dave Grove - 2006-09-04

    Logged In: YES
    user_id=1215435

    Mike, assigning this patch to you since you've offered to
    help push through some of the changes.

     
  • Ian Rogers

    Ian Rogers - 2006-09-23

    Logged In: YES
    user_id=308843

    Finally closed! :-D

     

Log in to post a comment.

Get latest updates about Open Source Projects, Conferences and News.

Sign up for the SourceForge newsletter:





No, thanks