XPath: Optimize insertion_sort

The previous implementation opted for doing two comparisons per element
in the sorted case in order to remove one iterator bounds check per
moved element when we actually need to copy. In our case however the
comparator is pretty expensive (except for remove_duplicates which is
fast as it is) so an extra object comparison hurts much more than an
iterator comparison saves.

This makes sorting by document order up to 3% faster for random
sequences.

1 files changed, 12 insertions, 26 deletions

diff --git a/src/pugixml.cpp b/src/pugixml.cpp
index 110ece6..90b24aa 100644
--- a/src/pugixml.cpp
+++ b/src/pugixml.cpp
@@ -7216,39 +7216,25 @@ PUGI__NS_BEGIN
 		return write + 1;
 	}
 
-	template <typename I> void copy_backwards(I begin, I end, I target)
+	template <typename T, typename Pred> void insertion_sort(T* begin, T* end, const Pred& pred)
 	{
-		while (begin != end) *--target = *--end;
-	}
-
-	template <typename I, typename Pred, typename T> void insertion_sort(I begin, I end, const Pred& pred, T*)
-	{
-		assert(begin != end);
+		if (begin == end)
+			return;
 
-		for (I it = begin + 1; it != end; ++it)
+		for (T* it = begin + 1; it != end; ++it)
 		{
 			T val = *it;
+			T* hole = it;
 
-			if (pred(val, *begin))
+			// move hole backwards
+			while (hole > begin && pred(val, *(hole - 1)))
 			{
-				// move to front
-				copy_backwards(begin, it, it + 1);
-				*begin = val;
+				*hole = *(hole - 1);
+				hole--;
 			}
-			else
-			{
-				I hole = it;
 
-				// move hole backwards
-				while (pred(val, *(hole - 1)))
-				{
-					*hole = *(hole - 1);
-					hole--;
-				}
-
-				// fill hole with element
-				*hole = val;
-			}
+			// fill hole with element
+			*hole = val;
 		}
 	}
 
@@ -7359,7 +7345,7 @@ PUGI__NS_BEGIN
 		}
 
 		// insertion sort small chunk
-		if (begin != end) insertion_sort(begin, end, pred, &*begin);
+		insertion_sort(begin, end, pred);
 	}
 PUGI__NS_END