Add introsort to avoid O(n^2) behavior and a benchmark for adversarial quick sort input.

[nilayvaish]

Summary

There are two commits in this request.  The first one adds a benchmark that tests std::sort on an adversarial inputs.  The second 
 commit adds intro sort to the std::sort.  Inputs where partitions are unbalanced even after 2 log(n) pivots have been selected, the 
 algorithm switches to heap sort to avoid the possibility of spending O(n^2) time on sorting the input.  Benchmark results show that
 the intro sort implementation does significantly better.

Benchmarking results before this change.  Time represents the sorting time
required per element.

----------------------------------------------------------------------------------------------------------
Benchmark                                                                Time             CPU   Iterations
----------------------------------------------------------------------------------------------------------
BM_Sort_uint32_QuickSortAdversary_1                                   3.75 ns         3.74 ns    187432960
BM_Sort_uint32_QuickSortAdversary_4                                   3.05 ns         3.05 ns    231211008
BM_Sort_uint32_QuickSortAdversary_16                                  2.45 ns         2.45 ns    288096256
BM_Sort_uint32_QuickSortAdversary_64                                  32.8 ns         32.8 ns     21495808
BM_Sort_uint32_QuickSortAdversary_256                                  132 ns          132 ns      5505024
BM_Sort_uint32_QuickSortAdversary_1024                                 498 ns          497 ns      1572864
BM_Sort_uint32_QuickSortAdversary_16384                               3846 ns         3845 ns       262144
BM_Sort_uint32_QuickSortAdversary_262144                             61431 ns        61400 ns       262144
BM_Sort_uint64_QuickSortAdversary_1                                   3.93 ns         3.92 ns    181141504
BM_Sort_uint64_QuickSortAdversary_4                                   3.10 ns         3.09 ns    222560256
BM_Sort_uint64_QuickSortAdversary_16                                  2.50 ns         2.50 ns    283639808
BM_Sort_uint64_QuickSortAdversary_64                                  33.2 ns         33.2 ns     21757952
BM_Sort_uint64_QuickSortAdversary_256                                  132 ns          132 ns      5505024
BM_Sort_uint64_QuickSortAdversary_1024                                 478 ns          477 ns      1572864
BM_Sort_uint64_QuickSortAdversary_16384                               3932 ns         3930 ns       262144
BM_Sort_uint64_QuickSortAdversary_262144                             61646 ns        61615 ns       262144

Benchmarking results after this change

----------------------------------------------------------------------------------------------------------
Benchmark                                                                Time             CPU   Iterations
----------------------------------------------------------------------------------------------------------
BM_Sort_uint32_QuickSortAdversary_1                                   6.31 ns         6.30 ns    107741184
BM_Sort_uint32_QuickSortAdversary_4                                   4.51 ns         4.50 ns    158859264
BM_Sort_uint32_QuickSortAdversary_16                                  3.00 ns         3.00 ns    223608832
BM_Sort_uint32_QuickSortAdversary_64                                  44.8 ns         44.8 ns     15990784
BM_Sort_uint32_QuickSortAdversary_256                                 69.0 ns         68.9 ns      9961472
BM_Sort_uint32_QuickSortAdversary_1024                                 118 ns          118 ns      6029312
BM_Sort_uint32_QuickSortAdversary_16384                                175 ns          175 ns      4194304
BM_Sort_uint32_QuickSortAdversary_262144                               210 ns          210 ns      3407872
BM_Sort_uint64_QuickSortAdversary_1                                   6.75 ns         6.73 ns    103809024
BM_Sort_uint64_QuickSortAdversary_4                                   4.53 ns         4.53 ns    160432128
BM_Sort_uint64_QuickSortAdversary_16                                  2.98 ns         2.97 ns    234356736 
BM_Sort_uint64_QuickSortAdversary_64                                  44.3 ns         44.3 ns     15990784
BM_Sort_uint64_QuickSortAdversary_256                                 69.2 ns         69.2 ns     10223616
BM_Sort_uint64_QuickSortAdversary_1024                                 119 ns          119 ns      6029312
BM_Sort_uint64_QuickSortAdversary_16384                                173 ns          173 ns      4194304
BM_Sort_uint64_QuickSortAdversary_262144                               212 ns          212 ns      3407872

[nilayvaish]

Fix compilation issues with cxx03

[nilayvaish]

Updated the commit message.

