From 774d5fe9df07ce68ac45ecdfebe71508a611d759 Mon Sep 17 00:00:00 2001 From: Arseny Kapoulkine Date: Mon, 6 Feb 2017 19:25:05 -0800 Subject: 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. --- src/pugixml.cpp | 38 ++++++++++++-------------------------- 1 file 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 void copy_backwards(I begin, I end, I target) + template void insertion_sort(T* begin, T* end, const Pred& pred) { - while (begin != end) *--target = *--end; - } - - template 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 -- cgit v1.2.3