This is the mail archive of the
glibc-cvs@sourceware.org
mailing list for the glibc project.
GNU C Library master sources branch azanella/qsort-refactor created. glibc-2.28.9000-89-gf425f5a
- From: azanella at sourceware dot org
- To: glibc-cvs at sourceware dot org
- Date: 31 Aug 2018 19:39:41 -0000
- Subject: GNU C Library master sources branch azanella/qsort-refactor created. glibc-2.28.9000-89-gf425f5a
This is an automated email from the git hooks/post-receive script. It was
generated because a ref change was pushed to the repository containing
the project "GNU C Library master sources".
The branch, azanella/qsort-refactor has been created
at f425f5ac83e55d218610a048c9134ded93e06914 (commit)
- Log -----------------------------------------------------------------
http://sourceware.org/git/gitweb.cgi?p=glibc.git;a=commitdiff;h=f425f5ac83e55d218610a048c9134ded93e06914
commit f425f5ac83e55d218610a048c9134ded93e06914
Author: Adhemerval Zanella <adhemerval.zanella@linaro.org>
Date: Tue Jan 16 14:24:53 2018 -0200
stdlib: Remove undefined behavior from qsort implementation
Internally qsort is implemented on top of __qsort_r by casting the
function pointer to another type (__compar_fn_t tp __compar_d_fn_t)
and passing a NULL extra argument. Casting function pointer with
different types for subsequent function call is undefined-behaviour
(C11 6.3.2.3):
"[8] A pointer to a function of one type may be converted to a pointer
to a function of another type and back again; the result shall compare
equal to the original pointer. If a converted pointer is used to call
a function whose type is not compatible with the referenced type,
the behavior is undefined."
Also 'compatible' in this case also does not apply according to
6.7.6.3 Function declarators (including prototypes):
"[15] For two function types to be compatible, both shall specify
compatible return types. (146) Moreover, the parameter type lists,
if both are present, shall agree in the number of parameters and
in use of the ellipsis terminator; corresponding parameters shall
have compatible types. [...]"
Although this works on all architectures glibc supports (mostly because
it casts function pointers with similar calling conventions), I think
it is worth to avoid it. This patch fixes it by adding a common
implementation (qsort_common.c) which redefines the function based
on the required types.
For x86_64 (i7-4790K, gcc 7.2.1) shows a slight better performance
for qsort:
Results for member size 4
Sorted
nmemb | base | patched | diff
32| 1304 | 1257 | -3.60
4096| 330707 | 302235 | -8.61
32768| 3300210 | 3020728 | -8.47
524288| 65673289 | 59306436 | -9.69
Repeated
nmemb | base | patched | diff
32| 1885 | 1873 | -0.64
4096| 951490 | 904864 | -4.90
32768| 9272366 | 8542801 | -7.87
524288| 183337854 | 168426795 | -8.13
MostlySorted
nmemb | base | patched | diff
32| 1836 | 1776 | -3.27
4096| 758359 | 709937 | -6.39
32768| 7199982 | 6855890 | -4.78
524288| 139242170 | 129385161 | -7.08
Unsorted
nmemb | base | patched | diff
32| 2073 | 1941 | -6.37
4096| 1058383 | 969021 | -8.44
32768| 10310116 | 9462116 | -8.22
524288| 202427388 | 186560908 | -7.84
Results for member size 8
Sorted
nmemb | base | patched | diff
32| 1224 | 1205 | -1.55
4096| 336100 | 325554 | -3.14
32768| 3539890 | 3264125 | -7.79
524288| 67268510 | 66107684 | -1.73
Repeated
nmemb | base | patched | diff
32| 2096 | 2118 | 1.05
4096| 1015585 | 979114 | -3.59
32768| 9871981 | 9028606 | -8.54
524288| 189710172 | 174903867 | -7.80
MostlySorted
nmemb | base | patched | diff
32| 2318 | 2346 | 1.21
4096| 805051 | 759158 | -5.70
32768| 8346363 | 7810444 | -6.42
524288| 143597264 | 135900146 | -5.36
Unsorted
nmemb | base | patched | diff
32| 2364 | 2301 | -2.66
4096| 1076998 | 1014018 | -5.85
32768| 10442153 | 9888078 | -5.31
524288| 206235337 | 192479957 | -6.67
Results for member size 32
Sorted
nmemb | base | patched | diff
32| 1214 | 1184 | -2.47
4096| 332449 | 325865 | -1.98
32768| 3313274 | 3331750 | 0.56
524288| 70786673 | 69067176 | -2.43
Repeated
nmemb | base | patched | diff
32| 4913 | 4813 | -2.04
4096| 1693735 | 1624137 | -4.11
32768| 17054760 | 15896739 | -6.79
524288| 332149265 | 316328778 | -4.76
MostlySorted
nmemb | base | patched | diff
32| 5490 | 5332 | -2.88
4096| 1394312 | 1312703 | -5.85
32768| 12743599 | 12360726 | -3.00
524288| 240249011 | 231603294 | -3.60
Unsorted
nmemb | base | patched | diff
32| 6251 | 6047 | -3.26
4096| 1959306 | 1695241 | -13.48
32768| 17204840 | 16430388 | -4.50
524288| 342716199 | 329496913 | -3.86
Checked on x86_64-linux-gnu.
* stdlib/qsort.c: Move common code to stdlib/qsort_common.c
and parametrize the function definition based wether to use
the '_r' variant.
* stdlib/qsort_common.c: New file.
diff --git a/stdlib/qsort.c b/stdlib/qsort.c
index c3fb0e8..10b8059 100644
--- a/stdlib/qsort.c
+++ b/stdlib/qsort.c
@@ -16,17 +16,13 @@
License along with the GNU C Library; if not, see
<http://www.gnu.org/licenses/>. */
-/* If you consider tuning this algorithm, you should consult first:
- Engineering a sort function; Jon Bentley and M. Douglas McIlroy;
- Software - Practice and Experience; Vol. 23 (11), 1249-1265, 1993. */
-
#include <limits.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
-/* Swap SIZE bytes between addresses A and B. Helper to generic types
- are provided as an optimization. */
+/* Swap SIZE bytes between addresses A and B. These helpers are provided
+ along the generic one as an optimization. */
typedef void (*swap_t)(void *, void *, size_t);
@@ -104,202 +100,14 @@ typedef struct
#define POP(low, high) ((void) (--top, (low = top->lo), (high = top->hi)))
#define STACK_NOT_EMPTY (stack < top)
-
-/* Order size using quicksort. This implementation incorporates
- four optimizations discussed in Sedgewick:
-
- 1. Non-recursive, using an explicit stack of pointer that store the
- next array partition to sort. To save time, this maximum amount
- of space required to store an array of SIZE_MAX is allocated on the
- stack. Assuming a 32-bit (64 bit) integer for size_t, this needs
- only 32 * sizeof(stack_node) == 256 bytes (for 64 bit: 1024 bytes).
- Pretty cheap, actually.
-
- 2. Chose the pivot element using a median-of-three decision tree.
- This reduces the probability of selecting a bad pivot value and
- eliminates certain extraneous comparisons.
-
- 3. Only quicksorts TOTAL_ELEMS / MAX_THRESH partitions, leaving
- insertion sort to order the MAX_THRESH items within each partition.
- This is a big win, since insertion sort is faster for small, mostly
- sorted array segments.
-
- 4. The larger of the two sub-partitions is always pushed onto the
- stack first, with the algorithm then concentrating on the
- smaller partition. This *guarantees* no more than log (total_elems)
- stack size is needed (actually O(1) in this case)! */
-
-void
-__qsort_r (void *const pbase, size_t total_elems, size_t size,
- __compar_d_fn_t cmp, void *arg)
-{
- char *base_ptr = (char *) pbase;
-
- const size_t max_thresh = MAX_THRESH * size;
-
- if (total_elems == 0)
- /* Avoid lossage with unsigned arithmetic below. */
- return;
-
- swap_t swap = select_swap_func (pbase, size);
-
- if (total_elems > MAX_THRESH)
- {
- char *lo = base_ptr;
- char *hi = &lo[size * (total_elems - 1)];
- stack_node stack[STACK_SIZE];
- stack_node *top = stack;
-
- PUSH (NULL, NULL);
-
- while (STACK_NOT_EMPTY)
- {
- char *left_ptr;
- char *right_ptr;
-
- /* Select median value from among LO, MID, and HI. Rearrange
- LO and HI so the three values are sorted. This lowers the
- probability of picking a pathological pivot value and
- skips a comparison for both the LEFT_PTR and RIGHT_PTR in
- the while loops. */
-
- char *mid = lo + size * ((hi - lo) / size >> 1);
-
- if ((*cmp) ((void *) mid, (void *) lo, arg) < 0)
- swap (mid, lo, size);
- if ((*cmp) ((void *) hi, (void *) mid, arg) < 0)
- swap (mid, hi, size);
- else
- goto jump_over;
- if ((*cmp) ((void *) mid, (void *) lo, arg) < 0)
- swap (mid, lo, size);
- jump_over:;
-
- left_ptr = lo + size;
- right_ptr = hi - size;
-
- /* Here's the famous ``collapse the walls'' section of quicksort.
- Gotta like those tight inner loops! They are the main reason
- that this algorithm runs much faster than others. */
- do
- {
- while ((*cmp) ((void *) left_ptr, (void *) mid, arg) < 0)
- left_ptr += size;
-
- while ((*cmp) ((void *) mid, (void *) right_ptr, arg) < 0)
- right_ptr -= size;
-
- if (left_ptr < right_ptr)
- {
- swap (left_ptr, right_ptr, size);
- if (mid == left_ptr)
- mid = right_ptr;
- else if (mid == right_ptr)
- mid = left_ptr;
- left_ptr += size;
- right_ptr -= size;
- }
- else if (left_ptr == right_ptr)
- {
- left_ptr += size;
- right_ptr -= size;
- break;
- }
- }
- while (left_ptr <= right_ptr);
-
- /* Set up pointers for next iteration. First determine whether
- left and right partitions are below the threshold size. If so,
- ignore one or both. Otherwise, push the larger partition's
- bounds on the stack and continue sorting the smaller one. */
-
- if ((size_t) (right_ptr - lo) <= max_thresh)
- {
- if ((size_t) (hi - left_ptr) <= max_thresh)
- /* Ignore both small partitions. */
- POP (lo, hi);
- else
- /* Ignore small left partition. */
- lo = left_ptr;
- }
- else if ((size_t) (hi - left_ptr) <= max_thresh)
- /* Ignore small right partition. */
- hi = right_ptr;
- else if ((right_ptr - lo) > (hi - left_ptr))
- {
- /* Push larger left partition indices. */
- PUSH (lo, right_ptr);
- lo = left_ptr;
- }
- else
- {
- /* Push larger right partition indices. */
- PUSH (left_ptr, hi);
- hi = right_ptr;
- }
- }
- }
-
- /* Once the BASE_PTR array is partially sorted by quicksort the rest
- is completely sorted using insertion sort, since this is efficient
- for partitions below MAX_THRESH size. BASE_PTR points to the beginning
- of the array to sort, and END_PTR points at the very last element in
- the array (*not* one beyond it!). */
-
-#define min(x, y) ((x) < (y) ? (x) : (y))
-
- {
- char *const end_ptr = &base_ptr[size * (total_elems - 1)];
- char *tmp_ptr = base_ptr;
- char *thresh = min(end_ptr, base_ptr + max_thresh);
- char *run_ptr;
-
- /* Find smallest element in first threshold and place it at the
- array's beginning. This is the smallest array element,
- and the operation speeds up insertion sort's inner loop. */
-
- for (run_ptr = tmp_ptr + size; run_ptr <= thresh; run_ptr += size)
- if ((*cmp) ((void *) run_ptr, (void *) tmp_ptr, arg) < 0)
- tmp_ptr = run_ptr;
-
- if (tmp_ptr != base_ptr)
- swap (tmp_ptr, base_ptr, size);
-
- /* Insertion sort, running from left-hand-side up to right-hand-side. */
-
- run_ptr = base_ptr + size;
- while ((run_ptr += size) <= end_ptr)
- {
- tmp_ptr = run_ptr - size;
- while ((*cmp) ((void *) run_ptr, (void *) tmp_ptr, arg) < 0)
- tmp_ptr -= size;
-
- tmp_ptr += size;
- if (tmp_ptr != run_ptr)
- {
- char *trav;
-
- trav = run_ptr + size;
- while (--trav >= run_ptr)
- {
- char c = *trav;
- char *hi, *lo;
-
- for (hi = lo = trav; (lo -= size) >= tmp_ptr; hi = lo)
- *hi = *lo;
- *hi = c;
- }
- }
- }
- }
-}
+#define R_VERSION
+#define R_FUNC __qsort_r
+#include <stdlib/qsort_common.c>
libc_hidden_def (__qsort_r)
weak_alias (__qsort_r, qsort_r)
-void
-qsort (void *b, size_t n, size_t s, __compar_fn_t cmp)
-{
- return __qsort_r (b, n, s, (__compar_d_fn_t) cmp, NULL);
-}
+#define R_FUNC qsort
+#include <stdlib/qsort_common.c>
+
libc_hidden_def (qsort)
diff --git a/stdlib/qsort.c b/stdlib/qsort_common.c
similarity index 65%
copy from stdlib/qsort.c
copy to stdlib/qsort_common.c
index c3fb0e8..666b195 100644
--- a/stdlib/qsort.c
+++ b/stdlib/qsort_common.c
@@ -1,6 +1,6 @@
-/* Copyright (C) 1991-2018 Free Software Foundation, Inc.
+/* Common implementation for both qsort and qsort_r.
+ Copyright (C) 2018 Free Software Foundation, Inc.
This file is part of the GNU C Library.
- Written by Douglas C. Schmidt (schmidt@ics.uci.edu).
The GNU C Library is free software; you can redistribute it and/or
modify it under the terms of the GNU Lesser General Public
@@ -20,90 +20,15 @@
Engineering a sort function; Jon Bentley and M. Douglas McIlroy;
Software - Practice and Experience; Vol. 23 (11), 1249-1265, 1993. */
-#include <limits.h>
-#include <stdlib.h>
-#include <string.h>
-#include <stdbool.h>
-
-/* Swap SIZE bytes between addresses A and B. Helper to generic types
- are provided as an optimization. */
-
-typedef void (*swap_t)(void *, void *, size_t);
-
-static inline bool
-check_alignment (const void *base, size_t align)
-{
- return _STRING_ARCH_unaligned || ((uintptr_t)base & (align - 1)) == 0;
-}
-
-static void
-swap_u32 (void * restrict a, void * restrict b, size_t size)
-{
- uint32_t *ua = a, *ub = b, tmp = *ua;
- *ua = *ub, *ub = tmp;
-}
-
-static void
-swap_u64 (void * restrict a, void * restrict b, size_t size)
-{
- uint64_t *ua = a, *ub = b, tmp = *ua;
- *ua = *ub, *ub = tmp;
-}
-
-static void
-swap_generic (void * restrict a, void * restrict b, size_t size)
-{
- /* Use multiple small memcpys with constant size to enable inlining
- on most targets. */
- enum {
- SWAP_GENERIC_SIZE = 32
- };
- unsigned char tmp[SWAP_GENERIC_SIZE];
- while (size > SWAP_GENERIC_SIZE)
- {
- memcpy (tmp, a, SWAP_GENERIC_SIZE);
- a = memcpy (a, b, SWAP_GENERIC_SIZE) + SWAP_GENERIC_SIZE;
- b = memcpy (b, tmp, SWAP_GENERIC_SIZE) + SWAP_GENERIC_SIZE;
- size -= SWAP_GENERIC_SIZE;
- }
- memcpy (tmp, a, size);
- memcpy (a, b, size);
- memcpy (b, tmp, size);
-}
-
-static inline swap_t
-select_swap_func (const void *base, size_t size)
-{
- if (size == sizeof (uint32_t)
- && check_alignment (base, _Alignof (uint32_t)))
- return swap_u32;
- else if (size == sizeof (uint64_t)
- && check_alignment (base, _Alignof (uint64_t)))
- return swap_u64;
- return swap_generic;
-}
-
-/* Discontinue quicksort algorithm when partition gets below this size.
- This particular magic number was chosen to work best on a Sun 4/260. */
-#define MAX_THRESH 4
-
-/* Stack node declarations used to store unfulfilled partition obligations. */
-typedef struct
- {
- char *lo;
- char *hi;
- } stack_node;
-
-/* The next 4 #defines implement a very fast in-line stack abstraction. */
-/* The stack needs log (total_elements) entries (we could even subtract
- log(MAX_THRESH)). Since total_elements has type size_t, we get as
- upper bound for log (total_elements):
- bits per byte (CHAR_BIT) * sizeof(size_t). */
-#define STACK_SIZE (CHAR_BIT * sizeof(size_t))
-#define PUSH(low, high) ((void) ((top->lo = (low)), (top->hi = (high)), ++top))
-#define POP(low, high) ((void) (--top, (low = top->lo), (high = top->hi)))
-#define STACK_NOT_EMPTY (stack < top)
-
+#ifdef R_VERSION
+# define R_CMP_TYPE __compar_d_fn_t
+# define R_CMP_ARG , void *arg
+# define R_CMP(p1, p2) cmp (p1, p2, arg)
+#else
+# define R_CMP_TYPE __compar_fn_t
+# define R_CMP_ARG
+# define R_CMP(p1, p2) cmp (p1, p2)
+#endif
/* Order size using quicksort. This implementation incorporates
four optimizations discussed in Sedgewick:
@@ -130,17 +55,16 @@ typedef struct
stack size is needed (actually O(1) in this case)! */
void
-__qsort_r (void *const pbase, size_t total_elems, size_t size,
- __compar_d_fn_t cmp, void *arg)
+R_FUNC (void *pbase, size_t total_elems, size_t size, R_CMP_TYPE cmp R_CMP_ARG)
{
- char *base_ptr = (char *) pbase;
-
- const size_t max_thresh = MAX_THRESH * size;
-
if (total_elems == 0)
/* Avoid lossage with unsigned arithmetic below. */
return;
+ char *base_ptr = (char *) pbase;
+
+ const size_t max_thresh = MAX_THRESH * size;
+
swap_t swap = select_swap_func (pbase, size);
if (total_elems > MAX_THRESH)
@@ -165,13 +89,13 @@ __qsort_r (void *const pbase, size_t total_elems, size_t size,
char *mid = lo + size * ((hi - lo) / size >> 1);
- if ((*cmp) ((void *) mid, (void *) lo, arg) < 0)
+ if (R_CMP ((void *) mid, (void *) lo) < 0)
swap (mid, lo, size);
- if ((*cmp) ((void *) hi, (void *) mid, arg) < 0)
+ if (R_CMP ((void *) hi, (void *) mid) < 0)
swap (mid, hi, size);
else
goto jump_over;
- if ((*cmp) ((void *) mid, (void *) lo, arg) < 0)
+ if (R_CMP ((void *) mid, (void *) lo) < 0)
swap (mid, lo, size);
jump_over:;
@@ -183,10 +107,10 @@ __qsort_r (void *const pbase, size_t total_elems, size_t size,
that this algorithm runs much faster than others. */
do
{
- while ((*cmp) ((void *) left_ptr, (void *) mid, arg) < 0)
+ while (R_CMP ((void *) left_ptr, (void *) mid) < 0)
left_ptr += size;
- while ((*cmp) ((void *) mid, (void *) right_ptr, arg) < 0)
+ while (R_CMP ((void *) mid, (void *) right_ptr) < 0)
right_ptr -= size;
if (left_ptr < right_ptr)
@@ -246,12 +170,11 @@ __qsort_r (void *const pbase, size_t total_elems, size_t size,
of the array to sort, and END_PTR points at the very last element in
the array (*not* one beyond it!). */
-#define min(x, y) ((x) < (y) ? (x) : (y))
-
{
char *const end_ptr = &base_ptr[size * (total_elems - 1)];
char *tmp_ptr = base_ptr;
- char *thresh = min(end_ptr, base_ptr + max_thresh);
+ char *thresh = end_ptr < base_ptr + max_thresh ?
+ end_ptr : base_ptr + max_thresh;
char *run_ptr;
/* Find smallest element in first threshold and place it at the
@@ -259,7 +182,7 @@ __qsort_r (void *const pbase, size_t total_elems, size_t size,
and the operation speeds up insertion sort's inner loop. */
for (run_ptr = tmp_ptr + size; run_ptr <= thresh; run_ptr += size)
- if ((*cmp) ((void *) run_ptr, (void *) tmp_ptr, arg) < 0)
+ if (R_CMP ((void *) run_ptr, (void *) tmp_ptr) < 0)
tmp_ptr = run_ptr;
if (tmp_ptr != base_ptr)
@@ -271,7 +194,7 @@ __qsort_r (void *const pbase, size_t total_elems, size_t size,
while ((run_ptr += size) <= end_ptr)
{
tmp_ptr = run_ptr - size;
- while ((*cmp) ((void *) run_ptr, (void *) tmp_ptr, arg) < 0)
+ while (R_CMP ((void *) run_ptr, (void *) tmp_ptr) < 0)
tmp_ptr -= size;
tmp_ptr += size;
@@ -294,12 +217,9 @@ __qsort_r (void *const pbase, size_t total_elems, size_t size,
}
}
-libc_hidden_def (__qsort_r)
-weak_alias (__qsort_r, qsort_r)
-
-void
-qsort (void *b, size_t n, size_t s, __compar_fn_t cmp)
-{
- return __qsort_r (b, n, s, (__compar_d_fn_t) cmp, NULL);
-}
-libc_hidden_def (qsort)
+#undef R_NAME
+#undef R_CMP_TYPE
+#undef R_CMP_ARG
+#undef R_CMP
+#undef R_FUNC
+#undef R_VERSION
http://sourceware.org/git/gitweb.cgi?p=glibc.git;a=commitdiff;h=71ed300d4b967465f4a56cb45295046811c7f9b9
commit 71ed300d4b967465f4a56cb45295046811c7f9b9
Author: Adhemerval Zanella <adhemerval.zanella@linaro.org>
Date: Tue Jan 16 11:19:15 2018 -0200
stdlib: Optimization qsort{_r} swap implementation
This patchs adds a optimized swap operation on qsort based in previous
msort one. Instead of byte operation, three variants are provided:
1. Using uint32_t loads and stores.
2. Using uint64_t loads and stores.
3. Generic one with a temporary buffer and memcpy/mempcpy.
The 1. and 2. option are selected only either if architecture defines
_STRING_ARCH_unaligned or if base pointer is aligned to required type.
This is due based on data for bench-qsort, usually programs calls
qsort with array with multiple of machine word as element size.
Benchmarking shows an increase performance:
Results for member size 4
MostlySorted
nmemb | base | patched | diff
32 | 2512 | 1858 | -26.04
4096 | 825039 | 702725 | -14.83
32768 | 7227910 | 6665149 | -7.79
524288 | 141602678 | 137332279 | -3.02
Repeated
nmemb | base | patched | diff
32 | 1948 | 2053 | 5.39
4096 | 973735 | 880246 | -9.60
32768 | 9695857 | 8501170 | -12.32
524288 | 184086492 | 170832127 | -7.20
Sorted
nmemb | base | patched | diff
32 | 3163 | 3800 | 20.14
4096 | 712679 | 618425 | -13.23
32768 | 3198064 | 3121069 | -2.41
524288 | 62327097 | 62135963 | -0.31
Unsorted
nmemb | base | patched | diff
32 | 2243 | 2036 | -9.23
4096 | 1035615 | 959467 | -7.35
32768 | 10077407 | 9268030 | -8.03
524288 | 198242838 | 182920727 | -7.73
Results for member size 8
MostlySorted
nmemb | base | patched | diff
32 | 2218 | 1737 | -21.69
4096 | 859333 | 725539 | -15.57
32768 | 7843666 | 6543577 | -16.58
524288 | 150404586 | 125632826 | -16.47
Repeated
nmemb | base | patched | diff
32 | 2484 | 1799 | -27.58
4096 | 1028579 | 887522 | -13.71
32768 | 10355933 | 8441606 | -18.49
524288 | 197692669 | 166863090 | -15.59
Sorted
nmemb | base | patched | diff
32 | 1159 | 1108 | -4.40
4096 | 284228 | 285501 | 0.45
32768 | 2816725 | 2796568 | -0.72
524288 | 56171914 | 55222756 | -1.69
Unsorted
nmemb | base | patched | diff
32 | 2627 | 2181 | -16.98
4096 | 1113614 | 965834 | -13.27
32768 | 10833759 | 9796429 | -9.57
524288 | 213615135 | 183258605 | -14.21
Results for member size 32
MostlySorted
nmemb | base | patched | diff
32 | 4428 | 5050 | 14.05
4096 | 1478246 | 1095604 | -25.88
32768 | 12657783 | 10235439 | -19.14
524288 | 254235649 | 185929218 | -26.87
Repeated
nmemb | base | patched | diff
32 | 5087 | 3453 | -32.12
4096 | 1715554 | 1254764 | -26.86
32768 | 17183223 | 11983349 | -30.26
524288 | 337323090 | 240349163 | -28.75
Sorted
nmemb | base | patched | diff
32 | 1172 | 1737 | 48.21
4096 | 284651 | 312751 | 9.87
32768 | 2795492 | 2792345 | -0.11
524288 | 59840778 | 60216689 | 0.63
Unsorted
nmemb | base | patched | diff
32 | 5427 | 4212 | -22.39
4096 | 1817705 | 1360557 | -25.15
32768 | 17388618 | 13014313 | -25.16
524288 | 349929708 | 256942681 | -26.57
Checked on x86_64-linux-gnu.
[BZ #19305].
* stdlib/qsort.c (SWAP): Remove.
(check_alignment, swap_u32, swap_u64, swap_generic,
select_swap_func): New functions.
(__qsort_r):
diff --git a/stdlib/qsort.c b/stdlib/qsort.c
index b3a5102..c3fb0e8 100644
--- a/stdlib/qsort.c
+++ b/stdlib/qsort.c
@@ -23,20 +23,65 @@
#include <limits.h>
#include <stdlib.h>
#include <string.h>
+#include <stdbool.h>
-/* Byte-wise swap two items of size SIZE. */
-#define SWAP(a, b, size) \
- do \
- { \
- size_t __size = (size); \
- char *__a = (a), *__b = (b); \
- do \
- { \
- char __tmp = *__a; \
- *__a++ = *__b; \
- *__b++ = __tmp; \
- } while (--__size > 0); \
- } while (0)
+/* Swap SIZE bytes between addresses A and B. Helper to generic types
+ are provided as an optimization. */
+
+typedef void (*swap_t)(void *, void *, size_t);
+
+static inline bool
+check_alignment (const void *base, size_t align)
+{
+ return _STRING_ARCH_unaligned || ((uintptr_t)base & (align - 1)) == 0;
+}
+
+static void
+swap_u32 (void * restrict a, void * restrict b, size_t size)
+{
+ uint32_t *ua = a, *ub = b, tmp = *ua;
+ *ua = *ub, *ub = tmp;
+}
+
+static void
+swap_u64 (void * restrict a, void * restrict b, size_t size)
+{
+ uint64_t *ua = a, *ub = b, tmp = *ua;
+ *ua = *ub, *ub = tmp;
+}
+
+static void
+swap_generic (void * restrict a, void * restrict b, size_t size)
+{
+ /* Use multiple small memcpys with constant size to enable inlining
+ on most targets. */
+ enum {
+ SWAP_GENERIC_SIZE = 32
+ };
+ unsigned char tmp[SWAP_GENERIC_SIZE];
+ while (size > SWAP_GENERIC_SIZE)
+ {
+ memcpy (tmp, a, SWAP_GENERIC_SIZE);
+ a = memcpy (a, b, SWAP_GENERIC_SIZE) + SWAP_GENERIC_SIZE;
+ b = memcpy (b, tmp, SWAP_GENERIC_SIZE) + SWAP_GENERIC_SIZE;
+ size -= SWAP_GENERIC_SIZE;
+ }
+ memcpy (tmp, a, size);
+ memcpy (a, b, size);
+ memcpy (b, tmp, size);
+}
+
+static inline swap_t
+select_swap_func (const void *base, size_t size)
+{
+ if (size == sizeof (uint32_t)
+ && check_alignment (base, _Alignof (uint32_t)))
+ return swap_u32;
+ else if (size == sizeof (uint64_t)
+ && check_alignment (base, _Alignof (uint64_t)))
+ return swap_u64;
+ return swap_generic;
+}
/* Discontinue quicksort algorithm when partition gets below this size.
This particular magic number was chosen to work best on a Sun 4/260. */
@@ -96,6 +141,8 @@ __qsort_r (void *const pbase, size_t total_elems, size_t size,
/* Avoid lossage with unsigned arithmetic below. */
return;
+ swap_t swap = select_swap_func (pbase, size);
+
if (total_elems > MAX_THRESH)
{
char *lo = base_ptr;
@@ -119,13 +166,13 @@ __qsort_r (void *const pbase, size_t total_elems, size_t size,
char *mid = lo + size * ((hi - lo) / size >> 1);
if ((*cmp) ((void *) mid, (void *) lo, arg) < 0)
- SWAP (mid, lo, size);
+ swap (mid, lo, size);
if ((*cmp) ((void *) hi, (void *) mid, arg) < 0)
- SWAP (mid, hi, size);
+ swap (mid, hi, size);
else
goto jump_over;
if ((*cmp) ((void *) mid, (void *) lo, arg) < 0)
- SWAP (mid, lo, size);
+ swap (mid, lo, size);
jump_over:;
left_ptr = lo + size;
@@ -144,7 +191,7 @@ __qsort_r (void *const pbase, size_t total_elems, size_t size,
if (left_ptr < right_ptr)
{
- SWAP (left_ptr, right_ptr, size);
+ swap (left_ptr, right_ptr, size);
if (mid == left_ptr)
mid = right_ptr;
else if (mid == right_ptr)
@@ -216,7 +263,7 @@ __qsort_r (void *const pbase, size_t total_elems, size_t size,
tmp_ptr = run_ptr;
if (tmp_ptr != base_ptr)
- SWAP (tmp_ptr, base_ptr, size);
+ swap (tmp_ptr, base_ptr, size);
/* Insertion sort, running from left-hand-side up to right-hand-side. */
http://sourceware.org/git/gitweb.cgi?p=glibc.git;a=commitdiff;h=324cef4857ae1c420539a434d5de92f389a6b8d3
commit 324cef4857ae1c420539a434d5de92f389a6b8d3
Author: Adhemerval Zanella <adhemerval.zanella@linaro.org>
Date: Tue Jan 16 10:49:43 2018 -0200
stdlib: Remove use of mergesort on qsort
This patch removes the mergesort optimization on qsort{_r} implementation
and use the quicksort instead. The mergesort implementation has some
issues:
- It is as-safe only for certain types sizes (if total size is less
than 1 KB with large element sizes also forcing memory allocation)
which contradicts the function documentation. Although not required
by the C standard, it is preferable and doable to have a O(1) space
implementation.
- The malloc for certain element size and element number adds arbitrary
latency (might even be worse if malloc is interposed).
- To avoid trigger swap from memory allocation the implementation relies
on system information that might be virtualized (for instance VMs with
overcommit memory) which might leads to potentially use of swap even
if system advertise more memory than actually has. The check also have
the downside of issuing syscalls where none is expected (although only
once per execution).
- The mergesort is suboptimal on already sorted array (BZ#21719).
The quicksort implementation is already optimized to use constant extra
space (due the limit of total number of elements from maximum VM size)
and thus can be used to avoid the malloc usage issues.
Using bench-qsort (i7-4510U, gcc 7.1.1) shows the performance difference
between mergesort (base) and quicksort (patched):
Results for member size 4
MostlySorted
nmemb | base | patched | diff
32 | 1727 | 2512 | 45.45
4096 | 490729 | 825039 | 68.13
32768 | 5062570 | 7227910 | 42.77
524288 | 99397572 | 141602678 | 42.46
Repeated
nmemb | base | patched | diff
32 | 2014 | 1948 | -3.28
4096 | 836096 | 973735 | 16.46
32768 | 8288515 | 9695857 | 16.98
524288 | 171234266 | 184086492 | 7.51
Sorted
nmemb | base | patched | diff
32 | 1508 | 3163 | 109.75
4096 | 279452 | 712679 | 155.03
32768 | 2389989 | 3198064 | 33.81
524288 | 46684810 | 62327097 | 33.51
Unsorted
nmemb | base | patched | diff
32 | 2166 | 2243 | 3.55
4096 | 969238 | 1035615 | 6.85
32768 | 8782888 | 10077407 | 14.74
524288 | 180907441 | 198242838 | 9.58
Results for member size 8
MostlySorted
nmemb | base | patched | diff
32 | 1537 | 2218 | 44.31
4096 | 464279 | 859333 | 85.09
32768 | 5181208 | 7843666 | 51.39
524288 | 102380344 | 150404586 | 46.91
Repeated
nmemb | base | patched | diff
32 | 1712 | 2484 | 45.09
4096 | 833519 | 1028579 | 23.40
32768 | 8642878 | 10355933 | 19.82
524288 | 175210230 | 197692669 | 12.83
Sorted
nmemb | base | patched | diff
32 | 1237 | 1159 | -6.31
4096 | 236972 | 284228 | 19.94
32768 | 2282819 | 2816725 | 23.39
524288 | 48007437 | 56171914 | 17.01
Unsorted
nmemb | base | patched | diff
32 | 1861 | 2627 | 41.16
4096 | 879328 | 1113614 | 26.64
32768 | 9186338 | 10833759 | 17.93
524288 | 187880836 | 213615135 | 13.70
Results for member size 32
MostlySorted
nmemb | base | patched | diff
32 | 6446 | 4428 | -31.31
4096 | 1565811 | 1478246 | -5.59
32768 | 16474957 | 12657783 | -23.17
524288 | 364464135 | 254235649 | -30.24
Repeated
nmemb | base | patched | diff
32 | 5544 | 5087 | -8.24
4096 | 2030560 | 1715554 | -15.51
32768 | 21053028 | 17183223 | -18.38
524288 | 451659503 | 337323090 | -25.31
Sorted
nmemb | base | patched | diff
32 | 3668 | 1172 | -68.05
4096 | 878063 | 284651 | -67.58
32768 | 9071819 | 2795492 | -69.18
524288 | 192633325 | 59840778 | -68.94
Unsorted
nmemb | base | patched | diff
32 | 4906 | 5427 | 10.62
4096 | 2044417 | 1817705 | -11.09
32768 | 21885590 | 17388618 | -20.55
524288 | 477850312 | 349929708 | -26.77
The result shows an increase in latency, and some performance difference is due
the fact mergesort uses a slight improved swap operation than quicksort (which
a following patch addresses it). This change also renders the BZ #21719 fix
unrequired (since it is meeant to fix the sorted input performance degradation
for mergesort). The manual is also updated to indicate the function is now
async-cancel safe.
Checked on x86_64-linux-gnu.
[BZ #21719]
* stdlib/Makefile (routines): Remove msort.
(CFLAGS-msort.c): Remove rule.
* stdlib/msort.c: Remove file.
* stdlib/qsort.c (_quicksort): Rename to __qsort_r and add weak_alias
to qsort_r.
(qsort): New symbol.
* manual/argp.texi: Remove qsort @acu* annotation.
* manual/locale.texi: Likewise.
* manual/search.texi: Likewise.
diff --git a/manual/argp.texi b/manual/argp.texi
index 0023441..b77ad68 100644
--- a/manual/argp.texi
+++ b/manual/argp.texi
@@ -735,7 +735,7 @@ for options, bad phase of the moon, etc.
@c hol_set_group ok
@c hol_find_entry ok
@c hol_sort @mtslocale @acucorrupt
-@c qsort dup @acucorrupt
+@c qsort dup
@c hol_entry_qcmp @mtslocale
@c hol_entry_cmp @mtslocale
@c group_cmp ok
diff --git a/manual/locale.texi b/manual/locale.texi
index dabb959..15d3b78 100644
--- a/manual/locale.texi
+++ b/manual/locale.texi
@@ -253,7 +253,7 @@ The symbols in this section are defined in the header file @file{locale.h}.
@c calculate_head_size ok
@c __munmap ok
@c compute_hashval ok
-@c qsort dup @acucorrupt
+@c qsort dup
@c rangecmp ok
@c malloc @ascuheap @acsmem
@c strdup @ascuheap @acsmem
@@ -275,7 +275,6 @@ The symbols in this section are defined in the header file @file{locale.h}.
@c realloc @ascuheap @acsmem
@c realloc @ascuheap @acsmem
@c fclose @ascuheap @asulock @acsmem @acsfd @aculock
-@c qsort @ascuheap @acsmem
@c alias_compare dup
@c libc_lock_unlock @aculock
@c _nl_explode_name @ascuheap @acsmem
diff --git a/manual/search.texi b/manual/search.texi
index 57dad7a..148d451 100644
--- a/manual/search.texi
+++ b/manual/search.texi
@@ -159,7 +159,7 @@ To sort an array using an arbitrary comparison function, use the
@deftypefun void qsort (void *@var{array}, size_t @var{count}, size_t @var{size}, comparison_fn_t @var{compare})
@standards{ISO, stdlib.h}
-@safety{@prelim{}@mtsafe{}@assafe{}@acunsafe{@acucorrupt{}}}
+@safety{@prelim{}@mtsafe{}@assafe{}@acsafe{}}
The @code{qsort} function sorts the array @var{array}. The array
contains @var{count} elements, each of which is of size @var{size}.
@@ -199,9 +199,8 @@ Functions}):
The @code{qsort} function derives its name from the fact that it was
originally implemented using the ``quick sort'' algorithm.
-The implementation of @code{qsort} in this library might not be an
-in-place sort and might thereby use an extra amount of memory to store
-the array.
+The implementation of @code{qsort} in this library is an in-place sort
+and uses a constant extra space (allocated on the stack).
@end deftypefun
@node Search/Sort Example
diff --git a/stdlib/Makefile b/stdlib/Makefile
index 4e012a8..2c28033 100644
--- a/stdlib/Makefile
+++ b/stdlib/Makefile
@@ -34,7 +34,7 @@ headers := stdlib.h bits/stdlib.h bits/stdlib-ldbl.h bits/stdlib-float.h \
routines := \
atof atoi atol atoll \
abort \
- bsearch qsort msort \
+ bsearch qsort \
getenv putenv setenv secure-getenv \
exit on_exit atexit cxa_atexit cxa_finalize old_atexit \
quick_exit at_quick_exit cxa_at_quick_exit cxa_thread_atexit_impl \
@@ -139,7 +139,6 @@ extra-test-objs += tst-putenvmod.os
generated += isomac isomac.out tst-putenvmod.so
CFLAGS-bsearch.c += $(uses-callbacks)
-CFLAGS-msort.c += $(uses-callbacks)
CFLAGS-qsort.c += $(uses-callbacks)
CFLAGS-system.c += -fexceptions
CFLAGS-system.os = -fomit-frame-pointer
diff --git a/stdlib/msort.c b/stdlib/msort.c
deleted file mode 100644
index 266c253..0000000
--- a/stdlib/msort.c
+++ /dev/null
@@ -1,310 +0,0 @@
-/* An alternative to qsort, with an identical interface.
- This file is part of the GNU C Library.
- Copyright (C) 1992-2018 Free Software Foundation, Inc.
- Written by Mike Haertel, September 1988.
-
- The GNU C Library is free software; you can redistribute it and/or
- modify it under the terms of the GNU Lesser General Public
- License as published by the Free Software Foundation; either
- version 2.1 of the License, or (at your option) any later version.
-
- The GNU C 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
- Lesser General Public License for more details.
-
- You should have received a copy of the GNU Lesser General Public
- License along with the GNU C Library; if not, see
- <http://www.gnu.org/licenses/>. */
-
-#include <alloca.h>
-#include <stdint.h>
-#include <stdlib.h>
-#include <string.h>
-#include <unistd.h>
-#include <memcopy.h>
-#include <errno.h>
-#include <atomic.h>
-
-struct msort_param
-{
- size_t s;
- size_t var;
- __compar_d_fn_t cmp;
- void *arg;
- char *t;
-};
-static void msort_with_tmp (const struct msort_param *p, void *b, size_t n);
-
-static void
-msort_with_tmp (const struct msort_param *p, void *b, size_t n)
-{
- char *b1, *b2;
- size_t n1, n2;
-
- if (n <= 1)
- return;
-
- n1 = n / 2;
- n2 = n - n1;
- b1 = b;
- b2 = (char *) b + (n1 * p->s);
-
- msort_with_tmp (p, b1, n1);
- msort_with_tmp (p, b2, n2);
-
- char *tmp = p->t;
- const size_t s = p->s;
- __compar_d_fn_t cmp = p->cmp;
- void *arg = p->arg;
- switch (p->var)
- {
- case 0:
- while (n1 > 0 && n2 > 0)
- {
- if ((*cmp) (b1, b2, arg) <= 0)
- {
- *(uint32_t *) tmp = *(uint32_t *) b1;
- b1 += sizeof (uint32_t);
- --n1;
- }
- else
- {
- *(uint32_t *) tmp = *(uint32_t *) b2;
- b2 += sizeof (uint32_t);
- --n2;
- }
- tmp += sizeof (uint32_t);
- }
- break;
- case 1:
- while (n1 > 0 && n2 > 0)
- {
- if ((*cmp) (b1, b2, arg) <= 0)
- {
- *(uint64_t *) tmp = *(uint64_t *) b1;
- b1 += sizeof (uint64_t);
- --n1;
- }
- else
- {
- *(uint64_t *) tmp = *(uint64_t *) b2;
- b2 += sizeof (uint64_t);
- --n2;
- }
- tmp += sizeof (uint64_t);
- }
- break;
- case 2:
- while (n1 > 0 && n2 > 0)
- {
- unsigned long *tmpl = (unsigned long *) tmp;
- unsigned long *bl;
-
- tmp += s;
- if ((*cmp) (b1, b2, arg) <= 0)
- {
- bl = (unsigned long *) b1;
- b1 += s;
- --n1;
- }
- else
- {
- bl = (unsigned long *) b2;
- b2 += s;
- --n2;
- }
- while (tmpl < (unsigned long *) tmp)
- *tmpl++ = *bl++;
- }
- break;
- case 3:
- while (n1 > 0 && n2 > 0)
- {
- if ((*cmp) (*(const void **) b1, *(const void **) b2, arg) <= 0)
- {
- *(void **) tmp = *(void **) b1;
- b1 += sizeof (void *);
- --n1;
- }
- else
- {
- *(void **) tmp = *(void **) b2;
- b2 += sizeof (void *);
- --n2;
- }
- tmp += sizeof (void *);
- }
- break;
- default:
- while (n1 > 0 && n2 > 0)
- {
- if ((*cmp) (b1, b2, arg) <= 0)
- {
- tmp = (char *) __mempcpy (tmp, b1, s);
- b1 += s;
- --n1;
- }
- else
- {
- tmp = (char *) __mempcpy (tmp, b2, s);
- b2 += s;
- --n2;
- }
- }
- break;
- }
-
- if (n1 > 0)
- memcpy (tmp, b1, n1 * s);
- memcpy (b, p->t, (n - n2) * s);
-}
-
-
-void
-__qsort_r (void *b, size_t n, size_t s, __compar_d_fn_t cmp, void *arg)
-{
- size_t size = n * s;
- char *tmp = NULL;
- struct msort_param p;
-
- /* For large object sizes use indirect sorting. */
- if (s > 32)
- size = 2 * n * sizeof (void *) + s;
-
- if (size < 1024)
- /* The temporary array is small, so put it on the stack. */
- p.t = __alloca (size);
- else
- {
- /* We should avoid allocating too much memory since this might
- have to be backed up by swap space. */
- static long int phys_pages;
- static int pagesize;
-
- if (pagesize == 0)
- {
- phys_pages = __sysconf (_SC_PHYS_PAGES);
-
- if (phys_pages == -1)
- /* Error while determining the memory size. So let's
- assume there is enough memory. Otherwise the
- implementer should provide a complete implementation of
- the `sysconf' function. */
- phys_pages = (long int) (~0ul >> 1);
-
- /* The following determines that we will never use more than
- a quarter of the physical memory. */
- phys_pages /= 4;
-
- /* Make sure phys_pages is written to memory. */
- atomic_write_barrier ();
-
- pagesize = __sysconf (_SC_PAGESIZE);
- }
-
- /* Just a comment here. We cannot compute
- phys_pages * pagesize
- and compare the needed amount of memory against this value.
- The problem is that some systems might have more physical
- memory then can be represented with a `size_t' value (when
- measured in bytes. */
-
- /* If the memory requirements are too high don't allocate memory. */
- if (size / pagesize > (size_t) phys_pages)
- {
- _quicksort (b, n, s, cmp, arg);
- return;
- }
-
- /* It's somewhat large, so malloc it. */
- int save = errno;
- tmp = malloc (size);
- __set_errno (save);
- if (tmp == NULL)
- {
- /* Couldn't get space, so use the slower algorithm
- that doesn't need a temporary array. */
- _quicksort (b, n, s, cmp, arg);
- return;
- }
- p.t = tmp;
- }
-
- p.s = s;
- p.var = 4;
- p.cmp = cmp;
- p.arg = arg;
-
- if (s > 32)
- {
- /* Indirect sorting. */
- char *ip = (char *) b;
- void **tp = (void **) (p.t + n * sizeof (void *));
- void **t = tp;
- void *tmp_storage = (void *) (tp + n);
-
- while ((void *) t < tmp_storage)
- {
- *t++ = ip;
- ip += s;
- }
- p.s = sizeof (void *);
- p.var = 3;
- msort_with_tmp (&p, p.t + n * sizeof (void *), n);
-
- /* tp[0] .. tp[n - 1] is now sorted, copy around entries of
- the original array. Knuth vol. 3 (2nd ed.) exercise 5.2-10. */
- char *kp;
- size_t i;
- for (i = 0, ip = (char *) b; i < n; i++, ip += s)
- if ((kp = tp[i]) != ip)
- {
- size_t j = i;
- char *jp = ip;
- memcpy (tmp_storage, ip, s);
-
- do
- {
- size_t k = (kp - (char *) b) / s;
- tp[j] = jp;
- memcpy (jp, kp, s);
- j = k;
- jp = kp;
- kp = tp[k];
- }
- while (kp != ip);
-
- tp[j] = jp;
- memcpy (jp, tmp_storage, s);
- }
- }
- else
- {
- if ((s & (sizeof (uint32_t) - 1)) == 0
- && ((char *) b - (char *) 0) % __alignof__ (uint32_t) == 0)
- {
- if (s == sizeof (uint32_t))
- p.var = 0;
- else if (s == sizeof (uint64_t)
- && ((char *) b - (char *) 0) % __alignof__ (uint64_t) == 0)
- p.var = 1;
- else if ((s & (sizeof (unsigned long) - 1)) == 0
- && ((char *) b - (char *) 0)
- % __alignof__ (unsigned long) == 0)
- p.var = 2;
- }
- msort_with_tmp (&p, b, n);
- }
- free (tmp);
-}
-libc_hidden_def (__qsort_r)
-weak_alias (__qsort_r, qsort_r)
-
-
-void
-qsort (void *b, size_t n, size_t s, __compar_fn_t cmp)
-{
- return __qsort_r (b, n, s, (__compar_d_fn_t) cmp, NULL);
-}
-libc_hidden_def (qsort)
diff --git a/stdlib/qsort.c b/stdlib/qsort.c
index 264a06b..b3a5102 100644
--- a/stdlib/qsort.c
+++ b/stdlib/qsort.c
@@ -20,7 +20,6 @@
Engineering a sort function; Jon Bentley and M. Douglas McIlroy;
Software - Practice and Experience; Vol. 23 (11), 1249-1265, 1993. */
-#include <alloca.h>
#include <limits.h>
#include <stdlib.h>
#include <string.h>
@@ -86,8 +85,8 @@ typedef struct
stack size is needed (actually O(1) in this case)! */
void
-_quicksort (void *const pbase, size_t total_elems, size_t size,
- __compar_d_fn_t cmp, void *arg)
+__qsort_r (void *const pbase, size_t total_elems, size_t size,
+ __compar_d_fn_t cmp, void *arg)
{
char *base_ptr = (char *) pbase;
@@ -247,3 +246,13 @@ _quicksort (void *const pbase, size_t total_elems, size_t size,
}
}
}
+
+libc_hidden_def (__qsort_r)
+weak_alias (__qsort_r, qsort_r)
+
+void
+qsort (void *b, size_t n, size_t s, __compar_fn_t cmp)
+{
+ return __qsort_r (b, n, s, (__compar_d_fn_t) cmp, NULL);
+}
+libc_hidden_def (qsort)
http://sourceware.org/git/gitweb.cgi?p=glibc.git;a=commitdiff;h=be32755802647035de2ac48dc6cf7bed8ade1cda
commit be32755802647035de2ac48dc6cf7bed8ade1cda
Author: Adhemerval Zanella <adhemerval.zanella@linaro.org>
Date: Thu Aug 31 20:24:03 2017 -0300
benchtests: Add bench-qsort
This patch adds a qsort benchmark. I tried to model the benchmark taking in
consideration the possible input variation in both internal element size,
element numbers, and internal state for 1. real word cases and 2. possible
scenarios based on hardware characteristics.
For 1. I tracked qsort usage (using a simple preload library to dump its usage
and a script to pos-process it) on both GCC bootstrap and Firefox. GCC 8
bootstrap build shows 51786641 call to qsort with the following characterics:
Key: number of elements:
key=2 : 39.74
key=3 : 19.23
key=4 : 9.77
key=1 : 8.44
key=0 : 6.60
key=5 : 4.40
key=7 : 2.37
key=6 : 2.25
key=9 : 1.48
key=8 : 0.97
Key: element size in bytes:
key=8 : 91.74
key=32 : 3.62
key=4 : 2.42
key=40 : 1.20
key=16 : 0.67
key=24 : 0.30
key=48 : 0.05
key=56 : 0.00
key=1 : 0.00
Key: total size (number of elements * element size):
key=16 : 35.98
key=24 : 18.67
key=32 : 9.79
key=8 : 8.28
key=0 : 6.60
key=40 : 4.21
key=64 : 3.15
key=48 : 2.24
key=56 : 2.15
key=80 : 1.45
So for GCC:
- 80% of total qsort usage are done with 10 elements of less.
- All usages are done element size of maximum of 56 bytes.
- 90% of calls are done with array of maximum size of 80 bytes or less.
The Firefox usage was done with 2 hours of usage, with first 10 minutes activelly
openning and closing different types of sites. It resulted in 21042 calls with
following characteristics:
Key: number of elements:
key=7 : 24.40
key=1 : 10.44
key=3 : 6.33
key=4 : 5.81
key=2 : 5.46
key=6 : 4.80
key=17 : 4.54
key=0 : 3.07
key=5 : 3.05
key=9 : 2.51
key=12 : 2.06
Key: element size in bytes:
key=8 : 94.49
key=28 : 4.40
key=2 : 0.70
key=16 : 0.19
key=36 : 0.07
key=12 : 0.07
key=40 : 0.07
key=24 : 0.03
Key: total size (number of elements * element size):
key=56 : 24.20
key=8 : 10.27
key=24 : 6.36
key=32 : 5.86
key=16 : 5.46
key=48 : 4.80
key=476 : 3.75
key=0 : 3.07
key=40 : 3.05
key=72 : 2.50
So for Firefox:
- 72% of total qsort usage are done with 18 elements of less.
- All usages are done element size of maximum of 40 bytes.
- 70% of calls are done with array of maximum size of 476 bytes or less.
For 2. I used the idea of a machine with 3 levels of cache with sizes
L1 32kb, L2 256kb, and L3 4096Kb.
It resulted in a benchmark with following traits:
* It checks four types of input arrays: sorted, mostly sorted, unsorted, and
repeated. For 'sorted' the array is already sorted, 'mostly sorted' the
array will have a certain number of random elements with random values
(current ratio used is 20%), for 'unsorted' the array will contain random
elements from full range based on used type, and for 'repeated' the array
will have random elements with a certain number (current ratio is 20%) of
a repeated element distributed randomly.
* Three elements sizes are checked: uint32_t, uint64_t, and an element with
32 bytes (but using the uint64_t comparison checks). These element sizes
are used to 1. to avoid include the comparison function itself and/or
memory copy in sort benchmark itself, and 2. because key of size_t are the
most used for both GCC and Firefox.
* Five different element numbers: 64 (which cover mostly of used element
sizes for both GCC and Firefox), 4096/8192 (which cover 32 KB of L1 for
32 and 64 bits), 32768/65536 (L2 with 256 KB), and 24288/1048576 (L3 with
4 MB). The sizes are configurable by --nelem option.
Checked on x86_64-linux-gnu
* benchtests/Makefile (stdlib-benchset): Add qsort.
* benchtests/bench-qsort.c: New file.
diff --git a/benchtests/Makefile b/benchtests/Makefile
index bcd6a9c..796ea91 100644
--- a/benchtests/Makefile
+++ b/benchtests/Makefile
@@ -66,7 +66,7 @@ LOCALES := en_US.UTF-8 tr_TR.UTF-8 cs_CZ.UTF-8 fa_IR.UTF-8 fr_FR.UTF-8 \
include ../gen-locales.mk
endif
-stdlib-benchset := strtod
+stdlib-benchset := strtod qsort
stdio-common-benchset := sprintf
diff --git a/benchtests/bench-qsort.c b/benchtests/bench-qsort.c
new file mode 100644
index 0000000..5394aac
--- /dev/null
+++ b/benchtests/bench-qsort.c
@@ -0,0 +1,343 @@
+/* Measure qsort function.
+ Copyright (C) 2018 Free Software Foundation, Inc.
+ This file is part of the GNU C Library.
+
+ The GNU C Library is free software; you can redistribute it and/or
+ modify it under the terms of the GNU Lesser General Public
+ License as published by the Free Software Foundation; either
+ version 2.1 of the License, or (at your option) any later version.
+
+ The GNU C 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
+ Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public
+ License along with the GNU C Library; if not, see
+ <http://www.gnu.org/licenses/>. */
+
+#include <stdlib.h>
+#include <string.h>
+#include <getopt.h>
+#include <unistd.h>
+#include <errno.h>
+#include <assert.h>
+
+#include "json-lib.h"
+#include "bench-timing.h"
+#include "bench-util.h"
+
+#include <support/test-driver.h>
+#include <support/support.h>
+#include <support/support_random.h>
+
+#define ARRAY_SIZE(A) (sizeof (A) / sizeof ((A)[0]))
+
+/* Type of inputs arrays:
+ - Sorted: array already sorted in placed.
+ - MostlySorted: sorted array with 'MostlySortedRatio * size' elements
+ in random positions set to random values.
+ - Unsorted: all elements in array set to random values.
+ - Repeated: random array with 'RepeatedRation' elements in random
+ positions set to an unique value. */
+typedef enum {
+ Sorted = 0,
+ MostlySorted = 1,
+ Unsorted = 2,
+ Repeated = 3,
+} arraytype_t;
+
+/* Ratio of total of elements which will randomized. */
+static const double MostlySortedRatio = 0.2;
+
+/* Ratio of total of elements which will be repeated. */
+static const double RepeatedRatio = 0.2;
+
+struct array_t
+{
+ arraytype_t type;
+ const char *name;
+};
+static struct array_t arraytypes[] =
+{
+ { Sorted, "Sorted" },
+ { Unsorted, "Unsorted" },
+ { MostlySorted, "MostlySorted" },
+ { Repeated, "Repeated" },
+};
+
+
+typedef int (*cmpfunc_t)(const void *, const void *);
+typedef void (*seq_element_t) (void *, size_t);
+
+static inline void *
+arr (void *base, size_t idx, size_t size)
+{
+ return (void*)((uintptr_t)base + (idx * size));
+}
+
+static support_random_state rand_state;
+
+static void *
+create_array (size_t nmemb, size_t type_size, arraytype_t type,
+ seq_element_t seq)
+{
+ assert (nmemb < UINT32_MAX);
+ size_t size = nmemb * type_size;
+ void *array = xmalloc (size);
+
+ switch (type)
+ {
+ case Sorted:
+ for (size_t i = 0; i < nmemb; i++)
+ seq (arr (array, i, type_size), i);
+ break;
+
+ case MostlySorted:
+ {
+ for (size_t i = 0; i < nmemb; i++)
+ seq (arr (array, i, type_size), i);
+
+ /* Change UNSORTED elements (based on MostlySortedRatio ratio)
+ in the sorted array. */
+ size_t unsorted = (size_t)(nmemb * MostlySortedRatio);
+ for (size_t i = 0; i < unsorted; i++)
+ {
+ size_t pos = support_random_uniform_distribution (&rand_state,
+ 0, nmemb - 1);
+ support_random_buf (&rand_state, arr (array, pos, type_size),
+ type_size);
+ }
+ }
+ break;
+
+ case Unsorted:
+ support_random_buf (&rand_state, array, size);
+ break;
+
+ case Repeated:
+ {
+ support_random_buf (&rand_state, array, size);
+
+ void *randelem = xmalloc (type_size);
+ support_random_buf (&rand_state, randelem, type_size);
+
+ /* Repeat REPEATED elements (based on RepeatRatio ratio) in the random
+ array. */
+ size_t repeated = (size_t)(nmemb * RepeatedRatio);
+ for (size_t i = 0; i < repeated; i++)
+ {
+ size_t pos = support_random_uniform_distribution (&rand_state,
+ 0, nmemb - 1);
+ memcpy (arr (array, pos, type_size), randelem, type_size);
+ }
+ free (randelem);
+ }
+ break;
+ }
+
+ return array;
+}
+
+/* Functions for uint32_t type. */
+static int
+cmp_uint32_t (const void *a, const void *b)
+{
+ uint32_t ia = *(uint32_t*)a;
+ uint32_t ib = *(uint32_t*)b;
+ return (ia > ib) - (ia < ib);
+}
+
+static void
+seq_uint32_t (void *base, size_t idx)
+{
+ *(uint32_t *)base = idx;
+}
+
+/* Functions for uint64_t type. */
+static int
+cmp_uint64_t (const void *a, const void *b)
+{
+ uint64_t ia = *(uint64_t*)a;
+ uint64_t ib = *(uint64_t*)b;
+ return (ia > ib) - (ia < ib);
+}
+
+static void
+seq_uint64_t (void *base, size_t idx)
+{
+ *(uint64_t *)base = idx;
+}
+
+/* Number of elements of determined type to be measured. */
+static const size_t default_elem[] =
+{
+ 256/sizeof(size_t), /* 64/128 which covers mostly used element number
+ on GCC build. */
+ 32768/sizeof(size_t), /* 4096/8192 to fit on a L1 with 32 KB. */
+ 262144/sizeof(size_t), /* 32768/65536 to fit on a L2 with 256 KB. */
+ 4194304/sizeof(size_t), /* 524288/1048576 to fix on a L3 with 4 MB. */
+};
+
+
+#define OPT_NELEM 10000
+#define OPT_SEED 10001
+#define CMDLINE_OPTIONS \
+ { "nelem", required_argument, NULL, OPT_NELEM }, \
+ { "seed", required_argument, NULL, OPT_SEED },
+
+static const size_t max_nelem = 16;
+static size_t *elems = NULL;
+static size_t nelem = 0;
+static uint64_t seed = 0;
+static bool seed_set = false;
+
+static void __attribute__ ((used))
+cmdline_process_function (int c)
+{
+ switch (c)
+ {
+ /* Handle the --nelem option to run different sizes than DEFAULT_ELEM.
+ The elements sizes as passed with a ':' as the delimiter, for
+ instance --nelem 32:128:1024 will ran 32, 128, and 1024 elements. */
+ case OPT_NELEM:
+ {
+ elems = xmalloc (max_nelem * sizeof (size_t));
+ nelem = 0;
+
+ char *saveptr;
+ char *token;
+ token = strtok_r (optarg, ":", &saveptr);
+ if (token == NULL)
+ {
+ printf ("error: invalid --nelem value\n");
+ exit (EXIT_FAILURE);
+ }
+ do
+ {
+ if (nelem == max_nelem)
+ {
+ printf ("error: invalid --nelem value (max elem)\n");
+ exit (EXIT_FAILURE);
+ }
+ elems[nelem++] = atol (token);
+ token = strtok_r (saveptr, ":", &saveptr);
+ } while (token != NULL);
+ }
+ break;
+
+ /* handle the --seed option to use a different seed than a random one.
+ The SEED used should be a uint64_t number. */
+ case OPT_SEED:
+ {
+ uint64_t value = strtoull (optarg, NULL, 0);
+ if (errno == ERANGE || value > UINT64_MAX)
+ {
+ printf ("error: seed should be a value in range of "
+ "[0, UINT64_MAX]\n");
+ exit (EXIT_FAILURE);
+ }
+ seed = value;
+ seed_set = true;
+ }
+ }
+}
+
+#define CMDLINE_PROCESS cmdline_process_function
+
+static const size_t inner_loop_iters = 16;
+
+struct run_t
+{
+ size_t type_size;
+ cmpfunc_t cmp;
+ seq_element_t seq;
+};
+static const struct run_t runs[] =
+{
+ { sizeof (uint32_t), cmp_uint32_t, seq_uint32_t },
+ { sizeof (uint64_t), cmp_uint64_t, seq_uint64_t },
+ { 32, cmp_uint64_t, seq_uint64_t },
+};
+
+static int
+do_test (void)
+{
+ if (seed_set)
+ support_random_seed (&rand_state, seed);
+ else
+ support_random_rseed (&rand_state);
+
+ json_ctx_t json_ctx;
+
+ json_init (&json_ctx, 0, stdout);
+
+ json_document_begin (&json_ctx);
+ json_attr_string (&json_ctx, "timing_type", TIMING_TYPE);
+
+ json_attr_object_begin (&json_ctx, "functions");
+ json_attr_object_begin (&json_ctx, "qsort");
+ json_attr_uint (&json_ctx, "seed", seed);
+
+ json_array_begin (&json_ctx, "results");
+
+ const size_t *welem = elems == NULL ? default_elem : elems;
+ const size_t wnelem = elems == NULL ? ARRAY_SIZE (default_elem)
+ : nelem;
+
+ for (int j = 0; j < ARRAY_SIZE (runs); j++)
+ {
+ for (int i = 0; i < ARRAY_SIZE (arraytypes); i++)
+ {
+ for (int k = 0; k < wnelem; k++)
+ {
+ json_element_object_begin (&json_ctx);
+
+ size_t nmemb = welem[k];
+ size_t ts = runs[j].type_size;
+ size_t arraysize = nmemb * ts;
+
+ json_attr_uint (&json_ctx, "nmemb", nmemb);
+ json_attr_uint (&json_ctx, "type_size", ts);
+ json_attr_string (&json_ctx, "property", arraytypes[i].name);
+
+ void *base = create_array (nmemb, ts, arraytypes[i].type, runs[j].seq);
+ void *work = xmalloc (arraysize);
+
+ timing_t total;
+ TIMING_INIT (total);
+
+ for (int n = 0; n < inner_loop_iters; n++)
+ {
+ memcpy (work, base, arraysize);
+
+ timing_t start, end, diff;
+ TIMING_NOW (start);
+ qsort (work, nmemb, ts, runs[j].cmp);
+ TIMING_NOW (end);
+
+ TIMING_DIFF (diff, start, end);
+ TIMING_ACCUM (total, diff);
+ }
+
+ json_attr_uint (&json_ctx, "timings",
+ (double) total / (double) inner_loop_iters);
+ json_element_object_end (&json_ctx);
+
+ free (base);
+ free (work);
+ }
+ }
+ }
+
+ json_array_end (&json_ctx);
+
+ json_attr_object_end (&json_ctx);
+ json_attr_object_end (&json_ctx);
+ json_document_end (&json_ctx);
+
+ return 0;
+}
+
+#define TIMEOUT 600
+#include <support/test-driver.c>
http://sourceware.org/git/gitweb.cgi?p=glibc.git;a=commitdiff;h=55365d62b7f86c00ddf1554289938e5ac795683b
commit 55365d62b7f86c00ddf1554289938e5ac795683b
Author: Adhemerval Zanella <adhemerval.zanella@linaro.org>
Date: Mon Jan 15 09:20:30 2018 -0200
stdlib: Add more qsort{_r} coverage
This patch adds a qsort and qsort_t (which glibc current lacks
coverage). The test check with random input (created using support
random) with different internal types (uint8_t, uint16_t, uint32_t,
and uint64_t) and with different set of element numbers (from 0
to 262144).
Checked on x86_64-linux-gnu.
* stdlib/tst-qsort3.c: New file.
* stdlib/Makefile (tests): Add tst-qsort3.
diff --git a/stdlib/Makefile b/stdlib/Makefile
index 01194bb..4e012a8 100644
--- a/stdlib/Makefile
+++ b/stdlib/Makefile
@@ -87,7 +87,7 @@ tests := tst-strtol tst-strtod testmb testrand testsort testdiv \
tst-makecontext-align test-bz22786 tst-strtod-nan-sign \
tst-swapcontext1 tst-setcontext4 tst-setcontext5 \
tst-setcontext6 tst-setcontext7 tst-setcontext8 \
- tst-setcontext9
+ tst-setcontext9 tst-qsort3
tests-internal := tst-strtod1i tst-strtod3 tst-strtod4 tst-strtod5i \
tst-tls-atexit tst-tls-atexit-nodelete
diff --git a/stdlib/tst-qsort3.c b/stdlib/tst-qsort3.c
new file mode 100644
index 0000000..26db0c2
--- /dev/null
+++ b/stdlib/tst-qsort3.c
@@ -0,0 +1,235 @@
+/* qsort(_r) generic tests.
+ Copyright (C) 2017 Free Software Foundation, Inc.
+ This file is part of the GNU C Library.
+
+ The GNU C Library is free software; you can redistribute it and/or
+ modify it under the terms of the GNU Lesser General Public
+ License as published by the Free Software Foundation; either
+ version 2.1 of the License, or (at your option) any later version.
+
+ The GNU C 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
+ Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public
+ License along with the GNU C Library; if not, see
+ <http://www.gnu.org/licenses/>. */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdint.h>
+#include <getopt.h>
+#include <errno.h>
+#include <stdbool.h>
+
+#include <support/check.h>
+#include <support/support.h>
+#include <support/support_random.h>
+#include <support/test-driver.h>
+
+/* Functions used to check qsort. */
+static int
+uint8_t_cmp (const void *a, const void *b)
+{
+ uint8_t ia = *(uint8_t*)a;
+ uint8_t ib = *(uint8_t*)b;
+ return (ia > ib) - (ia < ib);
+}
+
+static int
+uint16_t_cmp (const void *a, const void *b)
+{
+ uint16_t ia = *(uint16_t*)a;
+ uint16_t ib = *(uint16_t*)b;
+ return (ia > ib) - (ia < ib);
+}
+
+static int
+uint32_t_cmp (const void *a, const void *b)
+{
+ uint32_t ia = *(uint32_t*)a;
+ uint32_t ib = *(uint32_t*)b;
+ return (ia > ib) - (ia < ib);
+}
+
+static int
+uint64_t_cmp (const void *a, const void *b)
+{
+ uint64_t ia = *(uint64_t*)a;
+ uint64_t ib = *(uint64_t*)b;
+ return (ia > ib) - (ia < ib);
+}
+
+/* Function used to check qsort_r. */
+
+enum type_cmp_t
+{
+ UINT8_CMP_T = 0,
+ UINT16_CMP_T = 1,
+ UINT32_CMP_T = 2,
+ UINT64_CMP_T = 3,
+};
+
+static enum type_cmp_t
+uint_t_cmp_type (size_t sz)
+{
+ switch (sz)
+ {
+ case sizeof (uint8_t): return UINT8_CMP_T;
+ case sizeof (uint16_t): return UINT16_CMP_T;
+ case sizeof (uint64_t): return UINT64_CMP_T;
+ case sizeof (uint32_t):
+ default: return UINT32_CMP_T;
+ }
+}
+
+static int
+uint_t_cmp (const void *a, const void *b, void *arg)
+{
+ enum type_cmp_t type = *(enum type_cmp_t*) arg;
+ switch (type)
+ {
+ case UINT8_CMP_T: return uint8_t_cmp (a, b);
+ case UINT16_CMP_T: return uint16_t_cmp (a, b);
+ case UINT64_CMP_T: return uint64_t_cmp (a, b);
+ case UINT32_CMP_T:
+ default: return uint32_t_cmp (a, b);
+ }
+}
+
+static support_random_state rand_state;
+
+static void *
+create_array (size_t nmemb, size_t type_size)
+{
+ size_t size = nmemb * type_size;
+ uint8_t *array = xmalloc (size);
+ support_random_buf (&rand_state, array, size);
+ return array;
+}
+
+typedef int (*cmpfunc_t)(const void *, const void *);
+
+static void
+check_array (void *array, size_t nmemb, size_t type_size,
+ cmpfunc_t cmpfunc)
+{
+ for (size_t i = 1; i < nmemb; i++)
+ {
+ void *array_i = (void*)((uintptr_t)array + i * type_size);
+ void *array_i_1 = (void*)((uintptr_t)array + (i-1) * type_size);
+ int ret;
+ TEST_VERIFY ((ret = cmpfunc (array_i, array_i_1)) >= 0);
+ if (ret < 0)
+ break;
+ }
+}
+
+static uint32_t seed;
+static bool seed_set = false;
+
+#define OPT_SEED 10000
+#define CMDLINE_OPTIONS \
+ { "seed", required_argument, NULL, OPT_SEED },
+
+static void __attribute__ ((used))
+cmdline_process_function (int c)
+{
+ switch (c)
+ {
+ case OPT_SEED:
+ {
+ unsigned long int value = strtoul (optarg, NULL, 0);
+ if (errno == ERANGE || value > UINT32_MAX)
+ {
+ printf ("error: seed should be a value in range of "
+ "[0, UINT32_MAX]\n");
+ exit (EXIT_FAILURE);
+ }
+ seed = value;
+ seed_set = true;
+ }
+ break;
+ }
+}
+
+#define CMDLINE_PROCESS cmdline_process_function
+
+
+static int
+do_test (void)
+{
+ if (test_verbose > 0)
+ printf ("info: seed=0x%08x\n", seed);
+ if (seed_set)
+ support_random_seed (&rand_state, seed);
+ else
+ support_random_rseed (&rand_state);
+
+ const size_t elem[] = { 0, 1, 64, 128, 4096, 16384, 262144 };
+ const size_t nelem = sizeof (elem) / sizeof (elem[0]);
+
+ struct test_t
+ {
+ size_t type_size;
+ cmpfunc_t cmpfunc;
+ }
+ tests[] =
+ {
+ { sizeof (uint8_t), uint8_t_cmp },
+ { sizeof (uint16_t), uint16_t_cmp },
+ { sizeof (uint32_t), uint32_t_cmp },
+ { sizeof (uint64_t), uint64_t_cmp },
+ /* Test swap with large elements. */
+ { 32, uint32_t_cmp },
+ };
+ size_t ntests = sizeof (tests) / sizeof (tests[0]);
+
+ for (size_t i = 0; i < ntests; i++)
+ {
+ size_t ts = tests[i].type_size;
+ if (test_verbose > 0)
+ printf ("info: testing qsort with type_size=%zu\n", ts);
+ for (size_t n = 0; n < nelem; n++)
+ {
+ size_t nmemb = elem[n];
+ if (test_verbose > 0)
+ printf (" nmemb=%zu, total size=%zu\n", nmemb, nmemb * ts);
+
+ void *array = create_array (nmemb, ts);
+
+ qsort (array, nmemb, ts, tests[i].cmpfunc);
+
+ check_array (array, nmemb, ts, tests[i].cmpfunc);
+
+ free (array);
+ }
+ }
+
+ for (size_t i = 0; i < ntests; i++)
+ {
+ size_t ts = tests[i].type_size;
+ if (test_verbose > 0)
+ printf ("info: testing qsort_r type_size=%zu\n", ts);
+ for (size_t n = 0; n < nelem; n++)
+ {
+ size_t nmemb = elem[n];
+ if (test_verbose > 0)
+ printf (" nmemb=%zu, total size=%zu\n", nmemb, nmemb * ts);
+
+ void *array = create_array (nmemb, ts);
+
+ enum type_cmp_t type = uint_t_cmp_type (ts);
+ qsort_r (array, nmemb, ts, uint_t_cmp, &type);
+
+ check_array (array, nmemb, ts, tests[i].cmpfunc);
+
+ free (array);
+ }
+ }
+
+ return 0;
+}
+
+#include <support/test-driver.c>
http://sourceware.org/git/gitweb.cgi?p=glibc.git;a=commitdiff;h=67d73eff7657b74ac1f42c85ce9892d0ad39ff8d
commit 67d73eff7657b74ac1f42c85ce9892d0ad39ff8d
Author: Adhemerval Zanella <adhemerval.zanella@linaro.org>
Date: Mon Dec 25 10:53:13 2017 -0200
support: Add pseudo-random number generator interface
This is based on POSIX mrand48 and the interfaces provided is just
to wrap around common usages (buffer fill and uniform distribution).
Although better PNRGs exists, the already in place POSIXs one is
used for simplicity and because a better de factor one is being
discussed for inclusion (arc4random based on AES-CTR). Ideally it
would replace the mrand48 usage for this interface.
Checked on x86_64-linux-gnu.
* support/Makefile (libsupport-routines): Add support_random.
(tests): Add tst-support_random.
* support/support_random.c: New file.
* support/support_random.h: Likewise.
diff --git a/support/Makefile b/support/Makefile
index 9063046..db46be6 100644
--- a/support/Makefile
+++ b/support/Makefile
@@ -56,6 +56,7 @@ libsupport-routines = \
support_openpty \
support_quote_blob \
support_record_failure \
+ support_random \
support_run_diff \
support_shared_allocate \
support_test_compare_blob \
@@ -161,7 +162,7 @@ tests = \
tst-support_record_failure \
tst-test_compare \
tst-test_compare_blob \
- tst-xreadlink \
+ tst-xreadlink
ifeq ($(run-built-tests),yes)
tests-special = \
diff --git a/support/support_random.c b/support/support_random.c
new file mode 100644
index 0000000..5feee1a
--- /dev/null
+++ b/support/support_random.c
@@ -0,0 +1,90 @@
+/* Function for pseudo-random number generation.
+ Copyright (C) 2018 Free Software Foundation, Inc.
+ This file is part of the GNU C Library.
+
+ The GNU C Library is free software; you can redistribute it and/or
+ modify it under the terms of the GNU Lesser General Public
+ License as published by the Free Software Foundation; either
+ version 2.1 of the License, or (at your option) any later version.
+
+ The GNU C 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
+ Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public
+ License along with the GNU C Library; if not, see
+ <http://www.gnu.org/licenses/>. */
+
+#include <assert.h>
+#include <fcntl.h>
+#include <unistd.h>
+#include <string.h>
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <sys/random.h>
+
+#include <support/support_random.h>
+#include <support/check.h>
+#include <support/xunistd.h>
+
+void
+support_random_seed (support_random_state *state, uint32_t seed)
+{
+ unsigned short int seed16v[3] = { 0 };
+ memcpy (seed16v, &seed, sizeof (seed));
+ seed48_r (seed16v, state);
+}
+
+void
+support_random_rseed (support_random_state *state)
+{
+ unsigned short int buf[3];
+ size_t len = sizeof buf;
+
+ ssize_t ret = getrandom (buf, len, 0);
+ if (ret != len)
+ {
+ int fd = xopen ("/dev/urandom", O_RDONLY, 0);
+ uintptr_t pbuf = (uintptr_t) buf;
+ uintptr_t pend = pbuf + len;
+ while (pbuf < pend)
+ {
+ ret = read (fd, buf, pend - pbuf);
+ if (ret <= 0)
+ FAIL_EXIT1 ("read %zu bytes from /dev/urandom failed: %m",
+ pend - pbuf);
+ pbuf += ret;
+ }
+ close (fd);
+ }
+
+ seed48_r (buf, state);
+}
+
+uint32_t
+support_random_u32 (support_random_state *state)
+{
+ long int rl;
+ mrand48_r (state, &rl);
+ return rl;
+}
+
+void
+support_random_buf (support_random_state *state, void *buf, size_t nbytes)
+{
+ size_t nw = nbytes / sizeof (uint32_t);
+ for (size_t i = 0; i < nw; i++)
+ {
+ uint32_t r = support_random_u32 (state);
+ memcpy (buf, &r, sizeof (uint32_t));
+ buf = (void*)((uintptr_t)buf + sizeof (uint32_t));
+ }
+
+ size_t nb = nbytes % sizeof (uint32_t);
+ if (nb != 0)
+ {
+ uint32_t r = support_random_u32 (state);
+ memcpy (buf, &r, nb);
+ }
+}
diff --git a/support/support_random.h b/support/support_random.h
new file mode 100644
index 0000000..8224c2b
--- /dev/null
+++ b/support/support_random.h
@@ -0,0 +1,59 @@
+/* Function for pseudo-random number generation.
+ Copyright (C) 2018 Free Software Foundation, Inc.
+ This file is part of the GNU C Library.
+
+ The GNU C Library is free software; you can redistribute it and/or
+ modify it under the terms of the GNU Lesser General Public
+ License as published by the Free Software Foundation; either
+ version 2.1 of the License, or (at your option) any later version.
+
+ The GNU C 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
+ Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public
+ License along with the GNU C Library; if not, see
+ <http://www.gnu.org/licenses/>. */
+
+#ifndef SUPPORT_MT_RAND_H
+#define SUPPORT_MT_RAND_H
+
+#include <stdint.h>
+#include <stdlib.h>
+
+typedef struct drand48_data support_random_state;
+
+void support_random_seed (support_random_state *state, uint32_t seed);
+void support_random_rseed (support_random_state *state);
+
+uint32_t support_random_u32 (support_random_state *state);
+void support_random_buf (support_random_state *state, void *buf,
+ size_t nbytes);
+
+/* Scales the number NUMBER to the uniformly distributed closed internal
+ [min, max]. */
+static inline uint32_t
+support_random_uniform_distribution (support_random_state *state,
+ uint32_t min, uint32_t max)
+{
+ uint32_t ret;
+ uint32_t range = max - min;
+ /* It assumes the input random number RANDOM range is as larger or equal
+ than the RANGE, so the result will either returned or downscaled. */
+ if (range != UINT32_MAX)
+ {
+ uint32_t urange = range + 1; /* range can be 0. */
+ uint32_t scaling = UINT32_MAX / urange;
+ uint32_t past = urange * scaling;
+ do
+ ret = support_random_u32 (state);
+ while (ret >= past);
+ ret /= scaling;
+ }
+ else
+ ret = support_random_u32 (state);
+ return ret + min;
+}
+
+#endif
http://sourceware.org/git/gitweb.cgi?p=glibc.git;a=commitdiff;h=8f4ff21990502b3420689620f9f67631e25d27dc
commit 8f4ff21990502b3420689620f9f67631e25d27dc
Author: Adhemerval Zanella <adhemerval.zanella@linaro.org>
Date: Fri Dec 15 09:49:37 2017 -0200
stdlib: Adjust tst-qsort{2} to libsupport
* stdlib/tst-qsort.c: Use libsupport.
* stdlib/tst-qsort2.c: Likewise.
diff --git a/stdlib/tst-qsort.c b/stdlib/tst-qsort.c
index 2b26e74..c3230fd 100644
--- a/stdlib/tst-qsort.c
+++ b/stdlib/tst-qsort.c
@@ -3,6 +3,8 @@
#include <stdlib.h>
#include <tst-stack-align.h>
+#include <support/check.h>
+
struct big { char c[4 * 1024]; };
struct big *array;
@@ -10,7 +12,7 @@ struct big *array_end;
static int align_check;
-int
+static int
compare (void const *a1, void const *b1)
{
struct big const *a = a1;
@@ -19,37 +21,34 @@ compare (void const *a1, void const *b1)
if (!align_check)
align_check = TEST_STACK_ALIGN () ? -1 : 1;
- if (! (array <= a && a < array_end
- && array <= b && b < array_end))
- {
- exit (EXIT_FAILURE);
- }
- return b->c[0] - a->c[0];
+ TEST_VERIFY_EXIT (array <= a && a < array_end
+ && array <= b && b < array_end);
+
+ return (b->c[0] - a->c[0]) > 0;
}
int
-main (int argc, char **argv)
+do_test (void)
{
- size_t i;
- size_t array_members = argv[1] ? atoi (argv[1]) : 50;
- array = (struct big *) malloc (array_members * sizeof *array);
- if (array == NULL)
+ const size_t sizes[] = { 8, 16, 24, 48, 96, 192, 384 };
+ const size_t sizes_len = sizeof (sizes) / sizeof (sizes[0]);
+
+ for (size_t s = 0; s < sizes_len; s++)
{
- puts ("no memory");
- exit (EXIT_FAILURE);
- }
+ array = (struct big *) malloc (sizes[s] * sizeof *array);
+ TEST_VERIFY_EXIT (array != NULL);
- array_end = array + array_members;
- for (i = 0; i < array_members; i++)
- array[i].c[0] = i % 128;
+ array_end = array + sizes[s];
+ for (size_t i = 0; i < sizes[s]; i++)
+ array[i].c[0] = i % 128;
- qsort (array, array_members, sizeof *array, compare);
+ qsort (array, sizes[s], sizeof *array, compare);
+ TEST_VERIFY_EXIT (align_check != -1);
- if (align_check == -1)
- {
- puts ("stack not sufficiently aligned");
- exit (EXIT_FAILURE);
+ free (array);
}
return 0;
}
+
+#include <support/test-driver.c>
diff --git a/stdlib/tst-qsort2.c b/stdlib/tst-qsort2.c
index 10d1685..595875d 100644
--- a/stdlib/tst-qsort2.c
+++ b/stdlib/tst-qsort2.c
@@ -1,11 +1,13 @@
#include <stdio.h>
#include <stdlib.h>
-char *array;
-char *array_end;
-size_t member_size;
+#include <support/check.h>
-int
+static char *array;
+static char *array_end;
+static size_t member_size;
+
+static int
compare (const void *a1, const void *b1)
{
const char *a = a1;
@@ -25,7 +27,7 @@ compare (const void *a1, const void *b1)
return 0;
}
-int
+static int
test (size_t nmemb, size_t size)
{
array = malloc (nmemb * size);
@@ -66,24 +68,20 @@ test (size_t nmemb, size_t size)
return 0;
}
-int
-main (int argc, char **argv)
+static int
+do_test (void)
{
- int ret = 0;
- if (argc >= 3)
- ret |= test (atoi (argv[1]), atoi (argv[2]));
- else
- {
- ret |= test (10000, 1);
- ret |= test (200000, 2);
- ret |= test (2000000, 3);
- ret |= test (2132310, 4);
- ret |= test (1202730, 7);
- ret |= test (1184710, 8);
- ret |= test (272710, 12);
- ret |= test (14170, 32);
- ret |= test (4170, 320);
- }
+ test (10000, 1);
+ test (200000, 2);
+ test (2000000, 3);
+ test (2132310, 4);
+ test (1202730, 7);
+ test (1184710, 8);
+ test (272710, 12);
+ test (14170, 32);
+ test (4170, 320);
- return ret;
+ return 0;
}
+
+#include <support/test-driver.c>
-----------------------------------------------------------------------
hooks/post-receive
--
GNU C Library master sources