https://gcc.gnu.org/bugzilla/show_bug.cgi?id=109022
Bug ID: 109022 Summary: Low performance of std::map constructor for already sorted data of std::pair<none-const key, value> Product: gcc Version: 12.2.0 Status: UNCONFIRMED Severity: normal Priority: P3 Component: libstdc++ Assignee: unassigned at gcc dot gnu.org Reporter: marekr22 at wp dot pl Target Milestone: --- Performance of constructor accepting iterators to sorted data of std::pair<none-const key, value> is much lower then inserting same data for std::pair<const key, value> (matches value_type of std::map). Here is benchmark showing the issue: ``` #include <sstream> #include <map> #include <iomanip> #include <algorithm> #include <random> constexpr size_t DataSizeStart = 8 << 0; constexpr size_t DataSizeStop = 8 << 3; using TestData = std::vector<std::pair<std::string, int>>; using TestDataConst = std::vector<std::pair<const std::string, int>>; std::string makeStringFor(size_t x) { std::ostringstream out; out << std::setfill('0') << std::setw(6) << x; return out.str(); } TestData sortedData(size_t n) { TestData r; r.reserve(n); size_t i = 0; std::generate_n(std::back_inserter(r), n, [&i]() { return std::pair{makeStringFor(++i), i}; }); return r; } TestData shuffledData(size_t n) { auto data = sortedData(n); std::random_device rd; std::mt19937 g(rd()); std::shuffle(data.begin(), data.end(), g); return data; } TestDataConst sortedConstData(size_t n) { auto r = sortedData(n); return {r.begin(), r.end()}; } TestDataConst shuffledConstData(size_t n) { auto r = shuffledData(n); return {r.begin(), r.end()}; } template<auto Data> static void CreateMapInsert(benchmark::State& state) { auto n = state.range(0); auto data = Data(n); for (auto _ : state) { benchmark::DoNotOptimize(data); std::map<std::string, int> m; for (auto& p : data) { m.insert(m.end(), p); } benchmark::DoNotOptimize(m); } } BENCHMARK(CreateMapInsert<sortedData>)->RangeMultiplier(2)->Range(DataSizeStart, DataSizeStop); // BENCHMARK(CreateMapInsert<shuffledData>)->RangeMultiplier(2)->Range(DataSizeStart, DataSizeStop); BENCHMARK(CreateMapInsert<sortedConstData>)->RangeMultiplier(2)->Range(DataSizeStart, DataSizeStop); // BENCHMARK(CreateMapInsert<shuffledConstData>)->RangeMultiplier(2)->Range(DataSizeStart, DataSizeStop); template<auto Data> static void CreateMapDirectly(benchmark::State& state) { auto n = state.range(0); auto data = Data(n); for (auto _ : state) { benchmark::DoNotOptimize(data); std::map<std::string, int> m{data.begin(), data.end()}; benchmark::DoNotOptimize(m); } } BENCHMARK(CreateMapDirectly<sortedData>)->RangeMultiplier(2)->Range(DataSizeStart, DataSizeStop); // BENCHMARK(CreateMapDirectly<shuffledData>)->RangeMultiplier(2)->Range(DataSizeStart, DataSizeStop); BENCHMARK(CreateMapDirectly<sortedConstData>)->RangeMultiplier(2)->Range(DataSizeStart, DataSizeStop); // BENCHMARK(CreateMapDirectly<shuffledConstData>)->RangeMultiplier(2)->Range(DataSizeStart, DataSizeStop); ``` Live demo gcc 12.2: https://quick-bench.com/q/H8lqugNgMG-sWQ6cKBsdB7EBRpU Note that CreateMapInsert<sortedConstData> performs best since it feeds to constructos to iterators to std::pair<const std::string, in> while CreateMapInsert<sortedData> performs badly (looks like time complexity is worse) adn only diffrence is that it provides iterators to std::<std::string, int>. Same issue is observed for clang 14.0 and libstdc++: https://quick-bench.com/q/6VA3vRdKmqPEYrvTnFFla4gxwXk but it is not a problem on clang 14.0 and libc++: https://quick-bench.com/q/-S-lX3N8Y-8vL9CCl-5bW5jolWA here is result for sing size input data (easier to read): https://quick-bench.com/q/kbDOPA8PNZFfrzUH_-70cJgApeE Issue was observed when filing answer on https://stackoverflow.com/a/75535056/1387438