[Bug c++/19422] New: assoc. containers: ctor taking range is O(n log n) even if the range is sorted

[Bug c++/19422] New: assoc. containers: ctor taking range is O(n log n) even if the range is sorted

[SWElef at post dot sk]

The template constructor of associative containers with range [first,last)
should have linear complexity if the range is sorted. libstdc++ fails to
comply.

This is quite evident when looking at the include file bits/stl_tree.h,
more precisely the functions insert_unique and insert_equal taking ranges.

To be sure I made some runtime tests. The complexity is really O(n log n),
where n=distance(first,last). It is not evident with the default allocator,
but one can see the trend. I also tested with a self-made single-threaded
pool allocator and the results were very clear. I can submit the source
if need be.

Regards,
Vladimir Marko

-- 
           Summary: assoc. containers: ctor taking range is O(n log n) even
                    if the range is sorted
           Product: gcc
           Version: 3.4.3
            Status: UNCONFIRMED
          Severity: normal
          Priority: P2
         Component: c++
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: SWElef at post dot sk
                CC: gcc-bugs at gcc dot gnu dot org


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

[Bug libstdc++/19422] assoc. containers: ctor taking range is O(n log n) even if the range is sorted

[SWElef at post dot sk]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
          Component|c++                         |libstdc++


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

[Bug libstdc++/19422] assoc. containers: ctor taking range is O(n log n) even if the range is sorted

[pcarlini at suse dot de]

------- Additional Comments From pcarlini at suse dot de  2005-01-13 12:25 -------
> ... I can submit the source if need be.

Please do, that would help. Thanks in advance.


-- 


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

[Bug libstdc++/19422] assoc. containers: ctor taking range is O(n log n) even if the range is sorted

[pcarlini at suse dot de]

------- Additional Comments From pcarlini at suse dot de  2005-01-13 13:05 -------
A naive idea (I haven't really studied the issue in detail): wouldn't be of help
calling in the insert_unique/insert_equal loops the overloads taking an iterator
(which would be end()) and a value?

-- 


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

[Bug libstdc++/19422] assoc. containers: ctor taking range is O(n log n) even if the range is sorted

[SWElef at post dot sk]

------- Additional Comments From SWElef at post dot sk  2005-01-13 16:59 -------
Created an attachment (id=7953)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=7953&action=view)
performance test

This is my test program.

After giving it some thought I believe that calling the
insert_unique/insert_equal function is wrong. I don't think that any hint
(position) can help to make the running time linear in distance(first,last).
A special function should be writen for this purpose.

Regards,
Vladimir Marko


-- 


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

[Bug libstdc++/19422] assoc. containers: ctor taking range is O(n log n) even if the range is sorted

[pcarlini at suse dot de]

------- Additional Comments From pcarlini at suse dot de  2005-01-13 17:20 -------
> This is my test program.

Thanks.

> After giving it some thought I believe that calling the
> insert_unique/insert_equal function is wrong. I don't think that any hint
> (position) can help to make the running time linear in distance(first,last).
> A special function should be writen for this purpose.

Why? Are you aware of the fact that insert with hint has amortized *constant*
complexity if t is inserted after p? (Table 69)




-- 


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

[Bug libstdc++/19422] assoc. containers: ctor taking range is O(n log n) even if the range is sorted

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-01-13 17:29 -------
Just a note, here is the fits of x/10000 vs ts:
The first time:
8.666+4.8264 x + 0.04201 x^2 - 0.0003 x^3

The second time:
5.628 + 1.19516 x - 0.0004 x^2 + 0.000127 x^3

So the second one is O(n) but the first is about O(n^2).

-- 


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

