[Soot-list] Why Spark in soot 2.2.4 slows down

[Eric Bodden]

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