This is the mail archive of the
mailing list for the libstdc++ project.
Re: [Bug libstdc++/61107] stl_algo.h: std::__inplace_stable_partition() doesn't process the whole data range
- From: Jonathan Wakely <jwakely at redhat dot com>
- To: Christopher Jefferson <chris at bubblescope dot net>
- Cc: François Dumont <frs dot dumont at gmail dot com>, "libstdc++ at gcc dot gnu dot org" <libstdc++ at gcc dot gnu dot org>, gcc-patches <gcc-patches at gcc dot gnu dot org>
- Date: Wed, 12 Nov 2014 18:05:41 +0000
- Subject: Re: [Bug libstdc++/61107] stl_algo.h: std::__inplace_stable_partition() doesn't process the whole data range
- Authentication-results: sourceware.org; auth=none
- References: <5441800A dot 1040609 at gmail dot com> <546124F8 dot 4050003 at gmail dot com> <20141110214511 dot GF5191 at redhat dot com> <546138B1 dot 7000304 at gmail dot com> <20141110222000 dot GH5191 at redhat dot com> <CA+jCFLub3i2E4hqjkkdH2uYq_v5RTsh=EwC=405gS1XkGNZmVw at mail dot gmail dot com>
On 12/11/14 14:56 +0000, 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
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
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! :-)