[Bug libstdc++/58358] search_n has a Complexity violation for random access iterator

[Bug libstdc++/58358] search_n has a Complexity violation for random access iterator

[glisse at gcc dot gnu.org]

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

Marc Glisse <glisse at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2013-09-08
     Ever confirmed|0                           |1

--- Comment #1 from Marc Glisse <glisse at gcc dot gnu.org> ---
The indexes of the values that are tested:
9 8 7 6 5 4 3 2 1 0 10 9 8 7 6 5 4 3 2 1

It starts well, first checking 9 because if that one fails we can skip testing
0-8. The backtrack is normal. Once the backtracking fails, the code jumps to a
sensible place (so that backtracking will go precisely to the last place before
we failed) but it forgets that it has already tested many of those values.

[Bug libstdc++/58358] search_n has a Complexity violation for random access iterator

[paolo.carlini at oracle dot com]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |chris at bubblescope dot net

--- Comment #2 from Paolo Carlini <paolo.carlini at oracle dot com> ---
This isn't the original HP/SGI algorithm, and was supposed to be an
optimization, probably often is, but we can't violate the requirements so
easily. Luckily Chris is around, let's ask him to look into this.

[Bug libstdc++/58358] [4.7/4.8/4.9 Regression] search_n has a Complexity violation for random access iterator

[paolo.carlini at oracle dot com]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|search_n has a Complexity   |[4.7/4.8/4.9 Regression]
                   |violation for random access |search_n has a Complexity
                   |iterator                    |violation for random access
                   |                            |iterator

--- Comment #3 from Paolo Carlini <paolo.carlini at oracle dot com> ---
And this is a regression, old but still a regression. If we can't fix the new
algorithm easily enough, we may have to return to the old one.

[Bug libstdc++/58358] [4.7/4.8/4.9 Regression] search_n has a Complexity violation for random access iterator

[chris at bubblescope dot net]

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

--- Comment #4 from Chris Jefferson <chris at bubblescope dot net> ---
Just to say I see this, and fortunately it's not hard to keep the optimisation
and meet the complexity requirements.

Expect patch later today.

[Bug libstdc++/58358] [4.7/4.8/4.9 Regression] search_n has a Complexity violation for random access iterator

[paolo.carlini at oracle dot com]

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

--- Comment #5 from Paolo Carlini <paolo.carlini at oracle dot com> ---
Great, thanks Chris.

[Bug libstdc++/58358] [4.7/4.8/4.9 Regression] search_n has a Complexity violation for random access iterator

[chris at bubblescope dot net]

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

--- Comment #6 from Chris Jefferson <chris at bubblescope dot net> ---
I have a patch I believe fixes this, but trunk doesn't currently build on my
machine (Bug 58340). I'll wait for that to get fixed.

It is annoying there is still separate predicate and non-predicate copies of
every function.

[Bug libstdc++/58358] [4.7/4.8/4.9 Regression] search_n has a Complexity violation for random access iterator

[paolo.carlini at oracle dot com]

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

--- Comment #7 from Paolo Carlini <paolo.carlini at oracle dot com> ---
Yes, bootstrap is known to be broken, you can do:

  update -r202295 tree-ssa-threadedge.c

[Bug libstdc++/58358] [4.7/4.8/4.9 Regression] search_n has a Complexity violation for random access iterator

[paolo.carlini at oracle dot com]

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

--- Comment #8 from Paolo Carlini <paolo.carlini at oracle dot com> ---
About the duplication, you may want to review what Francois posted to the
mailing list a few days ago and send your comments. Personally, I agree it
would be very nice to avoid the duplication, but at the same time when I
discussed the topic with Howard a few years ago he explained that there are
some tricky details, in particular vs proxy-iterators, we want to be really
sure that nothing breaks vs those, the "natural" idea of using std::less & co
doesn't work, a beefed up version is required (this is horrible IMHO, but we
may have to live with it). Again, if you are interested, please have a look to
that patch. Thanks!

[Bug libstdc++/58358] [4.7/4.8/4.9 Regression] search_n has a Complexity violation for random access iterator

[daniel.kruegler at googlemail dot com]

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

