Cleanup __uninitialized_temporary_buffer internals.

[EricWF]

Summary

There are a few improvements this patch makes. First, it only
uses aligned allocation when the type actually requires it. This
addresses a sizable user-reported performance regression in some of the
algorithms.

Second, it removes a significant amount unused template & function parameters,
which improves code size and makes the type less error prone and more readable.

And finally, it fixes a bug where operator new/delete were being called
directly, rather than as a builtin -- preventing the compiler from
eliding the allocation.

[EricWF]

Fix C++03 build

[MaskRay]

Thanks for posting the fix (the lost !__is_overaligned_for_new branch).

Switching to __libcpp_allocate removes some duplicate code, which looks good to me. https://clang.llvm.org/docs/LanguageExtensions.html#builtin-operator-new-and-builtin-operator-delete

If you don't use arc diff, there needs to be some context. https://llvm.org/docs/Phabricator.html#requesting-a-review-via-the-web-interface

uses aligned allocation when the type actually requires it. [...]

You may accidentally indent the paragraph by 4 spaces, so it was detected as a code block in Markdown.

[Mordante]

Thanks for working on this. In general looks good, I like to see a green CI.

libcxx/include/__memory/uninitialized_buffer.h

38

pre-existing nit: sizeof(_Tp) * __count_ seems more natural and matches line 48.

libcxx/include/new

297

s/_LIBCPP_INLINE_VISIBILITY/_LIBCPP_HIDE_FROM_ABI/

300

Mainly curious, but would it make sense to have this check in the Clang builtin?

[MaskRay]

libcxx/include/new

300

Mainly curious, but would it make sense to have this check in the Clang builtin?

Which check?

[ldionne]

libcxx/include/__algorithm/inplace_merge.h

228

We were using nothrow to make it clear that this will return nullptr instead of throwing if the allocation fails. This was initially designed in the context of making sure that exception safety is really easy to determine since this will be used inside PSTL, where we want to have strict control over what can and can't throw (because we need to exclusively propagate exceptions that originate from the library "setup" code, but terminate for any other user-thrown exception).

I still feel like nothrow has its place here in that context.

libcxx/include/__memory/uninitialized_buffer.h

33

I don't think we need the default argument here since you're always passing an argument to the constructor below.

35

IIUC, you're not destroying the elements in the buffer anymore, which seems like a bug.

48

__libcpp_allocate vs operator new is a great catch, thanks for catching that.

66–67

We were using the _Tp[] syntax so that you would get an array specialization of unique_ptr<_Tp[]>, which then supports nice things like operator[]. I still think it makes sense to do that.

[ldionne]

@davidxl @mingmingl Did you folks notice the perf regression through libc++'s own benchmarks? If not, can you please share which benchmarks you used to see the difference? I'd like to add something to libc++'s benchmark suite alongside with this patch so we can have a concrete "regression test" and verify that this is making things better.

Edit: We do have an ongoing problem in libc++ that we have some benchmarks and we run them on a regular basis in the CI, but we don't have any infrastructure that allows comparing benchmark results and detecting regressions. This makes these benchmarks a lot less useful than they could be.

libcxx/include/__memory/uninitialized_buffer.h

10

Not attached to anything: would it be possible to upload the patch with context? This makes it easier to review. arc diff does that automatically, normally.

[ldionne]

Also see https://github.com/llvm/llvm-project/issues/63603 for a related issue that could actually improve the perf potentially more than this patch for small number of elements.

[EricWF]

libcxx/include/__algorithm/inplace_merge.h

228

I strongly disagree. It's very confusing to introduce a novel use of a tag type, to document rather than dispatch, on an API that's purpose is to _maybe_ provide memory _if_ it's available.

If we're looking to document the semantics of get_temporary_buffer further, that's OK. If we're looking to improve the usability & safety of the of the API, that's OK too.
But let's proceed with that some other way.

I'll change the name to get __maybe_get_temporary_buffer.

libcxx/include/__memory/uninitialized_buffer.h

33

