Re: [Bug libstdc++/61107] stl_algo.h: std::__inplace_stable_partition() doesn't process the whole data range
I did suggest this change, so I feel I should defend it! Our testing of many algorithms is woefully slim, that is how (for example) the segfaulting bug in std::nth_element got through into a release -- the tests for that algorithm were terrible, and basically didn't test the functionality on enough possible inputs. I consider a series of random inputs to be a good practical way of getting decent code coverage and perform a basic sanity test, without the need for an excessive amount of coding. While these tests aren't showing anything yet, a) We didn't know that until after they were written and executed, and: b) They might help catch problems in future, particular in other algorithms changing underlying functionality. I recently added a set of similar tests for a number of algorithms. If you have an alternative suggestion for better testing I'd be happy to hear it, but I think the algorithms need something beyond just one or two hardwired inputs. Chris On 10 November 2014 22:20, Jonathan Wakely jwak...@redhat.com wrote: On 10/11/14 23:14 +0100, François Dumont wrote: I introduced the random tests after Christopher Jefferson request to have more intensive tests on those algos. Is it the whole stuff of tests using random numbers that you don't like or just the usage of mt19937 ? The use of random number in general. If second is this new version using the usual random_device I used so far better ? That would be much worse because failures would not be reproducible! If it is the whole usage of random numbers that you don't like I will simply get rid of the new tests files. Did the new tests fail before your fix to stl_algo.h? If yes, you could extract the values generated in the case that fails and add a test using those values (this is what I should have done for the leaking set tests) If no, they aren't really testing anything useful.
Re: [Bug libstdc++/61107] stl_algo.h: std::__inplace_stable_partition() doesn't process the whole data range
On 12/11/14 14:56 +, Christopher Jefferson wrote: I did suggest this change, so I feel I should defend it! Our testing of many algorithms is woefully slim, that is how (for example) the segfaulting bug in std::nth_element got through into a release -- the tests for that algorithm were terrible, and basically didn't test the functionality on enough possible inputs. I consider a series of random inputs to be a good practical way of getting decent code coverage and perform a basic sanity test, without the need for an excessive amount of coding. While these tests aren't showing anything yet, a) We didn't know that until after they were written and executed, and: b) They might help catch problems in future, particular in other algorithms changing underlying functionality. I recently added a set of similar tests for a number of algorithms. If you have an alternative suggestion for better testing I'd be happy to hear it, but I think the algorithms need something beyond just one or two hardwired inputs. OK, that makes sense. Testing sorting algorithms is *hard* because the edge cases are not obvious so it's difficult to craft input that is known to stress the possible failures. But if we're going to use random numbers then we should definitely not use std::random_device (or we'll get truly random failures that are very hard to reproduce) and I'd like to see more iterations with the PRNG than just for (int i = 0; i 10; ++i), because otherwise it *is* just ten hardwired inputs (albeit with up to 1000 elements per iteration), because the PRNG is deterministic. (Again, my reproducer for the std::set memory leaks used 10 rounds with a PRNG because I was lazy and just wanted to demonstrate there was still a bug, not because I thought that was a good test.) We could use std::random_device to seed the PRNG iff we print the seed to the logs, so the test can be easily run again with the same seed. That would avoid testing the exact same data on every run, while still being reproducable. I think it's best to avoid std::random_device though. If we test more than 10 rounds, the number should be configurable so it can be overriden on simulators using a -D option in the dg-options. So Chris, if you think the new test adds value then I'm OK with it being added. I reserve the right to remain sceptical about just throwing random numbers at the sorting algos though. I'd prefer to see something more methodical, like taking several permutations of a fixed input and verifying that it is always sorted correctly; verifying that sorting it twice does nothing (e.g. do we have tests that stable_sort on a sorted range doesn't ever try to swap elements? or that elements that are swapped are not equivalent?); sorting a range that is composed of sorted subranges (1,2,3,1,3,5,2,4,6,1,3,6) and that sort of thing. But sorting algorithms are not my strong point, and if I'm not going to write those tests myself I have no right to complain! :-)
Re: [Bug libstdc++/61107] stl_algo.h: std::__inplace_stable_partition() doesn't process the whole data range
On 10/11/14 21:50 +0100, François Dumont wrote: Any news about this one ? Here is another version with additional random tests on algos just to challenge other combinations of tests. PR libstdc++/61107 * include/bits/stl_algo.h (__inplace_stable_partition): Delete. (__stable_partition_adaptive): Return __first is range length is 1. The first is should be if. The change to stl_algo.h looks OK. I don't like the use of mt19937 in the tests, I know you committed a test I wrote recently that uses mt19937, but that was only meant to demonstrate the bug for bugzilla, not necessarily as the final test. The PRNG produces the exact same sequence of numbers every time (when you don't seed it) so if you can make the test fail using a few iterations with the PRNG then you can find the input that fails and just add that input to the testsuite. I didn't do that for the test I put in bugzilla because I didn't have time to work out which input caused the memory leak, only that it leaked for *some* easily reproducible input. I wasn't trying to start a trend where we use fixed sequences of pseudorandom numbers in lots of tests.
Re: [Bug libstdc++/61107] stl_algo.h: std::__inplace_stable_partition() doesn't process the whole data range
I introduced the random tests after Christopher Jefferson request
to have more intensive tests on those algos. Is it the whole stuff of
tests using random numbers that you don't like or just the usage of
mt19937 ? If second is this new version using the usual random_device I
used so far better ?
If it is the whole usage of random numbers that you don't like I will
simply get rid of the new tests files.
François
On 10/11/2014 22:45, Jonathan Wakely wrote:
On 10/11/14 21:50 +0100, François Dumont wrote:
Any news about this one ?
Here is another version with additional random tests on algos just to
challenge other combinations of tests.
PR libstdc++/61107
* include/bits/stl_algo.h (__inplace_stable_partition): Delete.
(__stable_partition_adaptive): Return __first is range length is 1.
The first is should be if.
The change to stl_algo.h looks OK.
I don't like the use of mt19937 in the tests, I know you committed a
test I wrote recently that uses mt19937, but that was only meant to
demonstrate the bug for bugzilla, not necessarily as the final test.
The PRNG produces the exact same sequence of numbers every time (when
you don't seed it) so if you can make the test fail using a few
iterations with the PRNG then you can find the input that fails and
just add that input to the testsuite. I didn't do that for the test I
put in bugzilla because I didn't have time to work out which input
caused the memory leak, only that it leaked for *some* easily
reproducible input. I wasn't trying to start a trend where we use
fixed sequences of pseudorandom numbers in lots of tests.
Index: include/bits/stl_algo.h
===
--- include/bits/stl_algo.h (revision 217320)
+++ include/bits/stl_algo.h (working copy)
@@ -1512,34 +1512,6 @@
// partition
/// This is a helper function...
- /// Requires __len != 0 and !__pred(*__first),
- /// same as __stable_partition_adaptive.
- templatetypename _ForwardIterator, typename _Predicate, typename _Distance
-_ForwardIterator
-__inplace_stable_partition(_ForwardIterator __first,
- _Predicate __pred, _Distance __len)
-{
- if (__len == 1)
- return __first;
- _ForwardIterator __middle = __first;
- std::advance(__middle, __len / 2);
- _ForwardIterator __left_split =
- std::__inplace_stable_partition(__first, __pred, __len / 2);
- // Advance past true-predicate values to satisfy this
- // function's preconditions.
- _Distance __right_len = __len - __len / 2;
- _ForwardIterator __right_split =
- std::__find_if_not_n(__middle, __right_len, __pred);
- if (__right_len)
- __right_split = std::__inplace_stable_partition(__middle,
- __pred,
- __right_len);
- std::rotate(__left_split, __middle, __right_split);
- std::advance(__left_split, std::distance(__middle, __right_split));
- return __left_split;
-}
-
- /// This is a helper function...
/// Requires __first != __last and !__pred(__first)
/// and __len == distance(__first, __last).
///
@@ -1554,10 +1526,14 @@
_Pointer __buffer,
_Distance __buffer_size)
{
+ if (__len == 1)
+ return __first;
+
if (__len = __buffer_size)
{
_ForwardIterator __result1 = __first;
_Pointer __result2 = __buffer;
+
// The precondition guarantees that !__pred(__first), so
// move that element to the buffer before starting the loop.
// This ensures that we only call __pred once per element.
@@ -1575,31 +1551,33 @@
*__result2 = _GLIBCXX_MOVE(*__first);
++__result2;
}
+
_GLIBCXX_MOVE3(__buffer, __result2, __result1);
return __result1;
}
- else
- {
- _ForwardIterator __middle = __first;
- std::advance(__middle, __len / 2);
- _ForwardIterator __left_split =
- std::__stable_partition_adaptive(__first, __middle, __pred,
- __len / 2, __buffer,
- __buffer_size);
- // Advance past true-predicate values to satisfy this
- // function's preconditions.
- _Distance __right_len = __len - __len / 2;
- _ForwardIterator __right_split =
- std::__find_if_not_n(__middle, __right_len, __pred);
- if (__right_len)
- __right_split =
- std::__stable_partition_adaptive(__right_split, __last, __pred,
- __right_len,
- __buffer, __buffer_size);
- std::rotate(__left_split, __middle, __right_split);
- std::advance(__left_split, std::distance(__middle, __right_split));
- return __left_split;
- }
+
+ _ForwardIterator __middle = __first;
+ std::advance(__middle, __len / 2);
+ _ForwardIterator __left_split =
+ std::__stable_partition_adaptive(__first, __middle, __pred,
+ __len / 2, __buffer,
+ __buffer_size);
+
+ // Advance past true-predicate values to satisfy this
+ // function's preconditions.
+ _Distance __right_len = __len - __len / 2;
+ _ForwardIterator __right_split =
+ std::__find_if_not_n(__middle,
Re: [Bug libstdc++/61107] stl_algo.h: std::__inplace_stable_partition() doesn't process the whole data range
On 10/11/14 23:14 +0100, François Dumont wrote: I introduced the random tests after Christopher Jefferson request to have more intensive tests on those algos. Is it the whole stuff of tests using random numbers that you don't like or just the usage of mt19937 ? The use of random number in general. If second is this new version using the usual random_device I used so far better ? That would be much worse because failures would not be reproducible! If it is the whole usage of random numbers that you don't like I will simply get rid of the new tests files. Did the new tests fail before your fix to stl_algo.h? If yes, you could extract the values generated in the case that fails and add a test using those values (this is what I should have done for the leaking set tests) If no, they aren't really testing anything useful.
Re: [Bug libstdc++/61107] stl_algo.h: std::__inplace_stable_partition() doesn't process the whole data range
No the random tests didn't show any problem. I had demonstrated the problems with the modifications on the existing tests simulating constraint memory context. So unless specified otherwise I will commit tomorrow without the tests using random numbers. François On 10/11/2014 23:20, Jonathan Wakely wrote: On 10/11/14 23:14 +0100, François Dumont wrote: I introduced the random tests after Christopher Jefferson request to have more intensive tests on those algos. Is it the whole stuff of tests using random numbers that you don't like or just the usage of mt19937 ? The use of random number in general. If second is this new version using the usual random_device I used so far better ? That would be much worse because failures would not be reproducible! If it is the whole usage of random numbers that you don't like I will simply get rid of the new tests files. Did the new tests fail before your fix to stl_algo.h? If yes, you could extract the values generated in the case that fails and add a test using those values (this is what I should have done for the leaking set tests) If no, they aren't really testing anything useful.
Re: [Bug libstdc++/61107] stl_algo.h: std::__inplace_stable_partition() doesn't process the whole data range
On 10/11/14 23:39 +0100, François Dumont wrote: No the random tests didn't show any problem. I had demonstrated the problems with the modifications on the existing tests simulating constraint memory context. So unless specified otherwise I will commit tomorrow without the tests using random numbers. OK, thanks.
Re: [Bug libstdc++/61107] stl_algo.h: std::__inplace_stable_partition() doesn't process the whole data range
Any news about this one ?
Here is another version with additional random tests on algos just to
challenge other combinations of tests.
PR libstdc++/61107
* include/bits/stl_algo.h (__inplace_stable_partition): Delete.
(__stable_partition_adaptive): Return __first is range length is 1.
(__stable_partition): Adapt.
* testsuite/util/testsuite_new_operators.h: New.
* testsuite/25_algorithms/stable_sort/1.cc: Test algo in simulated
constraint memory context.
* testsuite/25_algorithms/inplace_merge/1.cc: Likewise.
* testsuite/25_algorithms/stable_partition/1.cc: Likewise.
* testsuite/25_algorithms/stable_sort/4.cc: New.
* testsuite/25_algorithms/inplace_merge/2.cc: New.
* testsuite/25_algorithms/stable_partition/2.cc: New.
Ok to commit ?
François
On 17/10/2014 22:46, François Dumont wrote:
Hi
As proposed in the bug report I just removed the
__inplace_stable_partition as __stable_partition_adaptive is able to
handle a 0 buffer size.
To test this bug I introduced overloads of new/delete operators in
the testsuite utils. The existing set_memory_limits has no impact on
new operator. I wonder if some test using it really have the expected
behavior.
I also tests other algos that try to use a buffer and didn't found
any issue. Those algos however can't be simplified like stable_partition.
2014-10-16 François Dumont fdum...@gcc.gnu.org
PR libstdc++/61107
* include/bits/stl_algo.h (__inplace_stable_partition): Delete.
(__stable_partition): Adapt.
* testsuite/util/testsuite_new_operators.h: New.
* testsuite/25_algorithms/stable_sort/1.cc: Test algo in simulated
constraint memory context.
* testsuite/25_algorithms/inplace_merge/1.cc: Likewise.
* testsuite/25_algorithms/stable_partition/1.cc: Likewise.
Tested under Linux x86_64.
Ok to commit ?
François
Index: include/bits/stl_algo.h
===
--- include/bits/stl_algo.h (revision 217160)
+++ include/bits/stl_algo.h (working copy)
@@ -1512,34 +1512,6 @@
// partition
/// This is a helper function...
- /// Requires __len != 0 and !__pred(*__first),
- /// same as __stable_partition_adaptive.
- templatetypename _ForwardIterator, typename _Predicate, typename _Distance
-_ForwardIterator
-__inplace_stable_partition(_ForwardIterator __first,
- _Predicate __pred, _Distance __len)
-{
- if (__len == 1)
- return __first;
- _ForwardIterator __middle = __first;
- std::advance(__middle, __len / 2);
- _ForwardIterator __left_split =
- std::__inplace_stable_partition(__first, __pred, __len / 2);
- // Advance past true-predicate values to satisfy this
- // function's preconditions.
- _Distance __right_len = __len - __len / 2;
- _ForwardIterator __right_split =
- std::__find_if_not_n(__middle, __right_len, __pred);
- if (__right_len)
- __right_split = std::__inplace_stable_partition(__middle,
- __pred,
- __right_len);
- std::rotate(__left_split, __middle, __right_split);
- std::advance(__left_split, std::distance(__middle, __right_split));
- return __left_split;
-}
-
- /// This is a helper function...
/// Requires __first != __last and !__pred(__first)
/// and __len == distance(__first, __last).
///
@@ -1554,10 +1526,14 @@
_Pointer __buffer,
_Distance __buffer_size)
{
+ if (__len == 1)
+ return __first;
+
if (__len = __buffer_size)
{
_ForwardIterator __result1 = __first;
_Pointer __result2 = __buffer;
+
// The precondition guarantees that !__pred(__first), so
// move that element to the buffer before starting the loop.
// This ensures that we only call __pred once per element.
@@ -1575,11 +1551,11 @@
*__result2 = _GLIBCXX_MOVE(*__first);
++__result2;
}
+
_GLIBCXX_MOVE3(__buffer, __result2, __result1);
return __result1;
}
- else
- {
+
_ForwardIterator __middle = __first;
std::advance(__middle, __len / 2);
_ForwardIterator __left_split =
@@ -1586,21 +1562,23 @@
std::__stable_partition_adaptive(__first, __middle, __pred,
__len / 2, __buffer,
__buffer_size);
+
// Advance past true-predicate values to satisfy this
// function's preconditions.
_Distance __right_len = __len - __len / 2;
_ForwardIterator __right_split =
std::__find_if_not_n(__middle, __right_len, __pred);
+
if (__right_len)
__right_split =
std::__stable_partition_adaptive(__right_split, __last, __pred,
__right_len,
__buffer, __buffer_size);
+
std::rotate(__left_split, __middle, __right_split);
std::advance(__left_split, std::distance(__middle, __right_split));
return __left_split;
}
-}
templatetypename _ForwardIterator, typename _Predicate
_ForwardIterator
@@ -1618,16 +1596,11 @@
_DistanceType;
