[Bug libstdc++/19422] assoc. containers: ctor taking range is O(n log n) even if the range is sorted
--- 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
[Bug libstdc++/19422] assoc. containers: ctor taking range is O(n log n) even if the range is sorted
--- 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: [EMAIL PROTECTED] 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 <[EMAIL PROTECTED]> 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
--- 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
--- 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
--- 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
--- 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
--- 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|-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
--- 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
--- Additional Comments From pinskia at gcc dot gnu dot org 2005-01-13 17:29 --- Just a note, here is the fits of x/1 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
--- 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
--- 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
--- 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
--- 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
-- What|Removed |Added Component|c++ |libstdc++ http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19422
