[Bug libstdc++/13537] New: std::deque Is Not Conformant

[Bug libstdc++/13537] New: std::deque Is Not Conformant

[stl at caltech dot edu]

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

[Bug libstdc++/13537] std::deque Is Not Conformant

[pinskia at gcc dot gnu dot org]

------- 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

[Bug libstdc++/13537] std::deque Is Not Conformant

[stl at caltech dot edu]

------- 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

[Bug libstdc++/13537] std::deque Is Not Conformant

[paolo at gcc dot gnu dot org]

------- 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

[Bug libstdc++/13537] std::deque Is Not Conformant

[paolo at gcc dot gnu dot org]

-- 
           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

[Bug libstdc++/13537] std::deque Is Not Conformant

[paolo at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
   Attachment #5451|gcc-3_4.out                 |
           filename|                            |


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

[Bug libstdc++/13537] std::deque Is Not Conformant

[paolo at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
Attachment #5451 is|0                           |1
           obsolete|                            |


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

[Bug libstdc++/13537] std::deque Is Not Conformant

[skirby at acm dot org]

------- 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

[Bug libstdc++/13537] std::deque Is Not Conformant

[stl at caltech dot edu]

------- 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