Пакет javax.xml.xpath (Java 1.4) предоставляет пользователю независимый API для вычисления XPath выражений.
По умолчанию используется Sun’овская реализация всех классов из этого пакета. Работая с этой имплементацией была обнаружена одна интересная вещь.
По мере углубления в DOM-дерево (Document Object Model), скорость вычисления одних и тех же XPath выражений постепенно падает.
В этой статье я хочу продемонстрировать описанную проблему, а также предложить альтернативный способ работы с сильноветвящимся DOM-деревом при вычислении XPath.

Допустим, у нас есть дерево, корневой элемент (root) которого содержит множество дочерних элементов с повторяющейся структурой.
В DTD это выглядело бы следующим образом:

<!ELEMENT root (elem+)>
<!ELEMENT elem (elem_1*, elem_2*, ..., elem_n*)>
<!ELEMENT elem_1 (elem_1_1*, elem_1_2*, ..., elem_1_n*)>
...

Рассмотрим следующий класс (import опущен):

public class TestXPath {
    public static final int ELEMENTS = 20;
    public static final int DEEP = 1500;

    public static final String ELEM_NAME = "element";
    public static final String SLASH = "/";

    private Document document = null;
    private Document tempDocument = null;
    private String xPathStr = null;

    public void setUp() throws Exception {
        document = DocumentBuilderFactory.newInstance()
                .newDocumentBuilder().newDocument();
        Node node = document.createElement(ELEM_NAME);
        document.appendChild(node);
        for (int i = 0; i < ELEMENTS; i++) {
            Node nodeParent = document.createElement(ELEM_NAME + 0);
            node.appendChild(nodeParent);
            for (int j = 1; j < DEEP; j++) {
                Node nodeChild = document.createElement(ELEM_NAME + j);
                nodeParent.appendChild(nodeChild);
                nodeParent = nodeChild;
            }
        }
        StringBuffer buf = new StringBuffer(ELEM_NAME);
        buf.append(1);
        for (int i = 2; i < DEEP; i++) {
            buf.append(SLASH).append(ELEM_NAME).append(i);
        }
        xPathStr = buf.toString();

        tempDocument = DocumentBuilderFactory.newInstance()
                .newDocumentBuilder().newDocument();
    }

    public void testXPath() throws Exception {
        XPath xPath = XPathFactory.newInstance().newXPath();
        Node root = document.getDocumentElement();
        Node node = root.getFirstChild();
        for (; node != null; node = node.getNextSibling()) {
            if (node.getNodeType() == Node.ELEMENT_NODE) {
                xPath.evaluate(xPathStr, node, XPathConstants.NODE);
            }
        }
    }

    public void testImport() throws Exception {
        XPath xPath = XPathFactory.newInstance().newXPath();
        Node root = document.getDocumentElement();
        Node node = root.getFirstChild();
        for (; node != null; node = node.getNextSibling()) {
            if (node.getNodeType() == Node.ELEMENT_NODE) {
                Node tempRoot = tempDocument.importNode(node, true);
                tempDocument.appendChild(tempRoot);
                xPath.evaluate(xPathStr, tempDocument
                        .getDocumentElement(), XPathConstants.NODE);
                tempDocument.removeChild(tempRoot);
            }
        }
    }

    public static void main(String[] args) throws Exception {
        TestXPath test = new TestXPath();

        test.setUp();

        long start = System.currentTimeMillis();
        test.testXPath();
        long end = System.currentTimeMillis();
        System.out.println("TestXPath: " + (end - start));
        System.out.println("XPath average: "
                + ((end - start) / ELEMENTS));

        start = System.currentTimeMillis();
        test.testImport();
        end = System.currentTimeMillis();
        System.out.println("TestImport: " + (end - start));
        System.out.println("Import average: "
                + ((end - start) / ELEMENTS));
    }
}

В методе setUp происходит создание дерева. Количеством дочерних элементов у корневого элемента, а также глубиной вложенности элементов можно управлять с помощью констант ELEMENTS и DEEP. В этом методе еще генерируется XPath-строка для листьев DOM-дерева.
Метод testXPath вычисляет одно и то же XPath выражение относительно каждой ноды element0 (дочерние для root’овой ноды). Поэксперементировав с количеством элементов element0 (константа ELEMENTS), вы обнаружите, что среднее время вычисления XPath увеличивается (можете добавить вывод времени каждого вычисления).
Чтобы избавиться от этой проблемы, я решил воспользоваться методом importNode у объекта типа Document. Каждый элемент element0 импортировался во временный документ tempDocument и XPath вычислялся уже для этого дерева. Реализацию этого подхода можно посмотреть в методе testImport. Начина с некоторого элемента, накладные расходы на импортирование ноды в другой документ становятся меньше, чем падение производительности при вычислении XPath выражения.

Причину этой проблемы я пока еще не исследовал. Скорее всего, это связано с индексацией нод в реализации DOM-документа. Как только проблема будет изучена, обязательно дополню эту статью новой информацией. В любом случае, эта статья должна быть полезна всем, кто работает с XML и XPath.
Всего вам хорошего.