Bug 49561 - [C++0x] std::list::size complexity
Summary: [C++0x] std::list::size complexity
Status: RESOLVED FIXED
Alias: None
Product: gcc
Classification: Unclassified
Component: libstdc++ (show other bugs)
Version: 4.5.2
: P3 normal
Target Milestone: 5.0
Assignee: Not yet assigned to anyone
URL:
Keywords: ABI
Depends on:
Blocks: 61347
  Show dependency treegraph
 
Reported: 2011-06-28 08:17 UTC by yoch.melka
Modified: 2014-10-10 16:15 UTC (History)
5 users (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed: 2011-06-28 10:08:36


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description yoch.melka 2011-06-28 08:17:46 UTC
I realized that the complexity of std::list::size() is O(n), not O(1).

This does not conform to standard. The standard states that size() function is in constant time for alls containers. So, the behavior of gcc is not as expected.

This also affects parts of std::list::splice() function, as mentioned in the last drat (n3242 - 23.3.5.5):

[quote]
1 Since lists allow fast insertion and erasing from the middle of a list, certain operations are provided specifically
for them.
2 list provides three splice operations that destructively move elements from one list to another.[...]

void splice(const_iterator position, list<T,Allocator>& x) noexcept;
void splice(const_iterator position, list<T,Allocator>&& x) noexcept;
[...]
4 Effects: Inserts the contents of x before position and x becomes empty. Pointers and references to
the moved elements of x now refer to those same elements but as members of *this. Iterators referring
to the moved elements will continue to refer to their elements, but they now behave as iterators into
*this, not into x.
5 Complexity: Constant time.

void splice(const_iterator position, list<T,Allocator>& x, const_iterator i) noexcept;
void splice(const_iterator position, list<T,Allocator>&& x, const_iterator i) noexcept;
6 Effects: Inserts an element pointed to by i from list x before position and removes the element from
x. The result is unchanged if position == i or position == ++i. Pointers and references to *i
continue to refer to this same element but as a member of *this. Iterators to *i (including i itself)
continue to refer to the same element, but now behave as iterators into *this, not into x.
[...]
8 Complexity: Constant time.

void splice(const_iterator position, list<T,Allocator>& x, const_iterator first,
const_iterator last) noexcept;
void splice(const_iterator position, list<T,Allocator>&& x, const_iterator first,
const_iterator last) noexcept;
9 Effects: Inserts elements in the range [first,last) before position and removes the elements from
x.
[...]
11 Complexity: Constant time if &x == this; otherwise, linear time.
[/quote]
Comment 1 Jonathan Wakely 2011-06-28 08:47:47 UTC
(In reply to comment #0)
> I realized that the complexity of std::list::size() is O(n), not O(1).
> 
> This does not conform to standard. The standard states that size() function is
> in constant time for alls containers. 

No, the current standard does not.

The C++0x draft does, but it's not yet a standard, and parts of it are not yet implemented.
Comment 2 Bryce Lelbach (wash) 2011-09-20 00:15:40 UTC
(In reply to comment #1)
> (In reply to comment #0)
> > I realized that the complexity of std::list::size() is O(n), not O(1).
> > 
> > This does not conform to standard. The standard states that size() function is
> > in constant time for alls containers. 
> 
> No, the current standard does not.
> 
> The C++0x draft does, but it's not yet a standard, and parts of it are not yet
> implemented.

The current standard is now C++11. 23.2.1, Table 96 explicitly states that the size() method of Containers must execute in constant time.

Can this bug please be changed to confirmed? As of today (r178989), std::list<>::size() is still O(N).
Comment 3 Paolo Carlini 2011-09-20 00:28:37 UTC
It's already confirmed, NEW means confirmed.
Comment 4 Paolo Carlini 2011-09-21 10:56:00 UTC
Maybe I can do this in time for 4.7, I don't make promises however, the changes are conceptually simple but quite a few throughout the class. Of course then it will definitely impossible to mix C++98 and C++11 std::lists, a data member must be added in c++0x mode in order to implement this.
Comment 5 paolo@gcc.gnu.org 2011-10-04 22:19:48 UTC
Author: paolo
Date: Tue Oct  4 22:19:44 2011
New Revision: 179528

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=179528
Log:
2011-10-04  Paolo Carlini  <paolo.carlini@oracle.com>

	PR libstdc++/49561
	* include/bits/stl_list.h (_List_base<>::_List_impl::_M_size):
	Add in C++0x mode.
	(_List_base<>::_List_impl, _List_base<>::_M_get_node,
	_List_base<>::_M_put_node, _List_base<>::_List_base(_List_base&&),
	list<>::size, list<>::swap, list<>::splice): Use it.
	(operator==(const list<>&, const list<>&)): Rewrite in C++0x mode.
	* include/bits/list.tcc (list<>::erase): Likewise.
	(list<>::merge): Adjust in C++0x mode.
	* testsuite/23_containers/list/requirements/dr438/assign_neg.cc:
	Adjust dg-error line number.
	* testsuite/23_containers/list/requirements/dr438/insert_neg.cc:
	Likewise.
	* testsuite/23_containers/list/requirements/dr438/
	constructor_1_neg.cc: Likewise.
	* testsuite/23_containers/list/requirements/dr438/
	constructor_2_neg.cc: Likewise.

Modified:
    trunk/libstdc++-v3/ChangeLog
    trunk/libstdc++-v3/include/bits/list.tcc
    trunk/libstdc++-v3/include/bits/stl_list.h
    trunk/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/assign_neg.cc
    trunk/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/constructor_1_neg.cc
    trunk/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/constructor_2_neg.cc
    trunk/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/insert_neg.cc
Comment 6 Paolo Carlini 2011-10-04 22:22:39 UTC
Done. If you can, please stress std::list in C++0x mode in order to shake possible bugs related to the O(1) size in time for the 4.7.0 release.
Comment 7 Bryce Lelbach (wash) 2011-10-04 23:06:01 UTC
Thanks - I'll give it a whirl!
Comment 8 James Y Knight 2011-10-07 01:26:28 UTC
This change seems like it might be the first major incompatibility added to gcc's c++0x mode (at least, things appeared to work before, maybe that was just luck).

I guess it will now be dangerous to even load a shared lib compiled with --std=c++0x into the same executable as C++ code compiled in the default c++03 mode, because of the potential for the exported weak symbols from out-of-line std::list functions compiled for one layout to be used on a structure defined with the other layout in the other shared object. Even when no c++ objects are ever passed from one shared lib to the other.

This seems like a particularly bad failure mode to have, especially considering also bug 36022 (invalid), since it's by design difficult to *not* export the symbols even if you try.

I understand that the versioned namespaces feature is supposed to help with this sort of issue; is there any plan to use it to give the c++0x std::list object a different mangled name than the c++03 std::list object?
Comment 9 Jonathan Wakely 2011-10-07 01:36:02 UTC
(In reply to comment #8)
> I guess it will now be dangerous to even load a shared lib compiled with
> --std=c++0x into the same executable as C++ code compiled in the default c++03
> mode,

It was already an ODR violation for some code, see PR 45093

There are no promises of interoperability between -std=c++98 and -std=c++0x
Comment 10 Paolo Carlini 2011-10-07 01:37:34 UTC
I can confirm it was just luck, really.
Comment 11 paolo@gcc.gnu.org 2012-07-03 00:47:23 UTC
Author: paolo
Date: Tue Jul  3 00:47:17 2012
New Revision: 189185

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=189185
Log:
2012-07-02  Paolo Carlini  <paolo.carlini@oracle.com>

	Revert:
	2011-10-04  Paolo Carlini  <paolo.carlini@oracle.com>

	PR libstdc++/49561
	* include/bits/stl_list.h (_List_base<>::_List_impl::_M_size):
	Add in C++0x mode.
	(_List_base<>::_List_impl, _List_base<>::_M_get_node,
	_List_base<>::_M_put_node, _List_base<>::_List_base(_List_base&&),
	list<>::size, list<>::swap, list<>::splice): Use it.
	(operator==(const list<>&, const list<>&)): Rewrite in C++0x mode.
	* include/bits/list.tcc (list<>::erase): Likewise.
	(list<>::merge): Adjust in C++0x mode.
	* testsuite/23_containers/list/requirements/dr438/assign_neg.cc:
	Adjust dg-error line number.
	* testsuite/23_containers/list/requirements/dr438/insert_neg.cc:
	Likewise.
	* testsuite/23_containers/list/requirements/dr438/
	constructor_1_neg.cc: Likewise.
	* testsuite/23_containers/list/requirements/dr438/
	constructor_2_neg.cc: Likewise.

Modified:
    trunk/libstdc++-v3/ChangeLog
    trunk/libstdc++-v3/include/bits/list.tcc
    trunk/libstdc++-v3/include/bits/stl_list.h
    trunk/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/assign_neg.cc
    trunk/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/constructor_1_neg.cc
    trunk/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/constructor_2_neg.cc
    trunk/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/insert_neg.cc
Comment 12 paolo@gcc.gnu.org 2012-07-03 01:37:53 UTC
Author: paolo
Date: Tue Jul  3 01:37:48 2012
New Revision: 189186

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=189186
Log:
2012-07-02  Paolo Carlini  <paolo.carlini@oracle.com>

	Revert:
	2011-10-04  Paolo Carlini  <paolo.carlini@oracle.com>

	PR libstdc++/49561
	* include/bits/stl_list.h (_List_base<>::_List_impl::_M_size):
	Add in C++0x mode.
	(_List_base<>::_List_impl, _List_base<>::_M_get_node,
	_List_base<>::_M_put_node, _List_base<>::_List_base(_List_base&&),
	list<>::size, list<>::swap, list<>::splice): Use it.
	(operator==(const list<>&, const list<>&)): Rewrite in C++0x mode.
	* include/bits/list.tcc (list<>::erase): Likewise.
	(list<>::merge): Adjust in C++0x mode.
	* testsuite/23_containers/list/requirements/dr438/assign_neg.cc:
	Adjust dg-error line number.
	* testsuite/23_containers/list/requirements/dr438/insert_neg.cc:
	Likewise.
	* testsuite/23_containers/list/requirements/dr438/
	constructor_1_neg.cc: Likewise.
	* testsuite/23_containers/list/requirements/dr438/
	constructor_2_neg.cc: Likewise.

Modified:
    branches/gcc-4_7-branch/libstdc++-v3/ChangeLog
    branches/gcc-4_7-branch/libstdc++-v3/include/bits/list.tcc
    branches/gcc-4_7-branch/libstdc++-v3/include/bits/stl_list.h
    branches/gcc-4_7-branch/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/assign_neg.cc
    branches/gcc-4_7-branch/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/constructor_1_neg.cc
    branches/gcc-4_7-branch/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/constructor_2_neg.cc
    branches/gcc-4_7-branch/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/insert_neg.cc
Comment 13 Paolo Carlini 2012-07-03 01:40:12 UTC
Patch reverted, thus in C++11 mode size() is back to O(n) but std::list can interoperate with the C++98 version of it.
Comment 14 Bryce Lelbach (wash) 2012-07-03 03:35:31 UTC
(In reply to comment #13)
> Patch reverted, thus in C++11 mode size() is back to O(n) but std::list can
> interoperate with the C++98 version of it.

Why has this been reverted? If std::list<>::size() is not O(1), then GCC's C++11 standard library is not compliant with the C++11 international standard. I have personally spoken with multiple members of the standard body and confirmed that this behavior is REQUIRED by the C++11 standard.

Please re-apply this patch for C++11 mode, or state somewhere in the GCC docs that GCC is not compliant with the C++11 standard. In the C++03 and C++98 standards, it was highly suggested that compiler vendors implement std::list<>::size() as O(1).

I understand this is a breaking change, but honestly, the C++ standard has been suggesting the O(1) implementation for over a decade, and the GCC standard library developers have chosen to implement different behavior. You've had many years of warning about this.

(In reply to comment #10)
> I can confirm it was just luck, really.

^ Paolo, this is correct. I think it's a really, really bad idea for any particular vendor to cherrypick elements of an ISO standard to implement. If you feel that the C++11 standard is wrong to require an O(1) implementation, please file a standard defect (I'm afraid you can expect me to fight it). Otherwise, I'd like to ask that you please reconsider applying this patch.
Comment 15 Bryce Lelbach (wash) 2012-07-03 03:38:52 UTC
Also, didn't this already make it into the 4.7 release? Wouldn't reverting it now just cause incompatibilities with 4.7 and both older and newer releases?
Comment 16 Jonathan Wakely 2012-07-03 08:31:18 UTC
(In reply to comment #14)
> (In reply to comment #13)
> > Patch reverted, thus in C++11 mode size() is back to O(n) but std::list can
> > interoperate with the C++98 version of it.
> 
> Why has this been reverted? If std::list<>::size() is not O(1), then GCC's
> C++11 standard library is not compliant with the C++11 international standard.
> I have personally spoken with multiple members of the standard body and
> confirmed that this behavior is REQUIRED by the C++11 standard.

Yes, we're well aware of that, thanks.

This patch made c++98 and c++11 code incompatible and is causing serious problems for distros.

You've lived with O(n) size for 15 years, you can live with it for a while longer until libstdc++'s ABI changes.

> Please re-apply this patch for C++11 mode, or state somewhere in the GCC docs
> that GCC is not compliant with the C++11 standard. In the C++03 and C++98
> standards, it was highly suggested that compiler vendors implement
> std::list<>::size() as O(1).
>
> I understand this is a breaking change, but honestly, the C++ standard has been
> suggesting the O(1) implementation for over a decade, and the GCC standard
> library developers have chosen to implement different behavior. You've had many
> years of warning about this.

You seem to think we were taken by surprise, that has nothing to do with it. GCC has maintained ABI compatibility since version 3.4, including between c++98 and c++11 mode in most cases. This change broke that and caused a lot of problems in real systems (not just "you don't implement the standard!") and has been reverted until the entire library ABI gets updated at a later date.
 
> (In reply to comment #10)
> > I can confirm it was just luck, really.
> 
> ^ Paolo, this is correct. I think it's a really, really bad idea for any
> particular vendor to cherrypick elements of an ISO standard to implement. If
> you feel that the C++11 standard is wrong to require an O(1) implementation,
> please file a standard defect (I'm afraid you can expect me to fight it).
> Otherwise, I'd like to ask that you please reconsider applying this patch.

Calm down. Noone thinks it's wrong, but maintaining ABI compatibility has been decided to be more important for the current releases. See the mailing lists for more information.
Comment 17 Jonathan Wakely 2012-07-03 08:34:51 UTC
(In reply to comment #15)
> Also, didn't this already make it into the 4.7 release? Wouldn't reverting it
> now just cause incompatibilities with 4.7 and both older and newer releases?

Yes. But 4.7.0 and 4.7.1 are already incompatible with older releases. The maintainers have taken the decision to restore compatibility with older releases.

We plan to try and reimplement the change in a cleaner way asap.
Comment 18 Jonathan Wakely 2012-08-22 19:47:03 UTC
setting ABI keyword as this can't be properly fixed without an incompatible change
Comment 19 Jonathan Wakely 2014-10-10 15:34:29 UTC
Author: redi
Date: Fri Oct 10 15:33:57 2014
New Revision: 216094

URL: https://gcc.gnu.org/viewcvs?rev=216094&root=gcc&view=rev
Log:
	PR libstdc++/49561
	* acinclude.m4 (GLIBCXX_ENABLE_LIBSTDCXX_CXX11_ABI): Define.
	* configure.ac: Use GLIBCXX_ENABLE_LIBSTDCXX_CXX11_ABI.
	* configure: Regenerate.
	* include/Makefile.am (stamp-cxx11-abi): New target.
	(c++config.h): Set _GLIBCXX_USE_CXX11_ABI macro.
	* include/Makefile.in: Regenerate.
	* include/bits/c++config: Add _GLIBCXX_USE_CXX11_ABI placeholder and
	define _GLIBCXX_DEFAULT_ABI_TAG.
	* include/bits/list.tcc (list::emplace(const_iterator, _Args&...)):
	Increment size.
	(list::emplace(const_iterator, const value_type&)): Likewise.
	(list::merge(list&), list::merge(list&, _StrictWeakOrdering)): Adjust
	list sizes.
	* include/bits/stl_list.h (_List_base, list): Add ABI tag macro.
	(_List_base::_M_size): New data member in cxx11 ABI mode.
	(_List_base::_S_distance(_List_node_base*, _List_node_base*)): New
	function.
	(_List_base::_M_get_size(), _List_base::_M_set_size(size_t),
	_List_base::_M_inc_size(size_t), _List_base::_M_dec_size(size_t),
	_List_base::_M_distance, _List_base::_M_node_count): New functions for
	accessing list size correctly for the ABI mode.
	(_List_base::_List_base(_List_base&&)): Copy size and reset source.
	(_List_base::_M_init()): Initialize size member.
	(list::size()): Use _List_base::_M_node_count.
	(list::swap(list&)): Swap sizes.
	(list::splice(iterator, list&)): Update sizes.
	(list::splice(iterator, list&, iterator)): Likewise.
	(list::insert(iterator, const value_type&)): Update size.
	(list::insert(iterator, _Args&&...)): Likewise.
	(list::_M_erase(iterator)): Likewise.
	* testsuite/23_containers/list/requirements/dr438/assign_neg.cc:
	Adjust.
	* testsuite/23_containers/list/requirements/dr438/constructor_1_neg.cc:
	Adjust.
	* testsuite/23_containers/list/requirements/dr438/constructor_2_neg.cc:
	Adjust.
	* testsuite/23_containers/list/requirements/dr438/insert_neg.cc:
	Adjust.
	* testsuite/ext/profile/mutex_extensions_neg.cc: Adjust.

Modified:
    trunk/libstdc++-v3/ChangeLog
    trunk/libstdc++-v3/acinclude.m4
    trunk/libstdc++-v3/configure
    trunk/libstdc++-v3/configure.ac
    trunk/libstdc++-v3/include/Makefile.am
    trunk/libstdc++-v3/include/Makefile.in
    trunk/libstdc++-v3/include/bits/c++config
    trunk/libstdc++-v3/include/bits/list.tcc
    trunk/libstdc++-v3/include/bits/stl_list.h
    trunk/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/assign_neg.cc
    trunk/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/constructor_1_neg.cc
    trunk/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/constructor_2_neg.cc
    trunk/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/insert_neg.cc
    trunk/libstdc++-v3/testsuite/ext/profile/mutex_extensions_neg.cc
Comment 20 Jonathan Wakely 2014-10-10 16:00:30 UTC
Fixed for 5.0
Comment 21 Jonathan Wakely 2014-10-10 16:15:26 UTC
Author: redi
Date: Fri Oct 10 16:14:52 2014
New Revision: 216097

URL: https://gcc.gnu.org/viewcvs?rev=216097&root=gcc&view=rev
Log:
	PR libstdc++/49561
	* acinclude.m4 (GLIBCXX_ENABLE_LIBSTDCXX_CXX11_ABI): Define.
	* configure.ac: Use GLIBCXX_ENABLE_LIBSTDCXX_CXX11_ABI.
	* configure: Regenerate.
	* include/Makefile.am (stamp-cxx11-abi): New target.
	(c++config.h): Set _GLIBCXX_USE_CXX11_ABI macro.
	* include/Makefile.in: Regenerate.
	* include/bits/c++config: Add _GLIBCXX_USE_CXX11_ABI placeholder and
	define _GLIBCXX_DEFAULT_ABI_TAG.
	* include/bits/list.tcc (list::emplace(const_iterator, _Args&...)):
	Increment size.
	(list::emplace(const_iterator, const value_type&)): Likewise.
	(list::merge(list&), list::merge(list&, _StrictWeakOrdering)): Adjust
	list sizes.
	* include/bits/stl_list.h (_List_base, list): Add ABI tag macro.
	(_List_base::_M_size): New data member in cxx11 ABI mode.
	(_List_base::_S_distance(_List_node_base*, _List_node_base*)): New
	function.
	(_List_base::_M_get_size(), _List_base::_M_set_size(size_t),
	_List_base::_M_inc_size(size_t), _List_base::_M_dec_size(size_t),
	_List_base::_M_distance, _List_base::_M_node_count): New functions for
	accessing list size correctly for the ABI mode.
	(_List_base::_List_base(_List_base&&)): Copy size and reset source.
	(_List_base::_M_init()): Initialize size member.
	(list::size()): Use _List_base::_M_node_count.
	(list::swap(list&)): Swap sizes.
	(list::splice(iterator, list&)): Update sizes.
	(list::splice(iterator, list&, iterator)): Likewise.
	(list::insert(iterator, const value_type&)): Update size.
	(list::insert(iterator, _Args&&...)): Likewise.
	(list::_M_erase(iterator)): Likewise.
	* testsuite/23_containers/list/requirements/dr438/assign_neg.cc:
	Adjust.
	* testsuite/23_containers/list/requirements/dr438/constructor_1_neg.cc:
	Adjust.
	* testsuite/23_containers/list/requirements/dr438/constructor_2_neg.cc:
	Adjust.
	* testsuite/23_containers/list/requirements/dr438/insert_neg.cc:
	Adjust.
	* testsuite/ext/profile/mutex_extensions_neg.cc: Adjust.
# End of auto-generated commit message
Fix date and whitespace in libstdc++-v3/ChangeLog

Modified:
    trunk/libstdc++-v3/ChangeLog