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.26.9000-1134-gce67791
- From: azanella at sourceware dot org
- To: glibc-cvs at sourceware dot org
- Date: 23 Jan 2018 18:46:35 -0000
- Subject: GNU C Library master sources branch azanella/qsort-refactor created. glibc-2.26.9000-1134-gce67791
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 ce67791dececc810a701814eea472d086f624ab4 (commit)
- Log -----------------------------------------------------------------
http://sourceware.org/git/gitweb.cgi?p=glibc.git;a=commitdiff;h=ce67791dececc810a701814eea472d086f624ab4
commit ce67791dececc810a701814eea472d086f624ab4
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 8cdc21c..77aa2e7 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);
@@ -98,202 +94,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 67%
copy from stdlib/qsort.c
copy to stdlib/qsort_common.c
index 8cdc21c..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,84 +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)
-{
- unsigned char tmp[128];
- do
- {
- size_t s = size > sizeof (tmp) ? sizeof (tmp) : size;
- memcpy (tmp, a, s);
- a = __mempcpy (a, b, s);
- b = __mempcpy (b, tmp, s);
- size -= s;
- }
- while (size > 0);
-}
-
-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:
@@ -124,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)
@@ -159,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:;
@@ -177,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)
@@ -240,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
@@ -253,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)
@@ -265,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;
@@ -288,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=fd3d9f81068303bb501cccddc80037d4df8c78b7
commit fd3d9f81068303bb501cccddc80037d4df8c78b7
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
Sorted
nmemb | base | patched | diff
32| 1401 | 1958 | 39.76
4096| 351333 | 368533 | 4.90
32768| 3369386 | 3131712 | -7.05
524288| 63192972 | 59807494 | -5.36
MostlySorted
nmemb | base | patched | diff
32| 2391 | 2061 | -13.80
4096| 1124074 | 961816 | -14.43
32768| 11196607 | 9410438 | -15.95
524288| 215908169 | 185586732 | -14.04
Unsorted
nmemb | base | patched | diff
32| 4993 | 2021 | -59.52
4096| 1113860 | 963126 | -13.53
32768| 11251293 | 9518795 | -15.40
524288| 217252237 | 185072278 | -14.81
Results for member size 8
Sorted
nmemb | base | patched | diff
32| 1296 | 1267 | -2.24
4096| 359418 | 334852 | -6.83
32768| 3535229 | 3345157 | -5.38
524288| 69847251 | 67029358 | -4.03
MostlySorted
nmemb | base | patched | diff
32| 2745 | 2340 | -14.75
4096| 1222082 | 1014314 | -17.00
32768| 12244800 | 9924706 | -18.95
524288| 241557971 | 196898760 | -18.49
Unsorted
nmemb | base | patched | diff
32| 2972 | 2389 | -19.62
4096| 1314861 | 1024052 | -22.12
32768| 12397909 | 10120848 | -18.37
524288| 241789262 | 193414824 | -20.01
Results for member size 32
Sorted
nmemb | base | patched | diff
32| 1305 | 1287 | -1.38
4096| 346332 | 347979 | 0.48
32768| 3458244 | 3408058 | -1.45
524288| 72793445 | 69973719 | -3.87
MostlySorted
nmemb | base | patched | diff
32| 5435 | 4890 | -10.03
4096| 2032260 | 1688556 | -16.91
32768| 19909035 | 16419992 | -17.52
524288| 390339319 | 325921585 | -16.50
Unsorted
nmemb | base | patched | diff
32| 5833 | 5351 | -8.26
4096| 2022531 | 1724961 | -14.71
32768| 19842888 | 16588545 | -16.40
524288| 388838382 | 324102703 | -16.65
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..8cdc21c 100644
--- a/stdlib/qsort.c
+++ b/stdlib/qsort.c
@@ -23,20 +23,59 @@
#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)
+{
+ unsigned char tmp[128];
+ do
+ {
+ size_t s = size > sizeof (tmp) ? sizeof (tmp) : size;
+ memcpy (tmp, a, s);
+ a = __mempcpy (a, b, s);
+ b = __mempcpy (b, tmp, s);
+ size -= s;
+ }
+ while (size > 0);
+}
+
+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 +135,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 +160,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 +185,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 +257,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=400d842ed9e6a13f616ff12fa7a2400c20495c3c
commit 400d842ed9e6a13f616ff12fa7a2400c20495c3c
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
qsort 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-4790K, gcc 7.2.1) shows the performance difference
between mergesort (base) and quicksort (patched):
Results for member size 4
Sorted
nmemb | base | patched | diff
32| 1447 | 1401 | -3.18
4096| 315978 | 351333 | 11.19
32768| 2559093 | 3369386 | 31.66
524288| 46228488 | 63192972 | 36.70
MostlySorted
nmemb | base | patched | diff
32| 1974 | 2391 | 21.12
4096| 922332 | 1124074 | 21.87
32768| 9268671 | 11196607 | 20.80
524288| 186856297 | 215908169 | 15.55
Unsorted
nmemb | base | patched | diff
32| 1978 | 4993 | 152.43
4096| 916413 | 1113860 | 21.55
32768| 9270003 | 11251293 | 21.37
524288| 187606088 | 217252237 | 15.80
Results for member size 8
Sorted
nmemb | base | patched | diff
32| 1424 | 1296 | -8.99
4096| 299105 | 359418 | 20.16
32768| 2737859 | 3535229 | 29.12
524288| 53082807 | 69847251 | 31.58
MostlySorted
nmemb | base | patched | diff
32| 2129 | 2745 | 28.93
4096| 969465 | 1222082 | 26.06
32768| 9605227 | 12244800 | 27.48
524288| 193353927 | 241557971 | 24.93
Unsorted
nmemb | base | patched | diff
32| 2194 | 2972 | 35.46
4096| 958610 | 1314861 | 37.16
32768| 9664246 | 12397909 | 28.29
524288| 193758429 | 241789262 | 24.79
Results for member size 32
Sorted
nmemb | base | patched | diff
32| 4477 | 1305 | -70.85
4096| 1109492 | 346332 | -68.78
32768| 11075976 | 3458244 | -68.78
524288| 230773658 | 72793445 | -68.46
MostlySorted
nmemb | base | patched | diff
32| 5905 | 5435 | -7.96
4096| 2568895 | 2032260 | -20.89
32768| 24936755 | 19909035 | -20.16
524288| 526442900 | 390339319 | -25.85
Unsorted
nmemb | base | patched | diff
32| 6004 | 5833 | -2.85
4096| 2437943 | 2022531 | -17.04
32768| 24789971 | 19842888 | -19.96
524288| 525898556 | 388838382 | -26.06
An increase in latency, however some performance difference is due the fact
mergesort uses a slight improved swap operation than quicksort (which following
patch addresses). This change also renders the BZ #21719 fix unrequired (since
it is to fix the sorted input performance degradation for mergesort). The
manual is also updated to indicate the function is not 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 60ad2a1..9e742e4 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 6ef20a7..a39a176 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 \
@@ -135,10 +135,9 @@ 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-bsearch.c = $(uses-callbacks)
+CFLAGS-qsort.c = $(uses-callbacks)
+CFLAGS-system.c = -fexceptions
CFLAGS-system.os = -fomit-frame-pointer
CFLAGS-fmtmsg.c += -fexceptions
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)
-----------------------------------------------------------------------
hooks/post-receive
--
GNU C Library master sources