[ldionne]

libcxx/include/__algorithm/sort.h

264–273

It seems to me like you reformatted a lot of this code, making the change itself a lot more difficult to understand. Please do the re-formatting either before or after your functional change, in a separate "no functionality change" patch.

[nilayvaish]

Moved the diffs due to formatting by arc to a separate commit.

[nilayvaish]

Remove formatting diffs from the diff. It seems Phabricator is unable to show the diffs between different commits.

[nilayvaish]

Another attempt at uploading changes without formatting diff.

[nilayvaish]

Move the depth check after the initial switch so that small sized sorts are not affected by the depth check.

[nilayvaish]

libcxx/include/__algorithm/sort.h

264–273

I have dropped the formatting changes. Those were done by arc and I just accepted them.

[nilayvaish]

Pinging @ldionne.

[ldionne]

Do you need someone to commit this for you? If so, please provide Author Name <email@domain> for attribution. Thanks!

libcxx/include/__algorithm/sort.h

265

[nilayvaish]

In D113413#3134968, @ldionne wrote:

Do you need someone to commit this for you? If so, please provide Author Name <email@domain> for attribution. Thanks!

Yes, if you can commit this for me that would be great. You can use 'Nilay Vaish <[e-mail]>' for attribution. Thanks for all the help!

[haowei]

We are seeing build breakages on Fuchsia builders after this change. It complains definition of implicit copy constructor is deprecated because it has a user-provided copy assignment operator. Example of the failure can be found at https://ci.chromium.org/ui/p/fuchsia/builders/ci/clang_toolchain.ci.core.arm64-release/b8830264610876104385/overview . It is confirmed through bisection. Code that failed to build can be found at https://fuchsia.googlesource.com/third_party/flatbuffers/+/f22618113aea6d04ed10bcaf28cc3621eea146d2/include/flatbuffers/flatbuffers.h#1154

Would you mind taking a look? We can suppress the error on our end but we still haven't figure out why this change could trigger this error(warning).

[• Quuxplusone]

libcxx/include/__algorithm/sort.h

477

This line needs to use _VSTD::__introsort (ADL-proofing — hmm, how did this pass robust_against_adl.pass.cpp? I should investigate).
Also, it needs to use _Comp_ref<_Compare> instead of making a copy of __comp.
@nilayvaish, please hunt through the rest of this patch to see if there are any other similar cases. (I did not look.)

I will investigate adding a new test along the lines of algorithms/robust_*.cpp to verify that we never accidentally copy comparators or predicates.

[nilayvaish]

libcxx/include/__algorithm/sort.h

477

Noted. Will send a diff later today.

[• Quuxplusone]

libcxx/include/__algorithm/sort.h

477

Actually, nvm, I got nerdsniped into taking a look myself: D114133

[ayzhao]

We see that this patch is causing the size of the Chrome Android APK to increase by ~120 KB. This is confirmed via bisection. A breakdown of the symbols contributing to the size increase can be found at https://chrome-supersize.firebaseapp.com/viewer.html?load_url=https%3A%2F%2Fstorage.googleapis.com%2Fchromium-binary-size-trybot-results%2Fandroid-binary-size%2F2022%2F05%2F10%2F1112911%2Fsupersize_diff.sizediff&group_by=template .

At this point in time, I'm not exactly sure why this patch would increase the size by such a large amount. Does anyone have any ideas?

[pkasting]

In D113413#3512743, @ayzhao wrote:

We see that this patch is causing the size of the Chrome Android APK to increase by ~120 KB. This is confirmed via bisection. A breakdown of the symbols contributing to the size increase can be found at https://chrome-supersize.firebaseapp.com/viewer.html?load_url=https%3A%2F%2Fstorage.googleapis.com%2Fchromium-binary-size-trybot-results%2Fandroid-binary-size%2F2022%2F05%2F10%2F1112911%2Fsupersize_diff.sizediff&group_by=template .

At this point in time, I'm not exactly sure why this patch would increase the size by such a large amount. Does anyone have any ideas?

@From the symbol diffs on e.g. ng_grid_layout_algorithm.cc, it looks like we have lots of negative deltas for sort and larger positive deltas for introsort, which suggests that the difference is the cumulative effect of inlining many instances of __introsort with its slightly longer (len > 5) case in the new code.

