From 549a5fd0b789578fcb5ee72c9f4446660f759758 Mon Sep 17 00:00:00 2001 From: Nikolas Klauser Date: Thu, 12 Jan 2023 18:35:19 +0100 Subject: [PATCH] [libc++] Make pmr::monotonic_buffer_resource bump down 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. Reviewed By: ldionne, #libc Spies: libcxx-commits Differential Revision: https://reviews.llvm.org/D141435 --- libcxx/benchmarks/CMakeLists.txt | 1 + libcxx/benchmarks/monotonic_buffer.bench.cpp | 28 ++++++++++++++++++ .../__memory_resource/monotonic_buffer_resource.h | 5 ++-- libcxx/src/memory_resource.cpp | 33 ++++++++++++++++----- .../allocate_from_underaligned_buffer.pass.cpp | 34 ++++++++++++---------- 5 files changed, 76 insertions(+), 25 deletions(-) create mode 100644 libcxx/benchmarks/monotonic_buffer.bench.cpp rename libcxx/test/{std => libcxx}/utilities/utility/mem.res/mem.res.monotonic.buffer/mem.res.monotonic.buffer.mem/allocate_from_underaligned_buffer.pass.cpp (56%) diff --git a/libcxx/benchmarks/CMakeLists.txt b/libcxx/benchmarks/CMakeLists.txt index b9034ec..a792230 100644 --- a/libcxx/benchmarks/CMakeLists.txt +++ b/libcxx/benchmarks/CMakeLists.txt @@ -185,6 +185,7 @@ set(BENCHMARK_TESTS 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 diff --git a/libcxx/benchmarks/monotonic_buffer.bench.cpp b/libcxx/benchmarks/monotonic_buffer.bench.cpp new file mode 100644 index 0000000..cfedbe5 --- /dev/null +++ b/libcxx/benchmarks/monotonic_buffer.bench.cpp @@ -0,0 +1,28 @@ +//===----------------------------------------------------------------------===// +// +// 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 +#include + +#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 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(); diff --git a/libcxx/include/__memory_resource/monotonic_buffer_resource.h b/libcxx/include/__memory_resource/monotonic_buffer_resource.h index 5c35a62..fd34d20 100644 --- a/libcxx/include/__memory_resource/monotonic_buffer_resource.h +++ b/libcxx/include/__memory_resource/monotonic_buffer_resource.h @@ -69,7 +69,7 @@ public: : __res_(__upstream) { __initial_.__start_ = static_cast(__buffer); if (__buffer != nullptr) { - __initial_.__cur_ = static_cast(__buffer); + __initial_.__cur_ = static_cast(__buffer) + __buffer_size; __initial_.__end_ = static_cast(__buffer) + __buffer_size; } else { __initial_.__cur_ = nullptr; @@ -85,7 +85,8 @@ public: 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_); diff --git a/libcxx/src/memory_resource.cpp b/libcxx/src/memory_resource.cpp index d4a735b..e00611dd 100644 --- a/libcxx/src/memory_resource.cpp +++ b/libcxx/src/memory_resource.cpp @@ -410,23 +410,39 @@ bool synchronized_pool_resource::do_is_equal(const memory_resource& other) const // 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(ptr); + char* new_ptr = reinterpret_cast(reinterpret_cast(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(__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(new_ptr) + bytes; + __cur_ = static_cast(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(__cur_); - size_t new_capacity = (reinterpret_cast(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(new_ptr) + bytes; + __cur_ = static_cast(new_ptr); return aligned_ptr; } @@ -464,10 +480,11 @@ void* monotonic_buffer_resource::do_allocate(size_t bytes, size_t align) { } 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; diff --git a/libcxx/test/std/utilities/utility/mem.res/mem.res.monotonic.buffer/mem.res.monotonic.buffer.mem/allocate_from_underaligned_buffer.pass.cpp b/libcxx/test/libcxx/utilities/utility/mem.res/mem.res.monotonic.buffer/mem.res.monotonic.buffer.mem/allocate_from_underaligned_buffer.pass.cpp similarity index 56% rename from libcxx/test/std/utilities/utility/mem.res/mem.res.monotonic.buffer/mem.res.monotonic.buffer.mem/allocate_from_underaligned_buffer.pass.cpp rename to libcxx/test/libcxx/utilities/utility/mem.res/mem.res.monotonic.buffer/mem.res.monotonic.buffer.mem/allocate_from_underaligned_buffer.pass.cpp index e35d9bd..a997435 100644 --- a/libcxx/test/std/utilities/utility/mem.res/mem.res.monotonic.buffer/mem.res.monotonic.buffer.mem/allocate_from_underaligned_buffer.pass.cpp +++ b/libcxx/test/libcxx/utilities/utility/mem.res/mem.res.monotonic.buffer/mem.res.monotonic.buffer.mem/allocate_from_underaligned_buffer.pass.cpp @@ -14,8 +14,8 @@ // class monotonic_buffer_resource -#include #include +#include #include "count_new.h" #include "test_macros.h" @@ -24,33 +24,37 @@ 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); - assert(ret == buffer + 1); - mono1.release(); - - assert(globalMemCounter.checkNewCalledEq(0)); - ret = r1.allocate(16, 2); - ASSERT_WITH_LIBRARY_INTERNAL_ALLOCATIONS(globalMemCounter.checkNewCalledEq(1)); - ASSERT_WITH_LIBRARY_INTERNAL_ALLOCATIONS(globalMemCounter.checkLastNewSizeGe(16)); - mono1.release(); - ASSERT_WITH_LIBRARY_INTERNAL_ALLOCATIONS(globalMemCounter.checkDeleteCalledEq(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); + mono2.release(); + + assert(globalMemCounter.checkNewCalledEq(0)); + ret = r2.allocate(16, 2); + ASSERT_WITH_LIBRARY_INTERNAL_ALLOCATIONS(globalMemCounter.checkNewCalledEq(1)); + ASSERT_WITH_LIBRARY_INTERNAL_ALLOCATIONS(globalMemCounter.checkLastNewSizeGe(16)); + mono2.release(); + ASSERT_WITH_LIBRARY_INTERNAL_ALLOCATIONS(globalMemCounter.checkDeleteCalledEq(1)); + } } return 0; -- 2.7.4