Bug 872497 - Remove problematic "optimization" in NS_QuickSort. r=jlebar
authorDerrick Moser <derrick_moser@yahoo.com>
Sat, 18 May 2013 15:16:02 -0400
changeset 143826 aad29aa892374b20bded7db2980c24f9e109d2d8
parent 143822 1196b497640b5281e428ec58a257eacc895fb367
child 143827 43c0c4dd5a5c859eb2e92c7b52f53f8b324cd0d6
push id2697
push userbbajaj@mozilla.com
push dateMon, 05 Aug 2013 18:49:53 +0000
treeherdermozilla-beta@dfec938c7b63 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersjlebar
bugs872497
milestone24.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 872497 - Remove problematic "optimization" in NS_QuickSort. r=jlebar This change allows us to avoid O(n^2) performance when partially sorted data is given to NS_QuickSort. We no longer attempt an insertion sort if the input appears pre-sorted. This brings the expected performance back to O(n*log(n)) but also eliminates the possibility of O(n) best case performance. Attempts to achieve O(n) performance should be the responsibility of callers as they are in a better position to evaluate the costs/benefit trade-off of looking for special cases that can be sorted quicker.
xpcom/glue/nsQuickSort.cpp
--- a/xpcom/glue/nsQuickSort.cpp
+++ b/xpcom/glue/nsQuickSort.cpp
@@ -99,80 +99,79 @@ void NS_QuickSort (
 	void *a,
 	unsigned int n,
     unsigned int es,
 	cmp_t *cmp,
 	void *data
     )
 {
 	char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
-	int d, r, swaptype, swap_cnt;
+	int d, r, swaptype;
 
 loop:	SWAPINIT(a, es);
-	swap_cnt = 0;
+	/* Use insertion sort when input is small */
 	if (n < 7) {
 		for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
 			for (pl = pm; pl > (char *)a && cmp(pl - es, pl, data) > 0;
 			     pl -= es)
 				swap(pl, pl - es);
 		return;
 	}
+	/* Choose pivot */
 	pm = (char *)a + (n / 2) * es;
 	if (n > 7) {
 		pl = (char *)a;
 		pn = (char *)a + (n - 1) * es;
 		if (n > 40) {
 			d = (n / 8) * es;
 			pl = med3(pl, pl + d, pl + 2 * d, cmp, data);
 			pm = med3(pm - d, pm, pm + d, cmp, data);
 			pn = med3(pn - 2 * d, pn - d, pn, cmp, data);
 		}
 		pm = med3(pl, pm, pn, cmp, data);
 	}
 	swap(a, pm);
 	pa = pb = (char *)a + es;
 
 	pc = pd = (char *)a + (n - 1) * es;
+	/* loop invariants:
+	 * [a, pa) = pivot
+	 * [pa, pb) < pivot
+	 * [pb, pc + es) unprocessed
+	 * [pc + es, pd + es) > pivot
+	 * [pd + es, pn) = pivot
+	 */
 	for (;;) {
 		while (pb <= pc && (r = cmp(pb, a, data)) <= 0) {
 			if (r == 0) {
-				swap_cnt = 1;
 				swap(pa, pb);
 				pa += es;
 			}
 			pb += es;
 		}
 		while (pb <= pc && (r = cmp(pc, a, data)) >= 0) {
 			if (r == 0) {
-				swap_cnt = 1;
 				swap(pc, pd);
 				pd -= es;
 			}
 			pc -= es;
 		}
 		if (pb > pc)
 			break;
 		swap(pb, pc);
-		swap_cnt = 1;
 		pb += es;
 		pc -= es;
 	}
-	if (swap_cnt == 0) {  /* Switch to insertion sort */
-		for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
-			for (pl = pm; pl > (char *)a && cmp(pl - es, pl, data) > 0;
-			     pl -= es)
-				swap(pl, pl - es);
-		return;
-	}
-
+	/* Move pivot values */
 	pn = (char *)a + n * es;
 	r = XPCOM_MIN(pa - (char *)a, pb - pa);
 	vecswap(a, pb - r, r);
 	r = XPCOM_MIN<size_t>(pd - pc, pn - pd - es);
 	vecswap(pb, pn - r, r);
+	/* Recursively process partitioned items */
 	if ((r = pb - pa) > (int)es)
         NS_QuickSort(a, r / es, es, cmp, data);
 	if ((r = pd - pc) > (int)es) {
 		/* Iterate rather than recurse to save stack space */
 		a = pn - r;
 		n = r / es;
 		goto loop;
 	}