Perhaps this code is being built with excessive inlining and needs -Os or similar? Perhaps Clang itself needs some inliner heuristic tuning? Perhaps this is an unavoidable size hit unless you want to take a speed hit?

[ayzhao]

In D113413#3516599, @pkasting wrote:

In D113413#3512743, @ayzhao wrote:

We see that this patch is causing the size of the Chrome Android APK to increase by ~120 KB. This is confirmed via bisection. A breakdown of the symbols contributing to the size increase can be found at https://chrome-supersize.firebaseapp.com/viewer.html?load_url=https%3A%2F%2Fstorage.googleapis.com%2Fchromium-binary-size-trybot-results%2Fandroid-binary-size%2F2022%2F05%2F10%2F1112911%2Fsupersize_diff.sizediff&group_by=template .

At this point in time, I'm not exactly sure why this patch would increase the size by such a large amount. Does anyone have any ideas?

@From the symbol diffs on e.g. ng_grid_layout_algorithm.cc, it looks like we have lots of negative deltas for sort and larger positive deltas for introsort, which suggests that the difference is the cumulative effect of inlining many instances of __introsort with its slightly longer (len > 5) case in the new code.

Perhaps this code is being built with excessive inlining and needs -Os or similar? Perhaps Clang itself needs some inliner heuristic tuning? Perhaps this is an unavoidable size hit unless you want to take a speed hit?

For documentation purposes:

I chatted offline with pkasting@ and we found out that adding __attribute__((noinline)) to __introsort actually made the binary size even worse - it added an additional ~40KB.

[agrieve]

re: binary size - std::sort-related symbols make up more than 1% of Chrome's binary size (for arm32 Android at least). Any work to reduce the size overhead of std::sort() would be very welcome. From what I can tell, the main contributing factor is the templated nature of the function. It gets stamped out a *lot* of times, and in a way that identical-code-folding is often not applicable.

[hiraditya]

glad to see this land. we had a very similar patch almost 5 years ago but got lost in the review process: https://reviews.llvm.org/D36423

[hiraditya]

In D113413#3528143, @agrieve wrote:

re: binary size - std::sort-related symbols make up more than 1% of Chrome's binary size (for arm32 Android at least). Any work to reduce the size overhead of std::sort() would be very welcome. From what I can tell, the main contributing factor is the templated nature of the function. It gets stamped out a *lot* of times, and in a way that identical-code-folding is often not applicable.

Will it help to explicitly specialize some of the commonly used templates in Chrome?

[agrieve]

In D113413#3548857, @hiraditya wrote:

In D113413#3528143, @agrieve wrote:

re: binary size - std::sort-related symbols make up more than 1% of Chrome's binary size (for arm32 Android at least). Any work to reduce the size overhead of std::sort() would be very welcome. From what I can tell, the main contributing factor is the templated nature of the function. It gets stamped out a *lot* of times, and in a way that identical-code-folding is often not applicable.

Will it help to explicitly specialize some of the commonly used templates in Chrome?

We enable identical code folding, so I don't see how that would help.

If we could identify at compile time when sort is being called with aggregates / PODs and route all such calls through qsort(), I think that might help.

[smeenai]

I'm working on upgrading Meta's Android apps from libc++ 13 to libc++ 15, and seeing large size regressions caused by this change (similar to the Chrome case above). Was there any progress on figuring out how to offset the binary size increase?

(I recognize it's pretty annoying on my part to be raising the issue 9 months after the code was committed, and I apologize for that. We're working on being able to catch these issues earlier in the future.)

libcxx/benchmarks/algorithms.bench.cpp

std::conditional_t<
                                std::string> > > >;
 
 enum class Order {
   Random,
   Ascending,
   Descending,
   SingleElement,
   PipeOrgan,
-  Heap
+  Heap,
+  QuickSortAdversary,
 };
-struct AllOrders : EnumValuesAsTuple<AllOrders, Order, 6> {
+struct AllOrders : EnumValuesAsTuple<AllOrders, Order, 7> {
   static constexpr const char* Names[] = {"Random",     "Ascending",
                                           "Descending", "SingleElement",
-                                          "PipeOrgan",  "Heap"};
+                                          "PipeOrgan",  "Heap",
+                                          "QuickSortAdversary"};
 };
 
