diff options
| author | Adhemerval Zanella <adhemerval.zanella@linaro.org> | 2018-09-03 15:30:15 -0300 |
|---|---|---|
| committer | Adhemerval Zanella <adhemerval.zanella@linaro.org> | 2018-09-04 15:45:12 -0300 |
| commit | 367e56edc8b0a2d2eefbe4875d81caa82fe82654 (patch) | |
| tree | 2e6330f087244712ae5a4cabd172fb607db47e54 /io/tst-fchmodat.c | |
| parent | d3960af570f708e3f3a6c8a7c2d292f55d4d1da4 (diff) | |
| download | glibc-azanella/qsort-refactor.tar.gz | |
stdlib: Implement introsort with qsortazanella/qsort-refactor
This patch adds a introsort implementation on qsort to avoid worse-case
performance of quicksort to O(nlog n). The fallback used is a simple
heapsort based on Linux implementation. As a side note the introsort
implementation is similar the one used on libstdc++ for std::sort.
The performance shown some regression due heapsort usage, as expected:
Results for member size 4
MostlySorted
nmemb | base | patched | diff
32 | 1809 | 2034 | 12.44
4096 | 796888 | 1051955 | 32.01
32768 | 7616495 | 10820159 | 42.06
524288 | 142093487 | 250602727 | 76.36
Repeated
nmemb | base | patched | diff
32 | 1875 | 2046 | 9.12
4096 | 912206 | 1123392 | 23.15
32768 | 8690714 | 10223479 | 17.64
524288 | 171229868 | 287344355 | 67.81
Sorted
nmemb | base | patched | diff
32 | 1367 | 1354 | -0.95
4096 | 341229 | 1153712 | 238.10
32768 | 3358312 | 10983978 | 227.07
524288 | 66206257 | 232996299 | 251.92
Unsorted
nmemb | base | patched | diff
32 | 2182 | 2209 | 1.24
4096 | 990920 | 1101897 | 11.20
32768 | 10119221 | 11319451 | 11.86
524288 | 188297819 | 295723362 | 57.05
Results for member size 8
MostlySorted
nmemb | base | patched | diff
32 | 1976 | 2061 | 4.30
4096 | 720747 | 1048324 | 45.45
32768 | 7161384 | 10927694 | 52.59
524288 | 133265602 | 264259752 | 98.30
Repeated
nmemb | base | patched | diff
32 | 2123 | 2265 | 6.69
4096 | 913059 | 1124658 | 23.17
32768 | 8785972 | 11353472 | 29.22
524288 | 171667139 | 303675135 | 76.90
Sorted
nmemb | base | patched | diff
32 | 1193 | 1128 | -5.45
4096 | 301818 | 1101787 | 265.05
32768 | 2961904 | 10964479 | 270.18
524288 | 58873679 | 230789472 | 292.01
Unsorted
nmemb | base | patched | diff
32 | 2099 | 2407 | 14.67
4096 | 1024575 | 1154641 | 12.69
32768 | 10017934 | 11635442 | 16.15
524288 | 188778771 | 310044501 | 64.24
Results for member size 32
MostlySorted
nmemb | base | patched | diff
32 | 3864 | 4423 | 14.47
4096 | 1102305 | 1898226 | 72.21
32768 | 9915730 | 19176780 | 93.40
524288 | 193398884 | 478171367 | 147.25
Repeated
nmemb | base | patched | diff
32 | 4636 | 3730 | -19.54
4096 | 1359433 | 1847693 | 35.92
32768 | 13028460 | 19120804 | 46.76
524288 | 251463610 | 571423413 | 127.24
Sorted
nmemb | base | patched | diff
32 | 1223 | 1165 | -4.74
4096 | 310945 | 1922987 | 518.43
32768 | 2975730 | 19160622 | 543.90
524288 | 63995389 | 423600523 | 561.92
Unsorted
nmemb | base | patched | diff
32 | 4612 | 5024 | 8.93
4096 | 1436912 | 1989848 | 38.48
32768 | 14043593 | 20652436 | 47.06
524288 | 269586508 | 641284939 | 137.88
Checked on x86_64-linux-gnu.
* stdlib/qsort.c (lg): New function.
(R_HEAP): New define.
* stdlib/qsort_common.c (R_CMP_ARG_USE): New define.
(R_HEAP): New function: fallback heapsort implementation.
(R_FUNC): Use fallback heapsort if quicksort depth exceeds
2 times log2 of total element number.
Diffstat (limited to 'io/tst-fchmodat.c')
0 files changed, 0 insertions, 0 deletions