Testers needed for Kiama performance problems

[Tony Sloane]

Some Kiama users have experienced slowdowns due to our naive implementation of Relations and Trees in Kiama 2. E.g., when pattern-matching using a tree.parent relation.

The current Kiama master contains changes that significantly improve the performance. For example, our benchmarks show that common operations take constant (low) time rather than depending on the size of the relation or tree.

Hopefully things are much better with the latest version. If you have seen slowdowns and have time to try your code with a recent master, please let us know how it goes. If all is well we will release a new version in January.

cheers,

Tony

[Miguel Branco]

Great thank you. I have a couple of cases where this can be tested;
I'll give it a try this week & let you know. Should I use Kiama from
the head or is this now published?

> --
> You received this message because you are subscribed to the Google Groups
> "kiama" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to kiama+un...@googlegroups.com.
> To post to this group, send email to ki...@googlegroups.com.
> Visit this group at https://groups.google.com/group/kiama.
> For more options, visit https://groups.google.com/d/optout.

[Tony Sloane]

Thanks Miguel. Please use the head version. I don't want to publish quite yet, probably in the first part of January if everything goes ok.

cheers,

Tony

[Miguel Branco]

I'm just starting with this; we have a fairly large-ish test base, and
doing a dump of the new JAR, I see a few 2-5% speedup in the running
time; while it seems reproducible, it's not very large.
The bigger issue we had was in RelationLike.scala (reverse lookup; I
believe due to tree.parent use, but honestly I don't recall & need to
check). This was only circumvented with a (admittedly hacky path) that
builds another reverse graph. This was by very far the biggest issue;
not sure your changes touch it?
If it helps, you may want to take a look at the changes we made
(attached); these are files we include in our project to override the
default Kiama ones.

In any case, I'm investigating further, since I literally only started
moments ago.

[Miguel Branco]

Just to confirm some observations from yesterday: if I run with the
new code but without our patches (the ones I sent yesterday), our
total test runtime increases (about 30-40% slower; there's one single
case where it is orders of magnitude slower without the patch; that's
when a node has, well, *many* children). If I run with the new code
and our patches, it's a few percent faster. So at least in our case,
the fix doesn't fundamentally solve it; on the upside, the code seems
to work flawlessly!

[Tony Sloane]

Hi Miguel,

Thanks for your observations. I’m not sure I understand why your tests are showing increased runtime for the new version, since at the very least we have replaced some embarrassing linear searches with map lookups, so performance on non-small trees should be be much better. Or am I missing something?

I have just pushed a new commit that makes some further improvements, mostly tidying things up in the Relation, Tree and Memoiser components.

From my measurements this new version should be a bit faster than the one we had last year (for many reasons). I suspect we will never be able to match a plain IdentityHashMap as you use in your patches. Based on other user’s experience with the library we need weak keys at least. We are currently using Guava’s MapMaker to make maps which seem to give us lookups that are a bit faster than the corresponding Cache collections that we were using at the end of last year.

Any other info on your measurements you can provide would be helpful. Are they available somewhere so I can try them out?

thanks,

Tony

[Miguel Branco]

Hi all,

Sorry for re-surfacing this.

As part of a Kiama 2.1 -> Kiama 2.4 migration, we removed some performance-related patches that we had put in place.

These focused on a few areas. For instance:

- reducing object creation by removing the use immutable structures for queues and stacks (e.g. TreeRelation set)

- avoiding the NonLocalControlReturn exception, which is used by Scala when doing a return inside a closure (e.g. TreeRelation isLeaf, allProduct, allTraversable, etc). Code is rewritten to use while loops essentially.

At the time, these made a visible difference, particularly when dealing with larger ASTs. I do recall NonLocalControlReturn exception consuming significant CPU time for instance.

Admittedly, there is some hope that newer scalac's do a better job at these, although they are likely still an issue.

We haven't isolated a benchmark; but before we consider embarking on that, and perhaps attempting some PRs upstream, I'd like to ask if anyone has looked at similar-ish performance issues?

Thanks!

[Tony Sloane]

Hi Miguel,

I’m not aware of anyone out there who has Kiama performance enhancements.

If you’re willing to give me access to your customised version and point me to where you made improvements, I’m happy to look at measuring their effect and incorporating them in the next realise. No need to do a formal PR.

cheers,

Tony

To view this discussion on the web visit https://groups.google.com/d/msgid/kiama/5e791fcb-e355-4bf7-ade6-36f2e0ac7f3cn%40googlegroups.com.