I'm with you. I tried to make this not have a default constructor, but there are a bunch of uses in the algorithms header where the type is default constructod.

libcxx/include/new

297

Do we have a doc describing what the difference is and providing top? That way I can stop making the mistake in the future?

300

I think they mean dispatching the call to overaligned new. And I don't think so.
The clang builtin is a very thin wrapper whose only job is to annotate the function call as "builtin" so it can be elided.

Plus, I think the library has more knowledge about the availability of these functions, since we provide them.

[EricWF]

libcxx/include/__memory/uninitialized_buffer.h

35

We never we destroying the elements in the buffer.

The deleter template parameter was always nop, but the complexity hid this issue. It's also not possible for the unique_ptr to know how many elements were actually created when it gets deleted, so the API was inherently unsafe from the start. I had assumed the algorithms were doing it because unique_ptr certainly wasn't .

[EricWF]

Add documentation & rename __make_uninitialized_buffer to makes the non-throwing allocation semantics more readily apparent.

[EricWF]

In D154017#4459618, @ldionne wrote:

@davidxl @mingmingl Did you folks notice the perf regression through libc++'s own benchmarks? If not, can you please share which benchmarks you used to see the difference? I'd like to add something to libc++'s benchmark suite alongside with this patch so we can have a concrete "regression test" and verify that this is making things better.

Edit: We do have an ongoing problem in libc++ that we have some benchmarks and we run them on a regular basis in the CI, but we don't have any infrastructure that allows comparing benchmark results and detecting regressions. This makes these benchmarks a lot less useful than they could be.

Yeah, benchmarking infrastructure is hard to set up, especially one that can largely go unsupervised. My understanding is that the benchmarks we have are more macroscale. I believe the benchmarks which caught this internally are closer to a macro-scale benchmark and are dependent on a ton of infrastructure to gather and report macro-scale performance data, which makes it non-trivial to share externally.

