Re: Performance problems with Variable Type Analysis

[Winghong Felix KWOK <wkwok@sable.mcgill.ca>]

Hi,

I realize that Variable Type Analysis, as it stands, is very inefficient.
This is partly due to inefficiencies in the data structures and algorithms
used, but more importantly, due to the large number of classes that need
to be analyzed, as you rightly pointed out.

Unfortunately, the correctness of the VTA algorithm crucially depends on
the analysis of all the classes that are transitively referred to by
java.lang.Object, because it needs to know all the side effects of every
method that can be possibly executed. It is not easy to tell a priori
which methods are never used by the program, so VTA analyzes all
transitively reachable methods to determine which ones are actually used.
(In fact, I suspect that many of the methods analyzed are used internally
by the higher-level API, but this is hidden from the user, so one is
usually not aware of their execution.)

One alternative is to treat some classes as black boxes, and be very
conservative when approximating their effect. We haven't experimented with
such modifications, so we don't know its impact on the accuracy of the
results.

If you have any suggestions on how to improve VTA's performance, please
don't hesitate to e-mail us.

Regards,
Felix

On Tue, 18 Sep 2001, Ole Friis Ostergaard wrote:

> Hi!
>
> We're some guys that are trying to use SOOT as part of our thesis
> project, and as a part of this we would like to use the Variable Type
> Analysis that is already implemented in SOOT and is included in the
> distribution.
>
> However, it seems that for even extremely small programs, not using any
> JAVA classes except of course indirectly java.lang.Object, SOOT insists
> on loading the whole bunch of standard classes and using all this as the
> basis for creating a class hierarchy analysis, invoke graph, and the
> variable type analysis. The result: We get a lot of useless (from our
> point of view) classes analysed, causing waiting times of approximately
> 3 minutes and memory consumptions in the area of 300 MB for even the
> _very_ simplest applications. This is on 1GHz Athlon CPUs running
> HotSpot, which effectively renders the Variable Type Analysis unusable
> as part of a bigger memory analysis tool.
>
> Ideally, we would like to exclude all classes that we never make use of.
> Is there a simple way to do that? Or does anybody have any other
> suggestions on how to improve the speed of the process?
>
> Please send me a note if you want examples of the JAVA programs we've
> used, etc.
>
> --
> Ole Friis Østergaard <olef@daimi.au.dk>
>