This is the mail archive of the
newlib@sourceware.org
mailing list for the newlib project.
RE: [PATCH 1/2] Ensure qsort recursion depth is bounded
> -----Original Message-----
> From: Corinna Vinschen <vinschen@redhat.com>
> Sent: den 13 mars 2018 13:53
> To: newlib@sourceware.org
> Cc: Håkan Lindqvist <hakan.lindqvist@enea.com>
> Subject: Re: [PATCH 1/2] Ensure qsort recursion depth is bounded
>
> On Mar 12 15:44, Håkan Lindqvist wrote:
> > From 9d2f1fc59b8338f54c13dba4dac01d8751ceb8df Mon Sep 17 00:00:00
> 2001
> > From: Hakan Lindqvist <hakan.lindqvist@enea.com>
> > Date: Mon, 12 Mar 2018 13:51:07 +0100
> > Subject: [PATCH 1/2] Ensure qsort recursion depth is bounded
> >
> > The qsort algorithm splits the input array in three parts. The left
> > and right parts may need further sorting. One of them is sorted by
> > recursion, the other by iteration. This update ensures that it is the
> > smaller part that is chosen for recursion.
> >
> > By choosing the smaller part, each recursion level will handle less
> > than half the array of the previous recursion level. Hence the
> > recursion depth is bounded to be less than log2(n) i.e. 1 level per
> > significant bit in the array size n.
> >
> > The update also includes code comments explaining the algorithm.
>
> The patch looks good at first glance. Would you mind to outline how you
> tested it?
>
I wrote a test program, It mostly tests sorting random data, but also specific patterns. I'll include it below.
It's not "production quality"; there is lots of stuff from when I was testing different things. Sorry about that.
You can use command line arguments to select different patterns. Mostly random patterns, but also special pattern using negative -r values.
The program contains ifdeffed stuff. Some of it is for timing measurements with facilities from the OS we make. Other parts are some measurement probe stuff another version of qsort that I used to verify the recursion depth, and for when I was experimenting with other another patch.
Best regards
Håkan Lindqvist
---- TEST PROGRAM BELOW ---
#include "stdlib.h"
#include "stdio.h"
#include "stdint.h"
#include "assert.h"
#include "errno.h"
#include "string.h"
#include "getopt.h"
#ifdef USE_OSE_HWTIMER
#include "ose.h"
#include "hwtimer.h"
#include "cpu_access.h"
#endif
#ifdef USE_DEBUG_PROBE
/* Debug probe variables */
extern size_t qsort_peak_recursion;
extern size_t qsort_combined_recursion;
extern size_t qsort_insertion_count;
extern size_t qsort_disable_insertion;
extern size_t qsort_insertion_threshold;
/* Measurements */
static size_t max_peak_recursion;
#endif
#ifdef USE_OSE_HWTIMER
/* Timer */
static unsigned long hw_handle;
static uint32_t hw_freq;
#endif
/* Options */
static int verbose_level = 0;
static size_t set_size = 10000;
static int data_range = 100000;
static size_t data_stride = 1;
static uint32_t compare_delay = 0;
/* Data set */
static int *data_array;
/* Compare-function for integers */
static int
int_comp(const void *ap, const void *bp)
{
volatile uint32_t count;
int a = *(const int *)ap;
int b = *(const int *)bp;
if (compare_delay != 0)
for (count = 0; count < compare_delay; count++) { ; }
return (a < b) ? -1 : (a == b) ? 0 : 1;
}
static uint64_t
test_once(void)
{
size_t i, j;
uint64_t us = 0;
#ifdef USE_OSE_HWTIMER
uint32_t hw_time;
#endif
if (data_range <= 0)
{
if (data_range == 0)
{
/* Sequential sorted data */
for (i = 0; i < set_size;)
{
int data = i;
size_t stride = 1 + rand() % data_stride;
for (j = 0; i < set_size && j < stride; i++, j++)
data_array[i] = data;
}
}
else if (data_range == -1)
{
/* Best case for inserion sort */
for (i = 0; i < set_size; i++)
data_array[i] = i;
data_array[0] = set_size/2-1;
}
else if (data_range == -2)
{
/* Worst case for the insertion sort */
data_array[0] = set_size - 1;
data_array[set_size / 2] = set_size;
for (i = 1; i < (set_size / 2); i++)
{
data_array[i] = set_size / 2 - i;
data_array[i + set_size / 2] = set_size * 2 - i;
}
}
else if (data_range == -3)
{
for (i = 0; i < set_size; i++)
data_array[i] = set_size - i;
data_array[0] = set_size/2-1;
}
else if (data_range == -4)
{
for (i = 0; i < set_size; i++)
data_array[i] = set_size - i;
}
else
{
for (i = 0; i < (set_size / 2); i++)
data_array[i] = 0;
data_array[i++] = 1;
for (; i < set_size; i++)
data_array[i] = 2;
}
}
else
{
/* Initialize array with random data */
for (i = 0; i < set_size;)
{
int data = rand() % data_range;
size_t stride = 1 + rand() % data_stride;
for (j = 0; i < set_size && j < stride; i++, j++)
data_array[i] = data;
}
}
#ifdef USE_DEBUG_PROBE
qsort_peak_recursion = 0;
qsort_combined_recursion = 0;
qsort_insertion_count = 0;
#endif
#ifdef USE_OSE_HWTIMER
hw_time = hwtimer_read(hw_handle);
#endif
/* Sort */
qsort(data_array, set_size, sizeof(int), &int_comp);
#ifdef USE_OSE_HWTIMER
hw_time = hwtimer_read(hw_handle) - hw_time;
us = (hw_time * UINT64_C(1000000)) / hw_freq;
#endif
#ifdef USE_DEBUG_PROBE
if (verbose_level != 0)
printf("recursion=%2lu, ins_count=%2lu, us=%8llu\n",
qsort_peak_recursion, qsort_insertion_count, us);
if (max_peak_recursion < qsort_peak_recursion)
max_peak_recursion = qsort_peak_recursion;
assert(qsort_combined_recursion == 0);
#endif
/* Validate result */
for (i = 1; i < set_size; i++)
if (data_array[i-1] > data_array[i])
{
printf("Sort failure: data_range=%lu, set_size=%lu, i=%lu\n",
data_range, set_size, i);
exit(-1);
}
return us;
}
struct Suffix { char suffix; long factor; };
static const struct Suffix bytecount_suffixes[] = {
{ 'B', 1 },
{ 'K', 1024 },
{ 'M', 1024*1024 },
{ 'G', 1024*1024*1024 },
{ 0 }
};
/*
* Parse an argument string as a set of numbers with suffixes.
* E.g. 1h30m with time_suffixes is 1*60*60 + 30*60 = 5400.
* returns -1 in case of failure.
*/
static long
parsearg(const char *arg, const struct Suffix *suffixes)
{
long value = 0;
long part;
const char *str = arg;
char *endptr;
const struct Suffix *s;
for (;;)
{
part = strtol(str, &endptr, 0);
if (endptr == str)
goto fail; /* No subject part of the number */
str = endptr;
if (*str != '\0')
{
for (s = suffixes; ; s++)
{
if (s == NULL || s->suffix == 0)
goto fail; /* No recognized suffix */
if (*str == s->suffix)
{
part *= s->factor;
str++;
break;
}
}
}
value += part;
if (*str == '\0')
return value; /* Reached end of argument with no errors. */
}
fail:
fprintf(stderr, "Unrecognized option argument: %s\n", arg);
if (errno == 0)
errno = EINVAL;
return -1;
}
int
main(int argc, char *argv[])
{
uint64_t measure_set[2][12];
int c = 0;
/* Parse options. */
while (c != -1)
{
static const struct option longopts[] =
{
{ "verbose", no_argument, 0, 'v' },
{ "set", required_argument, 0, 's' },
{ "range", required_argument, 0, 'r' },
{ "stride", required_argument, 0, 'd' },
{ "delay", required_argument, 0, 'y' },
{ 0 }
};
errno = 0;
c = getopt_long (argc, argv, "vqnt:s:r:p:c:i:m:d:", longopts, NULL);
switch (c)
{
case -1: /* No more options */
break;
case 'v': /* Option "--verbose" */
verbose_level = 1;
break;
case 's':
set_size = parsearg(optarg, bytecount_suffixes);
break;
case 'r':
data_range = parsearg(optarg, bytecount_suffixes);
break;
case 'd':
data_stride = parsearg(optarg, bytecount_suffixes);
break;
case 'y':
compare_delay = parsearg(optarg, bytecount_suffixes);
break;
default:
fprintf(stderr, "Unknown option %d\n", c);
}
if (errno != 0)
{
fprintf(stderr, "Option error %s", strerror(errno));
exit(-1);
}
}
data_array = malloc(set_size * sizeof(int));
if (data_array == NULL)
{
printf("malloc of data_array failed.\n");
return -1;
}
#ifdef USE_OSE_HWTIMER
/* Prepare hwtimer */
hw_handle = biosOpen(HWTIMER_BIOSNAME);
hw_freq = hwtimer_freq(hw_handle, -1);
#endif
#ifdef USE_DEBUG_PROBE
for (qsort_insertion_threshold = 2;
qsort_insertion_threshold < 12;
qsort_insertion_threshold++)
{
for (qsort_disable_insertion = 0;
qsort_disable_insertion < 2;
qsort_disable_insertion++)
{
srand(1);
measure_set[qsort_disable_insertion][qsort_insertion_threshold] =
test_once();
}
}
#else
srand(1);
measure_set[0][0] =
test_once();
#endif
printf("-s set_size = %lu\n", set_size);
printf("-r data_range = %i\n", data_range);
printf("-d data_stride = %lu\n", data_stride);
printf("-l compare_delay = %lu\n", compare_delay);
#ifdef USE_OSE_HWTIMER
#ifdef USE_DEBUG_PROBE
printf("\nmax_recursion = %lu\n\n", max_peak_recursion);
printf("Thresh Insertion No Insertion\n");
for (qsort_insertion_threshold = 2;
qsort_insertion_threshold < 12;
qsort_insertion_threshold++)
{
printf("%-8d%9llu%9llu\n",
qsort_insertion_threshold,
measure_set[0][qsort_insertion_threshold],
measure_set[1][qsort_insertion_threshold]);
}
#else
printf("microseconds: %llu\n", measure_set[0][0]);
#endif
#endif
return 0;
}