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 E95403858D35; Tue, 23 Apr 2024 08:14:09 +0000 (GMT)
DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org E95403858D35
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org;
	s=default; t=1713860049;
	bh=m+lVDPkMD5hLwMd+kKpqGjuz0aSscmV5XKU8IStiTaM=;
	h=From:To:Subject:Date:From;
	b=heTMjokQBoriL8k6SGUqc71NdP+UmdO/GcHtOdwS7SfQtlLaIom0YNT8nnrmZvO8Y
	 XGHlNrFknk5v7uqQYxDUvFB2uCm6Xn5vX2TIImZRi64KLADDQb4wVmroOIFeGrNjld
	 Vpj972P3KoxE4PMIaOW8/g6AgNfhe6o7lm4bm9a4=
From: "hubicka at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug libstdc++/114821] New: _M_realloc_append should use memcpy
 instead of loop to copy data when possible
Date: Tue, 23 Apr 2024 08:14:08 +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: 14.0
X-Bugzilla-Keywords: 
X-Bugzilla-Severity: normal
X-Bugzilla-Who: hubicka at gcc dot gnu.org
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-114821-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=3D114821

            Bug ID: 114821
           Summary: _M_realloc_append should use memcpy instead of loop to
                    copy data when possible
           Product: gcc
           Version: 14.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: hubicka at gcc dot gnu.org
  Target Milestone: ---

In thestcase

#include <vector>
typedef unsigned int uint32_t;
std::pair<uint32_t, uint32_t> pair;
void
test()
{
        std::vector<std::pair<uint32_t, uint32_t>> stack;
        stack.push_back (pair);
        while (!stack.empty()) {
                std::pair<uint32_t, uint32_t> cur =3D stack.back();
                stack.pop_back();
                if (!cur.first)
                {
                        cur.second++;
                        stack.push_back (cur);
                        stack.push_back (cur);
                }
                if (cur.second > 10000)
                        break;
        }
}
int
main()
{
        for (int i =3D 0; i < 10000; i++)
          test();
}

We produce _M_reallloc_append which uses loop to copy data instead of memcp=
y.
This is bigger and slower.  The reason why __relocate_a does not use memcpy
seems to be fact that pair has copy constructor. It still can be pattern
matched by ldist but it fails with:

(compute_affine_dependence
  ref_a: *__first_1, stmt_a: *__cur_37 =3D *__first_1;
  ref_b: *__cur_37, stmt_b: *__cur_37 =3D *__first_1;
) -> dependence analysis failed

So we can not disambiguate old and new vector memory and prove that loop is
indeed memcpy loop. I think this is valid since operator new is not require=
d to
return new memory, but I think adding __restrict should solve this.

Problem is that I got lost on where to add them, since relocate_a uses
iterators instead of pointers=