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

50

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

74

[nilayvaish]

Addressed review comments.

[nilayvaish]

Addressed review comments.

[philnik]

LGTM with comments addressed.

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

65–68

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

77

Also for the ranges code.

[nilayvaish]

Addressed review comments.

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

65–68

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

77

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/libcxx/algorithms/alg.sorting/alg.heap.operations/sort.heap/complexity.pass.cpp

 
 // <algorithm>
 
 // template<class Iter>
 //   void sort_heap(Iter first, Iter last);
 
 #include <algorithm>
 #include <cassert>
+#include <iostream>
 #include <random>
 
 #include "test_macros.h"
 
 struct Stats {
   int compared = 0;
   int copied = 0;
   int moved = 0;
MyInt& operator=(MyInt&& other) {
     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;
+  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.
+    // 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());
+    std::sort_heap(first, last);
     assert(stats.copied == 0);
-  assert(stats.moved == 1'764'997);
+    assert(stats.moved <= 2 * n + n * logn);
 #ifndef _LIBCPP_ENABLE_DEBUG_MODE
-  assert(stats.compared == 1'534'701);
+    assert(stats.compared <= n * logn);
 #endif
-
-  assert(std::is_sorted(v.begin(), v.end()));
-
+    assert(std::is_sorted(first, last));
+  }
   return 0;
 }