{"thread":{"id":"44939","subject":"[PATCH v2 0/5] string-list: make string_list_sort() reentrant","startedAt":"2017-01-22T17:47:46Z","lastAt":"2017-01-26T13:49:27Z","messageCount":18,"participants":["René Scharfe","Junio C Hamano","Jeff King","Johannes Schindelin"],"isPatch":true,"patchVersion":2,"patchTotal":5},"messages":[{"id":"309929","messageId":"67ac53cd-3fc0-8bd0-30f4-129281c3090f@web.de","threadId":"44939","inReplyTo":null,"subject":"[PATCH v2 0/5] string-list: make string_list_sort() reentrant","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2017-01-22T17:47:18Z","receivedAt":"2017-01-22T17:47:46Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Use qsort_s() from C11 Annex K to make string_list_sort() safer, in\nparticular when called from parallel threads.\n\nChanges from v1:\n* Renamed HAVE_QSORT_S to HAVE_ISO_QSORT_S in Makefile to disambiguate.\n* Added basic perf test (patch 3).\n* Converted a second caller to QSORT_S, in ref-filter.c (patch 5).\n\n compat: add qsort_s()\n add QSORT_S\n perf: add basic sort performance test\n string-list: use QSORT_S in string_list_sort()\n ref-filter: use QSORT_S in ref_array_sort()\n\n Makefile | 8 ++++++\n compat/qsort_s.c | 69 +++++++++++++++++++++++++++++++++++++++++++++\n git-compat-util.h | 11 ++++++++\n ref-filter.c | 6 ++--\n string-list.c | 13 ++++-----\n t/helper/test-string-list.c | 25 ++++++++++++++++\n t/perf/p0071-sort.sh | 26 +++++++++++++++++\n 7 files changed, 146 insertions(+), 12 deletions(-)\n create mode 100644 compat/qsort_s.c\n create mode 100755 t/perf/p0071-sort.sh\n\n-- \n2.11.0\n\n"},{"id":"309930","messageId":"1caa38ac-0214-441f-8e8a-1ade0839337e@web.de","threadId":"44939","inReplyTo":"67ac53cd-3fc0-8bd0-30f4-129281c3090f@web.de","subject":"[PATCH v2 1/5] compat: add qsort_s()","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2017-01-22T17:51:11Z","receivedAt":"2017-01-22T17:53:07Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"The function qsort_s() was introduced with C11 Annex K; it provides the\nability to pass a context pointer to the comparison function, supports\nthe convention of using a NULL pointer for an empty array and performs a\nfew safety checks.\n\nAdd an implementation based on compat/qsort.c for platforms that lack a\nnative standards-compliant qsort_s() (i.e. basically everyone). It\ndoesn't perform the full range of possible checks: It uses size_t\ninstead of rsize_t and doesn't check nmemb and size against RSIZE_MAX\nbecause we probably don't have the restricted size type defined. For\nthe same reason it returns int instead of errno_t.\n\nSigned-off-by: Rene Scharfe \n---\n Makefile | 8 +++++++\n compat/qsort_s.c | 69 +++++++++++++++++++++++++++++++++++++++++++++++++++++++\n git-compat-util.h | 6 +++++\n 3 files changed, 83 insertions(+)\n create mode 100644 compat/qsort_s.c\n\ndiff --git a/Makefile b/Makefile\nindex 27afd0f378..53ecc84e28 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -279,6 +279,9 @@ all::\n # is a simplified version of the merge sort used in glibc. This is\n # recommended if Git triggers O(n^2) behavior in your platform's qsort().\n #\n+# Define HAVE_ISO_QSORT_S if your platform provides a qsort_s() that's\n+# compatible with the one described in C11 Annex K.\n+#\n # Define UNRELIABLE_FSTAT if your system's fstat does not return the same\n # information on a not yet closed file that lstat would return for the same\n # file after it was closed.\n@@ -1418,6 +1421,11 @@ ifdef INTERNAL_QSORT\n \tCOMPAT_CFLAGS += -DINTERNAL_QSORT\n \tCOMPAT_OBJS += compat/qsort.o\n endif\n+ifdef HAVE_ISO_QSORT_S\n+\tCOMPAT_CFLAGS += -DHAVE_ISO_QSORT_S\n+else\n+\tCOMPAT_OBJS += compat/qsort_s.o\n+endif\n ifdef RUNTIME_PREFIX\n \tCOMPAT_CFLAGS += -DRUNTIME_PREFIX\n endif\ndiff --git a/compat/qsort_s.c b/compat/qsort_s.c\nnew file mode 100644\nindex 0000000000..52d1f0a73d\n--- /dev/null\n+++ b/compat/qsort_s.c\n@@ -0,0 +1,69 @@\n+#include \"../git-compat-util.h\"\n+\n+/*\n+ * A merge sort implementation, simplified from the qsort implementation\n+ * by Mike Haertel, which is a part of the GNU C Library.\n+ * Added context pointer, safety checks and return value.\n+ */\n+\n+static void msort_with_tmp(void *b, size_t n, size_t s,\n+\t\t\t int (*cmp)(const void *, const void *, void *),\n+\t\t\t char *t, void *ctx)\n+{\n+\tchar *tmp;\n+\tchar *b1, *b2;\n+\tsize_t n1, n2;\n+\n+\tif (n <= 1)\n+\t\treturn;\n+\n+\tn1 = n / 2;\n+\tn2 = n - n1;\n+\tb1 = b;\n+\tb2 = (char *)b + (n1 * s);\n+\n+\tmsort_with_tmp(b1, n1, s, cmp, t, ctx);\n+\tmsort_with_tmp(b2, n2, s, cmp, t, ctx);\n+\n+\ttmp = t;\n+\n+\twhile (n1 > 0 && n2 > 0) {\n+\t\tif (cmp(b1, b2, ctx) <= 0) {\n+\t\t\tmemcpy(tmp, b1, s);\n+\t\t\ttmp += s;\n+\t\t\tb1 += s;\n+\t\t\t--n1;\n+\t\t} else {\n+\t\t\tmemcpy(tmp, b2, s);\n+\t\t\ttmp += s;\n+\t\t\tb2 += s;\n+\t\t\t--n2;\n+\t\t}\n+\t}\n+\tif (n1 > 0)\n+\t\tmemcpy(tmp, b1, n1 * s);\n+\tmemcpy(b, t, (n - n2) * s);\n+}\n+\n+int git_qsort_s(void *b, size_t n, size_t s,\n+\t\tint (*cmp)(const void *, const void *, void *), void *ctx)\n+{\n+\tconst size_t size = st_mult(n, s);\n+\tchar buf[1024];\n+\n+\tif (!n)\n+\t\treturn 0;\n+\tif (!b || !cmp)\n+\t\treturn -1;\n+\n+\tif (size < sizeof(buf)) {\n+\t\t/* The temporary array fits on the small on-stack buffer. */\n+\t\tmsort_with_tmp(b, n, s, cmp, buf, ctx);\n+\t} else {\n+\t\t/* It's somewhat large, so malloc it. */\n+\t\tchar *tmp = xmalloc(size);\n+\t\tmsort_with_tmp(b, n, s, cmp, tmp, ctx);\n+\t\tfree(tmp);\n+\t}\n+\treturn 0;\n+}\ndiff --git a/git-compat-util.h b/git-compat-util.h\nindex 87237b092b..f706744e6a 100644\n--- a/git-compat-util.h\n+++ b/git-compat-util.h\n@@ -988,6 +988,12 @@ static inline void sane_qsort(void *base, size_t nmemb, size_t size,\n \t\tqsort(base, nmemb, size, compar);\n }\n \n+#ifndef HAVE_ISO_QSORT_S\n+int git_qsort_s(void *base, size_t nmemb, size_t size,\n+\t\tint (*compar)(const void *, const void *, void *), void *ctx);\n+#define qsort_s git_qsort_s\n+#endif\n+\n #ifndef REG_STARTEND\n #error \"Git requires REG_STARTEND support. Compile with NO_REGEX=NeedsStartEnd\"\n #endif\n-- \n2.11.0\n\n"},{"id":"309931","messageId":"74edb08e-4470-e166-cc78-243fa7cb36b3@web.de","threadId":"44939","inReplyTo":"67ac53cd-3fc0-8bd0-30f4-129281c3090f@web.de","subject":"[PATCH v2 3/5] perf: add basic sort performance test","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2017-01-22T17:53:57Z","receivedAt":"2017-01-22T17:54:42Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Add a sort command to test-string-list that reads lines from stdin,\nstores them in a string_list and then sorts it. Use it in a simple\nperf test script to measure the performance of string_list_sort().\n\nSigned-off-by: Rene Scharfe \n---\n t/helper/test-string-list.c | 25 +++++++++++++++++++++++++\n t/perf/p0071-sort.sh | 26 ++++++++++++++++++++++++++\n 2 files changed, 51 insertions(+)\n create mode 100755 t/perf/p0071-sort.sh\n\ndiff --git a/t/helper/test-string-list.c b/t/helper/test-string-list.c\nindex 4a68967bd1..c502fa16d3 100644\n--- a/t/helper/test-string-list.c\n+++ b/t/helper/test-string-list.c\n@@ -97,6 +97,31 @@ int cmd_main(int argc, const char **argv)\n \t\treturn 0;\n \t}\n \n+\tif (argc == 2 && !strcmp(argv[1], \"sort\")) {\n+\t\tstruct string_list list = STRING_LIST_INIT_NODUP;\n+\t\tstruct strbuf sb = STRBUF_INIT;\n+\t\tstruct string_list_item *item;\n+\n+\t\tstrbuf_read(&sb, 0, 0);\n+\n+\t\t/*\n+\t\t * Split by newline, but don't create a string_list item\n+\t\t * for the empty string after the last separator.\n+\t\t */\n+\t\tif (sb.buf[sb.len - 1] == '\\n')\n+\t\t\tstrbuf_setlen(&sb, sb.len - 1);\n+\t\tstring_list_split_in_place(&list, sb.buf, '\\n', -1);\n+\n+\t\tstring_list_sort(&list);\n+\n+\t\tfor_each_string_list_item(item, &list)\n+\t\t\tputs(item->string);\n+\n+\t\tstring_list_clear(&list, 0);\n+\t\tstrbuf_release(&sb);\n+\t\treturn 0;\n+\t}\n+\n \tfprintf(stderr, \"%s: unknown function name: %s\\n\", argv[0],\n \t\targv[1] ? argv[1] : \"(there was none)\");\n \treturn 1;\ndiff --git a/t/perf/p0071-sort.sh b/t/perf/p0071-sort.sh\nnew file mode 100755\nindex 0000000000..7c9a35a646\n--- /dev/null\n+++ b/t/perf/p0071-sort.sh\n@@ -0,0 +1,26 @@\n+#!/bin/sh\n+\n+test_description='Basic sort performance tests'\n+. ./perf-lib.sh\n+\n+test_perf_default_repo\n+\n+test_expect_success 'setup' '\n+\tgit ls-files --stage \"*.[ch]\" \"*.sh\" |\n+\tcut -f2 -d\" \" |\n+\tgit cat-file --batch >unsorted\n+'\n+\n+test_perf 'sort(1)' '\n+\tsort expect\n+'\n+\n+test_perf 'string_list_sort()' '\n+\ttest-string-list sort actual\n+'\n+\n+test_expect_success 'string_list_sort() sorts like sort(1)' '\n+\ttest_cmp_bin expect actual\n+'\n+\n+test_done\n-- \n2.11.0\n\n"},{"id":"309932","messageId":"06ff91ec-21c5-f57b-a0ed-3c4b9c8696ff@web.de","threadId":"44939","inReplyTo":"67ac53cd-3fc0-8bd0-30f4-129281c3090f@web.de","subject":"[PATCH v2 4/5] string-list: use QSORT_S in string_list_sort()","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2017-01-22T17:57:09Z","receivedAt":"2017-01-22T17:57:24Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Pass the comparison function to cmp_items() via the context parameter of\nqsort_s() instead of using a global variable. That allows calling\nstring_list_sort() from multiple parallel threads.\n\nOur qsort_s() in compat/ is slightly slower than qsort(1) from glibc\n2.24 for sorting lots of lines:\n\nTest HEAD^ HEAD\n---------------------------------------------------------------------\n0071.2: sort(1) 0.10(0.22+0.01) 0.09(0.21+0.00) -10.0%\n0071.3: string_list_sort() 0.16(0.15+0.01) 0.17(0.15+0.00) +6.3%\n\nGNU sort(1) version 8.26 is significantly faster because it uses\nmultiple parallel threads; with the unportable option --parallel=1 it\nbecomes slower:\n\nTest HEAD^ HEAD\n--------------------------------------------------------------------\n0071.2: sort(1) 0.21(0.18+0.01) 0.20(0.18+0.01) -4.8%\n0071.3: string_list_sort() 0.16(0.13+0.02) 0.17(0.15+0.01) +6.3%\n\nThere is some instability -- the numbers for the sort(1) check shouldn't\nbe affected by this patch. Anyway, the performance of our qsort_s()\nimplementation is apparently good enough, at least for this test.\n\nSigned-off-by: Rene Scharfe \n---\n string-list.c | 13 +++++--------\n 1 file changed, 5 insertions(+), 8 deletions(-)\n\ndiff --git a/string-list.c b/string-list.c\nindex 8c83cac189..45016ad86d 100644\n--- a/string-list.c\n+++ b/string-list.c\n@@ -211,21 +211,18 @@ struct string_list_item *string_list_append(struct string_list *list,\n \t\t\tlist->strdup_strings ? xstrdup(string) : (char *)string);\n }\n \n-/* Yuck */\n-static compare_strings_fn compare_for_qsort;\n-\n-/* Only call this from inside string_list_sort! */\n-static int cmp_items(const void *a, const void *b)\n+static int cmp_items(const void *a, const void *b, void *ctx)\n {\n+\tcompare_strings_fn cmp = ctx;\n \tconst struct string_list_item *one = a;\n \tconst struct string_list_item *two = b;\n-\treturn compare_for_qsort(one->string, two->string);\n+\treturn cmp(one->string, two->string);\n }\n \n void string_list_sort(struct string_list *list)\n {\n-\tcompare_for_qsort = list->cmp ? list->cmp : strcmp;\n-\tQSORT(list->items, list->nr, cmp_items);\n+\tQSORT_S(list->items, list->nr, cmp_items,\n+\t\tlist->cmp ? list->cmp : strcmp);\n }\n \n struct string_list_item *unsorted_string_list_lookup(struct string_list *list,\n-- \n2.11.0\n\n"},{"id":"309933","messageId":"991872fc-dca6-566b-4e9f-d5b92e9ed8bf@web.de","threadId":"44939","inReplyTo":"67ac53cd-3fc0-8bd0-30f4-129281c3090f@web.de","subject":"[PATCH v2 5/5] ref-filter: use QSORT_S in ref_array_sort()","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2017-01-22T17:58:07Z","receivedAt":"2017-01-22T17:58:41Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Pass the array of sort keys to compare_refs() via the context parameter\nof qsort_s() instead of using a global variable; that's cleaner and\nsimpler. If ref_array_sort() is to be called from multiple parallel\nthreads then care still needs to be taken that the global variable\nused_atom is not modified concurrently.\n\nSigned-off-by: Rene Scharfe \n---\n ref-filter.c | 6 ++----\n 1 file changed, 2 insertions(+), 4 deletions(-)\n\ndiff --git a/ref-filter.c b/ref-filter.c\nindex 1a978405e6..3975022c88 100644\n--- a/ref-filter.c\n+++ b/ref-filter.c\n@@ -1589,8 +1589,7 @@ static int cmp_ref_sorting(struct ref_sorting *s, struct ref_array_item *a, stru\n \treturn (s->reverse) ? -cmp : cmp;\n }\n \n-static struct ref_sorting *ref_sorting;\n-static int compare_refs(const void *a_, const void *b_)\n+static int compare_refs(const void *a_, const void *b_, void *ref_sorting)\n {\n \tstruct ref_array_item *a = *((struct ref_array_item **)a_);\n \tstruct ref_array_item *b = *((struct ref_array_item **)b_);\n@@ -1606,8 +1605,7 @@ static int compare_refs(const void *a_, const void *b_)\n \n void ref_array_sort(struct ref_sorting *sorting, struct ref_array *array)\n {\n-\tref_sorting = sorting;\n-\tQSORT(array->items, array->nr, compare_refs);\n+\tQSORT_S(array->items, array->nr, compare_refs, sorting);\n }\n \n static void append_literal(const char *cp, const char *ep, struct ref_formatting_state *state)\n-- \n2.11.0\n\n"},{"id":"309934","messageId":"57d9277e-9ed1-40bf-43a7-ff23377cdf77@web.de","threadId":"44939","inReplyTo":"67ac53cd-3fc0-8bd0-30f4-129281c3090f@web.de","subject":"[PATCH v2 2/5] add QSORT_S","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2017-01-22T17:52:13Z","receivedAt":"2017-01-22T17:59:17Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Add the macro QSORT_S, a convenient wrapper for qsort_s() that infers\nthe size of the array elements and dies on error.\n\nBasically all possible errors are programming mistakes (passing NULL as\nbase of a non-empty array, passing NULL as comparison function,\nout-of-bounds accesses), so terminating the program should be acceptable\nfor most callers.\n\nSigned-off-by: Rene Scharfe \n---\n git-compat-util.h | 5 +++++\n 1 file changed, 5 insertions(+)\n\ndiff --git a/git-compat-util.h b/git-compat-util.h\nindex f706744e6a..f46d40e4a4 100644\n--- a/git-compat-util.h\n+++ b/git-compat-util.h\n@@ -994,6 +994,11 @@ int git_qsort_s(void *base, size_t nmemb, size_t size,\n #define qsort_s git_qsort_s\n #endif\n \n+#define QSORT_S(base, n, compar, ctx) do {\t\t\t\\\n+\tif (qsort_s((base), (n), sizeof(*(base)), compar, ctx))\t\\\n+\t\tdie(\"BUG: qsort_s() failed\");\t\t\t\\\n+} while (0)\n+\n #ifndef REG_STARTEND\n #error \"Git requires REG_STARTEND support. Compile with NO_REGEX=NeedsStartEnd\"\n #endif\n-- \n2.11.0\n\n"},{"id":"309935","messageId":"9f8b564d-ec9f-abc9-77f6-aa84c6e78b7a@web.de","threadId":"44939","inReplyTo":"67ac53cd-3fc0-8bd0-30f4-129281c3090f@web.de","subject":"[DEMO][PATCH v2 6/5] compat: add a qsort_s() implementation based on GNU's qsort_r(1)","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2017-01-22T18:02:25Z","receivedAt":"2017-01-22T18:02:48Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Implement qsort_s() as a wrapper to the GNU version of qsort_r(1) and\nuse it on Linux. Performance increases slightly:\n\nTest HEAD^ HEAD\n--------------------------------------------------------------------\n0071.2: sort(1) 0.10(0.20+0.02) 0.10(0.21+0.01) +0.0%\n0071.3: string_list_sort() 0.17(0.15+0.01) 0.16(0.15+0.01) -5.9%\n\nAdditionally the unstripped size of compat/qsort_s.o falls from 24576\nto 16544 bytes in my build.\n\nIMHO these savings aren't worth the increased complexity of having to\nsupport two implementations.\n---\n Makefile | 6 ++++++\n compat/qsort_s.c | 18 ++++++++++++++++++\n config.mak.uname | 1 +\n 3 files changed, 25 insertions(+)\n\ndiff --git a/Makefile b/Makefile\nindex 53ecc84e28..46db1c773f 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -282,6 +282,9 @@ all::\n # Define HAVE_ISO_QSORT_S if your platform provides a qsort_s() that's\n # compatible with the one described in C11 Annex K.\n #\n+# Define HAVE_GNU_QSORT_R if your platform provides a qsort_r() that's\n+# compatible with the one introduced with glibc 2.8.\n+#\n # Define UNRELIABLE_FSTAT if your system's fstat does not return the same\n # information on a not yet closed file that lstat would return for the same\n # file after it was closed.\n@@ -1426,6 +1429,9 @@ ifdef HAVE_ISO_QSORT_S\n else\n \tCOMPAT_OBJS += compat/qsort_s.o\n endif\n+ifdef HAVE_GNU_QSORT_R\n+\tCOMPAT_CFLAGS += -DHAVE_GNU_QSORT_R\n+endif\n ifdef RUNTIME_PREFIX\n \tCOMPAT_CFLAGS += -DRUNTIME_PREFIX\n endif\ndiff --git a/compat/qsort_s.c b/compat/qsort_s.c\nindex 52d1f0a73d..763ee1faae 100644\n--- a/compat/qsort_s.c\n+++ b/compat/qsort_s.c\n@@ -1,5 +1,21 @@\n #include \"../git-compat-util.h\"\n \n+#if defined HAVE_GNU_QSORT_R\n+\n+int git_qsort_s(void *b, size_t n, size_t s,\n+\t\tint (*cmp)(const void *, const void *, void *), void *ctx)\n+{\n+\tif (!n)\n+\t\treturn 0;\n+\tif (!b || !cmp)\n+\t\treturn -1;\n+\n+\tqsort_r(b, n, s, cmp, ctx);\n+\treturn 0;\n+}\n+\n+#else\n+\n /*\n * A merge sort implementation, simplified from the qsort implementation\n * by Mike Haertel, which is a part of the GNU C Library.\n@@ -67,3 +83,5 @@ int git_qsort_s(void *b, size_t n, size_t s,\n \t}\n \treturn 0;\n }\n+\n+#endif\ndiff --git a/config.mak.uname b/config.mak.uname\nindex 447f36ac2e..a1858f54ff 100644\n--- a/config.mak.uname\n+++ b/config.mak.uname\n@@ -37,6 +37,7 @@ ifeq ($(uname_S),Linux)\n \tNEEDS_LIBRT = YesPlease\n \tHAVE_GETDELIM = YesPlease\n \tSANE_TEXT_GREP=-a\n+\tHAVE_GNU_QSORT_R = YesPlease\n endif\n ifeq ($(uname_S),GNU/kFreeBSD)\n \tHAVE_ALLOCA_H = YesPlease\n-- \n2.11.0\n\n"},{"id":"310001","messageId":"xmqq60l5sihz.fsf@gitster.mtv.corp.google.com","threadId":"44939","inReplyTo":"9f8b564d-ec9f-abc9-77f6-aa84c6e78b7a@web.de","subject":"Re: [DEMO][PATCH v2 6/5] compat: add a qsort_s() implementation based on GNU's qsort_r(1)","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-01-23T19:07:04Z","receivedAt":"2017-01-23T19:07:12Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"René Scharfe writes:\n\n> Implement qsort_s() as a wrapper to the GNU version of qsort_r(1) and\n> use it on Linux. Performance increases slightly:\n>\n> Test HEAD^ HEAD\n> --------------------------------------------------------------------\n> 0071.2: sort(1) 0.10(0.20+0.02) 0.10(0.21+0.01) +0.0%\n> 0071.3: string_list_sort() 0.17(0.15+0.01) 0.16(0.15+0.01) -5.9%\n>\n> Additionally the unstripped size of compat/qsort_s.o falls from 24576\n> to 16544 bytes in my build.\n>\n> IMHO these savings aren't worth the increased complexity of having to\n> support two implementations.\n\nI do worry about having to support more implementations in the\nfuture that have different function signature for the comparison\ncallbacks, which will make things ugly, but this addition alone\ndoesn't look too bad to me.\n\nThanks.\n\n> diff --git a/compat/qsort_s.c b/compat/qsort_s.c\n> index 52d1f0a73d..763ee1faae 100644\n> --- a/compat/qsort_s.c\n> +++ b/compat/qsort_s.c\n> @@ -1,5 +1,21 @@\n> #include \"../git-compat-util.h\"\n> \n> +#if defined HAVE_GNU_QSORT_R\n> +\n> +int git_qsort_s(void *b, size_t n, size_t s,\n> +\t\tint (*cmp)(const void *, const void *, void *), void *ctx)\n> +{\n> +\tif (!n)\n> +\t\treturn 0;\n> +\tif (!b || !cmp)\n> +\t\treturn -1;\n> +\n> +\tqsort_r(b, n, s, cmp, ctx);\n> +\treturn 0;\n> +}\n> +\n> +#else\n> +\n> /*\n> * A merge sort implementation, simplified from the qsort implementation\n> * by Mike Haertel, which is a part of the GNU C Library.\n> @@ -67,3 +83,5 @@ int git_qsort_s(void *b, size_t n, size_t s,\n> \t}\n> \treturn 0;\n> }\n> +\n> +#endif\n> diff --git a/config.mak.uname b/config.mak.uname\n> index 447f36ac2e..a1858f54ff 100644\n> --- a/config.mak.uname\n> +++ b/config.mak.uname\n> @@ -37,6 +37,7 @@ ifeq ($(uname_S),Linux)\n> \tNEEDS_LIBRT = YesPlease\n> \tHAVE_GETDELIM = YesPlease\n> \tSANE_TEXT_GREP=-a\n> +\tHAVE_GNU_QSORT_R = YesPlease\n> endif\n> ifeq ($(uname_S),GNU/kFreeBSD)\n> \tHAVE_ALLOCA_H = YesPlease\n"},{"id":"310051","messageId":"20170123235445.qsejumltutd2vrhd@sigill.intra.peff.net","threadId":"44939","inReplyTo":"67ac53cd-3fc0-8bd0-30f4-129281c3090f@web.de","subject":"Re: [PATCH v2 0/5] string-list: make string_list_sort() reentrant","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-01-23T23:54:45Z","receivedAt":"2017-01-23T23:54:52Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Jan 22, 2017 at 06:47:18PM +0100, René Scharfe wrote:\n\n> Use qsort_s() from C11 Annex K to make string_list_sort() safer, in\n> particular when called from parallel threads.\n> \n> Changes from v1:\n> * Renamed HAVE_QSORT_S to HAVE_ISO_QSORT_S in Makefile to disambiguate.\n> * Added basic perf test (patch 3).\n> * Converted a second caller to QSORT_S, in ref-filter.c (patch 5).\n\nThis looks nicely done overall, and I appreciate the perf test.\n\nThe speed looks like a reasonable outcome. I'm torn on the qsort_r()\ndemo patch. I don't think it looks too bad. OTOH, I don't think I would\nwant to deal with the opposite-argument-order versions.\n\nIs there any interest in people adding the ISO qsort_s() to their libc\nimplementations? It seems like it's been a fair number of years by now.\n\n-Peff\n"},{"id":"310086","messageId":"alpine.DEB.2.20.1701241233390.3469@virtualbox","threadId":"44939","inReplyTo":"20170123235445.qsejumltutd2vrhd@sigill.intra.peff.net","subject":"Re: [PATCH v2 0/5] string-list: make string_list_sort() reentrant","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2017-01-24T11:44:10Z","receivedAt":"2017-01-24T11:44:32Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Peff,\n\nOn Mon, 23 Jan 2017, Jeff King wrote:\n\n> Is there any interest in people adding the ISO qsort_s() to their libc\n> implementations? It seems like it's been a fair number of years by now.\n\nVisual C supports it *at least* since Visual Studio 2005:\n\nhttps://msdn.microsoft.com/en-us/library/4xc60xas(v=vs.80).aspx\n\nWith René's patch, we have an adapter for GNU libc, and if anybody comes\nup with the (equally trivial) adapter for BSD libc's qsort_r(), we have a\nlot of bases covered.\n\nCiao,\nJohannes"},{"id":"310089","messageId":"20170124134430.am6yzskkcp2vq6a5@sigill.intra.peff.net","threadId":"44939","inReplyTo":"alpine.DEB.2.20.1701241233390.3469@virtualbox","subject":"Re: [PATCH v2 0/5] string-list: make string_list_sort() reentrant","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-01-24T13:44:30Z","receivedAt":"2017-01-24T13:44:43Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jan 24, 2017 at 12:44:10PM +0100, Johannes Schindelin wrote:\n\n> Hi Peff,\n> \n> On Mon, 23 Jan 2017, Jeff King wrote:\n> \n> > Is there any interest in people adding the ISO qsort_s() to their libc\n> > implementations? It seems like it's been a fair number of years by now.\n> \n> Visual C supports it *at least* since Visual Studio 2005:\n> \n> https://msdn.microsoft.com/en-us/library/4xc60xas(v=vs.80).aspx\n> \n> With René's patch, we have an adapter for GNU libc, and if anybody comes\n> up with the (equally trivial) adapter for BSD libc's qsort_r(), we have a\n> lot of bases covered.\n\nSadly, no. Microsoft's qsort_s() is not compatible with the ISO C one.\nAnd BSD's qsort_r() has a similar problem acting as a wrapper, because\nthe order of arguments in the callback functions is different (so you'd\nhave to actually wrap the callback, too, and rearrange the arguments for\neach call, or do some macro trickery).\n\nGory details are in:\n\n https://stackoverflow.com/questions/39560773/different-declarations-of-qsort-r-on-mac-and-linux/39561369\n\nand the original thread:\n\n http://public-inbox.org/git/3083fbf7-d67e-77e4-e05f-94a7e7e15eba@web.de/\n\n-Peff\n"},{"id":"310100","messageId":"b333ecd4-a147-904d-b1ce-b49179c4ad26@web.de","threadId":"44939","inReplyTo":"20170123235445.qsejumltutd2vrhd@sigill.intra.peff.net","subject":"Re: [PATCH v2 0/5] string-list: make string_list_sort() reentrant","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2017-01-24T18:00:07Z","receivedAt":"2017-01-24T18:00:31Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 24.01.2017 um 00:54 schrieb Jeff King:\n> The speed looks like a reasonable outcome. I'm torn on the qsort_r()\n> demo patch. I don't think it looks too bad. OTOH, I don't think I would\n> want to deal with the opposite-argument-order versions.\n\nThe code itself may look OK, but it's not really necessary and the \nspecial implementation for Linux makes increases maintenance costs. Can \nwe save it for later and first give the common implemention a chance to \nprove itself?\n\n> Is there any interest in people adding the ISO qsort_s() to their libc\n> implementations? It seems like it's been a fair number of years by now.\n\nhttps://sourceware.org/ml/libc-alpha/2014-12/msg00513.html is the last \npost mentioning qsort_s on the glibc mailing list, but it didn't even \nmake it into https://sourceware.org/glibc/wiki/Development_Todo/Master.\nNot sure what's planned in BSD land, didn't find anything (but didn't \nlook too hard).\n\nRené\n"},{"id":"310101","messageId":"4e416167-2a33-0943-5738-79b4da5f2c11@web.de","threadId":"44939","inReplyTo":"xmqq60l5sihz.fsf@gitster.mtv.corp.google.com","subject":"Re: [DEMO][PATCH v2 6/5] compat: add a qsort_s() implementation based on GNU's qsort_r(1)","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2017-01-24T18:00:03Z","receivedAt":"2017-01-24T18:00:37Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 23.01.2017 um 20:07 schrieb Junio C Hamano:\n> René Scharfe writes:\n> \n>> Implement qsort_s() as a wrapper to the GNU version of qsort_r(1) and\n>> use it on Linux. Performance increases slightly:\n>>\n>> Test HEAD^ HEAD\n>> --------------------------------------------------------------------\n>> 0071.2: sort(1) 0.10(0.20+0.02) 0.10(0.21+0.01) +0.0%\n>> 0071.3: string_list_sort() 0.17(0.15+0.01) 0.16(0.15+0.01) -5.9%\n>>\n>> Additionally the unstripped size of compat/qsort_s.o falls from 24576\n>> to 16544 bytes in my build.\n>>\n>> IMHO these savings aren't worth the increased complexity of having to\n>> support two implementations.\n> \n> I do worry about having to support more implementations in the\n> future that have different function signature for the comparison\n> callbacks, which will make things ugly, but this addition alone\n> doesn't look too bad to me.\n\nIt is unfair of me to show a 5% speedup and then recommend to not\ninclude it. ;-) That difference won't be measurable in real use cases\nand the patch is not necessary. This patch is simple, but the overall\ncomplexity (incl. #ifdefs etc.) will be lower without it.\n\nBut here's another one, with even higher performance and with an even\nbigger recommendation to not include it! :) It veers off into another\ndirection: Parallel execution. It requires thread-safe comparison\nfunctions, which might surprise callers. The value 1000 for the minimum\nnumber of items before threading kicks in is just a guess, not based on\nmeasurements. So it's quite raw -- and I'm not sure why it's still a\nbit slower than sort(1).\n\nTest HEAD^ HEAD\n---------------------------------------------------------------------\n0071.2: sort(1) 0.10(0.18+0.03) 0.10(0.20+0.02) +0.0%\n0071.3: string_list_sort() 0.17(0.14+0.02) 0.11(0.18+0.02) -35.3%\n\n---\n compat/qsort_s.c | 76 ++++++++++++++++++++++++++++++++++++++++++--------------\n 1 file changed, 58 insertions(+), 18 deletions(-)\n\ndiff --git a/compat/qsort_s.c b/compat/qsort_s.c\nindex 52d1f0a73d..1304a089af 100644\n--- a/compat/qsort_s.c\n+++ b/compat/qsort_s.c\n@@ -1,4 +1,5 @@\n #include \"../git-compat-util.h\"\n+#include \"../thread-utils.h\"\n \n /*\n * A merge sort implementation, simplified from the qsort implementation\n@@ -6,29 +7,58 @@\n * Added context pointer, safety checks and return value.\n */\n \n-static void msort_with_tmp(void *b, size_t n, size_t s,\n-\t\t\t int (*cmp)(const void *, const void *, void *),\n-\t\t\t char *t, void *ctx)\n+#define MIN_ITEMS_FOR_THREAD 1000\n+\n+struct work {\n+\tint nr_threads;\n+\tvoid *base;\n+\tsize_t nmemb;\n+\tsize_t size;\n+\tchar *tmp;\n+\tint (*cmp)(const void *, const void *, void *);\n+\tvoid *ctx;\n+};\n+\n+static void *msort_with_tmp(void *work)\n {\n+\tstruct work one, two, *w = work;\n \tchar *tmp;\n \tchar *b1, *b2;\n \tsize_t n1, n2;\n+\tsize_t s, n;\n \n-\tif (n <= 1)\n-\t\treturn;\n+\tif (w->nmemb <= 1)\n+\t\treturn NULL;\n \n-\tn1 = n / 2;\n-\tn2 = n - n1;\n-\tb1 = b;\n-\tb2 = (char *)b + (n1 * s);\n+\tone = two = *w;\n+\tone.nr_threads /= 2;\n+\ttwo.nr_threads -= one.nr_threads;\n+\tn = one.nmemb;\n+\ts = one.size;\n+\tn1 = one.nmemb = n / 2;\n+\tn2 = two.nmemb = n - n1;\n+\tb1 = one.base;\n+\tb2 = two.base = b1 + n1 * s;\n+\ttwo.tmp += n1 * s;\n \n-\tmsort_with_tmp(b1, n1, s, cmp, t, ctx);\n-\tmsort_with_tmp(b2, n2, s, cmp, t, ctx);\n+#ifndef NO_PTHREADS\n+\tif (one.nr_threads && n > MIN_ITEMS_FOR_THREAD) {\n+\t\tpthread_t thread;\n+\t\tint err = pthread_create(&thread, NULL, msort_with_tmp, &one);\n+\t\tmsort_with_tmp(&two);\n+\t\tif (err || pthread_join(thread, NULL))\n+\t\t\tmsort_with_tmp(&one);\n+\t} else\n+#endif\n+\t{\n+\t\tmsort_with_tmp(&one);\n+\t\tmsort_with_tmp(&two);\n+\t}\n \n-\ttmp = t;\n+\ttmp = one.tmp;\n \n \twhile (n1 > 0 && n2 > 0) {\n-\t\tif (cmp(b1, b2, ctx) <= 0) {\n+\t\tif (one.cmp(b1, b2, one.ctx) <= 0) {\n \t\t\tmemcpy(tmp, b1, s);\n \t\t\ttmp += s;\n \t\t\tb1 += s;\n@@ -42,7 +72,8 @@ static void msort_with_tmp(void *b, size_t n, size_t s,\n \t}\n \tif (n1 > 0)\n \t\tmemcpy(tmp, b1, n1 * s);\n-\tmemcpy(b, t, (n - n2) * s);\n+\tmemcpy(one.base, one.tmp, (n - n2) * s);\n+\treturn NULL;\n }\n \n int git_qsort_s(void *b, size_t n, size_t s,\n@@ -50,20 +81,29 @@ int git_qsort_s(void *b, size_t n, size_t s,\n {\n \tconst size_t size = st_mult(n, s);\n \tchar buf[1024];\n+\tstruct work w;\n \n \tif (!n)\n \t\treturn 0;\n \tif (!b || !cmp)\n \t\treturn -1;\n \n+\tw.nr_threads = online_cpus();\n+\tw.base = b;\n+\tw.nmemb = n;\n+\tw.size = s;\n+\tw.cmp = cmp;\n+\tw.ctx = ctx;\n+\n \tif (size < sizeof(buf)) {\n \t\t/* The temporary array fits on the small on-stack buffer. */\n-\t\tmsort_with_tmp(b, n, s, cmp, buf, ctx);\n+\t\tw.tmp = buf;\n \t} else {\n \t\t/* It's somewhat large, so malloc it. */\n-\t\tchar *tmp = xmalloc(size);\n-\t\tmsort_with_tmp(b, n, s, cmp, tmp, ctx);\n-\t\tfree(tmp);\n+\t\tw.tmp = xmalloc(size);\n \t}\n+\tmsort_with_tmp(&w);\n+\tif (w.tmp != buf)\n+\t\tfree(w.tmp);\n \treturn 0;\n }\n-- \n2.11.0\n\n"},{"id":"310109","messageId":"20170124203949.46lbmiyj26xx4hrk@sigill.intra.peff.net","threadId":"44939","inReplyTo":"4e416167-2a33-0943-5738-79b4da5f2c11@web.de","subject":"Re: [DEMO][PATCH v2 6/5] compat: add a qsort_s() implementation based on GNU's qsort_r(1)","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-01-24T20:39:49Z","receivedAt":"2017-01-24T20:39:56Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jan 24, 2017 at 07:00:03PM +0100, René Scharfe wrote:\n\n> > I do worry about having to support more implementations in the\n> > future that have different function signature for the comparison\n> > callbacks, which will make things ugly, but this addition alone\n> > doesn't look too bad to me.\n> \n> It is unfair of me to show a 5% speedup and then recommend to not\n> include it. ;-) That difference won't be measurable in real use cases\n> and the patch is not necessary. This patch is simple, but the overall\n> complexity (incl. #ifdefs etc.) will be lower without it.\n\nI care less about squeezing out the last few percent performance and\nmore that somebody libc qsort_r() might offer some other improvement.\nFor instance, it could sort in-place to lower memory use for some cases,\nor do some clever thing that gives more than a few percent in the real\nworld (something like TimSort).\n\nI don't know to what degree we should care about that.\n\n> But here's another one, with even higher performance and with an even\n> bigger recommendation to not include it! :) It veers off into another\n> direction: Parallel execution. It requires thread-safe comparison\n> functions, which might surprise callers. The value 1000 for the minimum\n> number of items before threading kicks in is just a guess, not based on\n> measurements. So it's quite raw -- and I'm not sure why it's still a\n> bit slower than sort(1).\n\nFun, but probably insane for our not-very-threadsafe code base. :)\n\n-Peff\n"},{"id":"310110","messageId":"20170124204105.2iqmincozuqbmqo2@sigill.intra.peff.net","threadId":"44939","inReplyTo":"b333ecd4-a147-904d-b1ce-b49179c4ad26@web.de","subject":"Re: [PATCH v2 0/5] string-list: make string_list_sort() reentrant","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-01-24T20:41:06Z","receivedAt":"2017-01-24T20:41:12Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jan 24, 2017 at 07:00:07PM +0100, René Scharfe wrote:\n\n> Am 24.01.2017 um 00:54 schrieb Jeff King:\n> > The speed looks like a reasonable outcome. I'm torn on the qsort_r()\n> > demo patch. I don't think it looks too bad. OTOH, I don't think I would\n> > want to deal with the opposite-argument-order versions.\n> \n> The code itself may look OK, but it's not really necessary and the special\n> implementation for Linux makes increases maintenance costs. Can we save it\n> for later and first give the common implemention a chance to prove itself?\n\nSure, I'm OK with leaving it out for now.\n\n> > Is there any interest in people adding the ISO qsort_s() to their libc\n> > implementations? It seems like it's been a fair number of years by now.\n> \n> https://sourceware.org/ml/libc-alpha/2014-12/msg00513.html is the last post\n> mentioning qsort_s on the glibc mailing list, but it didn't even make it\n> into https://sourceware.org/glibc/wiki/Development_Todo/Master.\n> Not sure what's planned in BSD land, didn't find anything (but didn't look\n> too hard).\n\nSo it sounds like \"no, not really\". I think that's OK. I was mostly\ncurious if we could expect our custom implementation to age out over\ntime.\n\n-Peff\n"},{"id":"310180","messageId":"f41e5053-ee24-060f-0fb9-b257b3ba35a0@web.de","threadId":"44939","inReplyTo":"20170124203949.46lbmiyj26xx4hrk@sigill.intra.peff.net","subject":"Re: [DEMO][PATCH v2 6/5] compat: add a qsort_s() implementation based on GNU's qsort_r(1)","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2017-01-25T18:43:01Z","receivedAt":"2017-01-25T18:43:24Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 24.01.2017 um 21:39 schrieb Jeff King:\n> On Tue, Jan 24, 2017 at 07:00:03PM +0100, René Scharfe wrote:\n>\n>>> I do worry about having to support more implementations in the\n>>> future that have different function signature for the comparison\n>>> callbacks, which will make things ugly, but this addition alone\n>>> doesn't look too bad to me.\n>>\n>> It is unfair of me to show a 5% speedup and then recommend to not\n>> include it. ;-) That difference won't be measurable in real use cases\n>> and the patch is not necessary. This patch is simple, but the overall\n>> complexity (incl. #ifdefs etc.) will be lower without it.\n>\n> I care less about squeezing out the last few percent performance and\n> more that somebody libc qsort_r() might offer some other improvement.\n> For instance, it could sort in-place to lower memory use for some cases,\n> or do some clever thing that gives more than a few percent in the real\n> world (something like TimSort).\n>\n> I don't know to what degree we should care about that.\n\nThat's a good question. Which workloads spend a significant amount of \ntime in qsort/qsort_s?\n\nWe could track processor time spent and memory allocated in QSORT_S and \nthe whole program and show a warning at the end if one of the two \nexceeded, say, 5% of the total, asking nicely to send it to our mailing \nlist. Would something like this be useful for other functions or \nmetrics as well? Would it be too impolite to use users as telemetry \ntransports?\n\nIf we find such cases then we'd better fix them for all platforms, e.g. \nby importing timsort, no?\n\nRené\n"},{"id":"310181","messageId":"20170125185153.obqwxiniyz2omxsi@sigill.intra.peff.net","threadId":"44939","inReplyTo":"f41e5053-ee24-060f-0fb9-b257b3ba35a0@web.de","subject":"Re: [DEMO][PATCH v2 6/5] compat: add a qsort_s() implementation based on GNU's qsort_r(1)","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-01-25T18:51:53Z","receivedAt":"2017-01-25T18:52:00Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jan 25, 2017 at 07:43:01PM +0100, René Scharfe wrote:\n\n> We could track processor time spent and memory allocated in QSORT_S and the\n> whole program and show a warning at the end if one of the two exceeded, say,\n> 5% of the total, asking nicely to send it to our mailing list. Would\n> something like this be useful for other functions or metrics as well? Would\n> it be too impolite to use users as telemetry transports?\n\nFrankly, that sounds a bit overboard to me. If people want to profile\nthere are profiling tools. If we want users to profile on their systems\nand send results to us, I think I'd rather give them instructions or a\nwrapper script for doing so.\n\n> If we find such cases then we'd better fix them for all platforms, e.g. by\n> importing timsort, no?\n\nYes, as long as they are strict improvements. I can't think of a case\nwhere some sorting behavior is a matter of opinion, and they'd prefer\nGit behave like the rest of their system rather than like Git on other\nsystems[1].\n\n-Peff\n\n[1] I wonder the same about regex implementations. I generally consider\n our GNU regex fallback to be a strict improvement over system\n versions, at least in terms of features. But I was interested to see\n recently that musl implements pcre-style \"\\x\" as an extension, but\n it _doesn't_ do REG_STARTEND. So it's at tradeoff. They have to use\n the fallback on newer versions of git (to get REG_STARTEND), but\n that means the rest of their system understands \"\\x\" but Git does\n not.\n"},{"id":"310314","messageId":"alpine.DEB.2.20.1701261446540.3469@virtualbox","threadId":"44939","inReplyTo":"20170125185153.obqwxiniyz2omxsi@sigill.intra.peff.net","subject":"Re: [DEMO][PATCH v2 6/5] compat: add a qsort_s() implementation based on GNU's qsort_r(1)","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2017-01-26T13:49:10Z","receivedAt":"2017-01-26T13:49:27Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Wed, 25 Jan 2017, Jeff King wrote:\n\n> On Wed, Jan 25, 2017 at 07:43:01PM +0100, René Scharfe wrote:\n> \n> > If we find such cases then we'd better fix them for all platforms, e.g. by\n> > importing timsort, no?\n> \n> Yes, as long as they are strict improvements.\n\nI think in many cases, we may be better off by replacing the use of a\nstring-list for lookups by hashmaps for the same purpose.\n\nCiao,\nDscho"}]}