[v3] Fix libstdc++/58358
Paolo Carlini
paolo.carlini@oracle.com
Wed Sep 11 10:04:00 GMT 2013
Hi,
thus we have this conformance issue with the optimized, "skipping",
search_n overloads for random access iterators: in some cases too many
comparisons are performed. We have on the table two different fixes: one
proposed by bug submitter, which actually simplifies what we have got;
another proposed by Chris (Jefferson) which extends the current code to
handle the problem. As you can see in the audit trail, we ran various
tests, we compared code size and performance, and all in all today I'm
going to propose Mitsuru's fix. I ran myself further tests, and I'm
finding that only in some cases, like the existing performance test, it
runs a littler slower of what we have got (but still so much faster of
the overload for forward iterators, our baseline), in other cases, like
iterator.cc in the main testsuite tweaked to TEST_DEPTH 23, I actually
find Mitsuru's solution faster than Chris' on at least a machine (an
i7-980X). Add to this the simplicity of the code, the smaller code size.
I'm attaching below the complete patch I tested on x86_64-linux and I
mean to commit later today. I'm also attaching Chris' code changes
alone, if you want to run your own comparison and give feedback.
Thanks!
Paolo.
PS: Mitsuru doesn't have a Copyright assignment but I think that the
size of the "invention" is small enough, assuming he is not going to
contribute more (and the real size is just half, because the version for
the search_n taking a predicate is conceptually identical)
///////////////////////
-------------- next part --------------
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.
-------------- next part --------------
Index: include/bits/stl_algo.h
===================================================================
--- include/bits/stl_algo.h (revision 202491)
+++ include/bits/stl_algo.h (working copy)
@@ -385,38 +385,23 @@
_DistanceType;
_DistanceType __tailSize = __last - __first;
- const _DistanceType __pattSize = __count;
+ _DistanceType __remainder = __count;
- if (__tailSize < __pattSize)
- return __last;
-
- const _DistanceType __skipOffset = __pattSize - 1;
- _RandomAccessIter __lookAhead = __first + __skipOffset;
- __tailSize -= __pattSize;
-
- while (1) // the main loop...
+ while (__remainder <= __tailSize) // the main loop...
{
- // __lookAhead here is always pointing to the last element of next
- // possible match.
- while (!(*__lookAhead == __val)) // the skip loop...
+ __first += __remainder;
+ __tailSize -= __remainder;
+ // __first here is always pointing to one past the last element of
+ // next possible match.
+ _RandomAccessIter __backTrack = __first;
+ while (*--__backTrack == __val)
{
- if (__tailSize < __pattSize)
- return __last; // Failure
- __lookAhead += __pattSize;
- __tailSize -= __pattSize;
- }
- _DistanceType __remainder = __skipOffset;
- for (_RandomAccessIter __backTrack = __lookAhead - 1;
- *__backTrack == __val; --__backTrack)
- {
if (--__remainder == 0)
- return (__lookAhead - __skipOffset); // Success
+ return (__first - __count); // Success
}
- if (__remainder > __tailSize)
- return __last; // Failure
- __lookAhead += __remainder;
- __tailSize -= __remainder;
+ __remainder = __count + 1 - (__first - __backTrack);
}
+ return __last; // Failure
}
// search_n
@@ -478,38 +463,23 @@
_DistanceType;
_DistanceType __tailSize = __last - __first;
- const _DistanceType __pattSize = __count;
+ _DistanceType __remainder = __count;
- if (__tailSize < __pattSize)
- return __last;
-
- const _DistanceType __skipOffset = __pattSize - 1;
- _RandomAccessIter __lookAhead = __first + __skipOffset;
- __tailSize -= __pattSize;
-
- while (1) // the main loop...
+ while (__remainder <= __tailSize) // the main loop...
{
- // __lookAhead here is always pointing to the last element of next
- // possible match.
- while (!bool(__binary_pred(*__lookAhead, __val))) // the skip loop...
+ __first += __remainder;
+ __tailSize -= __remainder;
+ // __first here is always pointing to one past the last element of
+ // next possible match.
+ _RandomAccessIter __backTrack = __first;
+ while (__binary_pred(*--__backTrack, __val))
{
- if (__tailSize < __pattSize)
- return __last; // Failure
- __lookAhead += __pattSize;
- __tailSize -= __pattSize;
- }
- _DistanceType __remainder = __skipOffset;
- for (_RandomAccessIter __backTrack = __lookAhead - 1;
- __binary_pred(*__backTrack, __val); --__backTrack)
- {
if (--__remainder == 0)
- return (__lookAhead - __skipOffset); // Success
+ return (__first - __count); // Success
}
- if (__remainder > __tailSize)
- return __last; // Failure
- __lookAhead += __remainder;
- __tailSize -= __remainder;
+ __remainder = __count + 1 - (__first - __backTrack);
}
+ return __last; // Failure
}
// find_end for forward iterators.
Index: testsuite/25_algorithms/search_n/58358.cc
===================================================================
--- testsuite/25_algorithms/search_n/58358.cc (revision 0)
+++ testsuite/25_algorithms/search_n/58358.cc (working copy)
@@ -0,0 +1,41 @@
+// Copyright (C) 2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=gnu++11" }
+
+// 25.1.9 [lib.alg.search]
+
+#include <algorithm>
+#include <vector>
+#include <testsuite_hooks.h>
+
+void test01()
+{
+ bool test __attribute__((unused)) = true;
+
+ std::vector<int> a{2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
+ int count = 0;
+ std::search_n(a.begin(), a.end(), 10, 1,
+ [&count](int t, int u) { ++count; return t == u; });
+ VERIFY( count <= 11 );
+}
+
+int main()
+{
+ test01();
+ return 0;
+}
Index: testsuite/25_algorithms/search_n/iterator.cc
===================================================================
--- testsuite/25_algorithms/search_n/iterator.cc (revision 202491)
+++ testsuite/25_algorithms/search_n/iterator.cc (working copy)
@@ -31,9 +31,11 @@
int array1[11] = {0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0};
int array2[TEST_DEPTH];
+int pred_count;
bool
pred(int i, int j)
{
+ ++pred_count;
return i == j;
}
@@ -90,16 +92,22 @@
int* t1 = search_n(forwardcon.begin(),
forwardcon.end(), j, 1).ptr;
+ pred_count = 0;
int* t2 = search_n(forwardcon.begin(),
forwardcon.end(), j, 1, pred).ptr;
+ VERIFY(pred_count <= i);
int* t3 = search_n(bidircon.begin(),
bidircon.end(), j, 1).ptr;
+ pred_count = 0;
int* t4 = search_n(bidircon.begin(),
bidircon.end(), j, 1, pred).ptr;
+ VERIFY(pred_count <= i);
int* t5 = search_n(randomcon.begin(),
randomcon.end(), j, 1).ptr;
+ pred_count = 0;
int* t6 = search_n(randomcon.begin(),
randomcon.end(), j, 1, pred).ptr;
+ VERIFY(pred_count <= i);
VERIFY((t1 == t2) && (t2 == t3) && (t3 == t4) &&
(t4 == t5) && (t5 == t6));
}
More information about the Libstdc++
mailing list