Yes it's pretty much true except the current implementation try to avoid "comparing too much" by looking for perfect identical objects with a cheap comparison before going further. As you said this approach allow us to have "better" results but can ends up being more "explosive" from a computational point of view. So far our efforts have been focused on the merge consistency and better scalability through scope reduction, content match got rewritten by reusing the Diff logic itself and assume most of the model elements are not changing.

Longer term, we intend to have a proper distance from this and then have the ability to sort the storageToSearchFor, that would lead to having the best of both worlds and quickly find the closest element.
This approach had not be implemented yet because of lack of time, but I would gladly review the work of anybody wanting to speed things up.

- Any recommended way to avoid this exponential number of comparisons?
The figure you gives makes me think our "assumption" are not valid at all in your case and you ends up in the worst case..
Is your model "completely different" ? Are you using Featuremaps ?
ProximityIndex has a ProximityMatchStats object keeping track of the computation made during the process, what is it giving to you ?

I continued to work on the "search window" capability (not ready for general consumption yet), in the meantime I also introduced a cache for the distance computation.

http://git.eclipse.org/c/emfcompare/org.eclipse.emf.compare.git/commit/?id=6350fbb63dc60973510cd27068da73767b9ee014

It cuts my comparison times on decent to big models, could you have a try and tell me how it goes for you ?

Using the same feature filter for both the Match and Diff would be a better default IMO as long as one can have provide different ones when needed.

Regarding scalability I'm currently experimenting in containing the computation by using a SEARCH_WINDOW just like EMF compare 1.x. By doing so I have quite a few changes in the way big models are matched, I'm not sure yet if these changes are "normal" or if they are problematic and I'm going through them right now. In the meantime, if you want to give it a try, here is the modified ProximityMatcher

http://pastebin.com/cPZPE1gN

edit : SEARCH_WINDOW = 1500 works well for me from a matching quality perspective.

String leftValueFromWidget = new String(getContents(true), Charsets.UTF_8);
String rightValueFromWidget = new String(getContents(false), Charsets.UTF_8);

I continued to work on the "search window" capability (not ready for general consumption yet), in the meantime I also introduced a cache for the distance computation.

http://git.eclipse.org/c/emfcompare/org.eclipse.emf.compare.git/commit/?id=6350fbb63dc60973510cd27068da73767b9ee014

It cuts my comparison times on decent to big models, could you have a try and tell me how it goes for you ?

Using the same feature filter for both the Match and Diff would be a better default IMO as long as one can have provide different ones when needed.

Regarding scalability I'm currently experimenting in containing the computation by using a SEARCH_WINDOW just like EMF compare 1.x. By doing so I have quite a few changes in the way big models are matched, I'm not sure yet if these changes are "normal" or if they are problematic and I'm going through them right now. In the meantime, if you want to give it a try, here is the modified ProximityMatcher

http://pastebin.com/cPZPE1gN

edit : SEARCH_WINDOW = 1500 works well for me from a matching quality perspective.

String leftValueFromWidget = new String(getContents(true), Charsets.UTF_8);
String rightValueFromWidget = new String(getContents(false), Charsets.UTF_8);

Using the same feature filter for both the Match and Diff would be a better default IMO as long as one can have provide different ones when needed.

Regarding scalability I'm currently experimenting in containing the computation by using a SEARCH_WINDOW just like EMF compare 1.x. By doing so I have quite a few changes in the way big models are matched, I'm not sure yet if these changes are "normal" or if they are problematic and I'm going through them right now. In the meantime, if you want to give it a try, here is the modified ProximityMatcher

http://pastebin.com/cPZPE1gN

edit : SEARCH_WINDOW = 1500 works well for me from a matching quality perspective.

You're right, I forgot to add this file. Pushed a fixing commit right now and triggered a build https://hudson.eclipse.org/hudson/job/emf-compare-master/547/

by the way, I'm gonna have to bring back chocolate at the office because of this "last minute commit before leaving".

I was going back to our initial discussion : "[..] heuristic to reduce the size of storageToSearchFor by taking only elements with the same parent as the object subject to be matched. Not working perfectly anyway, but reduced the computation time."

Would you mind sharing it with us through a patch or something ?

Didn't the cache improved your comparison times ?

Another thing, not really related, but may help you guys.
There seems to exist a JDK 1.6 usage in org.eclipse.emf.compare.ide.ui:

/org.eclipse.emf.compare.ide.ui/src/org/eclipse/emf/compare/ide/ui/internal/contentmergeviewer/text/EMFCompareTextMergeViewer.java

Line 196:

String leftValueFromWidget = new String(getContents(true), Charsets.UTF_8);
String rightValueFromWidget = new String(getContents(false), Charsets.UTF_8);

I assume you guys want to keep 1.5 compatibility. The bundles execution environment declares J2SE15... so I assume that constructor shouldn't be used.

Another thing, not really related, but may help you guys.
There seems to exist a JDK 1.6 usage in org.eclipse.emf.compare.ide.ui:

/org.eclipse.emf.compare.ide.ui/src/org/eclipse/emf/compare/ide/ui/internal/contentmergeviewer/text/EMFCompareTextMergeViewer.java

Line 196:

String leftValueFromWidget = new String(getContents(true), Charsets.UTF_8);
String rightValueFromWidget = new String(getContents(false), Charsets.UTF_8);

I assume you guys want to keep 1.5 compatibility. The bundles execution environment declares J2SE15... so I assume that constructor shouldn't be used.

Yup, that was a mistake from my side (I forgot to "git pull" before checking ... came back from holidays yesterday ).

Java 6 usage is a mistake from another member of the Team, which has been fixed yesterday. This had been introduced post-M7, so only master was affected. As Cédric said in a previous comment, someone will have to bring chocolate to the office, that's the rule here since 2007.

Other than that, any chance you could provide us with the models you are seeing these performance issues with? As Cedric mentionned, we eventually plan on having something more flexible for the content match, but for now profiling would be a lot more help to track down what goes wrong in your case with our current implementation.

I wish I could, these models represent clients code, I dont think I have permission to spread clients code

I wish we had a model obfuscator somewhere . Shuffling randomly all primitive attributes would probably suffice to have an incomprehensible model that is still representative of a "real world" use case showing these issues?

Or if you can profile and send us a snapshot of the comparison time's profiling (yourkit does a really good job http://www.yourkit.com/purchase/index.jsp)?

I believe that one of the bottlenecks we've fixed is still present in this snapshot's traces