--- Comment #9 from Daniel Krügler <daniel.kruegler at googlemail dot com> ---
(In reply to Paolo Carlini from comment #8)
> About the duplication, you may want to review what Francois posted to the
> mailing list a few days ago and send your comments. Personally, I agree it
> would be very nice to avoid the duplication, but at the same time when I
> discussed the topic with Howard a few years ago he explained that there are
> some tricky details, in particular vs proxy-iterators, we want to be really
> sure that nothing breaks vs those, the "natural" idea of using std::less &
> co doesn't work, a beefed up version is required (this is horrible IMHO, but
> we may have to live with it).

Shouldn't the library be able to use the new diamond operators (specializations
in void) that use perfect forwarding for both arguments and result? User-code
cannot specialize these operations.
>From gcc-bugs-return-429262-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Sun Sep 08 14:25:21 2013
Return-Path: <gcc-bugs-return-429262-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 28205 invoked by alias); 8 Sep 2013 14:25:21 -0000
Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <gcc-bugs.gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-help@gcc.gnu.org>
Sender: gcc-bugs-owner@gcc.gnu.org
Delivered-To: mailing list gcc-bugs@gcc.gnu.org
Received: (qmail 27732 invoked by uid 55); 8 Sep 2013 14:25:16 -0000
From: "hubicka at ucw dot cz" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug bootstrap/58340] [4.9 regression] gcc/cp/pt.c:7064:1: internal compiler error: in propagate_threaded_block_debug_into, at tree-ssa-threadedge.c:623
Date: Sun, 08 Sep 2013 14:25:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: bootstrap
X-Bugzilla-Version: 4.9.0
X-Bugzilla-Keywords:
X-Bugzilla-Severity: blocker
X-Bugzilla-Who: hubicka at ucw dot cz
X-Bugzilla-Status: NEW
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org
X-Bugzilla-Target-Milestone: 4.9.0
X-Bugzilla-Flags:
X-Bugzilla-Changed-Fields:
Message-ID: <bug-58340-4-S7GutN3cDi@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-58340-4@http.gcc.gnu.org/bugzilla/>
References: <bug-58340-4@http.gcc.gnu.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 7bit
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
X-SW-Source: 2013-09/txt/msg00502.txt.bz2
Content-length: 973

http://gcc.gnu.org/bugzilla/show_bug.cgi?idX340

--- Comment #14 from Jan Hubicka <hubicka at ucw dot cz> ---
I use the following workaround for time being.

Honza

Index: tree-ssa-threadedge.c
==================================================================--- tree-ssa-threadedge.c    (revision 202364)
+++ tree-ssa-threadedge.c    (working copy)
@@ -1015,8 +1015,9 @@ thread_across_edge (gimple dummy_cond,
         tmp = find_edge (taken_edge->src, path[path.length () - 1]->dest);
         if (!tmp || phi_args_equal_on_edges (tmp, path[path.length () - 1]))
           {
-        propagate_threaded_block_debug_into (path[path.length () - 1]->dest,
-                             taken_edge->dest);
+        if (path[path.length () - 1]->dest != taken_edge->dest)
+          propagate_threaded_block_debug_into (path[path.length () - 1]->dest,
+                               taken_edge->dest);
         register_jump_thread (path, true);
           }
       }

[Bug libstdc++/58358] [4.7/4.8/4.9 Regression] search_n has a Complexity violation for random access iterator

[paolo.carlini at oracle dot com]

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

--- Comment #10 from Paolo Carlini <paolo.carlini at oracle dot com> ---
Daniel, please send your comment to the mailing list, Francois wants to know.
In any case, note that we want to have something for C++98 too, otherwise we
can't really remove the duplicates. Or maybe those aren't *that* new, sorry I'm
in the middle of too many other things ;)

Anyway, this discussion is off topic here.

[Bug libstdc++/58358] [4.7/4.8/4.9 Regression] search_n has a Complexity violation for random access iterator

[glisse at gcc dot gnu.org]

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

