[PATCH v2 4/5] string-list: use QSORT_S in string_list_sort()
- From
René Scharfe <l.s.r@web.de>
- Date
- Jan 22, 2017, 17:57 UTC
- Message-ID
- <06ff91ec-21c5-f57b-a0ed-3c4b9c8696ff@web.de>
- In-Reply-To
- <67ac53cd-3fc0-8bd0-30f4-129281c3090f@web.de>
Pass the comparison function to cmp_items() via the context parameter of qsort_s() instead of using a global variable. That allows calling string_list_sort() from multiple parallel threads.
Our qsort_s() in compat/ is slightly slower than qsort(1) from glibc 2.24 for sorting lots of lines:
Test HEAD^ HEAD --------------------------------------------------------------------- 0071.2: sort(1) 0.10(0.22+0.01) 0.09(0.21+0.00) -10.0% 0071.3: string_list_sort() 0.16(0.15+0.01) 0.17(0.15+0.00) +6.3%
GNU sort(1) version 8.26 is significantly faster because it uses multiple parallel threads; with the unportable option --parallel=1 it becomes slower:
Test HEAD^ HEAD -------------------------------------------------------------------- 0071.2: sort(1) 0.21(0.18+0.01) 0.20(0.18+0.01) -4.8% 0071.3: string_list_sort() 0.16(0.13+0.02) 0.17(0.15+0.01) +6.3%
There is some instability -- the numbers for the sort(1) check shouldn't be affected by this patch. Anyway, the performance of our qsort_s() implementation is apparently good enough, at least for this test.
Signed-off-by: Rene Scharfe <l.s.r@web.de> --- string-list.c | 13 +++++-------- 1 file changed, 5 insertions(+), 8 deletions(-)
diff --git a/string-list.c b/string-list.c index 8c83cac189..45016ad86d 100644 --- a/string-list.c +++ b/string-list.c @@ -211,21 +211,18 @@ struct string_list_item *string_list_append(struct string_list *list, list->strdup_strings ? xstrdup(string) : (char *)string); } -/* Yuck */ -static compare_strings_fn compare_for_qsort; - -/* Only call this from inside string_list_sort! */ -static int cmp_items(const void *a, const void *b) +static int cmp_items(const void *a, const void *b, void *ctx) { + compare_strings_fn cmp = ctx; const struct string_list_item *one = a; const struct string_list_item *two = b; - return compare_for_qsort(one->string, two->string); + return cmp(one->string, two->string); } void string_list_sort(struct string_list *list) { - compare_for_qsort = list->cmp ? list->cmp : strcmp; - QSORT(list->items, list->nr, cmp_items); + QSORT_S(list->items, list->nr, cmp_items, + list->cmp ? list->cmp : strcmp); } struct string_list_item *unsorted_string_list_lookup(struct string_list *list,
-- 2.11.0