DIVYA updated this revision to Diff 111998.
DIVYA added a comment.
- added test qsort_worst_uint32 in algorithm.bench.cpp
https://reviews.llvm.org/D36423
Files:
benchmarks/GenerateInput.hpp
benchmarks/algorithms.bench.cpp
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: benchmarks/algorithms.bench.cpp
===================================================================
--- benchmarks/algorithms.bench.cpp
+++ benchmarks/algorithms.bench.cpp
@@ -5,7 +5,7 @@
#include "benchmark/benchmark_api.h"
#include "GenerateInput.hpp"
-constexpr std::size_t TestNumInputs = 1024;
+constexpr std::size_t TestNumInputs = 1024*64;
template <class GenInputs>
void BM_Sort(benchmark::State& st, GenInputs gen) {
@@ -58,5 +58,8 @@
BENCHMARK_CAPTURE(BM_Sort, single_element_strings,
getDuplicateStringInputs)->Arg(TestNumInputs);
+BENCHMARK_CAPTURE(BM_Sort, qsort_worst_uint32,
+ getQSortKiller<uint32_t>)->Arg(TestNumInputs);
+
BENCHMARK_MAIN()
Index: benchmarks/GenerateInput.hpp
===================================================================
--- benchmarks/GenerateInput.hpp
+++ benchmarks/GenerateInput.hpp
@@ -138,5 +138,40 @@
return cinputs;
}
+template <class T>
+inline std::vector<T> make_killer(size_t N) {
+ std::vector<T> inputs;
+ uint32_t candidate = 0;
+ uint32_t num_solid = 0;
+ uint32_t gas = N - 1;
+
+ std::vector<T> tmp(N);
+ inputs.resize(N);
+
+ for (T i = 0; i < N; ++i) {
+ tmp[i] = i;
+ inputs[i] = gas;
+ }
+
+ std::sort(tmp.begin(), tmp.end(), [&](T x, T y) {
+ if (inputs[x] == gas && inputs[y] == gas) {
+ if (x == candidate) inputs[x] = num_solid++;
+ else inputs[y] = num_solid++;
+ }
+
+ if (inputs[x] == gas) candidate = x;
+ else if (inputs[y] == gas) candidate = y;
+
+ return inputs[x] < inputs[y];
+ });
+ return inputs;
+}
+
+
+template <class T>
+inline std::vector<T> getQSortKiller(size_t N){
+ std::vector<T> inputs = make_killer<T>(N);
+ return inputs;
+}
#endif // BENCHMARK_GENERATE_INPUT_HPP
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