--- Comment #11 from Marc Glisse <glisse at gcc dot gnu.org> ---
(In reply to Daniel Krügler from comment #9)
> Shouldn't the library be able to use the new diamond operators
> (specializations in void) that use perfect forwarding for both arguments and
> result? User-code cannot specialize these operations.

Perfect forwarding was never perfect, I wish that name hadn't stuck.

http://gcc.gnu.org/ml/libstdc++/2012-06/msg00066.html
>From gcc-bugs-return-429268-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Sun Sep 08 15:34:06 2013
Return-Path: <gcc-bugs-return-429268-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 31472 invoked by alias); 8 Sep 2013 15:34:04 -0000
Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <gcc-bugs.gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-help@gcc.gnu.org>
Sender: gcc-bugs-owner@gcc.gnu.org
Delivered-To: mailing list gcc-bugs@gcc.gnu.org
Received: (qmail 31430 invoked by uid 48); 8 Sep 2013 15:33:59 -0000
From: "paolo.carlini at oracle dot com" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug c++/58362] Wrong column number for unused parameter
Date: Sun, 08 Sep 2013 15:34:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: c++
X-Bugzilla-Version: 4.9.0
X-Bugzilla-Keywords: diagnostic
X-Bugzilla-Severity: normal
X-Bugzilla-Who: paolo.carlini at oracle dot com
X-Bugzilla-Status: UNCONFIRMED
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org
X-Bugzilla-Target-Milestone: ---
X-Bugzilla-Flags:
X-Bugzilla-Changed-Fields:
Message-ID: <bug-58362-4-iQGUCF8tfQ@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-58362-4@http.gcc.gnu.org/bugzilla/>
References: <bug-58362-4@http.gcc.gnu.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 7bit
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
X-SW-Source: 2013-09/txt/msg00508.txt.bz2
Content-length: 195

http://gcc.gnu.org/bugzilla/show_bug.cgi?idX362

--- Comment #4 from Paolo Carlini <paolo.carlini at oracle dot com> ---
The damage happens at error.c:3435. Should we just use "%qD", no '+' ?

[Bug libstdc++/58358] [4.7/4.8/4.9 Regression] search_n has a Complexity violation for random access iterator

[chris at bubblescope dot net]

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

--- Comment #13 from Chris Jefferson <chris at bubblescope dot net> ---
Created attachment 30767
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=30767&action=edit
Bug patch

Patch attached.

This features:

1) As well as checking backwards when we find a match, check forwards too.
Improve so we never do more than n checks in an array of size n.

2) Improve the existing tester (which tries all arrays up to length 15) to
check the number of predicate calls.

3) Add the test included in this bug as a new test, just for completeness.

[Bug libstdc++/58358] [4.7/4.8/4.9 Regression] search_n has a Complexity violation for random access iterator

[chris at bubblescope dot net]

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

