{"thread":{"id":"11845","subject":"[PATCH] compat: Add simplified merge sort implementation from glibc","startedAt":"2008-02-03T01:11:30Z","lastAt":"2008-02-05T21:07:29Z","messageCount":11,"participants":["Brian Downing","Johannes Schindelin","Junio C Hamano","Edgar Toernig","Mike Ralphson"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"67168","messageId":"20080203011130.GK26392@lavos.net","threadId":"11845","inReplyTo":null,"subject":"[PATCH] compat: Add simplified merge sort implementation from glibc","fromName":"Brian Downing","fromEmail":"bdowning-ou/tddhfglreowh0uzbu5w@public.gmane.org","sentAt":"2008-02-03T01:11:30Z","receivedAt":"2008-02-03T01:11:30Z","isPatch":true,"sender":{"key":"bdowning-ou/tddhfglreowh0uzbu5w@public.gmane.org","avatar":null},"body":"\nqsort in Windows 2000 (and possibly other older Windows' C libraries)\nis a Quicksort with the usual O(n^2) worst case. Unfortunately, sorting\nGit trees seems to get very close to that worst case quite often:\n\n $ /git/gitbad runstatus\n # On branch master\n qsort, nmemb = 30842\n done, 237838087 comparisons.\n\nThis patch adds a simplified version of the merge sort that is glibc's\nqsort(3). As a merge sort, this needs a temporary array equal in size\nto the array that is to be sorted.\n\nThe complexity that was removed is:\n\n* Doing direct stores for word-size and -aligned data.\n* Falling back to quicksort if the allocation required to perform the\n merge sort would likely push the machine into swap.\n\nEven with these simplifications, this seems to outperform the Windows\nqsort(3) implementation, even in Windows XP (where it is \"fixed\" and\ndoesn't trigger O(n^2) complexity on trees).\n\n[jes: moved into compat/qsort.c, as per Johannes Sixt's suggestion]\n\nSigned-off-by: Brian Downing \nSigned-off-by: Steffen Prohaska \nSigned-off-by: Johannes Schindelin \n---\n Junio,\n\n This is for consideration for mainline Git now that 1.5.4 is out. It\n is used to avoid an awful qsort implementation on Windows 2000, and I\n believe there was some discussion about other Unixes (AIX, etc) that\n have a similar problem.\n\n -bcd\n\n Makefile | 7 ++++++\n compat/qsort.c | 60 +++++++++++++++++++++++++++++++++++++++++++++++++++++\n git-compat-util.h | 6 +++++\n 3 files changed, 73 insertions(+), 0 deletions(-)\n create mode 100644 compat/qsort.c\n\ndiff --git a/Makefile b/Makefile\nindex 92341c4..1698bc4 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -137,6 +137,9 @@ all::\n # Define THREADED_DELTA_SEARCH if you have pthreads and wish to exploit\n # parallel delta searching when packing objects.\n #\n+# Define NEEDS_QUICK_QSORT if your qsort() implementation has O(n^2)\n+# worst case complexity.\n+#\n \n GIT-VERSION-FILE: .FORCE-GIT-VERSION-FILE\n \t@$(SHELL_PATH) ./GIT-VERSION-GEN\n@@ -722,6 +725,10 @@ ifdef NO_MEMMEM\n \tCOMPAT_CFLAGS += -DNO_MEMMEM\n \tCOMPAT_OBJS += compat/memmem.o\n endif\n+ifdef NEEDS_QUICK_QSORT\n+\tCOMPAT_CFLAGS += -DNEEDS_QUICK_QSORT\n+\tCOMPAT_OBJS += compat/qsort.o\n+endif\n \n ifdef THREADED_DELTA_SEARCH\n \tBASIC_CFLAGS += -DTHREADED_DELTA_SEARCH\ndiff --git a/compat/qsort.c b/compat/qsort.c\nnew file mode 100644\nindex 0000000..734866e\n--- /dev/null\n+++ b/compat/qsort.c\n@@ -0,0 +1,60 @@\n+#include \"../git-compat-util.h\"\n+\n+/* This merge sort implementation is simplified from glibc's. */\n+static void msort_with_tmp(void *b, size_t n, size_t s,\n+\t\t\t int (*cmp)(const void *, const void *),\n+\t\t\t char *t)\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);\n+\tmsort_with_tmp(b2, n2, s, cmp, t);\n+\n+\ttmp = t;\n+\n+\twhile (n1 > 0 && n2 > 0) {\n+\t\tif (cmp(b1, b2) <= 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+void git_qsort(void *b, size_t n, size_t s,\n+\t int (*cmp)(const void *, const void *))\n+{\n+\tconst size_t size = n * s;\n+\n+\tif (size < 1024) {\n+\t\tchar buf[size]; /* gcc-ism */\n+\n+\t\t/* The temporary array is small, so put it on\n+\t\t the stack. */\n+\t\tmsort_with_tmp(b, n, s, cmp, buf);\n+\t} else {\n+\t\t/* It's somewhat large, so malloc it. */\n+\t\tchar *tmp = malloc(size);\n+\t\tmsort_with_tmp(b, n, s, cmp, tmp);\n+\t\tfree(tmp);\n+\t}\n+}\ndiff --git a/git-compat-util.h b/git-compat-util.h\nindex 4df90cb..e848a73 100644\n--- a/git-compat-util.h\n+++ b/git-compat-util.h\n@@ -426,4 +426,10 @@ static inline int strtol_i(char const *s, int base, int *result)\n \treturn 0;\n }\n \n+#ifdef NEEDS_QUICK_QSORT\n+void git_qsort(void *base, size_t nmemb, size_t size,\n+\t int(*compar)(const void *, const void *));\n+#define qsort git_qsort\n+#endif\n+\n #endif\n-- \n1.5.4.rc3\n"},{"id":"67175","messageId":"alpine.LSU.1.00.0802030231080.7372@racer.site","threadId":"11845","inReplyTo":"20080203011130.GK26392-oU/tDdhfGLReoWH0uzbU5w@public.gmane.org","subject":"Re: [PATCH] compat: Add simplified merge sort implementation from glibc","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin-mmb7mzphnfy@public.gmane.org","sentAt":"2008-02-03T02:37:27Z","receivedAt":"2008-02-03T02:37:27Z","isPatch":true,"sender":{"key":"johannes.schindelin-mmb7mzphnfy@public.gmane.org","avatar":null},"body":"\nHi,\n\nOn Sat, 2 Feb 2008, Brian Downing wrote:\n\n> qsort in Windows 2000 (and possibly other older Windows' C libraries)\n> is a Quicksort with the usual O(n^2) worst case. Unfortunately, sorting\n> Git trees seems to get very close to that worst case quite often:\n> \n> $ /git/gitbad runstatus\n> # On branch master\n> qsort, nmemb = 30842\n> done, 237838087 comparisons.\n> \n> This patch adds a simplified version of the merge sort that is glibc's\n> qsort(3). As a merge sort, this needs a temporary array equal in size\n> to the array that is to be sorted.\n> \n> The complexity that was removed is:\n> \n> * Doing direct stores for word-size and -aligned data.\n> * Falling back to quicksort if the allocation required to perform the\n> merge sort would likely push the machine into swap.\n> \n> Even with these simplifications, this seems to outperform the Windows\n> qsort(3) implementation, even in Windows XP (where it is \"fixed\" and\n> doesn't trigger O(n^2) complexity on trees).\n> \n> [jes: moved into compat/qsort.c, as per Johannes Sixt's suggestion]\n> \n> Signed-off-by: Brian Downing \n> Signed-off-by: Steffen Prohaska \n> Signed-off-by: Johannes Schindelin \n\nI should add that this is a stripped-down version of glibc's sort() (yes, \nthe GPL of glibc allows that we rip it, for all you license wieners out \nthere).\n\nAFAIR the discussion about the different implementations of a sort \nalgorithm boiled down to one particular implementation being quicker than \nwhat this patch has, but with dubious licensing, and the glibc \nimplementation without the modifications present in this patch being \nslower.\n\nSo I would like this to go in, evidently, if only as a starting point for \npeople to play with sorting algorithms, to find the one which is optimal \nfor our general use (we have quite some uses where we put in _almost_ \nsorted data, which seems to be the worst-case for many sorting \nalgorithms).\n\nCiao,\nDscho\n"},{"id":"67182","messageId":"20080203045033.GL26392@lavos.net","threadId":"11845","inReplyTo":"alpine.LSU.1.00.0802030231080.7372@racer.site","subject":"Re: [PATCH] compat: Add simplified merge sort implementation from glibc","fromName":"Brian Downing","fromEmail":"bdowning@lavos.net","sentAt":"2008-02-03T04:50:34Z","receivedAt":"2008-02-03T04:50:34Z","isPatch":true,"sender":{"key":"bdowning@lavos.net","avatar":"https://avatars.githubusercontent.com/u/366426?v=4"},"body":"On Sun, Feb 03, 2008 at 02:37:27AM +0000, Johannes Schindelin wrote:\n> I should add that this is a stripped-down version of glibc's sort() (yes, \n> the GPL of glibc allows that we rip it, for all you license wieners out \n> there).\n> \n> AFAIR the discussion about the different implementations of a sort \n> algorithm boiled down to one particular implementation being quicker than \n> what this patch has, but with dubious licensing, and the glibc \n> implementation without the modifications present in this patch being \n> slower.\n> \n> So I would like this to go in, evidently, if only as a starting point for \n> people to play with sorting algorithms, to find the one which is optimal \n> for our general use (we have quite some uses where we put in _almost_ \n> sorted data, which seems to be the worst-case for many sorting \n> algorithms).\n\nIf this is what I am thinking of, the sort of dubious licensing was\nfaster than glibc's quicksort. This patch, however, is simplified from\nglibc's mergesort (which is what glibc uses for the qsort() call except\nfor very large arrays), and was determined to be faster than both.\n\nSee:\n\nhttp://groups.google.com/group/msysgit/browse_frm/thread/3c2eb564b9d0a994\n\nand the links from that thread for more information.\n\n-bcd\n"},{"id":"67186","messageId":"7v1w7u1ruz.fsf@gitster.siamese.dyndns.org","threadId":"11845","inReplyTo":"alpine.LSU.1.00.0802030231080.7372@racer.site","subject":"Re: [PATCH] compat: Add simplified merge sort implementation from glibc","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-02-03T06:22:44Z","receivedAt":"2008-02-03T06:22:44Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johannes Schindelin writes:\n\n> So I would like this to go in, evidently, if only as a starting point for \n> people to play with sorting algorithms, to find the one which is optimal \n> for our general use (we have quite some uses where we put in _almost_ \n> sorted data, which seems to be the worst-case for many sorting \n> algorithms).\n\nI do not think we want to spend arguing over the last few\npercent to get anything ultra-fast. The aim for compat/ is to\nhave a replacement for unusable platform-supplied stuff.\n\nThe patch looked fine, thanks.\n\nIf I may add a bikeshed comment, I probably would have modelled\nthe make variable, not after ssl-with-crypto and libiconv, but\nafter {arm,mozilla,ppc}-sha1, if I were naming it. This is not\nlike an absolute must-to-have: \"on this platform, libc is not\nenough and we NEED to explicitly ask for -liconv\". It is more\nlike a choose-to-use: \"we could use openssl sha1 implementation,\nbut I choose to use Mozilla one\".\n"},{"id":"67258","messageId":"alpine.LSU.1.00.0802032109050.7372@racer.site","threadId":"11845","inReplyTo":"20080203045033.GL26392-oU/tDdhfGLReoWH0uzbU5w@public.gmane.org","subject":"Re: [PATCH] compat: Add simplified merge sort implementation from glibc","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin-mmb7mzphnfy@public.gmane.org","sentAt":"2008-02-03T21:09:35Z","receivedAt":"2008-02-03T21:09:35Z","isPatch":true,"sender":{"key":"johannes.schindelin-mmb7mzphnfy@public.gmane.org","avatar":null},"body":"\nHi,\n\nOn Sat, 2 Feb 2008, Brian Downing wrote:\n\n> On Sun, Feb 03, 2008 at 02:37:27AM +0000, Johannes Schindelin wrote:\n> > I should add that this is a stripped-down version of glibc's sort() \n> > (yes, the GPL of glibc allows that we rip it, for all you license \n> > wieners out there).\n> > \n> > AFAIR the discussion about the different implementations of a sort \n> > algorithm boiled down to one particular implementation being quicker \n> > than what this patch has, but with dubious licensing, and the glibc \n> > implementation without the modifications present in this patch being \n> > slower.\n> > \n> > So I would like this to go in, evidently, if only as a starting point \n> > for people to play with sorting algorithms, to find the one which is \n> > optimal for our general use (we have quite some uses where we put in \n> > _almost_ sorted data, which seems to be the worst-case for many \n> > sorting algorithms).\n> \n> If this is what I am thinking of, the sort of dubious licensing was \n> faster than glibc's quicksort. This patch, however, is simplified from \n> glibc's mergesort (which is what glibc uses for the qsort() call except \n> for very large arrays), and was determined to be faster than both.\n> \n> See:\n> \n> http://groups.google.com/group/msysgit/browse_frm/thread/3c2eb564b9d0a994\n> \n> and the links from that thread for more information.\n\nYeah, sorry, I forgot that important fact.\n\nThanks,\nDscho\n"},{"id":"67284","messageId":"20080204010552.03541642.froese@gmx.de","threadId":"11845","inReplyTo":"20080203011130.GK26392@lavos.net","subject":"Re: [PATCH] compat: Add simplified merge sort implementation from glibc","fromName":"Edgar Toernig","fromEmail":"froese@gmx.de","sentAt":"2008-02-04T00:05:52Z","receivedAt":"2008-02-04T00:05:52Z","isPatch":true,"sender":{"key":"froese@gmx.de","avatar":null},"body":"\tif (size < 1024) {\n-\t\tchar buf[size]; /* gcc-ism */\n+\t\tchar buf[1024];\n"},{"id":"67313","messageId":"20080204024644.GM26392@lavos.net","threadId":"11845","inReplyTo":"20080204010552.03541642.froese-Mmb7MZpHnFY@public.gmane.org","subject":"Re: [PATCH] compat: Add simplified merge sort implementation from glibc","fromName":"Brian Downing","fromEmail":"bdowning-ou/tddhfglreowh0uzbu5w@public.gmane.org","sentAt":"2008-02-04T02:46:44Z","receivedAt":"2008-02-04T02:46:44Z","isPatch":true,"sender":{"key":"bdowning-ou/tddhfglreowh0uzbu5w@public.gmane.org","avatar":null},"body":"\nOn Mon, Feb 04, 2008 at 01:05:52AM +0100, Edgar Toernig wrote:\n> \tif (size < 1024) {\n> -\t\tchar buf[size]; /* gcc-ism */\n> +\t\tchar buf[1024];\n\nGood point; when it was a mingw-only hack the gcc-ism didn't matter.\n\nI'll see if I can push an updated patch in a day or so...\n\n-bcd\n"},{"id":"67498","messageId":"e2b179460802050219h58f086fer77792e3f06d74ff4@mail.gmail.com","threadId":"11845","inReplyTo":"20080203045033.GL26392-oU/tDdhfGLReoWH0uzbU5w@public.gmane.org","subject":"Re: [PATCH] compat: Add simplified merge sort implementation from glibc","fromName":"Mike Ralphson","fromEmail":"mike.ralphson-re5jqeeqqe8avxtiumwx3w@public.gmane.org","sentAt":"2008-02-05T10:19:32Z","receivedAt":"2008-02-05T10:19:32Z","isPatch":true,"sender":{"key":"mike.ralphson-re5jqeeqqe8avxtiumwx3w@public.gmane.org","avatar":null},"body":"\nOn Feb 3, 2008 4:50 AM, Brian Downing wrote:\n> On Sun, Feb 03, 2008 at 02:37:27AM +0000, Johannes Schindelin wrote:\n> > I should add that this is a stripped-down version of glibc's sort() (yes,\n> > the GPL of glibc allows that we rip it, for all you license wieners out\n> > there).\n> >\n> > AFAIR the discussion about the different implementations of a sort\n> > algorithm boiled down to one particular implementation being quicker than\n> > what this patch has, but with dubious licensing, and the glibc\n> > implementation without the modifications present in this patch being\n> > slower.\n> >\n> > So I would like this to go in, evidently, if only as a starting point for\n> > people to play with sorting algorithms, to find the one which is optimal\n> > for our general use (we have quite some uses where we put in _almost_\n> > sorted data, which seems to be the worst-case for many sorting\n> > algorithms).\n>\n> If this is what I am thinking of, the sort of dubious licensing was\n> faster than glibc's quicksort. This patch, however, is simplified from\n> glibc's mergesort (which is what glibc uses for the qsort() call except\n> for very large arrays), and was determined to be faster than both.\n>\n> See:\n>\n> http://groups.google.com/group/msysgit/browse_frm/thread/3c2eb564b9d0a994\n>\n> and the links from that thread for more information.\n\nTested-by: Mike Ralphson \n\nMany thanks Brian, I held off from submitting your patch to git.git\nbecause of the 1.5.4 freeze. I'll retest my other candidate qsort\nimplementations and report back. For now this makes git look good on\nAIX. It would be good to have feedback from users of older versions of\nSolaris too.\n\nOnce the final patch is in, I'll drop some queued AIX Makefile patches on top.\n\nCheers, Mike\n"},{"id":"67515","messageId":"20080205141139.GN26392@lavos.net","threadId":"11845","inReplyTo":"1202209509-13760-1-git-send-email-bdowning@lavos.net","subject":"Re: [PATCH] compat: Add simplified merge sort implementation from glibc","fromName":"Brian Downing","fromEmail":"bdowning@lavos.net","sentAt":"2008-02-05T14:11:39Z","receivedAt":"2008-02-05T14:11:39Z","isPatch":true,"sender":{"key":"bdowning@lavos.net","avatar":"https://avatars.githubusercontent.com/u/366426?v=4"},"body":"I didn't notice that the previous patch made it into pu. The only other\nchanges to this patch was changing the makefile variable name from\n\"NEED_QUICK_QSORT\" to \"INTERNAL_QSORT\", and some changes to the commit\nmessage.\n\nI am fine with either version going in.\n\n-bcd\n"},{"id":"67541","messageId":"7v3as7b29q.fsf@gitster.siamese.dyndns.org","threadId":"11845","inReplyTo":"20080205141139.GN26392@lavos.net","subject":"Re: [PATCH] compat: Add simplified merge sort implementation from glibc","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-02-05T20:02:09Z","receivedAt":"2008-02-05T20:02:09Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"bdowning@lavos.net (Brian Downing) writes:\n\n> I didn't notice that the previous patch made it into pu.\n\nWell, 'pu' is not something to \"make into\". Being there is to\nserve merely as a reminder that such a topic existed and as an\nencouragement for a resend of an improved version.\n\nIf you have more polished one, please send it in. I'll discard\nthe one in 'pu' and replace.\n"},{"id":"67555","messageId":"20080205210728.GO26392@lavos.net","threadId":"11845","inReplyTo":"7v3as7b29q.fsf@gitster.siamese.dyndns.org","subject":"Re: [PATCH] compat: Add simplified merge sort implementation from glibc","fromName":"Brian Downing","fromEmail":"bdowning@lavos.net","sentAt":"2008-02-05T21:07:29Z","receivedAt":"2008-02-05T21:07:29Z","isPatch":true,"sender":{"key":"bdowning@lavos.net","avatar":"https://avatars.githubusercontent.com/u/366426?v=4"},"body":"On Tue, Feb 05, 2008 at 12:02:09PM -0800, Junio C Hamano wrote:\n> If you have more polished one, please send it in. I'll discard\n> the one in 'pu' and replace.\n\nThe \"more polished\" one is the great-grandparent of this post.\n\nExcept now I notice that it didn't make it to the vger list, at least\naccording to gmane's view of things. I've had other problems with\ngit-send-email in the past.\n\nI'll resend it (replying to this message) through my normal mailer.\n\n-bcd\n"}]}