From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <gcc-bugzilla@gcc.gnu.org>
Received: by sourceware.org (Postfix, from userid 48)
	id 07FC03858D20; Sat,  4 Mar 2023 13:28:35 +0000 (GMT)
DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 07FC03858D20
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org;
	s=default; t=1677936516;
	bh=5s5gHwFzJml7Ug4GKLKRfkTDAb5Wg7NgrabwBsNdkQI=;
	h=From:To:Subject:Date:From;
	b=B6PE/W0tLjl8d4l34aKbo/HCOOnZkfbgOt97Z0yBofdP3MnCZkzw+hw0wX1OWiuQ9
	 kqhIfNbU2ptQLfck8twL/Ry3s7gFrZFCq9Yn2voPmXI5AJG6nI9uWWP9PrtxyBOgmh
	 Wshb4kHpWrsux5MdvjYvKvgi3d4S1XJweI/CXp6w=
From: "marekr22 at wp dot pl" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug libstdc++/109022] New: Low performance of std::map constructor
 for already sorted data of std::pair<none-const key, value>
Date: Sat, 04 Mar 2023 13:28:34 +0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: new
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: libstdc++
X-Bugzilla-Version: 12.2.0
X-Bugzilla-Keywords: 
X-Bugzilla-Severity: normal
X-Bugzilla-Who: marekr22 at wp dot pl
X-Bugzilla-Status: UNCONFIRMED
X-Bugzilla-Resolution: 
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org
X-Bugzilla-Target-Milestone: ---
X-Bugzilla-Flags: 
X-Bugzilla-Changed-Fields: bug_id short_desc product version bug_status
 bug_severity priority component assigned_to reporter target_milestone
Message-ID: <bug-109022-4@http.gcc.gnu.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
List-Id: <gcc-bugs.sourceware.org>

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

            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 =3D 8 << 0;
constexpr size_t DataSizeStop =3D 8 << 3;

using TestData =3D std::vector<std::pair<std::string, int>>;
using TestDataConst =3D 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 =3D 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 =3D 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 =3D sortedData(n);
  return {r.begin(), r.end()};
}

TestDataConst shuffledConstData(size_t n)
{
  auto r =3D shuffledData(n);
  return {r.begin(), r.end()};
}

template<auto Data>
static void CreateMapInsert(benchmark::State& state) {
  auto n =3D state.range(0);
  auto data =3D 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(DataSizeS=
tart,
DataSizeStop);
//
BENCHMARK(CreateMapInsert<shuffledData>)->RangeMultiplier(2)->Range(DataSiz=
eStart,
DataSizeStop);
BENCHMARK(CreateMapInsert<sortedConstData>)->RangeMultiplier(2)->Range(Data=
SizeStart,
DataSizeStop);
//
BENCHMARK(CreateMapInsert<shuffledConstData>)->RangeMultiplier(2)->Range(Da=
taSizeStart,
DataSizeStop);

template<auto Data>
static void CreateMapDirectly(benchmark::State& state) {
  auto n =3D state.range(0);
  auto data =3D 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(DataSiz=
eStart,
DataSizeStop);
//
BENCHMARK(CreateMapDirectly<shuffledData>)->RangeMultiplier(2)->Range(DataS=
izeStart,
DataSizeStop);
BENCHMARK(CreateMapDirectly<sortedConstData>)->RangeMultiplier(2)->Range(Da=
taSizeStart,
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::strin=
g,
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=