Re: test for lib.alg.sort

[Martin Sebor <se...@roguewave.com>]

Anton Pevtsov wrote:
> I am porting tests for lib.alg.sort algorithms (sort, stable_sort,
> partial_sort and partial_copy_sort) and I have several questions about
> these tests:
> 
> 1. Current test version contains code for some tracing:
> ...
>             if (!(i % 20))
>                 TRACE
> ("+------+------+------+------+------+------+------+\n"
>                        "|   N  | COMP | COPY |N lg N|   X  | max X| min
> X|\n"
>  
> "+======+======+======+======+======+======+======+\n");
> 
>             // # | comp | assign | exp. complexity | X | max X |
>             TRACE ("|%6d|%6d|%6d|%6d|%6.2f|%6.2f|%6.2f|\n",
>                    i + 1, ops, cpy, cmplx, x, x_max, x_min);
> ...
> 
> Do we need to keep this trace in new version ? 

Feel free to disable it but please leave the code in so that it can
be enabled if need be.

> 
> 2. Current test version doesn't exercise stable_sort, partial_sort and
> partial_copy_sort at all. I'll add tests for these algorithms.

That'll be great!

> As a part
> of them I'll need to verify their complexity. For the sort algorithm I
> found the upper estimate value in the code (3.33 * N * log N). Is this
> the correct upper estimate value for stable_sort, partial_sort and
> partial_sort_copy too? 

Not really, it's just something that happened to work for the test
as well as our implementation. I never did like it. I don't think
we can use a general formula to test the complexity.

> The standard talks about O(N * log M), M <= N
> for these algorithms, but this is not enough for strict tests.

I see O(N * log N) for sort() but I don't see how we can reliably
test the complexity requirements. The original sort implementation
used the quicksort algorithm which has quadratic worst case behavior.
The only semi-reliable way to verify the implementation performs in
log time on average is to do a whole bunch of runs on random data
and check we're in the ballpark.

We've been using the introsort algorithm which has a guaranteed
logarithmic complexity but even with this algorithm the only way
to test the complexity is over a large number of runs.

> (Of
> course, I suppose here that stable_sort uses additional memory).
> 
> 3. I think it is necessary to verify the complexity of stable_sort in
> case then no additional memory is available. Is it possible to disable
> the memory allocation in this algorithm? (I think that the using of huge
> arrays is not a right way to do it).

AFAIK, the algorithm uses the std::get_temporary_buffer() function
template. While it's not guaranteed, in our implementation, each
specialization of the template manages just one buffer (or maybe
all of them share the same buffer, either way). So if you grab
the buffer by calling std::get_temporary_buffer() before invoking
the algorithm you should prevent it from using it too and force
get_temporary_buffer to dynamically allocate the memory requested
by the algorithm. Be sure to verify this in the test itself (i.e.,
the test should issue an error when it can't force the algorithm
to use dynamically allocated memory. You might want to look at
rw_new.h and new.cpp to see if you could exploit the replacement
operator new for this purpose. Be aware that the replacement
operator new doesn't work across shared library boundaries on AIX
and Windows.

> 
> 4. I assume to use random-generated sequences for these algorithms
> tests. Of course, it is possible to use hardcoded sequences like it is
> done in almost all other tests, but this will result in difficulties
> with the complexity tests (to test the complexity correctly we are
> needed in large sequences). May be, it would be good to verify the
> algorithms correctness on the hardcoded sequences and use
> random-generated arrays to verify the complexity. What do you think
> about it?

That sounds like a very reasonable approach.

Martin