[Bug libstdc++/56861] std::vector::reserve optimization bug

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=56861

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|WAITING                     |UNCONFIRMED
     Ever confirmed|1                           |0

--- Comment #3 from Jonathan Wakely <redi at gcc dot gnu.org> ---
This is the testcase, without the Boost dependency. Compile with -std=c++11.
Define RESERVE or RESERVE_PLUS_ONE to change the behaviour.

I can't reproduce any significant difference in performance using 4.7.4 or
trunk. The time is surely bound by the std::find_if calls and I/O on the file
(which fails unless the file already exists btw, because you use std::fstream
not std::ofstream).

I don't see any bug here, or anything that needs fixing.


#include <algorithm>
#include <array>
#include <cstdint>
#include <vector>
#include <random>
#include <string>
#include <iostream>
#include <fstream>
#include <chrono>

namespace {
constexpr size_t array_size = 1;

unsigned number() {
        static std::random_device rd;
        static std::mt19937 random_engine(rd());
        static std::uniform_int_distribution<uint32_t> distribution(0,
std::numeric_limits<uint32_t>::max());
        return distribution(random_engine);
}

class Class {
        public:
                Class() {
                        x[0] = number();
                }
                std::string to_string() const {
                        return std::to_string(x[0]);
                }
                inline friend bool operator<=(Class const & lhs, Class const &
rhs) {
                        return lhs.x[0] <= rhs.x[0];
                }
        private:
                std::array<uint32_t, array_size> x;
};

template<typename Container>
void add(Container & container, Class const & value) {
        auto const it = std::find_if(std::begin(container),
std::end(container), [&](Class const & c) {
                return value <= c;
        });
        container.emplace(it, value);
}

// Do something with the result
template<typename Container>
void insert_to_file(Container const & container) {
        std::fstream file("file.txt");
        for (auto const & value : container) {
                file << value.to_string() << '\n';
        }
}

template<typename Container>
void f(std::vector<Class> const & values) {
        Container container;
#if defined RESERVE
        container.reserve(values.size());
#elif defined RESERVE_PLUS_ONE
        container.reserve(values.size() + 1);
#endif
        for (auto const & value : values) {
                add(container, value);
        }
        insert_to_file(container);
}

}

int main(int argc, char ** argv) {
        std::size_t const size = (argc == 1) ? 1 : std::stoul(argv[1]);
        // Default constructor of Class fills in values here
        std::vector<Class> const values_to_be_copied(size);
        typedef std::vector<Class> Container;
        auto start = std::chrono::system_clock::now();
        f<Container>(values_to_be_copied);
        auto finish = std::chrono::system_clock::now();
        std::cerr << "Finished in " <<
std::chrono::duration_cast<std::chrono::duration<double>>(finish -
start).count() << " seconds.\n";
}