+// fillAdversarialQuickSortInput fills the input vector with N int-like values.
+// These values are arranged in such a way that they would invoke O(N^2)
+// behavior on any quick sort implementation that satisifies certain conditions.
+// Details are available in the following paper:
+// "A Killer Adversary for Quicksort", M. D. McIlroy, Software—Practice &
+// ExperienceVolume 29 Issue 4 April 10, 1999 pp 341–344.
+// https://dl.acm.org/doi/10.5555/311868.311871.
+template <class T>
+void fillAdversarialQuickSortInput(T& V, size_t N) {
+  assert(N > 0);
+  // If an element is equal to gas, it indicates that the value of the element
+  // is still to be decided and may change over the course of time.
+  const int gas = N - 1;
+  V.resize(N);
+  for (int i = 0; i < N; ++i) {
+    V[i] = gas;
+  }
+  // Candidate for the pivot position.
+  int candidate = 0;
+  int nsolid = 0;
+  // Populate all positions in the generated input to gas.
+  std::vector<int> ascVals(V.size());
+  // Fill up with ascending values from 0 to V.size()-1.  These will act as
+  // indices into V.
+  std::iota(ascVals.begin(), ascVals.end(), 0);
+  std::sort(ascVals.begin(), ascVals.end(), [&](int x, int y) {
+    if (V[x] == gas && V[y] == gas) {
+      // We are comparing two inputs whose value is still to be decided.
+      if (x == candidate) {
+        V[x] = nsolid++;
+      } else {
+        V[y] = nsolid++;
+      }
+    }
+    if (V[x] == gas) {
+      candidate = x;
+    } else if (V[y] == gas) {
+      candidate = y;
+    }
+    return V[x] < V[y];
+  });
+}
+
 template <typename T>
 void fillValues(std::vector<T>& V, size_t N, Order O) {
   if (O == Order::SingleElement) {
     V.resize(N, 0);
+  } else if (O == Order::QuickSortAdversary) {
+    fillAdversarialQuickSortInput(V, N);
   } else {
     while (V.size() < N)
       V.push_back(V.size());
   }
 }
 
 template <typename T>
 void fillValues(std::vector<std::pair<T, T> >& V, size_t N, Order O) {
case Order::SingleElement:
     break;
   case Order::PipeOrgan:
     std::sort(V.begin(), V.end());
     std::reverse(V.begin() + V.size() / 2, V.end());
     break;
   case Order::Heap:
     std::make_heap(V.begin(), V.end());
     break;
+  case Order::QuickSortAdversary:
+    // Nothing to do
+    break;
   }
 }
 
 constexpr size_t TestSetElements =
 #if !TEST_HAS_FEATURE(memory_sanitizer)
     1 << 18;
 #else
     1 << 14;

libcxx/include/__algorithm/sort.h

if (__first1 != __last1)
                 ::new ((void*)__j2) value_type(_VSTD::move(*__first1));
                 __d.template __incr<value_type>();
             }
         }
         __h.release();
     }
 }
 
 template <class _Compare, class _RandomAccessIterator>
 void
-__sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
+__introsort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
+            typename _VSTD::iterator_traits<_RandomAccessIterator>::difference_type __depth)
 {
     typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
     typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
     const difference_type __limit = is_trivially_copy_constructible<value_type>::value &&
                                     is_trivially_copy_assignable<value_type>::value ? 30 : 6;
+    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
     while (true)
     {
     __restart:
         difference_type __len = __last - __first;
         switch (__len)
         {
         case 0:
         case 1:
__restart:
             return;
         }
         if (__len <= __limit)
         {
             _VSTD::__insertion_sort_3<_Compare>(__first, __last, __comp);
             return;
         }
         // __len > 5
+        if (__depth == 0)
+        {
+          // Fallback to heap sort as Introsort suggests.
+          _VSTD::__partial_sort<_Comp_ref>(__first, __last, __last, _Comp_ref(__comp));
+          return;
+        }
+        --__depth;
         _RandomAccessIterator __m = __first;
         _RandomAccessIterator __lm1 = __last;
         --__lm1;
         unsigned __n_swaps;
         {
         difference_type __delta;
         if (__len >= 1000)
         {
__restart:
                     __first = ++__i;
                     continue;
                 }
             }
         }
         // 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);
-            __first = ++__i;
+          _VSTD::__introsort<_Compare>(__first, __i, __comp, __depth);
         }
         else
         {
-            _VSTD::__sort<_Compare>(__i+1, __last, __comp);
-            // _VSTD::__sort<_Compare>(__first, __i, __comp);
-            __last = __i;
+          _VSTD::__introsort<_Compare>(__i + 1, __last, __comp, __depth);
         }
     }
 }
 
