llvmbot wrote:
<!--LLVM PR SUMMARY COMMENT--> @llvm/pr-subscribers-libcxx Author: Mark de Wever (mordante) <details> <summary>Changes</summary> This changes the __output_buffer to a new structure. This improves the performace of std::format, std::format_to, std::format_to_n, and std::foramtted size. --- Patch is 42.48 KiB, truncated to 20.00 KiB below, full version: https://github.com/llvm/llvm-project/pull/108990.diff 7 Files Affected: - (modified) libcxx/include/__format/buffer.h (+347-279) - (modified) libcxx/include/__format/format_functions.h (+14-15) - (modified) libcxx/test/libcxx/transitive_includes/cxx03.csv (-18) - (modified) libcxx/test/libcxx/transitive_includes/cxx11.csv (-18) - (modified) libcxx/test/libcxx/transitive_includes/cxx14.csv (-18) - (modified) libcxx/test/libcxx/transitive_includes/cxx17.csv (-8) - (modified) libcxx/test/std/utilities/format/format.functions/format_tests.h (+1-1) ``````````diff diff --git a/libcxx/include/__format/buffer.h b/libcxx/include/__format/buffer.h index 8598f0a1c03957..d3fa0e836366af 100644 --- a/libcxx/include/__format/buffer.h +++ b/libcxx/include/__format/buffer.h @@ -14,6 +14,7 @@ #include <__algorithm/fill_n.h> #include <__algorithm/max.h> #include <__algorithm/min.h> +#include <__algorithm/ranges_copy.h> #include <__algorithm/ranges_copy_n.h> #include <__algorithm/transform.h> #include <__algorithm/unwrap_iter.h> @@ -29,6 +30,7 @@ #include <__iterator/wrap_iter.h> #include <__memory/addressof.h> #include <__memory/allocate_at_least.h> +#include <__memory/allocator.h> #include <__memory/allocator_traits.h> #include <__memory/construct_at.h> #include <__memory/ranges_construct_at.h> @@ -38,6 +40,7 @@ #include <__utility/exception_guard.h> #include <__utility/move.h> #include <cstddef> +#include <stdexcept> #include <string_view> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) @@ -53,24 +56,150 @@ _LIBCPP_BEGIN_NAMESPACE_STD namespace __format { +// A helper to limit the total size of code units written. +class _LIBCPP_HIDE_FROM_ABI __max_output_size { +public: + [[nodiscard]] _LIBCPP_HIDE_FROM_ABI explicit __max_output_size(size_t __max_size) : __max_size_{__max_size} {} + + // This function adjusts the size of a (bulk) write operations. It ensures the + // number of code units written by a __output_buffer never exceeds + // __max_size_ code units. + [[nodiscard]] _LIBCPP_HIDE_FROM_ABI size_t __write_request(size_t __code_units) { + size_t __result = + __code_units_written_ < __max_size_ ? std::min(__code_units, __max_size_ - __code_units_written_) : 0; + __code_units_written_ += __code_units; + return __result; + } + + [[nodiscard]] _LIBCPP_HIDE_FROM_ABI size_t __code_units_written() const noexcept { return __code_units_written_; } + +private: + size_t __max_size_; + // The code units that would have been written if there was no limit. + // format_to_n returns this value. + size_t __code_units_written_{0}; +}; + /// A "buffer" that handles writing to the proper iterator. /// /// This helper is used together with the @ref back_insert_iterator to offer /// type-erasure for the formatting functions. This reduces the number to /// template instantiations. +/// +/// The design is the following: +/// - There is an external object that connects the buffer to the output. +/// - This buffer object: +/// - inherits publicly from this class. +/// - has a static or dynamic buffer. +/// - has a static member function to make space in its buffer write +/// operations. This can be done by increasing the size of the internal +/// buffer or by writing the contents of the buffer to the output iterator. +/// +/// This member function is a constructor argument, so its name is not +/// fixed. The code uses the name __prepare_write. +/// - The number of output code units can be limited by a __max_output_size +/// object. This is used in format_to_n This object: +/// - Contains the maximum number of code units to be written. +/// - Contains the number of code units that are requested to be written. +/// This number is returned to the user of format_to_n. +/// - The write functions call the object's __request_write member function. +/// This function: +/// - Updates the number of code units that are requested to be written. +/// - Returns the number of code units that can be written without +/// exceeding the maximum number of code units to be written. +/// +/// Documentation for the buffer usage members: +/// - __ptr_ +/// The start of the buffer. +/// - __capacity_ +/// The number of code units that can be written. This means +/// [__ptr_, __ptr_ + __capacity_) is a valid range to write to. +/// - __size_ +/// The number of code units written in the buffer. The next code unit will +/// be written at __ptr_ + __size_. This __size_ may NOT contain the total +/// number of code units written by the __output_buffer. Whether or not it +/// does depends on the sub-class used. Typically the total number of code +/// units written is not interesting. It is interesting for format_to_n which +/// has its own way to track this number. +/// +/// Documentation for the buffer changes function: +/// The subclasses have a function with the following signature: +/// +/// static void __prepare_write( +/// __output_buffer<_CharT>& __buffer, size_t __code_units); +/// +/// This function is called when a write function writes more code units than +/// the buffer's available space. When an __max_output_size object is provided +/// the number of code units is the number of code units returned from +/// __max_output_size::__request_write function. +/// +/// - The __buffer contains *this. Since the class containing this function +/// inherits from __output_buffer it's safe to cast it to the subclass being +/// used. +/// - The __code_units is the number of code units the caller will write + 1. +/// - This value does not take the avaiable space of the buffer into account. +/// - The push_back function is more efficient when writing before resizing, +/// this means the buffer should always have room for one code unit. Hence +/// the + 1 is the size. +/// - When the function returns there is room for at least one code unit. There +/// is no requirement there is room for __code_units code units: +/// - The class has some "bulk" operations. For example, __copy which copies +/// the contents of a basic_string_view to the output. If the sub-class has +/// a fixed size buffer the size of the basic_string_view may be larger +/// than the buffer. In that case it's impossible to honor the requested +/// size. +/// - The at least one code unit makes sure the entire output can be written. +/// (Obviously making room one code unit at a time is slow and +/// it's recommended to return a larger available space.) +/// - When the buffer has room for at least one code unit the function may be +/// a no-op. +/// - When the function makes space for more code units it uses one for these +/// functions to signal the change: +/// - __buffer_flushed() +/// - This function is typically used for a fixed sized buffer. +/// - The current contents of [__ptr_, __ptr_ + __size_) have been +/// processed. +/// - __ptr_ remains unchanged. +/// - __capacity_ remains unchanged. +/// - __size_ will be set to 0. +/// - __buffer_moved(_CharT* __ptr, size_t __capacity) +/// - This function is typically used for a dynamic sized buffer. There the +/// location of the buffer changes due to reallocations. +/// - __ptr_ will be set to __ptr. (This value may be the old value of +/// __ptr_). +/// - __capacity_ will be set to __capacity. (This value may be the old +/// value of __capacity_). +/// - __size_ remains unchanged, +/// - The range [__ptr, __ptr + __size_) contains the original data of the +/// range [__ptr_, __ptr_ + __size_). +/// +/// The push_back function expects a valid buffer and a capacity of at least 1. +/// This means: +/// - The class is constructed with a valid buffer, +/// - __buffer_moved is called with a valid buffer is used before the first +/// write operation, +/// - no write function is ever called, or +/// - the class is constructed with a __max_output_size object with __max_size 0. +/// +/// The latter option allows formatted_size to use the output buffer without +/// ever writing anything to the buffer. template <__fmt_char_type _CharT> class _LIBCPP_TEMPLATE_VIS __output_buffer { public: - using value_type = _CharT; + using value_type = _CharT; + using __prepare_write_type = void (*)(__output_buffer<_CharT>&, size_t); + + [[nodiscard]] + _LIBCPP_HIDE_FROM_ABI explicit __output_buffer(_CharT* __ptr, size_t __capacity, __prepare_write_type __function) + : __output_buffer{__ptr, __capacity, __function, nullptr} {} - template <class _Tp> - _LIBCPP_HIDE_FROM_ABI explicit __output_buffer(_CharT* __ptr, size_t __capacity, _Tp* __obj) - : __ptr_(__ptr), - __capacity_(__capacity), - __flush_([](_CharT* __p, size_t __n, void* __o) { static_cast<_Tp*>(__o)->__flush(__p, __n); }), - __obj_(__obj) {} + [[nodiscard]] _LIBCPP_HIDE_FROM_ABI explicit __output_buffer( + _CharT* __ptr, size_t __capacity, __prepare_write_type __function, __max_output_size* __max_output_size) + : __ptr_(__ptr), __capacity_(__capacity), __prepare_write_(__function), __max_output_size_(__max_output_size) {} - _LIBCPP_HIDE_FROM_ABI void __reset(_CharT* __ptr, size_t __capacity) { + _LIBCPP_HIDE_FROM_ABI void __buffer_flushed() { __size_ = 0; } + + _LIBCPP_HIDE_FROM_ABI void __buffer_moved(_CharT* __ptr, size_t __capacity) { __ptr_ = __ptr; __capacity_ = __capacity; } @@ -79,12 +208,18 @@ class _LIBCPP_TEMPLATE_VIS __output_buffer { // Used in std::back_insert_iterator. _LIBCPP_HIDE_FROM_ABI void push_back(_CharT __c) { + if (__max_output_size_ && __max_output_size_->__write_request(1) == 0) + return; + + _LIBCPP_ASSERT_INTERNAL( + __ptr_ && __size_ < __capacity_ && __available() >= 1, "attempted to write outside the buffer"); + __ptr_[__size_++] = __c; // Profiling showed flushing after adding is more efficient than flushing // when entering the function. if (__size_ == __capacity_) - __flush(); + __prepare_write(0); } /// Copies the input __str to the buffer. @@ -105,25 +240,20 @@ class _LIBCPP_TEMPLATE_VIS __output_buffer { // upper case. For integral these strings are short. // TODO FMT Look at the improvements above. size_t __n = __str.size(); - - __flush_on_overflow(__n); - if (__n < __capacity_) { // push_back requires the buffer to have room for at least one character (so use <). - std::copy_n(__str.data(), __n, std::addressof(__ptr_[__size_])); - __size_ += __n; - return; + if (__max_output_size_) { + __n = __max_output_size_->__write_request(__n); + if (__n == 0) + return; } - // The output doesn't fit in the internal buffer. - // Copy the data in "__capacity_" sized chunks. - _LIBCPP_ASSERT_INTERNAL(__size_ == 0, "the buffer should be flushed by __flush_on_overflow"); const _InCharT* __first = __str.data(); do { - size_t __chunk = std::min(__n, __capacity_); + __prepare_write(__n); + size_t __chunk = std::min(__n, __available()); std::copy_n(__first, __chunk, std::addressof(__ptr_[__size_])); - __size_ = __chunk; + __size_ += __chunk; __first += __chunk; __n -= __chunk; - __flush(); } while (__n); } @@ -137,121 +267,59 @@ class _LIBCPP_TEMPLATE_VIS __output_buffer { _LIBCPP_ASSERT_INTERNAL(__first <= __last, "not a valid range"); size_t __n = static_cast<size_t>(__last - __first); - __flush_on_overflow(__n); - if (__n < __capacity_) { // push_back requires the buffer to have room for at least one character (so use <). - std::transform(__first, __last, std::addressof(__ptr_[__size_]), std::move(__operation)); - __size_ += __n; - return; + if (__max_output_size_) { + __n = __max_output_size_->__write_request(__n); + if (__n == 0) + return; } - // The output doesn't fit in the internal buffer. - // Transform the data in "__capacity_" sized chunks. - _LIBCPP_ASSERT_INTERNAL(__size_ == 0, "the buffer should be flushed by __flush_on_overflow"); do { - size_t __chunk = std::min(__n, __capacity_); + __prepare_write(__n); + size_t __chunk = std::min(__n, __available()); std::transform(__first, __first + __chunk, std::addressof(__ptr_[__size_]), __operation); - __size_ = __chunk; + __size_ += __chunk; __first += __chunk; __n -= __chunk; - __flush(); } while (__n); } /// A \c fill_n wrapper. _LIBCPP_HIDE_FROM_ABI void __fill(size_t __n, _CharT __value) { - __flush_on_overflow(__n); - if (__n < __capacity_) { // push_back requires the buffer to have room for at least one character (so use <). - std::fill_n(std::addressof(__ptr_[__size_]), __n, __value); - __size_ += __n; - return; + if (__max_output_size_) { + __n = __max_output_size_->__write_request(__n); + if (__n == 0) + return; } - // The output doesn't fit in the internal buffer. - // Fill the buffer in "__capacity_" sized chunks. - _LIBCPP_ASSERT_INTERNAL(__size_ == 0, "the buffer should be flushed by __flush_on_overflow"); do { - size_t __chunk = std::min(__n, __capacity_); + __prepare_write(__n); + size_t __chunk = std::min(__n, __available()); std::fill_n(std::addressof(__ptr_[__size_]), __chunk, __value); - __size_ = __chunk; + __size_ += __chunk; __n -= __chunk; - __flush(); } while (__n); } - _LIBCPP_HIDE_FROM_ABI void __flush() { - __flush_(__ptr_, __size_, __obj_); - __size_ = 0; - } + [[nodiscard]] _LIBCPP_HIDE_FROM_ABI size_t __capacity() const { return __capacity_; } + [[nodiscard]] _LIBCPP_HIDE_FROM_ABI size_t __size() const { return __size_; } private: _CharT* __ptr_; size_t __capacity_; size_t __size_{0}; - void (*__flush_)(_CharT*, size_t, void*); - void* __obj_; - - /// Flushes the buffer when the output operation would overflow the buffer. - /// - /// A simple approach for the overflow detection would be something along the - /// lines: - /// \code - /// // The internal buffer is large enough. - /// if (__n <= __capacity_) { - /// // Flush when we really would overflow. - /// if (__size_ + __n >= __capacity_) - /// __flush(); - /// ... - /// } - /// \endcode - /// - /// This approach works for all cases but one: - /// A __format_to_n_buffer_base where \ref __enable_direct_output is true. - /// In that case the \ref __capacity_ of the buffer changes during the first - /// \ref __flush. During that operation the output buffer switches from its - /// __writer_ to its __storage_. The \ref __capacity_ of the former depends - /// on the value of n, of the latter is a fixed size. For example: - /// - a format_to_n call with a 10'000 char buffer, - /// - the buffer is filled with 9'500 chars, - /// - adding 1'000 elements would overflow the buffer so the buffer gets - /// changed and the \ref __capacity_ decreases from 10'000 to - /// __buffer_size (256 at the time of writing). - /// - /// This means that the \ref __flush for this class may need to copy a part of - /// the internal buffer to the proper output. In this example there will be - /// 500 characters that need this copy operation. - /// - /// Note it would be more efficient to write 500 chars directly and then swap - /// the buffers. This would make the code more complex and \ref format_to_n is - /// not the most common use case. Therefore the optimization isn't done. - _LIBCPP_HIDE_FROM_ABI void __flush_on_overflow(size_t __n) { - if (__size_ + __n >= __capacity_) - __flush(); - } -}; - -/// A storage using an internal buffer. -/// -/// This storage is used when writing a single element to the output iterator -/// is expensive. -template <__fmt_char_type _CharT> -class _LIBCPP_TEMPLATE_VIS __internal_storage { -public: - _LIBCPP_HIDE_FROM_ABI _CharT* __begin() { return __buffer_; } + void (*__prepare_write_)(__output_buffer<_CharT>&, size_t); + __max_output_size* __max_output_size_; - static constexpr size_t __buffer_size = 256 / sizeof(_CharT); + [[nodiscard]] _LIBCPP_HIDE_FROM_ABI size_t __available() const { return __capacity_ - __size_; } -private: - _CharT __buffer_[__buffer_size]; + _LIBCPP_HIDE_FROM_ABI void __prepare_write(size_t __code_units) { + // Always have space for one additional code unit. This is a precondition of the push_back function. + __code_units += 1; + if (__available() < __code_units) + __prepare_write_(*this, __code_units + 1); + } }; -/// A storage writing directly to the storage. -/// -/// This requires the storage to be a contiguous buffer of \a _CharT. -/// Since the output is directly written to the underlying storage this class -/// is just an empty class. -template <__fmt_char_type _CharT> -class _LIBCPP_TEMPLATE_VIS __direct_storage {}; - template <class _OutIt, class _CharT> concept __enable_direct_output = __fmt_char_type<_CharT> && @@ -260,40 +328,6 @@ concept __enable_direct_output = // `#ifdef`. || same_as<_OutIt, __wrap_iter<_CharT*>>); -/// Write policy for directly writing to the underlying output. -template <class _OutIt, __fmt_char_type _CharT> -class _LIBCPP_TEMPLATE_VIS __writer_direct { -public: - _LIBCPP_HIDE_FROM_ABI explicit __writer_direct(_OutIt __out_it) : __out_it_(__out_it) {} - - _LIBCPP_HIDE_FROM_ABI _OutIt __out_it() { return __out_it_; } - - _LIBCPP_HIDE_FROM_ABI void __flush(_CharT*, size_t __n) { - // _OutIt can be a __wrap_iter<CharT*>. Therefore the original iterator - // is adjusted. - __out_it_ += __n; - } - -private: - _OutIt __out_it_; -}; - -/// Write policy for copying the buffer to the output. -template <class _OutIt, __fmt_char_type _CharT> -class _LIBCPP_TEMPLATE_VIS __writer_iterator { -public: - _LIBCPP_HIDE_FROM_ABI explicit __writer_iterator(_OutIt __out_it) : __out_it_{std::move(__out_it)} {} - - _LIBCPP_HIDE_FROM_ABI _OutIt __out_it() && { return std::move(__out_it_); } - - _LIBCPP_HIDE_FROM_ABI void __flush(_CharT* __ptr, size_t __n) { - __out_it_ = std::ranges::copy_n(__ptr, __n, std::move(__out_it_)).out; - } - -private: - _OutIt __out_it_; -}; - /// Concept to see whether a \a _Container is insertable. /// /// The concept is used to validate whether multiple calls to a @@ -319,188 +353,222 @@ struct _LIBCPP_TEMPLATE_VIS __back_insert_iterator_container<back_insert_iterato using type = _Container; }; -/// Write policy for inserting the buffer in a container. -template <class _Container> -class _LIBCPP_TEMPLATE_VIS __writer_container { +// A dynamically growing buffer. +template <__fmt_char_type _CharT> +class _LIBCPP_TEMPLATE_VIS __allocating_buffer : public __output_buffer<_CharT> { public: - using _CharT = typename _Container::value_type; + __allocating_buffer(const __allocating_buffer&) = delete; + __allocating_buffer& operator=(const __allocating_buffer&) = delete; - _LIBCPP_HIDE_FROM_ABI explicit __writer_container(back_insert_iterator<_Container> __out_it) - : __container_{__out_it.__get_container()} {} + [[nodiscard]] _LIBCPP_HIDE_FROM_ABI __allocating_buffer() : __allocating_buffer{nullptr} {} - _LIBCPP_HIDE_FROM_ABI auto __out_it() { return std::back_inserter(*__container_); } + [[nodiscard]] + _LIBCPP_HIDE_FROM_ABI explicit __allocating_buffer(__max_output_size* __max_output_size) + : __output_buffer<_CharT>{__buffer_, __buffer_size_, __prepare_write, __max_output_size} {} - _LIBCPP_HIDE_FROM_ABI void __flush(_CharT* __ptr, size_t __n) { - __container_->insert(__container_->end(), __ptr, __ptr + __n); + _LIBCPP_HIDE_FROM_ABI ~__allocating_buffer() { + if (__ptr_ != __buffer_) { + ranges::destroy_n(__ptr_, this->__size()); + allocator_traits<_Alloc>::deallocate(__alloc_, __ptr_, this->__capacity()); + } } + [[nodiscard]] _LIBCPP_HIDE_FROM_ABI basic_string_view<_CharT> __view() { return {__ptr_, this->__size()}; } + private: - _Container* __container_; -}; + // At the moment the allocator is hard-code. There might be reasons to have + // an allocator trait in the future. This ensures forward compatibility. + using _Alloc = allocator<_CharT>; + _LIBCPP_NO_UNIQUE_ADDRESS _Alloc __alloc_; -/// Selects the type of the writer used for the output iterator. -template <class _OutIt, class _CharT> -class _LIBCPP_TEMPLATE_VIS __writer_selector { - using _Container = typename __back_insert_iterator_container<_OutIt>::type; + // Since allocating is expensive the class has a small internal buffer. When + // its capacity is exceeded a dynamic buffer will be allocated. + static constexpr size_t __buffer_size_ = 256; + _CharT __buffer_[__buffer_size_]; -public: - using type = - conditional_t<!same_as<_Container, void>, - __writer_container<_Container>, - c... [truncated] `````````` </details> https://github.com/llvm/llvm-project/pull/108990 _______________________________________________ llvm-branch-commits mailing list llvm-branch-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
