[Bug libstdc++/46659] New: std::list iterator debugging (_GLIBCXX_DEBUG) is much slower than stlport's one.

[Bug libstdc++/46659] New: std::list iterator debugging (_GLIBCXX_DEBUG) is much slower than stlport's one.

[pluto at agmk dot net]

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

           Summary: std::list iterator debugging (_GLIBCXX_DEBUG) is much
                    slower than stlport's one.
           Product: gcc
           Version: 4.5.2
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: pluto@agmk.net


Created attachment 22532
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=22532
testcase with preprocessed sources.

an evil testcase:

#include <list>
#include <vector>
int main()
{
        typedef std::list< int > L;
        L list;
        typedef std::vector< L::const_iterator > V;
        V vec;
        for ( int i = 0; i < 30000; i++ )
                list.push_back( 42 );
        for ( L::const_iterator j = list.begin(); j != list.end(); ++j )
                vec.push_back( j );
        list.clear();
}

compilation with libstdc++ and stlport-5.2.1 for benchmarking:

/local/devel/toolchain45/x86_64-gnu-linux.mt_alloc/bin/x86_64-gnu-linux-g++
-pthread -O2 -Wall -D_GLIBCXX_DEBUG --save-temps \
        t.cpp -o t-libstdcxx
mv t.ii t-libstdcxx.ii

/local/devel/toolchain45/x86_64-gnu-linux.mt_alloc/bin/x86_64-gnu-linux-g++
-pthread -O2 -Wall -D_STLP_DEBUG=1 -isystem ./STLport-5.2.1/include/stlport
--save-temps \
        t.cpp -o t-stlport ./STLport-5.2.1/lib64/libstlportstlg.a
mv t.ii t-stlport.ii


and few benchmarks on athlon64-2800+:

20000 elements:

$ time ./t-libstdcxx
./t-libstdcxx  8,28s user 0,00s system 97% cpu 8,458 total
$ time ./t-stlport  
./t-stlport  4,57s user 0,01s system 98% cpu 4,644 total

30000 elements:

$ time ./t-libstdcxx
./t-libstdcxx  19,03s user 0,01s system 97% cpu 19,433 total
$ time ./t-stlport
./t-stlport  8,93s user 0,00s system 98% cpu 9,095 tota

[Bug libstdc++/46659] std::list iterator debugging (_GLIBCXX_DEBUG) is much slower than stlport's one.

[redi at gcc dot gnu.org]

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

--- Comment #1 from Jonathan Wakely <redi at gcc dot gnu.org> 2010-11-25 15:45:58 UTC ---
the changes in http://gcc.gnu.org/ml/libstdc++/2010-11/msg00131.html might help

[Bug libstdc++/46659] std::list iterator debugging (_GLIBCXX_DEBUG) is much slower than stlport's one.

[paolo.carlini at oracle dot com]

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

Paolo Carlini <paolo.carlini at oracle dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |fdumont at gcc dot gnu.org
           Severity|normal                      |enhancement

--- Comment #2 from Paolo Carlini <paolo.carlini at oracle dot com> 2010-11-25 16:59:04 UTC ---
Let's add Francois in CC, he knows STLPort pretty well. And somebody should
profile this difference, redo the tests for current mainline (which already has
some performance improvement from Francois), etc.

[Bug libstdc++/46659] std::list iterator debugging (_GLIBCXX_DEBUG) is much slower than stlport's one.

[pluto at agmk dot net]

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

