Checked that complexity of std::sort_heap is 2N log(N) comparisons

[nilayvaish]

Summary

https://wg21.link/LWG2444 updated the comparison complexity of

std:sort_heap to be at most 2N log (N) where N == last - first.  In the
current implementation, we invoke __pop_heap exactly N-1 times.  In each
call to __pop_heap, we first go down the heap from first to possibly
last in the function __floyd_sift_down.  Then, we possibly go back up in
the function __sift_up.

In the function __floyd_sift_down, there is loop in which one comparison
is made in each iteration.  The loop runs till __child becomes greater
than (__len - 2) / 2.  __child starts at 0 and it is at least set to 2 *
__child + 1 on each iteration.  Thus, after k iterations, __child will
be at least 2^k - 1.  After log(N) iterations,  __child >= 2^(log(N)) -
1 = N - 1 > (__len - 2) / 2.  This means that the while loop in the
function __floyd_sift_down would perform at most log(N) comparisons on
each invocation.

In the function __sift_up, there is one comparison made that will almost
always occur.  After that there is a do-while loop.  The comparison
function is invoked once in each iteration.  In the worst case, the loop
will run till __len goes down to zero.  It can start from (N-3)/2.  In
each iteration, __len goes down to (__len-1) / 2.  After k iterations,
__len will be at most (N - 2^(k+1) -1) / 2^(k+1).  Thus, __len will
become  when (N-2^(k+1)-1) < 2^(k+1)  i.e. N  < 2^(k+2) + 1.  This means
at most log(N) - 1 iterations for the loop.  So in total at most log(N)
  comparison will be performed in __sift_up.

So overall for each iteration of the loop in __pop_heap, there will at
most 2 log(N) comparisons.  So, the total number of comparisons is
at most 2 N log(N).

[philnik]

Please add a test that counts the number of comparisons to show that it actually only takes 2N log(N) comparisons.

[nilayvaish]

Updated the test used for testing the complexity of heap sort implementation.

[nilayvaish]

Removed #include <iostream> as it is not required.

[nilayvaish]

In D144538#4144200, @philnik wrote:

Please add a test that counts the number of comparisons to show that it actually only takes 2N log(N) comparisons.

I updated the existing test to test for more lengths at a tighter complexity than what the C++ standard requires.

[nilayvaish]

Pinging reviewers!

[philnik]

libcxx/test/libcxx/algorithms/alg.sorting/alg.heap.operations/sort.heap/complexity.pass.cpp

49

Could you move this test to libcxx/test/std and also add it to ranges_sort_heap.pass.cpp?

73

[nilayvaish]

Addressed review comments.

[nilayvaish]

Addressed review comments.

[philnik]

LGTM with comments addressed.

libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/sort.heap/complexity.pass.cpp

63–66

This comments seems to be wrong now. Same in the ranges test.

72

Also for the ranges code.

[nilayvaish]

Addressed review comments.

libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/sort.heap/complexity.pass.cpp

63–66

Dropped lines 64-66 here and in the ranges test.

72

Added assert here and in the ranges test.

libcxx/docs/Status/Cxx20Issues.csv

 "Issue #","Issue Name","Meeting","Status","First released version","Labels"
 "`2070 <https://wg21.link/LWG2070>`__","``allocate_shared``\  should use ``allocator_traits<A>::construct``\ ","Toronto","Resolved by `P0674R1 <https://wg21.link/P0674R1>`__",""
-"`2444 <https://wg21.link/LWG2444>`__","Inconsistent complexity for ``std::sort_heap``\ ","Toronto","",""
+"`2444 <https://wg21.link/LWG2444>`__","Inconsistent complexity for ``std::sort_heap``\ ","Toronto","|Nothing To Do|",""
 "`2593 <https://wg21.link/LWG2593>`__","Moved-from state of Allocators","Toronto","",""
 "`2597 <https://wg21.link/LWG2597>`__","``std::log``\  misspecified for complex numbers","Toronto","",""
 "`2783 <https://wg21.link/LWG2783>`__","``stack::emplace()``\  and ``queue::emplace()``\  should return ``decltype(auto)``\ ","Toronto","|Complete|",""
 "`2932 <https://wg21.link/LWG2932>`__","Constraints on parallel algorithm implementations are underspecified","Toronto","",""
 "`2937 <https://wg21.link/LWG2937>`__","Is ``equivalent(""existing_thing"", ""not_existing_thing"")``\  an error","Toronto","|Complete|",""
 "`2940 <https://wg21.link/LWG2940>`__","``result_of``\  specification also needs a little cleanup","Toronto","|Nothing To Do|",""
 "`2942 <https://wg21.link/LWG2942>`__","LWG 2873's resolution missed ``weak_ptr::owner_before``\ ","Toronto","|Complete|",""
 "`2954 <https://wg21.link/LWG2954>`__","Specialization of the convenience variable templates should be prohibited","Toronto","|Complete|",""

libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/sort.heap/complexity.pass.cpp

 #include <algorithm>
 #include <cassert>
 #include <random>
 
 #include "test_macros.h"
 
 struct Stats {
   int compared = 0;
-  int copied = 0;
-  int moved = 0;
+  int copied   = 0;
+  int moved    = 0;
 } stats;
 
 struct MyInt {
   int value;
   explicit MyInt(int xval) : value(xval) {}
   MyInt(const MyInt& other) : value(other.value) { ++stats.copied; }
   MyInt(MyInt&& other) : value(other.value) { ++stats.moved; }
   MyInt& operator=(const MyInt& other) {
     value = other.value;
     ++stats.copied;
     return *this;
   }
   MyInt& operator=(MyInt&& other) {
     value = other.value;
     ++stats.moved;
     return *this;
   }
   friend bool operator<(const MyInt& a, const MyInt& b) {
     ++stats.compared;
     return a.value < b.value;
   }
 };
 
-int main(int, char**)
-{
-  const int N = 100'000;
+int main(int, char**) {
+  constexpr int N = (1 << 20);
   std::vector<MyInt> v;
   v.reserve(N);
   std::mt19937 g;
-  for (int i = 0; i < N; ++i)
-    v.emplace_back(g());
-  std::make_heap(v.begin(), v.end());
-
+  for (int i = 0; i < N; ++i) {
+    v.emplace_back(i);
+  }
+  for (int logn = 10; logn <= 20; ++logn) {
+    const int n = (1 << logn);
+    auto first  = v.begin();
+    auto last   = v.begin() + n;
+    std::shuffle(first, last, g);
+    std::make_heap(first, last);
     // The exact stats of our current implementation are recorded here.
-  // If something changes to make them go a bit up or down, that's probably fine,
-  // and we can just update this test.
-  // But if they suddenly leap upward, that's a bad thing.
-
     stats = {};
-  std::sort_heap(v.begin(), v.end());
-  assert(stats.copied == 0);
-  assert(stats.moved == 1'764'997);
+    std::sort_heap(first, last);
+    LIBCPP_ASSERT(stats.copied == 0);
+    LIBCPP_ASSERT(stats.moved <= 2 * n + n * logn);
 #ifndef _LIBCPP_ENABLE_DEBUG_MODE
-  assert(stats.compared == 1'534'701);
+    LIBCPP_ASSERT(stats.compared <= n * logn);
 #endif
-
-  assert(std::is_sorted(v.begin(), v.end()));
-
+    LIBCPP_ASSERT(std::is_sorted(first, last));
+    LIBCPP_ASSERT(stats.compared <= 2 * n * logn);
+  }
   return 0;
 }

libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/sort.heap/ranges_sort_heap.pass.cpp

 //   requires sortable<iterator_t<R>, Comp, Proj>
 //   constexpr borrowed_iterator_t<R>
 //     ranges::sort_heap(R&& r, Comp comp = {}, Proj proj = {});                             // since C++20
 
 #include <algorithm>
 #include <array>
 #include <concepts>
 #include <functional>
+#include <random>
 #include <ranges>
 
 #include "almost_satisfies_types.h"
 #include "boolean_testable.h"
 #include "test_iterators.h"
 
 // SFINAE tests.
 
constexpr bool test() {
   { // `std::ranges::dangling` is returned.
     [[maybe_unused]] std::same_as<std::ranges::dangling> decltype(auto) result =
         std::ranges::sort_heap(std::array{2, 1, 3});
   }
 
   return true;
 }
 
+struct Stats {
+  int compared = 0;
+  int copied   = 0;
+  int moved    = 0;
+} stats;
+
+struct MyInt {
+  int value;
+  explicit MyInt(int xval) : value(xval) {}
+  MyInt(const MyInt& other) : value(other.value) { ++stats.copied; }
+  MyInt(MyInt&& other) : value(other.value) { ++stats.moved; }
+  MyInt& operator=(const MyInt& other) {
+    value = other.value;
+    ++stats.copied;
+    return *this;
+  }
+  MyInt& operator=(MyInt&& other) {
+    value = other.value;
+    ++stats.moved;
+    return *this;
+  }
+  static bool Comp(const MyInt& a, const MyInt& b) {
+    ++stats.compared;
+    return a.value < b.value;
+  }
+};
+
+void test_complexity() {
+  constexpr int N = (1 << 20);
+  std::vector<MyInt> v;
+  v.reserve(N);
+  std::mt19937 g;
+  for (int i = 0; i < N; ++i) {
+    v.emplace_back(i);
+  }
+  for (int logn = 10; logn <= 20; ++logn) {
+    const int n = (1 << logn);
+    auto first  = v.begin();
+    auto last   = v.begin() + n;
+    std::shuffle(first, last, g);
+    std::make_heap(first, last, &MyInt::Comp);
+    // The exact stats of our current implementation are recorded here.
+    stats = {};
+    std::ranges::sort_heap(first, last, &MyInt::Comp);
+    LIBCPP_ASSERT(stats.copied == 0);
+    LIBCPP_ASSERT(stats.moved <= 2 * n + n * logn);
+#ifndef _LIBCPP_ENABLE_DEBUG_MODE
+    LIBCPP_ASSERT(stats.compared <= n * logn);
+#endif
+    LIBCPP_ASSERT(std::is_sorted(first, last, &MyInt::Comp));
+    LIBCPP_ASSERT(stats.compared <= 2 * n * logn);
+  }
+}
+
 int main(int, char**) {
   test();
   static_assert(test());
-
+  test_complexity();
   return 0;
 }