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

1 files 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);