(Also it's an unfortunate truth of benchmarks that macroscale ones seem to be much better at detecting regressions than nice & tidy microbenchmarks).

If somebody else knows more about the benchmarks that detected this, please chime in or correct me.

libcxx/include/__memory/uninitialized_buffer.h

10

Yeah, my arc install is a bit broken - and haven't had the time to fix it.

If you're looking to apply the patch, you can do so by downloading the raw patch, cd'ing into the libcxx directory, and running git apply <raw-patch-file>.

[ldionne]

libcxx/include/__memory/uninitialized_buffer.h

46

Nit: .. => .

51–53

The ability to have a non-trivial destructor was the reason why we created this class and refactored the existing uses of get_temporary_buffer() in the first place. We can't remove this functionality, this is needed for implementing the GCD backend in the PSTL.

61

__try_allocate_uninitialized_buffer?

libcxx/include/new

297

From __config:

// Just so we can migrate to the new macros gradually.
#  define _LIBCPP_INLINE_VISIBILITY _LIBCPP_HIDE_FROM_ABI

[MaskRay]

libcxx/include/new

297

https://libcxx.llvm.org/DesignDocs/VisibilityMacros.html

_LIBCPP_INLINE_VISIBILITY - Historical predecessor of _LIBCPP_HIDE_FROM_ABI – please use _LIBCPP_HIDE_FROM_ABI instead.

[MaskRay]

In D154017#4461107, @EricWF wrote:

In D154017#4459618, @ldionne wrote:

@davidxl @mingmingl Did you folks notice the perf regression through libc++'s own benchmarks? If not, can you please share which benchmarks you used to see the difference? I'd like to add something to libc++'s benchmark suite alongside with this patch so we can have a concrete "regression test" and verify that this is making things better.

Edit: We do have an ongoing problem in libc++ that we have some benchmarks and we run them on a regular basis in the CI, but we don't have any infrastructure that allows comparing benchmark results and detecting regressions. This makes these benchmarks a lot less useful than they could be.

Yeah, benchmarking infrastructure is hard to set up, especially one that can largely go unsupervised. My understanding is that the benchmarks we have are more macroscale. I believe the benchmarks which caught this internally are closer to a macro-scale benchmark and are dependent on a ton of infrastructure to gather and report macro-scale performance data, which makes it non-trivial to share externally.

(Also it's an unfortunate truth of benchmarks that macroscale ones seem to be much better at detecting regressions than nice & tidy microbenchmarks).

If somebody else knows more about the benchmarks that detected this, please chime in or correct me.

I have only read some mimalloc and jemalloc code and I suspect they are less affected by omitting if (__is_overaligned_for_new(__align)).
(For mimalloc, it's almost not affected except a negligible overhead due to checking whether the alignment is a power of 2.)
tcmalloc seems to be affected more, but I have no insight into it. class_to_size

[EricWF]

libcxx/include/__memory/uninitialized_buffer.h

51–53

We can cross that bridge and add that functionality when it's needed.

As it stands now, the features your referring to are both unused and broken.
I'm happy to have a more throughout conversation on API design later, but right now we're trying to fix forward to avoid having to revert even further.

It would be better & safer to check in functionality only once it's going to be used. Otherwise, we get untested dead code with bugs in it waiting to be discovered.

61

I have no preference on the name, but try to me implies that it can fail and throw. Where maybe seems like failing is a non-exceptional condition, as it is here.
Your call.

[Mordante]

libcxx/include/new

300

I think they mean dispatching the call to overaligned new. And I don't think so.

Yes that check.

The clang builtin is a very thin wrapper whose only job is to annotate the function call as "builtin" so it can be elided.

Plus, I think the library has more knowledge about the availability of these functions, since we provide them.

I assumed the compiler knows more about the required alignment. But as said, mainly curious so no request to change anything.

[EricWF]

Uploading with context

[ldionne]

__uninitialized_buffer was reverted, so I think this can be closed.

libcxx/include/__algorithm/inplace_merge.h

 __inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
               _Compare&& __comp)
 {
     typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
     typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
     difference_type __len1 = _IterOps<_AlgPolicy>::distance(__first, __middle);
     difference_type __len2 = _IterOps<_AlgPolicy>::distance(__middle, __last);
     difference_type __buf_size = _VSTD::min(__len1, __len2);
-    auto __buf = std::__make_uninitialized_buffer<value_type[]>(nothrow, __buf_size);
+    auto __buf = std::__maybe_allocate_uninitialized_buffer<value_type>(__buf_size);
     return std::__inplace_merge<_AlgPolicy>(
         std::move(__first),
         std::move(__middle),
         std::move(__last),
         __comp,
         __len1,
         __len2,
         __buf.get(),

libcxx/include/__algorithm/stable_partition.h

while (true)
         if (!__pred(*__first))
             break;
         ++__first;
     }
     // We now have a reduced range [__first, __last)
     // *__first is known to be false
     difference_type __len = _IterOps<_AlgPolicy>::distance(__first, __last);
 
-    __uninitialized_buffer_t<value_type[]> __buf;
+    __uninitialized_buffer_t<value_type> __buf;
     if (__len >= __alloc_limit)
-        __buf = std::__make_uninitialized_buffer<value_type[]>(nothrow, __len);
+        __buf = std::__maybe_allocate_uninitialized_buffer<value_type>(__len);
 
     return std::__stable_partition_impl<_AlgPolicy, _Predicate&>(
         std::move(__first),
         std::move(__last),
         __pred,
         __len,
         std::make_pair(__buf.get(), __buf ? __len : 0),
         forward_iterator_tag());
do
         if (__first == --__last)
             return __first;
     } while (!__pred(*__last));
     // We now have a reduced range [__first, __last]
     // *__first is known to be false
     // *__last is known to be true
     // __len >= 2
     difference_type __len = _IterOps<_AlgPolicy>::distance(__first, __last) + 1;
-    __uninitialized_buffer_t<value_type[]> __buf;
+    __uninitialized_buffer_t<value_type> __buf;
     if (__len >= __alloc_limit)
-        __buf = std::__make_uninitialized_buffer<value_type[]>(nothrow, __len);
+        __buf = std::__maybe_allocate_uninitialized_buffer<value_type>(__len);
 
     return std::__stable_partition_impl<_AlgPolicy, _Predicate&>(
         std::move(__first),
         std::move(__last),
         __pred,
         __len,
         std::make_pair(__buf.get(), __buf ? __len : 0),
         bidirectional_iterator_tag());

libcxx/include/__algorithm/stable_sort.h

 
 template <class _AlgPolicy, class _RandomAccessIterator, class _Compare>
 inline _LIBCPP_HIDE_FROM_ABI
 void __stable_sort_impl(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp) {
   using value_type = typename iterator_traits<_RandomAccessIterator>::value_type;
   using difference_type = typename iterator_traits<_RandomAccessIterator>::difference_type;
 
   difference_type __len = __last - __first;
-  __uninitialized_buffer_t<value_type[]> __buf;
+
+  __uninitialized_buffer_t<value_type> __buf;
   if (__len > static_cast<difference_type>(__stable_sort_switch<value_type>::value))
-        __buf = std::__make_uninitialized_buffer<value_type[]>(nothrow, __len);
+        __buf = std::__maybe_allocate_uninitialized_buffer<value_type>(__len);
 
   std::__stable_sort<_AlgPolicy, __comp_ref_type<_Compare> >(
       __first, __last, __comp, __len, __buf.get(), __buf ? __len : 0);
   std::__check_strict_weak_ordering_sorted(__first, __last, __comp);
 }
 
 template <class _RandomAccessIterator, class _Compare>
 inline _LIBCPP_HIDE_FROM_ABI

libcxx/include/__memory/uninitialized_buffer.h

 //===----------------------------------------------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef _LIBCPP___MEMORY_UNINITIALIZED_BUFFER_H
 #define _LIBCPP___MEMORY_UNINITIALIZED_BUFFER_H
 
 #include <__config>
-#include <__memory/construct_at.h>
 #include <__memory/unique_ptr.h>
-#include <__type_traits/is_array.h>
-#include <__type_traits/is_default_constructible.h>
-#include <__type_traits/remove_extent.h>
 #include <__utility/move.h>
 #include <cstddef>
 #include <new>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
-// __make_uninitialized_buffer is a utility function to allocate some memory for scratch storage. The __destructor is
-// called before deleting the memory, making it possible to destroy any leftover elements. The __destructor is called
-// with the pointer to the first element and the total number of elements.
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-template <class _Destructor>
 class __uninitialized_buffer_deleter {
   size_t __count_;
-  _Destructor __destructor_;
 
 public:
-  template <class _Dummy = int, __enable_if_t<is_default_constructible<_Destructor>::value, _Dummy> = 0>
-  _LIBCPP_HIDE_FROM_ABI __uninitialized_buffer_deleter() : __count_(0) {}
-
-  _LIBCPP_HIDE_FROM_ABI __uninitialized_buffer_deleter(size_t __count, _Destructor __destructor)
-      : __count_(__count), __destructor_(std::move(__destructor)) {}
+  _LIBCPP_HIDE_FROM_ABI explicit _LIBCPP_CONSTEXPR __uninitialized_buffer_deleter(size_t __count = 0) _NOEXCEPT
+      : __count_(__count) {}
 
   template <class _Tp>
-  _LIBCPP_HIDE_FROM_ABI void operator()(_Tp* __ptr) {
-    __destructor_(__ptr, __count_);
-#ifdef _LIBCPP_HAS_NO_ALIGNED_ALLOCATION
-    ::operator delete(__ptr);
-#else
-    ::operator delete(__ptr, __count_ * sizeof(_Tp), align_val_t(_LIBCPP_ALIGNOF(_Tp)));
-#endif
+  _LIBCPP_HIDE_FROM_ABI void operator()(_Tp* __ptr) const _NOEXCEPT {
+    std::__libcpp_deallocate(__ptr, __count_ * sizeof(_Tp), _LIBCPP_ALIGNOF(_Tp));
   }
 };
 
-struct __noop {
-  template <class... _Args>
-  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 void operator()(_Args&&...) const {}
-};
-
-template <class _Array, class _Destructor = __noop>
-using __uninitialized_buffer_t = unique_ptr<_Array, __uninitialized_buffer_deleter<_Destructor> >;
+template <class _Tp>
+using __uninitialized_buffer_t = unique_ptr<_Tp, __uninitialized_buffer_deleter>;
 
-template <class _Array, class _Destructor = __noop>
-_LIBCPP_HIDE_FROM_ABI _LIBCPP_NO_CFI __uninitialized_buffer_t<_Array, _Destructor>
-__make_uninitialized_buffer(nothrow_t, size_t __count, _Destructor __destructor = __noop()) {
-  static_assert(is_array<_Array>::value, "");
-  using _Tp = __remove_extent_t<_Array>;
-
-#ifdef _LIBCPP_HAS_NO_ALIGNED_ALLOCATION
-  _Tp* __ptr = static_cast<_Tp*>(::operator new(sizeof(_Tp) * __count, nothrow));
-#else
-  _Tp* __ptr = static_cast<_Tp*>(::operator new(sizeof(_Tp) * __count, align_val_t(_LIBCPP_ALIGNOF(_Tp)), nothrow));
-#endif
+/**
+ * __maybe_allocate_uninitialized_buffer
+ *
+ * Attempt to allocate an uninitialized buffer of `__count` elements of type `_Tp`..
+ * In case of allocation failure, the returned object will contain a nullptr and count 0.
+ *
+ * Attention points:
+ *
+ * 1. No initialization or destruction of elements:
+ *    It is the callers responsibility to manage both construction and destruction of the elements created
+ *    in the buffer.
+ *
+ * 2. No exception on allocation failure:
+ *    Instead it returns nullptr when an allocation failure occurs. It is the callers responsibility
+ *    to check for and handle this case.
+ */
+template <class _Tp>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_NO_CFI __uninitialized_buffer_t<_Tp>
+__maybe_allocate_uninitialized_buffer(size_t __count) {
+  _Tp* __ptr = static_cast<_Tp*>(std::__libcpp_allocate(sizeof(_Tp) * __count, _LIBCPP_ALIGNOF(_Tp), nothrow));
 
-  using _Deleter = __uninitialized_buffer_deleter<_Destructor>;
-  return unique_ptr<_Array, _Deleter>(__ptr, _Deleter(__count, std::move(__destructor)));
+  using _Deleter = __uninitialized_buffer_deleter;
+  return __uninitialized_buffer_t<_Tp>(__ptr, _Deleter(__ptr ? __count : 0));
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___MEMORY_UNINITIALIZED_BUFFER_H

libcxx/include/new

if (__is_overaligned_for_new(__align)) {
     return __libcpp_operator_new(__size, __align_val);
   }
 #endif
 
   (void)__align;
   return __libcpp_operator_new(__size);
 }
 
+inline _LIBCPP_HIDE_FROM_ABI
+void *__libcpp_allocate(size_t __size, size_t __align, nothrow_t) {
+#ifndef _LIBCPP_HAS_NO_ALIGNED_ALLOCATION
+  if (__is_overaligned_for_new(__align)) {
+    const align_val_t __align_val = static_cast<align_val_t>(__align);
+    return __libcpp_operator_new(__size, __align_val, nothrow);
+  }
+#endif
+
+  (void)__align;
+  return __libcpp_operator_new(__size, nothrow);
+}
+
 template <class ..._Args>
 _LIBCPP_INLINE_VISIBILITY
 void __do_deallocate_handle_size(void *__ptr, size_t __size, _Args ...__args) {
 #ifdef _LIBCPP_HAS_NO_SIZED_DEALLOCATION
   (void)__size;
   return std::__libcpp_operator_delete(__ptr, __args...);
 #else
   return std::__libcpp_operator_delete(__ptr, __size, __args...);