DIVYA created this revision.
The sorting algorithm currently employed in libc+ library uses quicksort with
tail recursion elimination, as a result of which the worst case complexity
turns out to be O(N^2).
This patch reduces the worst case time complexity, by employing Introsort
algorithm. Introsort is a sorting technique, which begins with quicksort and
when the recursion depth (or depth limit) goes beyond a threshold value, then
it switches to Heapsort .As a result the worst case complexity reduces to
O(NlogN)
Worked in collaboration with Aditya Kumar.
https://reviews.llvm.org/D36423
Files:
include/algorithm
Index: include/algorithm
===================================================================
--- include/algorithm
+++ include/algorithm
@@ -642,6 +642,7 @@
#include <utility> // needed to provide swap_ranges.
#include <memory>
#include <iterator>
+#include <cmath>
#include <cstddef>
#if defined(__IBMCPP__)
@@ -3994,7 +3995,14 @@
template <class _Compare, class _RandomAccessIterator>
void
-__sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare
__comp)
+__partial_sort(_RandomAccessIterator, _RandomAccessIterator,
_RandomAccessIterator,
+ _Compare);
+
+// Using introsort algorithm for sorting
+template <class _Compare, class _RandomAccessIterator>
+void
+__intro_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
_Compare __comp,
+ typename iterator_traits<_RandomAccessIterator>::difference_type
__depth_limit)
{
// _Compare is known to be a reference type
typedef typename iterator_traits<_RandomAccessIterator>::difference_type
difference_type;
@@ -4029,6 +4037,12 @@
_VSTD::__insertion_sort_3<_Compare>(__first, __last, __comp);
return;
}
+ if (__depth_limit == 0)
+ {
+ __partial_sort<_Compare>(__first,__last,__last,__comp);
+ return;
+ }
+
// __len > 5
_RandomAccessIterator __m = __first;
_RandomAccessIterator __lm1 = __last;
@@ -4172,19 +4186,33 @@
// sort smaller range with recursive call and larger with tail
recursion elimination
if (__i - __first < __last - __i)
{
- _VSTD::__sort<_Compare>(__first, __i, __comp);
- // _VSTD::__sort<_Compare>(__i+1, __last, __comp);
+ _VSTD::__intro_sort<_Compare>(__first, __i, __comp, __depth_limit);
+ // _VSTD::__intro_sort<_Compare>(__i+1, __last, __comp,
__depth_limit);
__first = ++__i;
}
else
{
- _VSTD::__sort<_Compare>(__i+1, __last, __comp);
- // _VSTD::__sort<_Compare>(__first, __i, __comp);
+ _VSTD::__intro_sort<_Compare>(__i+1, __last, __comp,
__depth_limit);
+ // _VSTD::__intro_sort<_Compare>(__first, __i, __comp,
__depth_limit);
__last = __i;
}
+ --__depth_limit;
}
}
+template <class _Compare, class _RandomAccessIterator>
+void
+__sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare
__comp)
+{
+
+ // Threshold(or depth limit) for introsort is taken to be 2*log2(size)
+ typedef typename iterator_traits<_RandomAccessIterator>::difference_type
difference_type;
+ const difference_type __dp = __last - __first;
+ difference_type __depth_limit = __last == __first ? 0 : _VSTD::log2(__dp);
+ __depth_limit *=2;
+ __intro_sort<_Compare>(__first, __last, __comp, __depth_limit);
+}
+
// This forwarder keeps the top call and the recursive calls using the same
instantiation, forcing a reference _Compare
template <class _RandomAccessIterator, class _Compare>
inline _LIBCPP_INLINE_VISIBILITY
Index: include/algorithm
===================================================================
--- include/algorithm
+++ include/algorithm
@@ -642,6 +642,7 @@
#include <utility> // needed to provide swap_ranges.
#include <memory>
#include <iterator>
+#include <cmath>
#include <cstddef>
#if defined(__IBMCPP__)
@@ -3994,7 +3995,14 @@
template <class _Compare, class _RandomAccessIterator>
void
-__sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
+__partial_sort(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator,
+ _Compare);
+
+// Using introsort algorithm for sorting
+template <class _Compare, class _RandomAccessIterator>
+void
+__intro_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
+ typename iterator_traits<_RandomAccessIterator>::difference_type __depth_limit)
{
// _Compare is known to be a reference type
typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
@@ -4029,6 +4037,12 @@
_VSTD::__insertion_sort_3<_Compare>(__first, __last, __comp);
return;
}
+ if (__depth_limit == 0)
+ {
+ __partial_sort<_Compare>(__first,__last,__last,__comp);
+ return;
+ }
+
// __len > 5
_RandomAccessIterator __m = __first;
_RandomAccessIterator __lm1 = __last;
@@ -4172,19 +4186,33 @@
// sort smaller range with recursive call and larger with tail recursion elimination
if (__i - __first < __last - __i)
{
- _VSTD::__sort<_Compare>(__first, __i, __comp);
- // _VSTD::__sort<_Compare>(__i+1, __last, __comp);
+ _VSTD::__intro_sort<_Compare>(__first, __i, __comp, __depth_limit);
+ // _VSTD::__intro_sort<_Compare>(__i+1, __last, __comp, __depth_limit);
__first = ++__i;
}
else
{
- _VSTD::__sort<_Compare>(__i+1, __last, __comp);
- // _VSTD::__sort<_Compare>(__first, __i, __comp);
+ _VSTD::__intro_sort<_Compare>(__i+1, __last, __comp, __depth_limit);
+ // _VSTD::__intro_sort<_Compare>(__first, __i, __comp, __depth_limit);
__last = __i;
}
+ --__depth_limit;
}
}
+template <class _Compare, class _RandomAccessIterator>
+void
+__sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
+{
+
+ // Threshold(or depth limit) for introsort is taken to be 2*log2(size)
+ typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
+ const difference_type __dp = __last - __first;
+ difference_type __depth_limit = __last == __first ? 0 : _VSTD::log2(__dp);
+ __depth_limit *=2;
+ __intro_sort<_Compare>(__first, __last, __comp, __depth_limit);
+}
+
// This forwarder keeps the top call and the recursive calls using the same instantiation, forcing a reference _Compare
template <class _RandomAccessIterator, class _Compare>
inline _LIBCPP_INLINE_VISIBILITY
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