--- Comment #3 from Pawel Sikora <pluto at agmk dot net> 2010-11-25 18:40:28 UTC ---
(In reply to comment #2)
> Let's add Francois in CC, he knows STLPort pretty well. And somebody should
> profile this difference, redo the tests for current mainline (which already has
> some performance improvement from Francois), etc.

with the current mainline i have following results
on my personal Q9300 cpu:

50000 elements:

$ time ./t-libstdcxx
./t-libstdcxx  11,17s user 0,00s system 99% cpu 11,171 total
$ time ./t-stlport
./t-stlport  7,18s user 0,00s system 99% cpu 7,180 total

100000 elements:

$ time ./t-libstdcxx
./t-libstdcxx  68,26s user 0,00s system 99% cpu 1:08,28 total
$ time ./t-stlport
./t-stlport  31,84s user 0,00s system 99% cpu 31,853 total

200000 elements:

$ time ./t-libstdcxx
./t-libstdcxx  316,08s user 0,02s system 99% cpu 5:16,13 total
$ time ./t-stlport
./t-stlport  184,10s user 0,01s system 99% cpu 3:04,12 total

[Bug libstdc++/46659] std::list iterator debugging (_GLIBCXX_DEBUG) is much slower than stlport's one.

[paolo.carlini at oracle dot com]

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

--- Comment #4 from Paolo Carlini <paolo.carlini at oracle dot com> 2010-12-07 11:06:11 UTC ---
Francois, do you have an opinion about this?

[Bug libstdc++/46659] std::list iterator debugging (_GLIBCXX_DEBUG) is much slower than stlport's one.

[redi at gcc dot gnu.org]

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

--- Comment #5 from Jonathan Wakely <redi at gcc dot gnu.org> 2010-12-07 21:40:38 UTC ---
With current mainline 200000 elements finishes in 0.1s on my x86_64 system,
which is only 5 times slower than non-debug mode.

That's compared with 5m36s with 4.5's debug mode.

I think it's safe to say François has fixed it :)

[Bug libstdc++/46659] std::list iterator debugging (_GLIBCXX_DEBUG) is much slower than stlport's one.

[pluto at agmk dot net]

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

--- Comment #6 from Pawel Sikora <pluto at agmk dot net> 2010-12-07 22:05:15 UTC ---
(In reply to comment #5)
> With current mainline 200000 elements finishes in 0.1s on my x86_64 system,
> which is only 5 times slower than non-debug mode.
> 
> That's compared with 5m36s with 4.5's debug mode.
> 
> I think it's safe to say François has fixed it :)

in fact :)
with current git-mirror 54486c25c3df3bdb314929fe30855f0d3bd2e0b5
checkout for 200'000 elemetns i have a fantastic speedup:

$ time ./t-libstdcxx
./t-libstdcxx  0,09s user 0,01s system 98% cpu 0,109 total
$ time ./t-stlport
./t-stlport  170,91s user 0,01s system 99% cpu 2:50,93 total

[Bug libstdc++/46659] std::list iterator debugging (_GLIBCXX_DEBUG) is much slower than stlport's one.

[paolo.carlini at oracle dot com]

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

--- Comment #7 from Paolo Carlini <paolo.carlini at oracle dot com> 2010-12-07 22:10:39 UTC ---
Excellent. If you can confirm that the improvement holds true also for a
smaller number of elements let's close this as fixed for 4.6.0.

[Bug libstdc++/46659] std::list iterator debugging (_GLIBCXX_DEBUG) is much slower than stlport's one.

[pluto at agmk dot net]

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

Pawel Sikora <pluto at agmk dot net> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |RESOLVED
         Resolution|                            |FIXED

--- Comment #8 from Pawel Sikora <pluto at agmk dot net> 2010-12-07 22:19:39 UTC ---
here're the results for current git: 54486c25c3df3bdb314929fe30855f0d3bd2e0b5

200000 elements:

$ time ./t-libstdcxx
./t-libstdcxx  0,09s user 0,01s system 98% cpu 0,109 total
$ time ./t-stlport
./t-stlport  170,91s user 0,01s system 99% cpu 2:50,93 total

100000 elements:

$ time ./t-libstdcxx
./t-libstdcxx  0,05s user 0,00s system 95% cpu 0,056 total
$ time ./t-stlport
./t-stlport  31,59s user 0,02s system 99% cpu 31,622 total

50000 elements:

$ time ./t-libstdcxx
./t-libstdcxx  0,02s user 0,00s system 93% cpu 0,029 total
$ time ./t-stlport
./t-stlport  7,28s user 0,00s system 99% cpu 7,287 total

so... it's fixed.

[Bug libstdc++/46659] std::list iterator debugging (_GLIBCXX_DEBUG) is much slower than stlport's one.

[paolo.carlini at oracle dot com]

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

Paolo Carlini <paolo.carlini at oracle dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |4.6.0

[Bug libstdc++/46659] std::list iterator debugging (_GLIBCXX_DEBUG) is much slower than stlport's one.

[fdumont at gcc dot gnu.org]

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

--- Comment #9 from François Dumont <fdumont at gcc dot gnu.org> 2010-12-09 21:05:22 UTC ---
testsuite performance suite already show very good results but this test is
rather explicit too. What will perhaps surprise you is that the only
optimization that can explain this difference is in the '++j'.

This operation require the iterator to be incrementable which is checked using
mostly !M_is_end(). This operation used to be performed with the creation of an
internal safe iterator end() resulting in:
- creation/destruction of this safe iterator with the respective
insertion/deletion from the safe iterator list (with mutex locks)
- additional checks when comparing this internal iterator with j.

With the patch the check is done using a normal iterator avoiding all those
operations.