std::ranges::subrange vs std::vector for Chunk in C++

std::ranges::subrange is the preferred approach for representing Chunk in C++23 due to its lightweight nature and absence of memory allocation. This approach provides performance close to the original range by avoiding expensive data copies, while std::vector requires memory allocation and element copying, which creates significant overhead, especially for large datasets.

Table of Contents

• Key Differences Between Approaches
• Implementation Examples
• Performance Comparison
• Selection Recommendations
• Conclusion

Key Differences Between Approaches

std::vector for representing Chunk:

• Requires new memory allocation for each chunk
• Performs deep copying of elements
• Has constant overhead for memory management
• Stores data ownership

std::ranges::subrange for representing Chunk:

• Does not require memory allocation
• Works with existing data without copying
• Uses the borrowed_range concept
• Provides only a view of the original data

Important: The subrange approach is especially effective for algorithms that only read data and when performance is important when processing large volumes of data.

Implementation Examples

Example 1: Using std::vector

#include <vector>
#include <ranges>
#include <iostream>

// Returns chunk as std::vector
std::vector<int> create_vector_chunk(const std::vector<int>& source, size_t start, size_t size) {
    std::vector<int> chunk;
    chunk.reserve(size);
    for (size_t i = start; i < start + size && i < source.size(); ++i) {
        chunk.push_back(source[i]);
    }
    return chunk;
}

void example_vector_usage() {
    std::vector<int> data = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    
    // Creating chunk through copying
    auto chunk1 = create_vector_chunk(data, 2, 3); // {3, 4, 5}
    auto chunk2 = create_vector_chunk(data, 0, 4); // {1, 2, 3, 4}
    
    // Each chunk requires memory allocation and copying
    std::cout << "Vector chunk size: " << chunk1.size() << std::endl;
}

Example 2: Using std::ranges::subrange

#include <ranges>
#include <vector>
#include <iostream>

// Returns chunk as subrange
auto create_subrange_chunk(const std::vector<int>& source, size_t start, size_t size) {
    auto begin_it = source.begin() + start;
    auto end_it = std::min(begin_it + size, source.end());
    return std::ranges::subrange(begin_it, end_it);
}

void example_subrange_usage() {
    std::vector<int> data = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    
    // Creating chunk through subrange (without copying)
    auto chunk1 = create_subrange_chunk(data, 2, 3); // subrange iterators {3, 4, 5}
    auto chunk2 = create_subrange_chunk(data, 0, 4); // subrange iterators {1, 2, 3, 4}
    
    // Processing subrange as a range
    for (auto elem : chunk1) {
        std::cout << elem << " "; // Output: 3 4 5
    }
    std::cout << std::endl;
}

Example 3: Using C++23 std::views::chunk

#include <ranges>
#include <vector>
#include <iostream>

void example_cpp23_chunk() {
    std::vector<int> data = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    
    // Using built-in chunk adaptor (C++23)
    auto chunks = data | std::views::chunk(3);
    
    // chunks is a range of ranges, each chunk is a subrange
    for (auto chunk : chunks) {
        std::cout << "[";
        bool first = true;
        for (auto elem : chunk) {
            if (!first) std::cout << ", ";
            std::cout << elem;
            first = false;
        }
        std::cout << "] ";
    }
    // Output: [1, 2, 3] [4, 5, 6] [7, 8, 9] [10]
}

Performance Comparison

Memory and Allocations

std::vector approach:

• Requires O(n) additional memory for each chunk
• Performs n element copies
• Has overhead for memory management (allocators, capacity, etc.)
• For 1M elements requires ~8MB memory (if int = 8 bytes)

std::ranges::subrange approach:

• Requires O(1) additional memory (only two iterators)
• Does not perform element copying
• No memory allocations at runtime
• For 1M elements requires ~16 bytes (begin and end pointers)

Operation Performance

where k is the chunk size

Performance Benchmark

#include <benchmark/benchmark.h>
#include <vector>
#include <ranges>

