[abc] type assigner complexity in Soot

>>>>> "hendren" == Prof Laurie HENDREN <hendren@sable.mcgill.ca> writes:

    hendren> The problem is that it spends a
    hendren> huge proportion of its time (while compiling itself)
    hendren> and the type assignment in one class which has a big
    hendren> monster method implementing a parser.

Let me guess without even looking at the example: does this
method have hundreds of local variables? The type assigner does
not scale well as the number of local variables increases.

When it merges two type nodes, the type assigner uses temporary
TreeSets to remove the duplicates from the merged sets of parent
nodes and child nodes (grep suggests that this happens in
soot.jimple.toolkits.typing.TypeVariable). When the number of
locals gets high, you spend a lot of time creating TreeSets that
you immediately discard.

    hendren> I remember that you did have some solutions for
    hendren> speeding up the type assigner, but I don't remember
    hendren> if we ever integrated them or not. What is your
    hendren> memory on this? Any chance you could take a look?

No, I didn't have a solution; I had a hack which confirmed the
nature of the problem (since it did improve times on the tests
where it worked) but which is not correct (it doesn't work for
arbitrary input).

The hack was to keep the parent and child nodes as sorted lists.
That lets you eliminate duplicates in a merged list in a single
pass, without creating any TreeSet. The difficulty with this, if
I remember correctly, is that there is no guarantee that the list
which you sort at time N will still be sorted any more at time N+m,
even if you don't move the elements, since the keys may change
(in the event that any of the nodes in the list are themselves
merged with some other node).

Dealing with this properly probably requires re-engineering the
data structures used for typing. The job might even be big
enough for a 623 (?) project.
Received on Thu Sep 16 22:18:20 2004