public inbox for gcc-bugs@sourceware.org
help / color / mirror / Atom feed
* [Bug libstdc++/13537] New: std::deque Is Not Conformant
@ 2004-01-01 4:16 stl at caltech dot edu
2004-01-01 4:49 ` [Bug libstdc++/13537] " pinskia at gcc dot gnu dot org
` (7 more replies)
0 siblings, 8 replies; 10+ messages in thread
From: stl at caltech dot edu @ 2004-01-01 4:16 UTC (permalink / raw)
To: gcc-bugs
23.2.1.3.3 says, "Inserting a single element either at the beginning or end of
a deque always takes constant time".
(Aside: Does the Standard mean true constant time there?
23.2.4.1 says, "A vector is a kind of sequence that supports random access
iterators. In addition, it supports (amortized) constant time insert and
erase operations at the end". So the Standard does recognize the difference
between amortized constant time and true constant time.
Of course, 23.1.1.12 says, "The operations in Table 68 are provided only for
the containers for which they take constant time", and then goes on to list
push_back for vector.
So the Standard sometimes says "constant time" in places where it really
means "amortized constant time".
But note the exact phrasing of 23.2.1.3.3. "always takes constant time"
clearly rules out the possibility that it is referring to amortized constant
time.)
*** Thus, I believe that libstdc++ is not conformant. ***
It seems (and I am not familiar with deque's implementation at all) that
a "map" of pointers is maintained in the deque, and insertions at the front or
back can cause the map to be reallocated. This takes O(N) time, even if the
map's size is N / 4096 or whatever.
Looking at the source for 3.3.2:
stl_deque.h: push_back() can call _M_push_back_aux().
deque.tcc: _M_push_back_aux() calls _M_reserve_map_at_back() with no arguments.
stl_deque.h: _M_reserve_map_at_back() takes __nodes_to_add which is by default
1.
It can thus call _M_reallocate_map(1, false).
deque.tcc: _M_reallocate_map() gets called with __nodes_to_add = 1 and
__add_at_front = false.
It can call copy(_M_start._M_node, _M_finish._M_node + 1, __new_nstart).
This looks like it is O(N).
Admittedly this bug is rather pedantic, but situations could be envisioned
where amortized constant time insertions cause total protonic reversal.
(This bug was found by ryanm@microsoft.com ; we discussed it, I verified that
he wasn't going crazy, and I agreed to submit a PR.)
--
Summary: std::deque Is Not Conformant
Product: gcc
Version: 3.3.2
Status: UNCONFIRMED
Severity: normal
Priority: P2
Component: libstdc++
AssignedTo: unassigned at gcc dot gnu dot org
ReportedBy: stl at caltech dot edu
CC: gcc-bugs at gcc dot gnu dot org,ryanm at microsoft dot
com
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=13537
^ permalink raw reply [flat|nested] 10+ messages in thread
* [Bug libstdc++/13537] std::deque Is Not Conformant
2004-01-01 4:16 [Bug libstdc++/13537] New: std::deque Is Not Conformant stl at caltech dot edu
@ 2004-01-01 4:49 ` pinskia at gcc dot gnu dot org
2004-01-01 5:33 ` stl at caltech dot edu
` (6 subsequent siblings)
7 siblings, 0 replies; 10+ messages in thread
From: pinskia at gcc dot gnu dot org @ 2004-01-01 4:49 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From pinskia at gcc dot gnu dot org 2004-01-01 04:49 -------
Can anyone realloc memory in constant time?
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=13537
^ permalink raw reply [flat|nested] 10+ messages in thread
* [Bug libstdc++/13537] std::deque Is Not Conformant
2004-01-01 4:16 [Bug libstdc++/13537] New: std::deque Is Not Conformant stl at caltech dot edu
2004-01-01 4:49 ` [Bug libstdc++/13537] " pinskia at gcc dot gnu dot org
@ 2004-01-01 5:33 ` stl at caltech dot edu
2004-01-11 10:08 ` paolo at gcc dot gnu dot org
` (5 subsequent siblings)
7 siblings, 0 replies; 10+ messages in thread
From: stl at caltech dot edu @ 2004-01-01 5:33 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From stl at caltech dot edu 2004-01-01 05:33 -------
Well, I don't know if it's possible to do what the Standard asks. I can't
immediately see a way to provide random access iterators and true constant
time insertion. But you guys are the implementors, not me! :->
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=13537
^ permalink raw reply [flat|nested] 10+ messages in thread
* [Bug libstdc++/13537] std::deque Is Not Conformant
2004-01-01 4:16 [Bug libstdc++/13537] New: std::deque Is Not Conformant stl at caltech dot edu
2004-01-01 4:49 ` [Bug libstdc++/13537] " pinskia at gcc dot gnu dot org
2004-01-01 5:33 ` stl at caltech dot edu
@ 2004-01-11 10:08 ` paolo at gcc dot gnu dot org
2004-01-11 10:11 ` paolo at gcc dot gnu dot org
` (4 subsequent siblings)
7 siblings, 0 replies; 10+ messages in thread
From: paolo at gcc dot gnu dot org @ 2004-01-11 10:08 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From paolo at gcc dot gnu dot org 2004-01-11 10:08 -------
Created an attachment (id=5451)
--> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=5451&action=view)
gcc-3.4 output
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=13537
^ permalink raw reply [flat|nested] 10+ messages in thread
* [Bug libstdc++/13537] std::deque Is Not Conformant
2004-01-01 4:16 [Bug libstdc++/13537] New: std::deque Is Not Conformant stl at caltech dot edu
` (2 preceding siblings ...)
2004-01-11 10:08 ` paolo at gcc dot gnu dot org
@ 2004-01-11 10:11 ` paolo at gcc dot gnu dot org
2004-01-11 10:16 ` paolo at gcc dot gnu dot org
` (3 subsequent siblings)
7 siblings, 0 replies; 10+ messages in thread
From: paolo at gcc dot gnu dot org @ 2004-01-11 10:11 UTC (permalink / raw)
To: gcc-bugs
--
What |Removed |Added
----------------------------------------------------------------------------
Attachment #5451|gcc-3.4 output |Sorry, attached to the
description| |wrong PR!
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=13537
^ permalink raw reply [flat|nested] 10+ messages in thread
* [Bug libstdc++/13537] std::deque Is Not Conformant
2004-01-01 4:16 [Bug libstdc++/13537] New: std::deque Is Not Conformant stl at caltech dot edu
` (3 preceding siblings ...)
2004-01-11 10:11 ` paolo at gcc dot gnu dot org
@ 2004-01-11 10:16 ` paolo at gcc dot gnu dot org
2004-01-11 16:45 ` paolo at gcc dot gnu dot org
` (2 subsequent siblings)
7 siblings, 0 replies; 10+ messages in thread
From: paolo at gcc dot gnu dot org @ 2004-01-11 10:16 UTC (permalink / raw)
To: gcc-bugs
--
What |Removed |Added
----------------------------------------------------------------------------
Attachment #5451|gcc-3_4.out |
filename| |
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=13537
^ permalink raw reply [flat|nested] 10+ messages in thread
* [Bug libstdc++/13537] std::deque Is Not Conformant
2004-01-01 4:16 [Bug libstdc++/13537] New: std::deque Is Not Conformant stl at caltech dot edu
` (4 preceding siblings ...)
2004-01-11 10:16 ` paolo at gcc dot gnu dot org
@ 2004-01-11 16:45 ` paolo at gcc dot gnu dot org
2004-01-28 22:27 ` skirby at acm dot org
2004-01-29 1:35 ` stl at caltech dot edu
7 siblings, 0 replies; 10+ messages in thread
From: paolo at gcc dot gnu dot org @ 2004-01-11 16:45 UTC (permalink / raw)
To: gcc-bugs
--
What |Removed |Added
----------------------------------------------------------------------------
Attachment #5451 is|0 |1
obsolete| |
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=13537
^ permalink raw reply [flat|nested] 10+ messages in thread
* [Bug libstdc++/13537] std::deque Is Not Conformant
2004-01-01 4:16 [Bug libstdc++/13537] New: std::deque Is Not Conformant stl at caltech dot edu
` (5 preceding siblings ...)
2004-01-11 16:45 ` paolo at gcc dot gnu dot org
@ 2004-01-28 22:27 ` skirby at acm dot org
2004-01-29 1:35 ` stl at caltech dot edu
7 siblings, 0 replies; 10+ messages in thread
From: skirby at acm dot org @ 2004-01-28 22:27 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From skirby at acm dot org 2004-01-28 22:27 -------
> 23.2.1.3.3 says, "Inserting a single element either at the beginning or end of
> a deque always takes constant time".
> (Aside: Does the Standard mean true constant time there?
23.1/2 says, "All of the complexity requirements in this clause are stated
solely in terms of the number of operations on the contained objects."
> 23.2.4.1 says, "A vector is a kind of sequence that supports random access
> iterators. In addition, it supports (amortized) constant time insert and
> erase operations at the end". So the Standard does recognize the difference
> between amortized constant time and true constant time.
>
> Of course, 23.1.1.12 says, "The operations in Table 68 are provided only for
> the containers for which they take constant time", and then goes on to list
> push_back for vector.
See http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/lwg-defects.html#139 for an
updated version.
> So the Standard sometimes says "constant time" in places where it really
> means "amortized constant time".
>
> But note the exact phrasing of 23.2.1.3.3. "always takes constant time"
> clearly rules out the possibility that it is referring to amortized constant
> time.)
>
> *** Thus, I believe that libstdc++ is not conformant. ***
>
> It seems (and I am not familiar with deque's implementation at all) that
> a "map" of pointers is maintained in the deque, and insertions at the front or
> back can cause the map to be reallocated. This takes O(N) time, even if the
> map's size is N / 4096 or whatever.
You are talking about complexity in terms of the number of operations performed
on pointers to the contained objects.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=13537
^ permalink raw reply [flat|nested] 10+ messages in thread
* [Bug libstdc++/13537] std::deque Is Not Conformant
2004-01-01 4:16 [Bug libstdc++/13537] New: std::deque Is Not Conformant stl at caltech dot edu
` (6 preceding siblings ...)
2004-01-28 22:27 ` skirby at acm dot org
@ 2004-01-29 1:35 ` stl at caltech dot edu
7 siblings, 0 replies; 10+ messages in thread
From: stl at caltech dot edu @ 2004-01-29 1:35 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From stl at caltech dot edu 2004-01-29 01:35 -------
Good point. This is neither a gcc bug nor a defect in the Standard.
--
What |Removed |Added
----------------------------------------------------------------------------
Status|UNCONFIRMED |RESOLVED
Resolution| |INVALID
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=13537
^ permalink raw reply [flat|nested] 10+ messages in thread
[parent not found: <20040101041622.13537.stl@nuwen.net>]
end of thread, other threads:[~2004-10-25 14:03 UTC | newest]
Thread overview: 10+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2004-01-01 4:16 [Bug libstdc++/13537] New: std::deque Is Not Conformant stl at caltech dot edu
2004-01-01 4:49 ` [Bug libstdc++/13537] " pinskia at gcc dot gnu dot org
2004-01-01 5:33 ` stl at caltech dot edu
2004-01-11 10:08 ` paolo at gcc dot gnu dot org
2004-01-11 10:11 ` paolo at gcc dot gnu dot org
2004-01-11 10:16 ` paolo at gcc dot gnu dot org
2004-01-11 16:45 ` paolo at gcc dot gnu dot org
2004-01-28 22:27 ` skirby at acm dot org
2004-01-29 1:35 ` stl at caltech dot edu
[not found] <20040101041622.13537.stl@nuwen.net>
2004-10-25 14:03 ` pcarlini at suse dot de
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).