1 files changed, 16 insertions, 4 deletions
diff --git a/libcxx/include/__algorithm/make_heap.h b/libcxx/include/__algorithm/make_heap.h
index e8f0cdb27333..8cfeda2b5981 100644
--- a/libcxx/include/__algorithm/make_heap.h
+++ b/libcxx/include/__algorithm/make_heap.h
@@ -12,9 +12,11 @@
 #include <__algorithm/comp.h>
 #include <__algorithm/comp_ref_type.h>
 #include <__algorithm/iterator_operations.h>
+#include <__algorithm/push_heap.h>
 #include <__algorithm/sift_down.h>
 #include <__config>
 #include <__iterator/iterator_traits.h>
+#include <__type_traits/is_arithmetic.h>
 #include <__utility/move.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
@@ -31,13 +33,23 @@ inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 void
 __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare&& __comp) {
   __comp_ref_type<_Compare> __comp_ref = __comp;
 
-  using difference_type = typename iterator_traits<_RandomAccessIterator>::difference_type;
-  difference_type __n   = __last - __first;
+  using __diff_t     = __iter_diff_t<_RandomAccessIterator>;
+  const __diff_t __n = __last - __first;
+
+  static const bool __assume_both_children = is_arithmetic<__iter_value_type<_RandomAccessIterator> >::value;
+
+  // While it would be correct to always assume we have both children, in practice we observed this to be a performance
+  // improvement only for arithmetic types.
+  const __diff_t __sift_down_n = __assume_both_children ? ((__n & 1) ? __n : __n - 1) : __n;
+
   if (__n > 1) {
     // start from the first parent, there is no need to consider children
-    for (difference_type __start = (__n - 2) / 2; __start >= 0; --__start) {
-      std::__sift_down<_AlgPolicy>(__first, __comp_ref, __n, __first + __start);
+
+    for (__diff_t __start = (__sift_down_n - 2) / 2; __start >= 0; --__start) {
+      std::__sift_down<_AlgPolicy, __assume_both_children>(__first, __comp_ref, __sift_down_n, __start);
     }
+    if _LIBCPP_CONSTEXPR (__assume_both_children)
+      std::__sift_up<_AlgPolicy>(__first, __last, __comp, __n);
   }
 }