[Bug 316988] Removing duplicates and putting into document order takes O(n^2) Increased feature and plugin versions for 3.2.3
diff --git a/tests/org.eclipse.wst.xml.xpath2.processor.tests/src/org/eclipse/wst/xml/xpath2/processor/test/TestPerformance.java b/tests/org.eclipse.wst.xml.xpath2.processor.tests/src/org/eclipse/wst/xml/xpath2/processor/test/TestPerformance.java new file mode 100644 index 0000000..154e8c2 --- /dev/null +++ b/tests/org.eclipse.wst.xml.xpath2.processor.tests/src/org/eclipse/wst/xml/xpath2/processor/test/TestPerformance.java
@@ -0,0 +1,184 @@ +/******************************************************************************* + * Copyright (c) 2010 Jesper S Moller and others. + * All rights reserved. This program and the accompanying materials + * are made available under the terms of the Eclipse Public License v1.0 + * which accompanies this distribution, and is available at + * http://www.eclipse.org/legal/epl-v10.html + * + * Contributors: + * Jesper S Moller - initial API and implementation + *******************************************************************************/ +package org.eclipse.wst.xml.xpath2.processor.test; + +import javax.xml.parsers.DocumentBuilderFactory; +import javax.xml.parsers.ParserConfigurationException; + +import org.eclipse.wst.xml.xpath2.processor.DefaultEvaluator; +import org.eclipse.wst.xml.xpath2.processor.DynamicContext; +import org.eclipse.wst.xml.xpath2.processor.DynamicError; +import org.eclipse.wst.xml.xpath2.processor.Evaluator; +import org.eclipse.wst.xml.xpath2.processor.ast.XPath; +import org.w3c.dom.Document; +import org.w3c.dom.Element; + +public class TestPerformance extends AbstractPsychoPathTest { + + private static final String COUNT = "count"; + private static final double FUDGE_FACTOR = 1.8; + private static boolean CHATTY = true; + + private final DocumentBuilderFactory factory = DocumentBuilderFactory.newInstance(); + { + factory.setNamespaceAware(true); + } + + interface DocBuilder { + Document createDocument(int complexity) throws ParserConfigurationException; + } + + public void testLinearPerformance() throws Exception { + checkPerformance("count(for $elem in //* return 'hej')", 1, 1000, 15, new DocBuilder() { + + public Document createDocument(int complexity) throws ParserConfigurationException { + Document document = factory.newDocumentBuilder().newDocument(); + + Element root = document.createElementNS("urn:x-root","xr:Root"); + int count = 1; + document.appendChild(root); + for (int i = 0; i < complexity; ++i) { + Element child = root.getOwnerDocument().createElementNS("urn:x-child-" + (i%5+1), "c"+(i%5+1) + ":UpperChild" + (i+1)); + root.appendChild(child); + count += addChildren(child, 3) + 1; + } + document.setUserData(COUNT, count, null); + return document; + } + }); + } + + public void testDeepPerformance() throws Exception { + checkPerformance("count(for $elem in //* return 'hej')", 0, 1000, 15, new DocBuilder() { + + public Document createDocument(int complexity) throws ParserConfigurationException { + + factory.setNamespaceAware(true); + Document document = factory.newDocumentBuilder().newDocument(); + + Element root = document.createElementNS("urn:x-root","xr:Root"); + document.appendChild(root); + int count = 1; + Element current = root; + for (int i = 0; i < complexity; ++i) { + Element child = root.getOwnerDocument().createElementNS("urn:x-child-" + (i%5+1), "c"+(i%5+1) + ":UpperChild" + (i+1)); + current.appendChild(child); + count += addChildren(child, 2) + 1; + current = child; + } + + document.setUserData(COUNT, count, null); + return document; + } + }); + } + + public void testExplosivePerformance() throws Exception { + checkPerformance("count(for $elem in //* return 'hej')", 2, 11, 1, new DocBuilder() { + + public Document createDocument(int complexity) throws ParserConfigurationException { + + factory.setNamespaceAware(true); + Document document = factory.newDocumentBuilder().newDocument(); + + Element root = document.createElementNS("urn:x-root","xr:Root"); + document.appendChild(root); + int count = addChildren(root, complexity); + + document.setUserData(COUNT, count+1, null); + return document; + } + }); + } + + public void checkPerformance(String xpath, int low, int high, int step, DocBuilder builder) throws Exception { + DynamicContext dc = setupDynamicContext(null); + + XPath path = compileXPath(dc, xpath); + Document smallDoc = builder.createDocument(low); + int referenceNodeCount = (Integer)smallDoc.getUserData(COUNT); + long time = timeEvaluation(dc, path, smallDoc, referenceNodeCount); + StringBuilder sb = new StringBuilder(); + + log(sb, "First iteration " + time + " µs for " + referenceNodeCount + " nodes"); + long timePerComplexity = (long)(FUDGE_FACTOR * time / referenceNodeCount); + log(sb, "Expected bound of " + timePerComplexity + " µs per unit"); + + int violations = 0; + for (int i = low + 1; i <= high; i+=step) { + Document compareDoc = builder.createDocument(i); + int nodeCount = (Integer)compareDoc.getUserData(COUNT); + if (CHATTY) { + System.out.println("Complexity " + i + " (going to " + high + "): Trying " + nodeCount + " nodes"); + } + long measured = timeEvaluation(dc, path, compareDoc, nodeCount); + + long actualTime = measured / nodeCount; + if (CHATTY) { + System.out.println("At " + nodeCount + " units, time per unit " + actualTime + " µs"); + } + if (actualTime > timePerComplexity) { + log(sb, "At " + nodeCount + " units, the time per unit " + actualTime + " µs was too high, indicating non-linear complexity"); + if (++violations >= 3) { + fail(sb.toString()); + } + } + } + } + + private void log(StringBuilder sb, String string) { + if (CHATTY) { + System.out.println(string); + } + sb.append(string).append("\n"); + + } + + private long timeEvaluation(DynamicContext dc, XPath path, Document bigDoc, long expected) + throws DynamicError { + long before = System.nanoTime(); + Evaluator eval = new DefaultEvaluator(dc, bigDoc); + String count = eval.evaluate(path).first().string_value(); + assertEquals(""+expected, count); + long after = System.nanoTime(); + return (after-before) / 1000; + } + + /** + * Constructs a tree of equal depth and number of children + * + * @param parent Element to add children to + * @param depth Desired depth + * @return number of nodes created + */ + private int addChildren(Element parent, int depth) { + int count = 0; + for (int i = 0; i < depth*2; ++i) { + count++; + Element child = parent.getOwnerDocument().createElementNS("urn:x-child-" + (i+1), "c"+(i+1) + ":Child" + (i+1)); + parent.appendChild(child); + count += addChildren(child, depth-2); + } + return count; + } + + public static void main(String[] args) throws Exception { + TestPerformance tp = new TestPerformance(); + tp.setUp(); + try { + tp.testLinearPerformance(); +// tp.testDeepPerformance(); + } catch (Exception e) { + // Boom + } + tp.tearDown(); + } +}