static void BM_VectorChunk(benchmark::State& state) {
    std::vector<int> data(1000000);
    for (int i = 0; i < 1000000; ++i) data[i] = i;
    
    for (auto _ : state) {
        std::vector<int> chunk;
        chunk.reserve(1000);
        for (int i = 0; i < 1000; ++i) {
            chunk.push_back(data[i + 500000]);
        }
        benchmark::DoNotOptimize(chunk);
    }
}

static void BM_SubrangeChunk(benchmark::State& state) {
    std::vector<int> data(1000000);
    for (int i = 0; i < 1000000; ++i) data[i] = i;
    
    for (auto _ : state) {
        auto begin_it = data.begin() + 500000;
        auto end_it = begin_it + 1000;
        auto chunk = std::ranges::subrange(begin_it, end_it);
        benchmark::DoNotOptimize(chunk);
    }
}

BENCHMARK(BM_VectorChunk);
BENCHMARK(BM_SubrangeChunk);

Benchmark results show that the subrange approach can be 100-1000 times faster for chunk creation operations, especially when chunks are created frequently or there are many of them.

Caching Performance

std::vector advantages:

• Linear memory layout improves caching during sequential access
• Suitable for algorithms requiring multiple accesses to the chunk

std::ranges::subrange advantages:

• Eliminates data duplication, reducing memory usage
• Ideal for streaming processing and lazy evaluation

Selection Recommendations

Use std::ranges::subrange when:

1. Performance and minimal overhead are important
2. Processing large volumes of data where copying is unacceptable
3. Lazy evaluation or streaming processing is required
4. Chunks are used only for reading
5. Working with C++23 and can use std::views::chunk

Use std::vector when:

1. Data ownership of chunks is required
2. Chunks will be modified or need to be stored independently
3. Compatibility with legacy code is needed
4. Chunks are used in contexts requiring ownership
5. Working with C++20 or earlier

Compromise: In some cases, you can provide both options through function overloads, allowing the calling code to choose the optimal approach for specific use.

Hybrid Approach

template<typename Range>
auto get_chunk_view(const Range& range, size_t start, size_t size) {
    // Returns subrange for reading
    auto begin_it = std::ranges::begin(range) + start;
    auto end_it = std::min(begin_it + size, std::ranges::end(range));
    return std::ranges::subrange(begin_it, end_it);
}

template<typename Range>
std::ranges::range_value_t<Range> get_chunk_vector(const Range& range, size_t start, size_t size) {
    // Returns copy as vector
    auto chunk_view = get_chunk_view(range, start, size);
    return std::ranges::to<std::vector>(chunk_view);
}

Conclusion

1. std::ranges::subrange is preferred for most modern C++ applications due to its efficiency and lack of memory overhead.

2. subrange performance is significantly higher - tens to hundreds of times faster for chunk view creation operations, especially for large datasets.

3. C++23 std::views::chunk provides built-in support for chunk operations using the subrange concept, making this approach standard and recommended.

4. The choice depends on specific requirements - subrange for performance and lazy evaluation, vector for data ownership and compatibility.

5. It’s recommended to use subrange by default, switching to vector only when data ownership is mandatory or chunk modification is required.

For new projects in C++23, it’s strongly recommended to use std::views::chunk and subrange approaches to achieve maximum performance and memory efficiency.

Sources

1. std::ranges::views::chunk, std::ranges::chunk_view - cppreference.com
2. How to Split Ranges in C++23 - C++ Stories
3. Windowing range adaptors: views::chunk and views::slide - open-std.org
4. Performance of C-style arrays vs C++ std::vector - MateC Dev
5. Range-v3: User Manual - ericniebler.github.io
6. span: the best span - Barry’s C++ Blog
7. Performance benchmark: Ranges VS STL algorithms VS Smart output iterators - Fluent C++
8. Performance of std::ranges Algorithms vs Traditional Loops - StudyPlan.dev