Skip to content

Navigation Menu

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

Appearance settings

Avoid unnecessary swaps for equal elements in __sift_down #139556

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Draft
wants to merge 1 commit into
base: main
Choose a base branch
Loading
from

Conversation

winner245
Copy link
Contributor

This PR optimizes the __sift_down operation to avoid unnecessary swaps when the parent and child elements are equal. The current implementation continues sifting down even when the parent and child are equal, leading to redundant operations. In the worst case (all elements equal), the current implementation performs O(log n) swaps per __sift_down. The optimized version reduces this to O(1) when the parent and child are equal.

@tgymnich tgymnich added the libc++ libc++ C++ Standard Library. Not GNU libstdc++. Not libc++abi. label May 12, 2025
@llvmbot
Copy link
Member

llvmbot commented May 12, 2025

@llvm/pr-subscribers-libcxx

Author: Peng Liu (winner245)

Changes

This PR optimizes the __sift_down operation to avoid unnecessary swaps when the parent and child elements are equal. The current implementation continues sifting down even when the parent and child are equal, leading to redundant operations. In the worst case (all elements equal), the current implementation performs O(log n) swaps per __sift_down. The optimized version reduces this to O(1) when the parent and child are equal.


Full diff: https://github.com/llvm/llvm-project/pull/139556.diff

2 Files Affected:

  • (modified) libcxx/include/__algorithm/sift_down.h (+2-2)
  • (added) libcxx/test/libcxx/algorithms/alg.sorting/alg.heap.operations/make.heap/sift_down_equal_elements.pass.cpp (+66)
diff --git a/libcxx/include/__algorithm/sift_down.h b/libcxx/include/__algorithm/sift_down.h
index 42803e30631fb..088d5e34c374b 100644
--- a/libcxx/include/__algorithm/sift_down.h
+++ b/libcxx/include/__algorithm/sift_down.h
@@ -51,7 +51,7 @@ __sift_down(_RandomAccessIterator __first,
   }
 
   // check if we are in heap-order
-  if (__comp(*__child_i, *__start))
+  if (!__comp(*__start, *__child_i))
     // we are, __start is larger than its largest child
     return;
 
@@ -75,7 +75,7 @@ __sift_down(_RandomAccessIterator __first,
     }
 
     // check if we are in heap-order
-  } while (!__comp(*__child_i, __top));
+  } while (__comp(__top, *__child_i));
   *__start = std::move(__top);
 }
 
diff --git a/libcxx/test/libcxx/algorithms/alg.sorting/alg.heap.operations/make.heap/sift_down_equal_elements.pass.cpp b/libcxx/test/libcxx/algorithms/alg.sorting/alg.heap.operations/make.heap/sift_down_equal_elements.pass.cpp
new file mode 100644
index 0000000000000..83d3c0bd6813f
--- /dev/null
+++ b/libcxx/test/libcxx/algorithms/alg.sorting/alg.heap.operations/make.heap/sift_down_equal_elements.pass.cpp
@@ -0,0 +1,66 @@
+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03
+
+// <algorithm>
+
+// template<class Iter>
+//   void make_heap(Iter first, Iter last);
+
+// This test ensures that equivalent elements are not moved or copied when the heap is created.
+
+#include <algorithm>
+#include <cassert>
+#include <vector>
+#include <utility>
+
+struct Stats {
+  int compared = 0;
+  int copied   = 0;
+  int moved    = 0;
+} stats;
+
+struct MyPair {
+  std::pair<int, int> p;
+  MyPair(int a, int b) : p{a, b} {}
+  MyPair(const MyPair& other) : p(other.p) { ++stats.copied; }
+  MyPair(MyPair&& other) : p(other.p) { ++stats.moved; }
+  MyPair& operator=(const MyPair& other) {
+    p = other.p;
+    ++stats.copied;
+    return *this;
+  }
+  MyPair& operator=(MyPair&& other) {
+    p = other.p;
+    ++stats.moved;
+    return *this;
+  }
+  friend bool operator<(const MyPair& lhs, const MyPair& rhs) {
+    ++stats.compared;
+    return lhs.p.first < rhs.p.first;
+  }
+  friend bool operator==(const MyPair& lhs, const MyPair& rhs) { return lhs.p == rhs.p; }
+};
+
+int main(int, char**) {
+  std::vector<MyPair> hp{{42, 1}, {42, 2}, {42, 3}, {42, 4}, {42, 5}, {42, 6}};
+  std::vector<MyPair> original_hp = hp;
+
+  stats = {};
+  std::make_heap(hp.begin(), hp.end());
+
+  assert(stats.copied == 0);
+  assert(stats.moved == 0);
+  assert(stats.compared == static_cast<int>(hp.size()) - 1);
+
+  assert(hp == original_hp);
+  assert(std::is_heap(hp.begin(), hp.end()));
+
+  return 0;
+}

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
libc++ libc++ C++ Standard Library. Not GNU libstdc++. Not libc++abi.
Projects
None yet
Development

Successfully merging this pull request may close these issues.

3 participants
Morty Proxy This is a proxified and sanitized view of the page, visit original site.