Dependency difference calculation can be faster

[matthewhague]

I have noticed a way to significantly speed up dependency difference calculation.

Currently, in CSSDependencyList.java, the getDifferencesWith method is implemented using two nested loops, giving a quadratic compexity in the size of the dependency lists. This is slow when there are a large number of dependencies (in one example i have 15000).

This can be reduced to linear by using HashSets instead of Lists and using .remove() for each element to calculate added and missing dependencies. See lines 186-189 of CSSDependencyList in this commit to my fork. Note, implementing this requires some work harmonising hashCodes with equals functions. (E.g. see changes to CSSValueOverridingDependencies.java in the same commit.) I apologise for formatting errors and deleted whitespace showing up in the commit -- i have not been very careful keeping this tidy...

For 15k dependencies the speed up is from over 10s to about 100ms!

Curiously, using removeAll instead of iterated remove()s does not yield a speed up. I think because HashSet does not override the default removeAll implementation, which cannot use hashes.

Ps. I responded to your comment on my pull request via email (the one listed on your website). If you have not seen this, it has possibly gone to spam.

[dmazinanian]

Thanks @matthewhague,

Yes, this is smarter and much more efficient, I will definitely change my code as soon as I can.

Unfortunately I didn't get anything from you, I will get in touch with you via your university email listed on your web page.

[matthewhague]

Cool. Look forward to hearing from you.

There is another efficiency gain to be had in RefactorToSatisfyDependencies, i think. Currently you use ChocoSolver to find an ordering of the CSS rules if one exists. This is, i think, just a topological sort of a graph whose vertices are rules and edges are dependencies. Toposort in this case is essentially just a depth first search.

In this commit i changed the class to use JGraphT's toposort instead of ChocoSolver (and subsequent commits sorting out mistakes -- apologies again for formatting!). On one example i observed a reduction from 1s to .15s in the refactoring time. I will try it tonight on some larger examples.

I haven't tested its correctness though -- i should look into running your unit tests :)

[dmazinanian]

I just emailed you.

P.S. You'll be disappointed by the unit tests, I'm essentially testing nothing. I certainly need to do something there.