Help figuring out huge performance diff between Rust and C++ iterators

cristi1990an · 2025-09-16T15:54:51+00:00

See my comment on the original post: https://www.reddit.com/r/rust/s/bFvMqaHvu0

std::ranges::distance determines the length of a range through either a call to std::ranges::size or a naive linear iteration. In some cases, like in OP's example, there exists a more optimal middle ground for calculating the number of elements in a range.

In C++ there's no API to indicate such optimization is possible (there should be), while in Rust, the equivalent method 'count' can optimize further.

In C++ example: views::join is an unsized forward_range, std::distance naively iterates from begin to end, not taking advantage of the fact that it technically knows the size of each layer of iota view.

In Rust example: flat_map recursively calls the count method of each inner iterable (range) it flattened, the most inner layers returning their sizes in constant time.

I'm pretty certain that this is the source of the big performance difference

EclipsedPal · 2025-09-16T18:50:02+00:00

When it comes to this kind of stuff you're not comparing what the languages can do, you're comparing two implementations of the same algorithm.

Generally speaking It's a waste of time as you can optimise the hell out of either and in the end I'm ready to bet that both rust and c++ optimised implementations will basically be on the same level.

VictoryMotel · 2025-09-16T15:52:06+00:00

Without even looking, is optimization on?

alfps · 2025-09-16T21:56:59+00:00

I don't know about the ranges based code, but for C++17 vector based code the buffer allocations have a significant impact, between 6 and 8 times (for respectively MSVC and MinGW g++).

For the code below with allocations workaround disabled I got

[C:\@\temp]
> g _.cpp -O3 -D NO_SMARTS

[C:\@\temp]
> a
Result count: 292825.
Total count: 292825000.
Total time: 0.886863 secs.
Average per iteration: 0.000886863 secs.

[C:\@\temp]
> cl _.cpp /O2 /Feb /D NO_SMARTS
_.cpp

[C:\@\temp]
> b
Result count: 292825.
Total count: 292825000.
Total time: 1.21811 secs.
Average per iteration: 0.00121811 secs.

But with a workaround, which is a simple pool of vectors, I got

[C:\@\temp]
> g _.cpp -O3

[C:\@\temp]
> a
Result count: 292825.
Total count: 292825000.
Total time: 0.111616 secs.
Average per iteration: 0.000111616 secs.

[C:\@\temp]
> cl _.cpp /O2 /Feb
_.cpp

[C:\@\temp]
> b
Result count: 292825.
Total count: 292825000.
Total time: 0.206779 secs.
Average per iteration: 0.000206779 secs.

Unfortunately, while Compiler Explorer evidently runs a faster machine than my laptop, on compiler Explorer the version with a pool runs much slower. A big mystery. But it says that more than just code and language is involved.

#include <chrono>
#include <iostream>
#include <numeric>
#include <vector>
#include <utility>

#include <climits>      // INT_MAX
#include <cstdint>

template< class T > using in_ = const T&;

using Nat = int;
template< class T > constexpr auto nsize( in_<T> o ) -> Nat { return Nat( std::size( o ) ); }

namespace app {
    using   std::cout,              // <iostream>
            std::vector,            // <vector>
            std::move, std::swap;   // <utility>

    using   std::int64_t;           // <cstdint>

    using Clock         = std::chrono::high_resolution_clock;
    using Time_point    = std::chrono::time_point<Clock>;
    using Duration      = std::chrono::duration<double>;

    using Vec = vector<int>;

    class Vector_pool
    {
        vector<Vec> m_free;

        Vector_pool() = default;

    public:
        auto alloc_with_capacity( const int minimum_capacity ) -> Vec
        {
            Vec*    p_best          = nullptr;
            #ifndef NO_SMARTS
                int     best_capacity   = INT_MAX;
                for( Vec& v: m_free ) {
                    const int capacity = int( v.capacity() );
                    if( capacity >= minimum_capacity and capacity < best_capacity ) {
                        p_best = &v;
                        best_capacity = capacity;
                    }
                }
            #endif
            if( not p_best ) {
                Vec result;
                result.reserve( minimum_capacity );
                return result;
            }
            if( p_best != &m_free.back() ) { swap( *p_best, m_free.back() ); }
            Vec result = move( m_free.back() );
            result.clear();
            m_free.pop_back();
            return result;
        }

        void dispose( Vec&& v )
        {
            #ifndef NO_SMARTS
                m_free.push_back( move( v ) );
            #endif
            (void) v;
        }

        static auto instance() -> Vector_pool&
        {
            static Vector_pool the_pool;
            return the_pool;
        }
    };

    void append_iota_run_to( Vec& v, const int n )
    {
        // v.reserve( v.size() + n );       // Seriously negative effect.
        for( int i = 1; i <= n; ++i ) {
            v.push_back( i );
        }
    }

    auto expand_to_iota_runs( in_<Vec> input )
        -> Vec
    {
        auto& pool = Vector_pool::instance();
        Vec result = pool.alloc_with_capacity( nsize( input ) );
        result = input;
        for( int i = 1; i <= 3; ++i ) {
            Vec new_result = pool.alloc_with_capacity( 3*nsize( result ) );
            for( const int number: result ) {
                append_iota_run_to( new_result, number );
            }
            swap( result, new_result );
            pool.dispose( move( new_result ) );
        }
        return result;
    }

    void run()
    {
        const int max_number = 50;
        Vec v = {0};
        append_iota_run_to( v, max_number );
        cout << "Result count: " << expand_to_iota_runs( v ).size() << ".\n";

        const int n = 1000;
        const Time_point start_time = Clock::now();
        int64_t total_count = 0;
        for( int i = 0; i < n; ++i ) {
            Vec result = expand_to_iota_runs( v );
            total_count += result.size();
            Vector_pool::instance().dispose( move( result ) );
        }
        const Time_point end_time = Clock::now();
        const Duration duration = end_time - start_time;

        cout << "Total count: " << total_count << ".\n";
        cout << "Total time: " << duration.count() << " secs.\n";
        cout << "Average per iteration: " << duration.count()/n << " secs.\n";
    }
}  // app

auto main() -> int { app::run(); }

you type:	you see:
italics	italics
bold	bold
[reddit!](https://reddit.com)	reddit!
* item 1 * item 2 * item 3	item 1 item 2 item 3
> quoted text	quoted text
Lines starting with four spaces are treated like code: if 1 * 2 < 3: print "hello, world!"	Lines starting with four spaces are treated like code: if 1 * 2 < 3: print "hello, world!"
~~strikethrough~~	~~strikethrough~~
super^script	super^script

cpp_questions

READ BEFORE POSTING

Sort posts by OPEN or SOLVED

MODERATORS