From 43fe901b71f81cdff142048dfc27e492c445d225 Mon Sep 17 00:00:00 2001 From: Brian Downing Date: Tue, 5 Feb 2008 15:10:44 -0600 Subject: compat: Add simplified merge sort implementation from glibc qsort in Windows 2000 (and various other C libraries) is a Quicksort with the usual O(n^2) worst case. Unfortunately, sorting Git trees seems to get very close to that worst case quite often: $ /git/gitbad runstatus # On branch master qsort, nmemb = 30842 done, 237838087 comparisons. This patch adds a simplified version of the merge sort that is glibc's qsort(3). As a merge sort, this needs a temporary array equal in size to the array that is to be sorted, but has a worst-case performance of O(n log n). The complexity that was removed is: * Doing direct stores for word-size and -aligned data. * Falling back to quicksort if the allocation required to perform the merge sort would likely push the machine into swap. Even with these simplifications, this seems to outperform the Windows qsort(3) implementation, even in Windows XP (where it is "fixed" and doesn't trigger O(n^2) complexity on trees). [jes: moved into compat/qsort.c, as per Johannes Sixt's suggestion] [bcd: removed gcc-ism, thanks to Edgar Toernig. renamed make variable per Junio's comment.] Signed-off-by: Brian Downing Signed-off-by: Steffen Prohaska Signed-off-by: Johannes Schindelin Signed-off-by: Junio C Hamano --- Makefile | 8 ++++++++ 1 file changed, 8 insertions(+) (limited to 'Makefile') diff --git a/Makefile b/Makefile index 92341c4bb..fb82d14da 100644 --- a/Makefile +++ b/Makefile @@ -137,6 +137,10 @@ all:: # Define THREADED_DELTA_SEARCH if you have pthreads and wish to exploit # parallel delta searching when packing objects. # +# Define INTERNAL_QSORT to use Git's implementation of qsort(), which +# is a simplified version of the merge sort used in glibc. This is +# recommended if Git triggers O(n^2) behavior in your platform's qsort(). +# GIT-VERSION-FILE: .FORCE-GIT-VERSION-FILE @$(SHELL_PATH) ./GIT-VERSION-GEN @@ -722,6 +726,10 @@ ifdef NO_MEMMEM COMPAT_CFLAGS += -DNO_MEMMEM COMPAT_OBJS += compat/memmem.o endif +ifdef INTERNAL_QSORT + COMPAT_CFLAGS += -DINTERNAL_QSORT + COMPAT_OBJS += compat/qsort.o +endif ifdef THREADED_DELTA_SEARCH BASIC_CFLAGS += -DTHREADED_DELTA_SEARCH -- cgit v1.2.1