XPath: ускоряем итерацию по NodeList

    При попытке обработки не очень маленького регулярного XML-файла (на самом деле всего лишь около тысячи записей) обнаружил, что итерирование по NodeList вместе с извлечением с помощью XPath начинает существенно тормозить (занимая порядка 2 минут на моём файле), причем тормоза увеличиваются с обработкой каждого следующего узла (node). Эта проблема поднимается также

    blog.astradele.com/2006/02/24/slow-xpath-evaluation-for-large-xml-documents-in-java-15

    jbwhammie.blogspot.com/2011/02/make-java-xpath-work-on-large-files.html

    Как я понял, это некая особенность реализации DOM & XPath в JDK, которая заключается в том, что если мы получили XPath-запросом некий Node из XML, то этот Node остаётся ссылающимся через parent на родительский XML Document. И последующие попытки XPath-запросов к этому Node приводят к тому, что обрабатывается не только сам Node но и весь XML Document. Поэтому логичным является попытка обнулить parent у Node, например, путем удаления этого Node из его родительского Node. Именно такой способ предлагается по ссылкам выше, и он работает. Единственный его недостаток в том, что он изменяет сам XML Document, делая его более не годным к дальнейшему извлечению данных. Я обнаружил, что есть другой способ не меняющий сам XML Document — клонирование Node, т.к., согласно документации, при этом у клона parent = null.

    Собственно, описанная проблема и подходы к решению иллюстрируются следующим кодом.

    import org.w3c.dom.Document;
    import org.w3c.dom.Node;
    import org.w3c.dom.NodeList;

    import javax.xml.parsers.DocumentBuilder;
    import javax.xml.parsers.DocumentBuilderFactory;
    import javax.xml.xpath.XPathConstants;
    import javax.xml.xpath.XPathExpression;
    import javax.xml.xpath.XPathExpressionException;
    import javax.xml.xpath.XPathFactory;
    import java.io.ByteArrayInputStream;

    public class SlowXPath {
      public static void main(String[] args) throws Exception {
        final DocumentBuilderFactory documentBuilderFactory = DocumentBuilderFactory.newInstance();

        final DocumentBuilder documentBuilder = documentBuilderFactory.newDocumentBuilder();

        String xmlString = prepareXml(5000);

    //    System.out.println(xmlString);
        final Document xmlDoc = documentBuilder.parse(new ByteArrayInputStream(xmlString.getBytes()));

        final XPathFactory xPathFactory = XPathFactory.newInstance();

        final XPathExpression nodeXPath = xPathFactory.newXPath().compile("//node");
        final XPathExpression iXPath = xPathFactory.newXPath().compile("./i/text()");

        final NodeList nodeList = (NodeList) nodeXPath.evaluate(xmlDoc, XPathConstants.NODESET);

        System.out.println("Nodes number=" + nodeList.getLength());

        timeIt("Simple iterate", new Runnable() {
          @Override
          public void run() {
            int sum = 0;

            for (int i = 0; i < nodeList.getLength(); i++) {
              final Node node = nodeList.item(i);
              try {
                final String iStr = (String) iXPath.evaluate(node, XPathConstants.STRING);
                sum += Integer.parseInt(iStr.trim());
              } catch (XPathExpressionException e) {
                e.printStackTrace();
              }
            }

            System.out.println("Sum=" + sum);
          }
        });
        timeIt("Iterate with cloning", new Runnable() {
          @Override
          public void run() {
            int sum = 0;

            for (int i = 0; i < nodeList.getLength(); i++) {
              final Node node = nodeList.item(i).cloneNode(true); // <-- Note cloning here
              try {
                final String iStr = (String) iXPath.evaluate(node, XPathConstants.STRING);
                sum += Integer.parseInt(iStr.trim());
              } catch (XPathExpressionException e) {
                e.printStackTrace();
              }
            }

            System.out.println("Sum=" + sum);
          }
        });
        timeIt("Iterate with detaching node", new Runnable() {
          @Override
          public void run() {
            int sum = 0;

            for (int i = 0; i < nodeList.getLength(); i++) {
              final Node node = nodeList.item(i);

              node.getParentNode().removeChild(node); // <-- Note detaching node

              try {
                final String iStr = (String) iXPath.evaluate(node, XPathConstants.STRING);
                sum += Integer.parseInt(iStr.trim());
              } catch (XPathExpressionException e) {
                e.printStackTrace();
              }
            }

            System.out.println("Sum=" + sum);
          }
        });
      }

      private static String prepareXml(int n) {
        StringBuilder sb = new StringBuilder();

        sb.append("<root>");

        for (int i = 0; i < n; i++) {
          sb.append("<node><i>\n")
              .append(i)
              .append("</i></node>\n");
        }

        sb.append("</root>");

        return sb.toString();
      }

      private static void timeIt(String name, Runnable runnable) {
        long t0 = System.currentTimeMillis();
        runnable.run();
        long t1 = System.currentTimeMillis();

        System.out.println(name + " executed " + ((t1 - t0) / 1000f) + "sec.");
      }
    }

    * This source code was highlighted with Source Code Highlighter.


    А вот результат работы:

    Nodes number=5000
    Sum=12497500
    Simple iterate executed 17.359sec.
    Sum=12497500
    Iterate with cloning executed 1.047sec.
    Sum=12497500
    Iterate with detaching node executed 1.031sec.

    Средняя зарплата в IT

    120 000 ₽/мес.
    Средняя зарплата по всем IT-специализациям на основании 7 283 анкет, за 1-ое пол. 2021 года Узнать свою зарплату
    Реклама
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее

    Комментарии 14

      +2
      Если узел сам имеет разветвленную структуру, то стоимость клонирования будет возрастать. Думаю, именно поэтому предлагают удалять.
        +2
        Просто наиогромнейшее спасибо! Вы только что спасли меня от нескольких предстоящих мне недель мучений и написания тысяч строк кода.

        Пишу сейчас на си код который очишает html страницы от всего лишнего, оставляя только лишь главный смысл (аналог Safari Reader — tagmac.ru/other/safari-5-reader-tolko-tekst-1185), так вот у меня используется огромное количество xpath запросов. На код угрохал примерно 3 недели и вот в итоге получилось что обработка того же топика на хабре занимает до 15 секунд, что конечно не приемлимо. Последнию неделю я оптимизировал код — распараллелил все что можно, включая циклы, оптимизировал код, пару узких мест переписал на ассемблере и всеравно не получилось обрабатывать быстрее, чем за секунд 10, профайлер показывал что практически все время уходит на эти запросы.

        И вот чудо, случайно на глаза попадается этот топик (хотя я даже не интересуюсь java), тажа самая ситуация. Написал только что одну строчку кода в основном цикле для удаления parent — обработка теперь мгновенная, менее секунды :) А ведь я уже собирался писать свой специализированный парсер и потратить на это еще месяц.
          0
          Рад, что так =)
            +1
            Может быть вам стоило использовать XSLT вместо «огромного количества xpath запросов»?
              0
              Возможно, я никогда не сталкивался до этого с более-менее серьезной необходимостью работать с html/xml и плохо представляю какие технологии вообше имеются в наличии. Я и про xpath месяц назад не подозревал.

              Сейчас почитал бегло про этот XSLT на вики и если честно не очень понимаю как мне это может помочь, это язык преобразования XML-документов, на что он мне?
                0
                По-моему к Вашей задаче лучше бы подошел потоковый стиль обработки документа, например что-то типа SAX ru.wikipedia.org/wiki/SAX.
                  +2
                  Да, про SAX-парсер я знаю, собственно до этого только с ним и сталкивался, но мне показалось что это получится более сложным архитектурным-решением. Я также знал что можно предварительно составив все дерево документа (DOM) и бегать по нему как угодно, попутно изменяя и удаляя элементы, чтение доков как раз и подсказало мне что можно не просто бегать в циклах, а составлять целые универсальные запросы с помошью xpath что еще сильнее упростило задачу.

                  Вообше я сейчас понял что имел ввиду ComodoHacker, но только это никак не относится к моей задаче. Суть в чем — есть какой угодно документ с любого сайта в мире, нужно определить что в нем является главной смысловой нагрузкой и оставить только это. Поэтому никакой XSLT тут не подойдет, как минимум у меня на входе что угодно, как максимум я еще не знаю что в документе нужно оставить. Для этого подсчитывается по куче разных правил веса каждой ноды (например сколько в ней <p> блоков, сколько картинок с размером от 100px и т.п.), потом слабые удаляются, сильные остаются, процесс может повторяться, в процессе какие-то ноды могут удаляться опять же в зависимости от их веса. На SAX такое реализовать как-то сложнее, все же проше DOM + свой спеициализированный аналог xpath который я думал написать, а теперь уже и не нужно.
                    0
                    Да, пожалуй в вашем случае XSLT не подойдет.

                    Хотя, подсчет разных метрик вроде «сколько <p> блоков», «сколько картинок» и т.п. с помощью XSLT тоже возможен. :)
                      0
                      XSLT все это умеет. И для вашей задачи именно его и надо было использовать.
                        0
                        Прочел сейчас всё его описание на w3schools.com и посмотрел там же некоторые примеры. И я даже отдаленно не представляю как можно его задействовать и как он может дать ускорение (он кроме своей личной работы еще и на xpath полагается).

                        Но был бы рад вашим идеям, если есть куда стремиться, то почему бы и нет?
                          0
                          Тот же Saxon вполне быстр. Кроме того, там есть кеширование шаблонов, что дает сильное ускорение. Мне доводилось писать шаблоны с относительно сложной логикой и никаких проблем со скоростью там не было. 15 секунд на одну страницу, все же, — это ппц.

                          А вообще, мне очень хочется дать вам ссылку на «Как правильно задавать вопросы». Попробуйте сначала сами, а потом уже задавайте конкретные вопросы. Ибо конкретно в данном случае я не вижу ни одной причины что мешает взять учебник по XSLT и все сделать самому.
                            +1
                            15 секунд — это частный случай связанный со спецификой обработки нод которая мне была не известна, до кучи и не оптимизированный код. Сейчас как я уже сказал, все обрабатывается менее чем за секунду. Дальше как мне видится можно копать только в сторону написания своего специализированного парсера, а еще лучше сразу совмещения его с кодом обработки. Ради интереса прочитал как устроена libxslt (http://xmlsoft.org/XSLT/internals.html), собственно так оно и есть.

                            Документацию я прочел, а вопрос задал к тому, что на основе увиденных мной примеров преобразования не вижу каких-то возможных способов решения задачи. Допускаю что сказывает шаблонное мышление в совсем других категориях, посему я даже не могу представить себе конечные цели при таком подходе. Вот и спросил — как вы это видите.
                              0
                              Как вижу? Очень просто — берем и вырезаем/изменяем дерево в соответствии с правилами.
              +1
              Прекрасно понимая, что это — утрированный пример, и вложенный XPath может быть значительно более сложным, хочу заметить, что в простых случаях правильнее использовать обычное DOM API.

              final Node node = nodeList.item(i);
              for (Node child = node.getFirstChild(); child != null; child = child.getNextSibling()) {
                  if ("i".equals(child.getNodeName())) {
                      final String iStr = child.getTextContent();
                      sum += Integer.parseInt(iStr.trim());
                      break;
                  }
              }

              Simple iterate executed 19.26sec.
              Iterate with cloning executed 3.241sec.
              Iterate with detaching node executed 2.128sec.
              Iterate with DOM API executed 0.017sec.

              При этом не портится DOM-дерево и не клонируются узлы. Да, это более громоздко, чем xpath.evaluate(). Но мы же тут говорим о достижении производительности?

              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

              Самое читаемое