+template <typename _Number>
+inline _LIBCPP_HIDE_FROM_ABI _Number __log2i(_Number __n) {
+  _Number __log2 = 0;
+  while (__n > 1) {
+    __log2++;
+    __n >>= 1;
+  }
+  return __log2;
+}
+
+template <class _Compare, class _RandomAccessIterator>
+void __sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
+  typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
+  difference_type __depth_limit = 2 * __log2i(__last - __first);
+  __introsort(__first, __last, __comp, __depth_limit);
+}
+
 template <class _Compare, class _Tp>
 inline _LIBCPP_INLINE_VISIBILITY
 void
 __sort(_Tp** __first, _Tp** __last, __less<_Tp*>&)
 {
     __less<uintptr_t> __comp;
     _VSTD::__sort<__less<uintptr_t>&, uintptr_t*>((uintptr_t*)__first, (uintptr_t*)__last, __comp);
 }

libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/sort.pass.cpp

for (int i = 0; i < array_size; i++) {
       pv[i] = &v[array_size - 1 - i];
     }
     std::sort(pv, pv + array_size);
     assert(*pv[0] == v[0]);
     assert(*pv[1] == v[1]);
     assert(*pv[array_size - 1] == v[array_size - 1]);
 }
 
+// test_adversarial_quicksort generates a vector with values arranged in such a
+// way that they would invoke O(N^2) behavior on any quick sort implementation
+// that satisifies certain conditions.  Details are available in the following
+// paper:
+// "A Killer Adversary for Quicksort", M. D. McIlroy, Software—Practice &
+// ExperienceVolume 29 Issue 4 April 10, 1999 pp 341–344.
+// https://dl.acm.org/doi/10.5555/311868.311871.
+struct AdversaryComparator {
+  AdversaryComparator(int N, std::vector<int>& input) : gas(N - 1), V(input) {
+    V.resize(N);
+    // Populate all positions in the generated input to gas to indicate that
+    // none of the values have been fixed yet.
+    for (int i = 0; i < N; ++i)
+      V[i] = gas;
+  }
+
+  bool operator()(int x, int y) {
+    if (V[x] == gas && V[y] == gas) {
+      // We are comparing two inputs whose value is still to be decided.
+      if (x == candidate) {
+        V[x] = nsolid++;
+      } else {
+        V[y] = nsolid++;
+      }
+    }
+    if (V[x] == gas) {
+      candidate = x;
+    } else if (V[y] == gas) {
+      candidate = y;
+    }
+    return V[x] < V[y];
+  }
+
+private:
+  // If an element is equal to gas, it indicates that the value of the element
+  // is still to be decided and may change over the course of time.
+  const int gas;
+  // This is a reference so that we can manipulate the input vector later.
+  std::vector<int>& V;
+  // Candidate for the pivot position.
+  int candidate = 0;
+  int nsolid = 0;
+};
+
+void test_adversarial_quicksort(int N) {
+  assert(N > 0);
+  std::vector<int> ascVals(N);
+  // Fill up with ascending values from 0 to N-1.  These will act as indices
+  // into V.
+  std::iota(ascVals.begin(), ascVals.end(), 0);
+  std::vector<int> V;
+  AdversaryComparator comp(N, V);
+  std::sort(ascVals.begin(), ascVals.end(), comp);
+  std::sort(V.begin(), V.end());
+  assert(std::is_sorted(V.begin(), V.end()));
+}
+
 int main(int, char**)
 {
     // test null range
     int d = 0;
     std::sort(&d, &d);
     // exhaustively test all possibilities up to length 8
     test_sort_<1>();
     test_sort_<2>();
     test_sort_<3>();
     test_sort_<4>();
     test_sort_<5>();
     test_sort_<6>();
     test_sort_<7>();
     test_sort_<8>();
 
     test_larger_sorts(256);
     test_larger_sorts(257);
     test_larger_sorts(499);
     test_larger_sorts(500);
     test_larger_sorts(997);
     test_larger_sorts(1000);
     test_larger_sorts(1009);
 
     test_pointer_sort();
+    test_adversarial_quicksort(1 << 20);
 
     return 0;
 }