From e66356715c8ab207350bc30904b30c4de4515506 Mon Sep 17 00:00:00 2001 From: Arseny Kapoulkine Date: Sun, 5 Oct 2014 04:20:38 +0000 Subject: Optimize XPath sorting for sorted sequences XPath evaluation frequently produces sequences that are sorted but are not tagged as such (area for improvement...). Doing a linear scan before sorting is cheap and results in tremendous speedup for already sorted sequences (especially if document_buffer_order optimization does not apply). git-svn-id: https://pugixml.googlecode.com/svn/trunk@1049 99668b35-9821-0410-8761-19e4c4f06640 --- src/pugixml.cpp | 29 ++++++++++++++++++++++++++--- 1 file changed, 26 insertions(+), 3 deletions(-) diff --git a/src/pugixml.cpp b/src/pugixml.cpp index 55dd8ec..94073f3 100644 --- a/src/pugixml.cpp +++ b/src/pugixml.cpp @@ -6844,7 +6844,7 @@ PUGI__NS_BEGIN for (; ln; ln = ln.next_sibling()) if (ln == rn) return true; - + return false; } @@ -7498,15 +7498,38 @@ PUGI__NS_END // Internal node set class PUGI__NS_BEGIN + PUGI__FN xpath_node_set::type_t xpath_get_order(const xpath_node* begin, const xpath_node* end) + { + if (end - begin < 2) + return xpath_node_set::type_sorted; + + document_order_comparator cmp; + + bool first = cmp(begin[0], begin[1]); + + for (const xpath_node* it = begin + 1; it + 1 < end; ++it) + if (cmp(it[0], it[1]) != first) + return xpath_node_set::type_unsorted; + + return first ? xpath_node_set::type_sorted : xpath_node_set::type_sorted_reverse; + } + PUGI__FN xpath_node_set::type_t xpath_sort(xpath_node* begin, xpath_node* end, xpath_node_set::type_t type, bool rev) { xpath_node_set::type_t order = rev ? xpath_node_set::type_sorted_reverse : xpath_node_set::type_sorted; if (type == xpath_node_set::type_unsorted) { - sort(begin, end, document_order_comparator()); + xpath_node_set::type_t sorted = xpath_get_order(begin, end); + + if (sorted == xpath_node_set::type_unsorted) + { + sort(begin, end, document_order_comparator()); - type = xpath_node_set::type_sorted; + type = xpath_node_set::type_sorted; + } + else + type = sorted; } if (type != order) reverse(begin, end); -- cgit v1.2.3