--- Comment #14 from Chris Jefferson <chris at bubblescope dot net> ---
(In reply to Marc Glisse from comment #12)
> Chris, did you consider applying this optimized code to bidirectional
> iterators and not just random access iterators? We may end up doing a few
> more ++/-- than necessary, but not by more than a factor 2 I believe, and we
> would often save many calls to the predicate. Something may also be doable
> for forward iterators, but that's more complicated for less gain and
> couldn't share the same code.

I considered this, but as you say this would slow things down in some cases,
and I've found bugs which cause slowdowns in any situation tend to have serious
problems getting accepted.

[Bug libstdc++/58358] [4.7/4.8/4.9 Regression] search_n has a Complexity violation for random access iterator

[kariya_mitsuru at hotmail dot com]

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

--- Comment #15 from Mitsuru Kariya <kariya_mitsuru at hotmail dot com> ---
Created attachment 30775
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=30775&action=edit
Patch

For your convenience, I attached a patch for this problem.

This algorithm is always scanned to reverse order.
If a scan fails in less than enough, a re-scan is performed from the point that
advanced necessary elements from the original starting point.

For example, if __count is 20 and a scan fails after 18 elements succeeded, a
re-scan is performed from the point that advanced 2 elements.

[Bug libstdc++/58358] [4.7/4.8/4.9 Regression] search_n has a Complexity violation for random access iterator

[paolo.carlini at oracle dot com]

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

--- Comment #16 from Paolo Carlini <paolo.carlini at oracle dot com> ---
Thanks Chris, but I almost missed the patch. Please send it to the mailing
list, thanks!

[Bug libstdc++/58358] [4.7/4.8/4.9 Regression] search_n has a Complexity violation for random access iterator

[paolo.carlini at oracle dot com]

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

--- Comment #17 from Paolo Carlini <paolo.carlini at oracle dot com> ---
Two nits: in the new testcase, remember to declare the test variable. Also, we
are standardizing on -std=gnu++11.

[Bug libstdc++/58358] [4.7/4.8/4.9 Regression] search_n has a Complexity violation for random access iterator

[paolo.carlini at oracle dot com]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |paolo.carlini at oracle dot com

--- Comment #18 from Paolo Carlini <paolo.carlini at oracle dot com> ---
Chris, I'm going to slightly tweak / test again locally / post to the mailing
list your patch in order to apply it. Please have a look to Comment #15, in the
meanwhile, thanks!

[Bug libstdc++/58358] [4.7/4.8/4.9 Regression] search_n has a Complexity violation for random access iterator

[chris at bubblescope dot net]

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

--- Comment #19 from Chris Jefferson <chris at bubblescope dot net> ---
(In reply to Mitsuru Kariya from comment #15)
> Created attachment 30775 [details]
> Patch
> 
> For your convenience, I attached a patch for this problem.
> 
> This algorithm is always scanned to reverse order.
> If a scan fails in less than enough, a re-scan is performed from the point
> that advanced necessary elements from the original starting point.
> 
> For example, if __count is 20 and a scan fails after 18 elements succeeded,
> a re-scan is performed from the point that advanced 2 elements.

This patch is good, but takes a different route., trying to always skip as far
forwards as possible. On a small test (compiling the 'search_n/iterator.cc'
test, disabling forward checking and bidirection tests, increasing TEST_DEPTH
to 23, compiling -O3):

Both implementations pass correctness and number of comparison tests.

Mitsuru's code is about 1K smaller.

My code is slightly faster (3.74sec vs 4.12sec)

I think I might choose Mitsuru's code, as his code is smaller in terms of both
source and binary, and the performance difference is not that big, but either
would be fine.

[Bug libstdc++/58358] [4.7/4.8/4.9 Regression] search_n has a Complexity violation for random access iterator

[paolo.carlini at oracle dot com]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|minor                       |normal

--- Comment #20 from Paolo Carlini <paolo.carlini at oracle dot com> ---
I see, thanks Chris. Don't you have the performance numbers for the baseline,
"naive" code, do you? To put in better perspective 3.74secs vs 4.12secs. Like,
if the baseline is 1 or 3.5 isn't the same!

In fact, I also like Mitsuru' patch, it's simplicity in particular. But again,
I would not choose it if the baseline is 3.5secs.

[Bug libstdc++/58358] [4.7/4.8/4.9 Regression] search_n has a Complexity violation for random access iterator

[paolo.carlini at oracle dot com]

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

--- Comment #21 from Paolo Carlini <paolo.carlini at oracle dot com> ---
Sorry. Take my 1sec and 3.5secs, as, say, 4.5secs and 20secs. You see may
point.

[Bug libstdc++/58358] [4.7/4.8/4.9 Regression] search_n has a Complexity violation for random access iterator

[chris at bubblescope dot net]

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

--- Comment #22 from Chris Jefferson <chris at bubblescope dot net> ---
Her are some comparisons. Just to compare, I also checked doing away with
skipping optimisations altogether. Binary sizes (-O3, stripped)


current head: 11928
my code:      12248
Mitsuru:      11384
No skip:      10904

Timing:

current head: 3.70
my code:      3.70
Mitsuru:      4.04
No skip:     15.37

So we clearly want to do skipping. The tradeoff is between same speed and
bigger executables (my code) or ~10% slower but saving 1K or so binary and some
source (Mitsuru's code). I don't know what gcc/libstdc++'s general direction in
that area is.

I actually would expect Mitsuru's code to be faster (as it tries harder to skip
forwards), but it is hard to predict how these things interact with
optimisers/caches/branch predictors at a low level.

[Bug libstdc++/58358] [4.7/4.8/4.9 Regression] search_n has a Complexity violation for random access iterator

[paolo.carlini at oracle dot com]

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

--- Comment #23 from Paolo Carlini <paolo.carlini at oracle dot com> ---
Thanks a lot Chris. Sorry if I bother you for a few minutes more: when you say
"doing away with skipping optimizations altogether", you mean, essentially,
using the algorithm we have got now for forward iterators? Which is also, if I
remember correctly, what we had earlier for random access iterators too? 

In that case, I'm really unsure: I'm tempted by what Mitsuru is proposing, but
I'm not 100% sure, not because of the 10% difference, but more importantly
because we know well what we have got, nobody complained for so many years, and
your change would be only a small tweak of it. Also, I know you are around to
maintain it, which isn't a minor detail! In case, would you be willing to
maintain Mitsuru's code too? Eventually, I think I will send both patches to
the mailing list with my personal opinion, and I will ask.

[Bug libstdc++/58358] [4.7/4.8/4.9 Regression] search_n has a Complexity violation for random access iterator

[paolo at gcc dot gnu.org]

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

--- Comment #24 from paolo at gcc dot gnu.org <paolo at gcc dot gnu.org> ---
Author: paolo
Date: Wed Sep 11 22:24:50 2013
New Revision: 202510

URL: http://gcc.gnu.org/viewcvs?rev=202510&root=gcc&view=rev
Log:
2013-09-11  Mitsuru Kariya  <kariya_mitsuru@hotmail.com>
        Chris Jefferson  <chris@bubblescope.net>

    PR libstdc++/58358
    * include/bits/stl_algo.h (search_n): Fix to guarantee a number
    of comparisons <= number of elements in the range.
    * testsuite/25_algorithms/search_n/58358.cc: New.
    * testsuite/25_algorithms/search_n/iterator.cc: Extend.

Added:
    trunk/libstdc++-v3/testsuite/25_algorithms/search_n/58358.cc
Modified:
    trunk/libstdc++-v3/ChangeLog
    trunk/libstdc++-v3/include/bits/stl_algo.h
    trunk/libstdc++-v3/testsuite/25_algorithms/search_n/iterator.cc

[Bug libstdc++/58358] [4.7/4.8 Regression] search_n has a Complexity violation for random access iterator

[paolo.carlini at oracle dot com]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|[4.7/4.8/4.9 Regression]    |[4.7/4.8 Regression]
                   |search_n has a Complexity   |search_n has a Complexity
                   |violation for random access |violation for random access
                   |iterator                    |iterator

--- Comment #25 from Paolo Carlini <paolo.carlini at oracle dot com> ---
Fixed in mainline so far.

[Bug libstdc++/58358] [4.7/4.8 Regression] search_n has a Complexity violation for random access iterator

[paolo at gcc dot gnu.org]

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

--- Comment #26 from paolo at gcc dot gnu.org <paolo at gcc dot gnu.org> ---
Author: paolo
Date: Thu Sep 19 10:19:58 2013
New Revision: 202736

URL: http://gcc.gnu.org/viewcvs?rev=202736&root=gcc&view=rev
Log:
2013-09-19  Mitsuru Kariya  <kariya_mitsuru@hotmail.com>
        Chris Jefferson  <chris@bubblescope.net>

    PR libstdc++/58358
    * include/bits/stl_algo.h (search_n): Fix to guarantee a number
    of comparisons <= number of elements in the range.
    * testsuite/25_algorithms/search_n/58358.cc: New.
    * testsuite/25_algorithms/search_n/iterator.cc: Extend.

Added:
   
branches/gcc-4_8-branch/libstdc++-v3/testsuite/25_algorithms/search_n/58358.cc
Modified:
    branches/gcc-4_8-branch/libstdc++-v3/ChangeLog
    branches/gcc-4_8-branch/libstdc++-v3/include/bits/stl_algo.h
   
branches/gcc-4_8-branch/libstdc++-v3/testsuite/25_algorithms/search_n/iterator.cc

[Bug libstdc++/58358] [4.7 Regression] search_n has a Complexity violation for random access iterator

[paolo.carlini at oracle dot com]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
            Version|4.8.1                       |4.8.2
         Resolution|---                         |FIXED
            Summary|[4.7/4.8 Regression]        |[4.7 Regression] search_n
                   |search_n has a Complexity   |has a Complexity violation
                   |violation for random access |for random access iterator
                   |iterator                    |

--- Comment #27 from Paolo Carlini <paolo.carlini at oracle dot com> ---
Fixed for 4.8.2 too. WONTFIX in 4.7.x.