poor performance in DOMDifferenceEngine for large XMLs

[gerpres]

I'm comparing two large XMLs.
One parent element contains around 45000 children.

the multiple List.indexOf()-calls in

org.xmlunit.diff.DOMDifferenceEngine.compareNodeLists(Iterable<Node>, XPathContext, Iterable<Node>, XPathContext)

are quite expensive, since all lists contain 45000 elements, and should be replaced by a more performant data-structure.
since the data-structure seems to be 'immutable' for the matches-loop, constructing multiple Map<Node,Integer> instances that contain the indizes, cuts the required comparison-time in half for my local tests.

private static <E> Map<E, Integer> index(Collection<E> collection) {
	Map<E, Integer> indizes = new HashMap<>();

	int i = 0;
	for (E e: collection) {
		indizes.put(e, i++);
	}

	return indizes;
}

and use it like:

private ComparisonState compareNodeLists(Iterable<Node> controlSeq, final XPathContext controlContext, Iterable<Node> testSeq, final XPathContext testContext) {
   ...
   Map<Node, Integer> controlListIndizes = index(controlList);
   ...
   for (Map.Entry<Node, Node> pair: matches) {
      ...
      int controlIndex = controlListIndizes.get(control);
      ...
}

[bodewig]

Interesting. The code has not really been optimized in any way - in particular as big inputs will suffer from using DOM anyway. But if a simple change like this really speeds up things, this is wonderful.

Any chance you could create a pull request? If not I'll take care of it myself, but it may take a bit longer.

[bodewig]

@gerpres it would be good if you could check commit 012a36a - I'll publish a 2.8.4-SNAPSHOT version right now.

[bodewig]

while porting the change to XMLUnit.NET I just realized I could safe keeping a reference to the temporary list now in -> aa329de

[gerpres]

checked with my usecases. significant improvement! thanks.

[bodewig]

great, thank you

[bodewig]

I'm in the process of releasing 2.8.4 but it seems Maven central is very slow right now - probably a lot of projects are cutting new releases right now.