[Bug libstdc++/58153] unordered_multimap::erase(iterator) is not constant-time when many entries have the same key

["fdumont at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain; charset="UTF-8", Size: 6148 bytes --]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=58153

--- Comment #5 from François Dumont <fdumont at gcc dot gnu.org> ---
And your remark is good too and will avoid me to spend some time on this idea.
Standard requirements regarding validity of iterators won't let us have
iterators invalidated because another iterator is erased, I do not need to
challenge it. For information, on my side I was more concerned about how I
would represent the past-the-end iterator.

Regarding the idea of having an erase_after method, usage of a forward_list
data structure for the hashtable implementation is a libstdc++ implementation
detail, not a Standard requirement. So Standard committee hasn't design it with
such a design decision. Our choice of a forward_list data structure is at the
moment the best tradeoff we came too but of course you are free to help us find
a better one. Note that I remember having tried to use a doubly linked list
when reviewing hashtable implementation but the memory overhead was resulting
in worst performance.

As you seem to have a lot of equivalent keys in your unordered_multimap<key,
value> you should perhaps move to an unordered_map<key, Container<value>>. I
even wonder if the libstdc++ profile mode could detect such an opportunity,
potentially saying what type of container should be used.
>From gcc-bugs-return-428411-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Mon Aug 26 20:27:36 2013
Return-Path: <gcc-bugs-return-428411-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 8384 invoked by alias); 26 Aug 2013 20:27:36 -0000
Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <gcc-bugs.gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-help@gcc.gnu.org>
Sender: gcc-bugs-owner@gcc.gnu.org
Delivered-To: mailing list gcc-bugs@gcc.gnu.org
Received: (qmail 8345 invoked by uid 48); 26 Aug 2013 20:27:32 -0000
From: "martin.konopka at stuba dot sk" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug regression/58244] global variable: many THOUSANDS times slower execution
Date: Mon, 26 Aug 2013 20:27:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: regression
X-Bugzilla-Version: 4.7.3
X-Bugzilla-Keywords:
X-Bugzilla-Severity: normal
X-Bugzilla-Who: martin.konopka at stuba dot sk
X-Bugzilla-Status: UNCONFIRMED
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:
Message-ID: <bug-58244-4-LKZDXIk8dQ@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-58244-4@http.gcc.gnu.org/bugzilla/>
References: <bug-58244-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
X-SW-Source: 2013-08/txt/msg01335.txt.bz2
Content-length: 332

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=58244

--- Comment #8 from Martin Konôpka <martin.konopka at stuba dot sk> ---
Yes, I understand now. Thanks. The lines with the sin() functions were not
evaluated with the local declaration. My apologies for reporting the false bug.
I will try to close the bug if I am allowed.
>From gcc-bugs-return-428412-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Mon Aug 26 22:02:32 2013
Return-Path: <gcc-bugs-return-428412-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 21640 invoked by alias); 26 Aug 2013 22:02:32 -0000
Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <gcc-bugs.gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-help@gcc.gnu.org>
Sender: gcc-bugs-owner@gcc.gnu.org
Delivered-To: mailing list gcc-bugs@gcc.gnu.org
Received: (qmail 21598 invoked by uid 48); 26 Aug 2013 22:02:27 -0000
From: "dj at redhat dot com" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug other/58238] cc1 crashes when built for ms-dos cross-compiling
Date: Mon, 26 Aug 2013 22:02:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: other
X-Bugzilla-Version: 4.7.3
X-Bugzilla-Keywords:
X-Bugzilla-Severity: normal
X-Bugzilla-Who: dj at redhat dot com
X-Bugzilla-Status: ASSIGNED
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: dj at redhat dot com
X-Bugzilla-Target-Milestone: ---
X-Bugzilla-Flags:
X-Bugzilla-Changed-Fields: bug_status cf_reconfirmed_on cc assigned_to everconfirmed attachments.created
Message-ID: <bug-58238-4-czhzrmhFx5@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-58238-4@http.gcc.gnu.org/bugzilla/>
References: <bug-58238-4@http.gcc.gnu.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 7bit
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
X-SW-Source: 2013-08/txt/msg01336.txt.bz2
Content-length: 834

http://gcc.gnu.org/bugzilla/show_bug.cgi?idX238

DJ Delorie <dj at redhat dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |ASSIGNED
   Last reconfirmed|                            |2013-08-26
                 CC|                            |dj at redhat dot com
           Assignee|unassigned at gcc dot gnu.org      |dj at redhat dot com
     Ever confirmed|0                           |1

--- Comment #1 from DJ Delorie <dj at redhat dot com> ---
Created attachment 30702
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id0702&actioníit
remove "signed" from internal type names

It seems gcc no longer permits "signed" in internal type names, so this patch
takes them out.