Changes in GenerateInput.h

0298e58c7dd1fa76b98ff270cdb9e0eba4949185 - [libc++] Optimize input_iterator-pair `insert` for std::vector (#113768)

Tue, 14 Jan 2025 16:40:29 +0000

[libc++] Optimize input_iterator-pair `insert` for std::vector (#113768)As a follow-up to #113852, this PR optimizes the performance of the `insert(const_iterator pos, InputIt first, InputIt last)` function for `input_iterator`-pair inputs in `std::vector` for cases where reallocation occurs during insertion. Additionally, this optimization enhances exception safety by replacing the traditional `try-catch` mechanism with a modern exception guard for the `insert` function. The optimization targets cases where insertion trigger reallocation. In scenarios without reallocation, the implementation remains unchanged. Previous implementation ----------------------- The previous implementation of `insert` is inefficient in reallocation scenarios because it performs the following steps separately: - `reserve()`: This leads to the first round of relocating old elements to new memory; - `rotate()`: This leads to the second round of reorganizing the existing elements; - Move-forward: Moves the elements after the insertion position to their final positions. - Insert: performs the actual insertion. This approach results in a lot of redundant operations, requiring the elements to undergo three rounds of relocations/reorganizations to be placed in their final positions. Proposed implementation ----------------------- The proposed implementation jointly optimize the above 4 steps in the previous implementation such that each element is placed in its final position in just one round of relocation. Specifically, this optimization reduces the total cost from 2 relocations + 1 std::rotate call to just 1 relocation, without needing to call `std::rotate`, thereby significantly improving overall performance. List of files: /llvm-project/libcxx/test/benchmarks/GenerateInput.h

056153f36eca184f81969f5cd5c8cd967c935f96 - Optimize vector::assign for InputIterator-only pair inputs (#113852)

Thu, 28 Nov 2024 19:52:59 +0000

Optimize vector::assign for InputIterator-only pair inputs (#113852)This PR optimizes the input iterator overload of `assign(_InputIterator, _InputIterator)` in `std::vector<_Tp, _Allocator>` by directly assigning to already initialized memory, rather than first destroying existing elements and then constructing new ones. By eliminating unnecessary destruction and construction, the proposed algorithm enhances the performance by up to 2x for trivial element types (e.g., `std::vector`), up to 2.6x for non-trivial element types like `std::vector`, and up to 3.4x for more complex non-trivial types (e.g., `std::vector>`). ### Google Benchmarks Benchmark tests (`libcxx/test/benchmarks/vector_operations.bench.cpp`) were conducted for the `assign()` implementations before and after this patch. The tests focused on trivial element types like `std::vector`, and non-trivial element types such as `std::vector` and `std::vector>`. #### Before ``` ------------------------------------------------------------------------------------------------- Benchmark Time CPU Iterations ------------------------------------------------------------------------------------------------- BM_AssignInputIterIter/vector_int/1024/1024 1157 ns 1169 ns 608188 BM_AssignInputIterIter<32>/vector_string/1024/1024 14559 ns 14710 ns 47277 BM_AssignInputIterIter<32>/vector_vector_int/1024/1024 26846 ns 27129 ns 25925 ``` #### After ``` ------------------------------------------------------------------------------------------------- Benchmark Time CPU Iterations ------------------------------------------------------------------------------------------------- BM_AssignInputIterIter/vector_int/1024/1024 561 ns 566 ns 1242251 BM_AssignInputIterIter<32>/vector_string/1024/1024 5604 ns 5664 ns 128365 BM_AssignInputIterIter<32>/vector_vector_int/1024/1024 7927 ns 8012 ns 88579 ``` List of files: /llvm-project/libcxx/test/benchmarks/GenerateInput.h

c25e09e238c6f872a116d10bbefba0beff145a57 - [libc++][test] Speed up input generating functions for benchmark tests (#115544)

Mon, 18 Nov 2024 15:32:54 +0000

[libc++][test] Speed up input generating functions for benchmark tests (#115544)The input generating functions for benchmark tests in the GenerateInput.h file can be slightly improved by invoking vector::reserve before calling vector::push_back. This slight performance improvement could potentially speed-up all benchmark tests for containers and algorithms that use these functions as inputs. List of files: /llvm-project/libcxx/test/benchmarks/GenerateInput.h

3af4c2e16ec1cf8a099d69d69f40f3aa8bb43cc7 - [libc++][test] Clean up code in GenerateInput.h for benchmark testing (#115560)

Mon, 11 Nov 2024 15:02:56 +0000

[libc++][test] Clean up code in GenerateInput.h for benchmark testing (#115560)This PR refines the code in `GenerateInput.h` used for benchmark testing by implementing the following changes: - Replaced all unqualified usages of `size_t` with `std::size_t`. - Removed unnecessary curly braces `{}` from for loops that contain simple single-statement bodies, in accordance with LLVM coding standards. List of files: /llvm-project/libcxx/test/benchmarks/GenerateInput.h

6a54dfbfe534276d644d7f9c027f0deeb748dd53 - [libc++][NFC] Add missing license headers

Wed, 31 Jul 2024 16:57:00 +0000

[libc++][NFC] Add missing license headersAlso standardize the license comment in several files where it wasdifferent from what we normally do. List of files: /llvm-project/libcxx/test/benchmarks/GenerateInput.h

78b4b5cccbd92363708906d9171e21b0307b91a2 - [libc++] Move the benchmarks under libcxx/test (#99371)

Wed, 31 Jul 2024 15:18:32 +0000

[libc++] Move the benchmarks under libcxx/test (#99371)This is an intermediate and fairly mechanical step towards unifying the benchmarks with the rest of the test suite. Moving this around requires a few changes, notably making sure we don't throw a wrench into the discovery process of the normal test suite. This won't be a problem anymore once benchmarks are taken into account by the test setup out of the box. List of files: /llvm-project/libcxx/test/benchmarks/GenerateInput.h