[libc++] Make pmr::monotonic_buffer_resource bump down

[philnik]

Summary

Bumping down is significantly faster than bumping up. This is ABI breaking, but the ABI of pmr::monotonic_buffer_resource was only stabilized in this release cycle, so we can still change it.
For a more detailed explanation why bumping down is better, see https://fitzgeraldnick.com/2019/11/01/always-bump-downwards.html.

[philnik]

Benchmarks:

--------------------------------
Benchmark          old       new
--------------------------------
bm_list/1      5.93 ns   4.05 ns
bm_list/8      46.8 ns   33.2 ns
bm_list/64      366 ns    240 ns
bm_list/512    3011 ns   1938 ns
bm_list/2048  14374 ns   8517 ns

[philnik]

Remove debug stuff

[philnik]

Try to fix CI

[philnik]

Try to fix CI

[ldionne]

libcxx/benchmarks/CMakeLists.txt

180

Can you add a link to the article (https://fitzgeraldnick.com/2019/11/01/always-bump-downwards.html) in the commit message?

[Mordante]

libcxx/benchmarks/CMakeLists.txt

180

I would love to see this link in the code too, that makes it a lot easier to find the design rationale than in the commit message.

libcxx/benchmarks/CMakeLists.txt

set(BENCHMARK_TESTS
     algorithms/ranges_sort_heap.bench.cpp
     algorithms/ranges_stable_sort.bench.cpp
     algorithms/sort.bench.cpp
     algorithms/sort_heap.bench.cpp
     algorithms/stable_sort.bench.cpp
     allocation.bench.cpp
     deque.bench.cpp
     filesystem.bench.cpp
     format_to_n.bench.cpp
     format_to.bench.cpp
     format.bench.cpp
     formatted_size.bench.cpp
     formatter_float.bench.cpp
     formatter_int.bench.cpp
     function.bench.cpp
     map.bench.cpp
+    monotonic_buffer.bench.cpp
     ordered_set.bench.cpp
     std_format_spec_string_unicode.bench.cpp
     string.bench.cpp
     stringstream.bench.cpp
     to_chars.bench.cpp
     unordered_set_operations.bench.cpp
     util_smartptr.bench.cpp
     variant_visit_1.bench.cpp

libcxx/benchmarks/monotonic_buffer.bench.cpp

+//===----------------------------------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#include <list>
+#include <memory_resource>
+
+#include "benchmark/benchmark.h"
+
+static void bm_list(benchmark::State& state) {
+  char buffer[16384];
+  std::pmr::monotonic_buffer_resource resource(buffer, sizeof(buffer));
+  for (auto _ : state) {
+    std::pmr::list<int> l(&resource);
+    for (size_t i = 0; i != state.range(); ++i) {
+      l.push_back(1);
+      benchmark::DoNotOptimize(l);
+    }
+    resource.release();
+  }
+}
+BENCHMARK(bm_list)->Range(1, 2048);
+
+BENCHMARK_MAIN();

libcxx/include/__memory_resource/monotonic_buffer_resource.h

public:
 
   _LIBCPP_HIDE_FROM_ABI monotonic_buffer_resource(size_t __initial_size, memory_resource* __upstream)
       : monotonic_buffer_resource(nullptr, __initial_size, __upstream) {}
 
   _LIBCPP_HIDE_FROM_ABI monotonic_buffer_resource(void* __buffer, size_t __buffer_size, memory_resource* __upstream)
       : __res_(__upstream) {
     __initial_.__start_ = static_cast<char*>(__buffer);
     if (__buffer != nullptr) {
-      __initial_.__cur_ = static_cast<char*>(__buffer);
+      __initial_.__cur_ = static_cast<char*>(__buffer) + __buffer_size;
       __initial_.__end_ = static_cast<char*>(__buffer) + __buffer_size;
     } else {
       __initial_.__cur_  = nullptr;
       __initial_.__size_ = __buffer_size;
     }
     __chunks_ = nullptr;
   }
 
   monotonic_buffer_resource(const monotonic_buffer_resource&) = delete;
 
   _LIBCPP_HIDE_FROM_ABI ~monotonic_buffer_resource() override { release(); }
 
   monotonic_buffer_resource& operator=(const monotonic_buffer_resource&) = delete;
 
   _LIBCPP_HIDE_FROM_ABI void release() {
-    __initial_.__cur_ = __initial_.__start_;
+    if (__initial_.__start_ != nullptr)
+      __initial_.__cur_ = __initial_.__end_;
     while (__chunks_ != nullptr) {
       __chunk_footer* __next = __chunks_->__next_;
       __res_->deallocate(__chunks_->__start_, __chunks_->__allocation_size(), __chunks_->__align_);
       __chunks_ = __next;
     }
   }
 
   _LIBCPP_HIDE_FROM_ABI memory_resource* upstream_resource() const { return __res_; }

libcxx/src/memory_resource.cpp

else {
     __fixed_pools_[i].__evacuate(p);
   }
 }
 
 bool synchronized_pool_resource::do_is_equal(const memory_resource& other) const noexcept { return &other == this; }
 
 // 23.12.6, mem.res.monotonic.buffer
 
+static void* align_down(size_t align, size_t size, void*& ptr, size_t& space) {
+  if (size > space)
+    return nullptr;
+
+  char* p1      = static_cast<char*>(ptr);
+  char* new_ptr = reinterpret_cast<char*>(reinterpret_cast<uintptr_t>(p1 - size) & ~(align - 1));
+
+  if (new_ptr < (p1 - space))
+    return nullptr;
+
+  ptr = new_ptr;
+  space -= p1 - new_ptr;
+
+  return ptr;
+}
+
 void* monotonic_buffer_resource::__initial_descriptor::__try_allocate_from_chunk(size_t bytes, size_t align) {
   if (!__cur_)
     return nullptr;
   void* new_ptr       = static_cast<void*>(__cur_);
-  size_t new_capacity = (__end_ - __cur_);
-  void* aligned_ptr   = std::align(align, bytes, new_ptr, new_capacity);
+  size_t new_capacity = (__cur_ - __start_);
+  void* aligned_ptr   = align_down(align, bytes, new_ptr, new_capacity);
   if (aligned_ptr != nullptr)
-    __cur_ = static_cast<char*>(new_ptr) + bytes;
+    __cur_ = static_cast<char*>(new_ptr);
   return aligned_ptr;
 }
 
 void* monotonic_buffer_resource::__chunk_footer::__try_allocate_from_chunk(size_t bytes, size_t align) {
   void* new_ptr       = static_cast<void*>(__cur_);
-  size_t new_capacity = (reinterpret_cast<char*>(this) - __cur_);
-  void* aligned_ptr   = std::align(align, bytes, new_ptr, new_capacity);
+  size_t new_capacity = (__cur_ - __start_);
+  void* aligned_ptr   = align_down(align, bytes, new_ptr, new_capacity);
   if (aligned_ptr != nullptr)
-    __cur_ = static_cast<char*>(new_ptr) + bytes;
+    __cur_ = static_cast<char*>(new_ptr);
   return aligned_ptr;
 }
 
 void* monotonic_buffer_resource::do_allocate(size_t bytes, size_t align) {
   const size_t footer_size  = sizeof(__chunk_footer);
   const size_t footer_align = alignof(__chunk_footer);
 
   auto previous_allocation_size = [&]() {
void* monotonic_buffer_resource::do_allocate(size_t bytes, size_t align) {
   size_t previous_capacity = previous_allocation_size();
 
   if (aligned_capacity <= previous_capacity) {
     size_t newsize   = 2 * (previous_capacity - footer_size);
     aligned_capacity = roundup(newsize, footer_align) + footer_size;
   }
 
   char* start            = (char*)__res_->allocate(aligned_capacity, align);
-  __chunk_footer* footer = (__chunk_footer*)(start + aligned_capacity - footer_size);
+  auto end               = start + aligned_capacity - footer_size;
+  __chunk_footer* footer = (__chunk_footer*)(end);
   footer->__next_        = __chunks_;
   footer->__start_       = start;
-  footer->__cur_         = start;
+  footer->__cur_         = end;
   footer->__align_       = align;
   __chunks_              = footer;
 
   return __chunks_->__try_allocate_from_chunk(bytes, align);
 }
 
 } // namespace pmr
 
 _LIBCPP_END_NAMESPACE_STD

libcxx/test/libcxx/utilities/utility/mem.res/mem.res.monotonic.buffer/mem.res.monotonic.buffer.mem/allocate_from_underaligned_buffer.pass.cpp

 //===----------------------------------------------------------------------===//
 //
 // 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, c++11, c++14
 // XFAIL: use_system_cxx_lib && target={{.+}}-apple-macosx10.{{9|10|11|12|13|14|15}}
 // XFAIL: use_system_cxx_lib && target={{.+}}-apple-macosx{{11.0|12.0}}
 
 // <memory_resource>
 
 // class monotonic_buffer_resource
 
-#include <memory_resource>
 #include <cassert>
+#include <memory_resource>
 
 #include "count_new.h"
 #include "test_macros.h"
 
 int main(int, char**) {
   globalMemCounter.reset();
   {
     alignas(4) char buffer[17];
-    auto mono1 = std::pmr::monotonic_buffer_resource(buffer + 1, 16, std::pmr::new_delete_resource());
+    auto mono1                    = std::pmr::monotonic_buffer_resource(buffer, 16, std::pmr::new_delete_resource());
     std::pmr::memory_resource& r1 = mono1;
 
     void* ret = r1.allocate(1, 1);
-    assert(ret == buffer + 1);
+    assert(ret == buffer + 15);
     mono1.release();
 
     ret = r1.allocate(1, 2);
-    assert(ret == buffer + 2);
+    assert(ret == buffer + 14);
     mono1.release();
 
     ret = r1.allocate(1, 4);
-    assert(ret == buffer + 4);
+    assert(ret == buffer + 12);
     mono1.release();
 
     // Test a size that is just big enough to fit in the buffer,
     // but can't fit if it's aligned.
-    ret = r1.allocate(16, 1);
+    {
+      auto mono2 = std::pmr::monotonic_buffer_resource(buffer + 1, 16, std::pmr::new_delete_resource());
+      std::pmr::memory_resource& r2 = mono2;
+      ret                           = r2.allocate(16, 1);
       assert(ret == buffer + 1);
-    mono1.release();
+      mono2.release();
 
       assert(globalMemCounter.checkNewCalledEq(0));
-    ret = r1.allocate(16, 2);
+      ret = r2.allocate(16, 2);
       ASSERT_WITH_LIBRARY_INTERNAL_ALLOCATIONS(globalMemCounter.checkNewCalledEq(1));
       ASSERT_WITH_LIBRARY_INTERNAL_ALLOCATIONS(globalMemCounter.checkLastNewSizeGe(16));
-    mono1.release();
+      mono2.release();
       ASSERT_WITH_LIBRARY_INTERNAL_ALLOCATIONS(globalMemCounter.checkDeleteCalledEq(1));
     }
+  }
 
   return 0;
 }