[Soot-list] Why Spark in soot 2.2.4 slows down
Eric Bodden
eric.bodden at mail.mcgill.ca
Wed Jul 4 12:00:45 EDT 2007
Ondrej, I actually think that actually it would be the cleanest
solution if Spark would use an IdentityHashSet at those places where
comparison on identity is required. Would that be possible?
Cheers,
Eric
On 04/07/07, Eric Bodden <eric.bodden at mail.mcgill.ca> wrote:
> In addition, I saw that hashCode() had an implementation bug:
>
> P2SetVisitorInt visitor = new P2SetVisitorInt(1) {
>
> final int PRIME = 31;
>
> public void visit(Node n) {
> intValue = PRIME * intValue + n.hashCode();
> }
>
> };
> this.forall(visitor); <<<<<<<<< WAS MISSING
> return visitor.intValue;
>
> Due to the missing line, the hashcode returned would always be 0. :-(
> No surprise that leads to slow results...
>
> Eric
>
>
> On 04/07/07, Eric Bodden <eric.bodden at mail.mcgill.ca> wrote:
> > Oh, I see. Sorry about that.
> >
> > Could the same be a problem in PointsToSetReadOnly in paddle and
> > AbstractFlowSet in Soot? I added similar methods there...
> >
> > I *do* require "equal" points-to sets to be equal in terms of
> > equals/hashCode in the case of points-to sets of Spark, i.e.
> > PointsToSetInternal. However, I could maybe come up with a wrapper
> > class or something like that.
> >
> > Ondrej, feel free to commit a fix to this at your will.
> >
> > Eric
> >
> > On 04/07/07, Ondrej Lhotak <olhotak at uwaterloo.ca> wrote:
> > > I've tracked down the cause of the slowdown. It is a bug that could also
> > > cause Spark to give an incorrect (unsound) answer, though I haven't
> > > observed an input program for which this would be the case.
> > >
> > > The problem is introduced in the change:
> > > ------------------------------------------------------------------------
> > > r2465 | ebodde | 2006-08-15 20:15:52 -0400 (Tue, 15 Aug 2006) | 1 line
> > >
> > > implementation of equals/hashCode for PointsToSets in Spark
> > > ------------------------------------------------------------------------
> > >
> > > This change adds expensive equals and hashCode methods to the class
> > > PointsToSetInternal, Spark's internal representation of a points-to
> > > set. These new methods override the object identity methods on Object,
> > > on which the Spark propagation algorithm depends. Inside Spark, a
> > > PointsToSetInternal is a mutable container that holds ever-changing sets
> > > of abstract objects during the analysis. Thus, from the point of view of
> > > Spark, the appropriate notion of equality for these containers is object
> > > identity, not equality of the contents. Specifically, Spark makes a
> > > worklist (actually a set) of PointsToSetInternal's whose contents need
> > > to be further propagated. The overridden methods cause adding to the
> > > worklist to be very slow, and may prevent PointsToSetInternal's whose
> > > contents still need to be propagated from being added, if their contents
> > > happen to be the same as another PointsToSetInternal.
> > >
> > > Removing these methods from PointsToSetInternal fixes the problem. I
> > > have not committed this change yet.
> > >
> > > Ondrej
> > >
> > > On Mon, Jun 25, 2007 at 04:58:45PM -0400, Eric Bodden wrote:
> > > > Ondrej could you do the same run with hprof enabled? I think with such
> > > > a significant difference, this should easily show up in a profile.
> > > >
> > > > Eric
> > > >
> > > > On 22/06/07, Ondrej Lhotak <olhotak at uwaterloo.ca> wrote:
> > > > >Strange, I also notice a big slowdown.
> > > > >
> > > > >Also, Soot 2.2.4 gives significantly different answers than 2.2.3.
> > > > >
> > > > >If I use the pre-jimplify switch, which separates Spark time from
> > > > >Jimplification time, I get the following Spark times on soot-c:
> > > > >2.2.3: 15.3s
> > > > >2.2.4: 113.9s
> > > > >
> > > > >Something *very* weird is going on.
> > > > >
> > > > >I'm not aware of any recent changes to Spark. Has anyone been working on
> > > > >Spark?
> > > > >
> > > > >I would like to do a binary search through the Subversion revisions
> > > > >between releases 2.2.3 and 2.2.4 to determine the cause of this.
> > > > >Unfortunately, the internet is dead here at the moment, so I can't do
> > > > >that right now (and who knows when this e-mail will even go out). I'll
> > > > >be travelling all next week, so I can't investigate the problem until
> > > > >later. If someone manages to track it down, I'd be interested to hear
> > > > >what the cause is.
> > > > >
> > > > >On Thu, Jun 21, 2007 at 08:39:25AM -0400, Eric Bodden wrote:
> > > > >> Nope. No such observation here. 50s sounds pretty fast to me. Are you
> > > > >> sure it's doing the right thing? If so, maybe could you email us you
> > > > >> test case and command line?
> > > > >>
> > > > >> Eric
> > > > >>
> > > > >> On 21/06/07, Joe Qian <owqian at gmail.com> wrote:
> > > > >> >Hi everyone,
> > > > >> >
> > > > >> > Recently I moved from soot 2.2.3 to soot 2.2.4. But when testing
> > > > >old
> > > > >> >programs (also with JDK1.4.1), i found the Spark points-to analysis run
> > > > >> >much slower than before. For my small test case, the old version of
> > > > >spark
> > > > >> >run about 50s, while the new spark version have to run about 200s.
> > > > >> >I have no idea about this situation. Does any one else have similar
> > > > >> >experience?
> > > > >> >
> > > > >> > Thanks
> > > > >> >
> > > > >> >Joe
> > > > >> >_______________________________________________
> > > > >> >Soot-list mailing list
> > > > >> >Soot-list at sable.mcgill.ca
> > > > >> >http://mailman.cs.mcgill.ca/mailman/listinfo/soot-list
> > > > >> >
> > > > >> >
> > > > >>
> > > > >>
> > > > >> --
> > > > >> Eric Bodden
> > > > >> Sable Research Group
> > > > >> McGill University, Montréal, Canada
> > > > >> _______________________________________________
> > > > >> Soot-list mailing list
> > > > >> Soot-list at sable.mcgill.ca
> > > > >> http://mailman.cs.mcgill.ca/mailman/listinfo/soot-list
> > > > >>
> > > > >
> > > >
> > > >
> > > > --
> > > > Eric Bodden
> > > > Sable Research Group
> > > > McGill University, Montréal, Canada
> > > >
> > >
> >
> >
> > --
> > Eric Bodden
> > Sable Research Group
> > McGill University, Montréal, Canada
> >
>
>
> --
> Eric Bodden
> Sable Research Group
> McGill University, Montréal, Canada
>
--
Eric Bodden
Sable Research Group
McGill University, Montréal, Canada
More information about the Soot-list
mailing list