[Bug libstdc++/19422] assoc. containers: ctor taking range is O(n log n) even if the range is sorted

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-01-13 17:30 -------
(In reply to comment #5)
One note about number numbers, they come from the mainline from today on a powerpc-darwin on a 
1.5GHz G4 and only with 60 lengths.

-- 


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

[Bug libstdc++/19422] assoc. containers: ctor taking range is O(n log n) even if the range is sorted

[pcarlini at suse dot de]

------- Additional Comments From pcarlini at suse dot de  2005-01-13 17:40 -------
Thanks Andrew.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |pcarlini at suse dot de
                   |dot org                     |
             Status|UNCONFIRMED                 |ASSIGNED
     Ever Confirmed|                            |1
   Last reconfirmed|0000-00-00 00:00:00         |2005-01-13 17:40:30
               date|                            |


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

[Bug libstdc++/19422] assoc. containers: ctor taking range is O(n log n) even if the range is sorted

[SWElef at post dot sk]

------- Additional Comments From SWElef at post dot sk  2005-01-14 08:24 -------
I was a little in a hurry, so I'll add a comment on the test programm now.
The "reference time" of std::list ctor taking range must be linear. Thus it
makes sence to have a look at the quotient of the second and third collumn
in the output. And that's where you can see the logarithmic behaviour.
It is visible even for std::allocator but the pool allocator makes it shine.

> > After giving it some thought I believe that calling the
> > insert_unique/insert_equal function is wrong. I don't think that any hint
> > (position) can help to make the running time linear in distance(first,last).
> > A special function should be writen for this purpose.
>
> Why? Are you aware of the fact that insert with hint has amortized *constant*
> complexity if t is inserted after p? (Table 69)

As stated in some thread on std.comp.c++ recently, "amortized" is allways
"with respect to something" and that part is missing from the standard.
The usual interpretation in this case is that if you take an assoc. container
in a given state and take the average time of the insertion with hint at every
position, it should be a constant (i.e. also independent of size()). It is far
from guaranteed to be constant if you make a lot of insertions at the end.

The position==end() is special-cased in the insert_unique/insert_equal
function with hint and a member function _M_rightmost() is used. [When I tried
to make an own version of map I decided not to have the information about
the rightmost node and I was able to satisfy all complexity requirements
anyway (except those deffective). This influenced my previously expressed
opinion.] With the access to the rightmost node in constant time the insertions
at the end could actualy be in "amortized" constant time ("amortized" wrt.
consecutive insertions at the end). This is just a feeling and needs to be
proved.

Regards,
Vladimir Marko


-- 


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

[Bug libstdc++/19422] assoc. containers: ctor taking range is O(n log n) even if the range is sorted

[pcarlini at suse dot de]

------- Additional Comments From pcarlini at suse dot de  2005-01-14 11:50 -------
> I was a little in a hurry, so I'll add a comment on the test programm now.
> The "reference time" of std::list ctor taking range must be linear. Thus it
> makes sence to have a look at the quotient of the second and third collumn
> in the output. And that's where you can see the logarithmic behaviour.
> It is visible even for std::allocator but the pool allocator makes it shine.

Thanks for the clarification. I will definitely adapt your test program for
our performance testsuite.

> ... With the access to the rightmost node in constant time the insertions
> at the end could actualy be in "amortized" constant time ("amortized" wrt.
> consecutive insertions at the end). This is just a feeling and needs to be
> proved.

Indeed, it works: on my home machine (P4-2400) currently the quotient above
grows from about 2.8 to 3.5 during the test. The trivial patch that I'm
finishing testing leads to a constant value (~2.4), as expected. This is
with the standard allocator, more suited for our testsuite.

-- 


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

[Bug libstdc++/19422] assoc. containers: ctor taking range is O(n log n) even if the range is sorted

[SWElef at post dot sk]

------- Additional Comments From SWElef at post dot sk  2005-01-14 13:33 -------
It took me quite a long time to realise that the best performance tests are
those where we count the elementary operations. The best way to expose the
O(n log n) complexity in non-fixed case is to supply the container with
a comparator object that counts the invocations of operator() in some global
variable. For an experimental proof that the fixed version is really linear
one also needs to count the node manipulations by, say, replacing _Base_ptr
with a "smart pointer" that acts as a plain pointer and counts every action
(ctor, dtor, copy, dereference).

Regards,
Vladimir Marko


-- 


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

[Bug libstdc++/19422] assoc. containers: ctor taking range is O(n log n) even if the range is sorted

[pcarlini at suse dot de]

------- Additional Comments From pcarlini at suse dot de  2005-01-14 14:28 -------
Yes, we are already using something similar, elsewhere (e.g., our copy_tracker
class). For the present needs, a tweaked version of your test program will do
rather well: even with std::allocator, the new numbers are very stable and much
improved, both in absolute value and as a trend. I will revisit the issue in
the context of 19433, perhaps.

-- 


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

[Bug libstdc++/19422] assoc. containers: ctor taking range is O(n log n) even if the range is sorted

[cvs-commit at gcc dot gnu dot org]

------- Additional Comments From cvs-commit at gcc dot gnu dot org  2005-01-14 21:09 -------
Subject: Bug 19422

CVSROOT:	/cvs/gcc
Module name:	gcc
Changes by:	paolo@gcc.gnu.org	2005-01-14 21:09:38

Modified files:
	libstdc++-v3   : ChangeLog 
	libstdc++-v3/include/bits: stl_tree.h 
Added files:
	libstdc++-v3/testsuite/performance/23_containers: 
	                                                  set_create_from_sorted.cc 

Log message:
	2005-01-14  Paolo Carlini  <pcarlini@suse.de>
	
	PR libstdc++/19422
	* include/bits/stl_tree.h (_Rb_tree<>::insert_equal(_II, _II),
	_Rb_tree<>::insert_unique(_II, _II)): Use insert_equal (insert_unique,
	respectively) with hint (end()).
	* testsuite/performance/23_containers/set_create_from_sorted.cc: New.

Patches:
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/libstdc++-v3/ChangeLog.diff?cvsroot=gcc&r1=1.2854&r2=1.2855
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/libstdc++-v3/include/bits/stl_tree.h.diff?cvsroot=gcc&r1=1.40&r2=1.41
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/libstdc++-v3/testsuite/performance/23_containers/set_create_from_sorted.cc.diff?cvsroot=gcc&r1=NONE&r2=1.1



-- 


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

[Bug libstdc++/19422] assoc. containers: ctor taking range is O(n log n) even if the range is sorted

[pcarlini at suse dot de]

------- Additional Comments From pcarlini at suse dot de  2005-01-14 22:47 -------
Fixed.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED
   Target Milestone|---                         |4.0.0


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