This is the mail archive of the cygwin mailing list for the Cygwin project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

damaged version of qsort.c in the Cygwin library


Here what I have send to M. Douglas McIlroy  ::::::

The Cygwin library has a copy of qsort, which you published with Bentley
around 1993.

About 5 years ago I obtained the source from that library in order to
compare its performance against my sorters.  I was delighted for
awhile that my sorters were wildly outperforming qsort on a family of
examples in your test bench.  Until I had a closer look at the source
and compared it against your published version.

The code had been damaged by an "improvement" that invokes sometimes
insertionsort (not only at the begining), which causes quadratic
blow ups.  I reported the problem to a 'volunteer', likely an employee
of RedHat.  It turns out that now, years later the damaged version is
still in the Cygwin library.  You can find it at:

  https://sourceware.org/viewvc/src/newlib/libc/search/qsort.c?revision=1.2&view=markup

See the variable swap_cnt and the associated code for the damage.

I am NOT reporting the problem again (due to the way I was harassed
when I reported the defect) and leave it to you to take action.

See below for my fixed version.
I removed swap_cnt and the associated code.
I have also ordered the actions on the two partitions to minimize
stack space.
The second recursive call has been replaced.

The Cygwin version has other undocumented changes involving a
procedure qsort_r for which I have no appetite to even think about
it; software engineering at its worst.

Please notify Bentley as you see fit.

-- 
Dennis de Champeaux     dc AT ontooo . com & ddcc AT rs6.risingnet . net

Home page:                          rs6.risingnet.net/~ddcc
Health Info Anytime for Everyone:   www.HealthCheck4Me.info
Exercise for the Mind:              www.SuDoKuChallenge.us 
Marketing site:                     www.OntoOO.com
               >>  Do NOT buy Dell, Mac, Ford, Chrysler  <<
               >>        Boycott Chinese Products        <<

====================================================================================

Here the fixed main procedure (which is named "bentley")::

void bentley(a, n, es, cmp)
     void *a;
     size_t n;
     size_t es;
     int (*cmp)();
{
  char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
  int d, r, swaptype; 
  // The use of swap_cnt and the 2nd invocation of insertionsort has been removed
  // int swap_cnt; 

loop:	SWAPINIT(a, es);
  // swap_cnt = 0;
	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) > 0;
			     pl -= es)
				swap(pl, pl - es);
		return;
	}
	pm = (char *) a + (n / 2) * es;
	if (n > 7) {
		pl = a;
		pn = (char *) a + (n - 1) * es;
		if (n > 40) {
			d = (n / 8) * es;
			pl = med33(pl, pl + d, pl + 2 * d, cmp);
			pm = med33(pm - d, pm, pm + d, cmp);
			pn = med33(pn - 2 * d, pn - d, pn, cmp);
		}
		pm = med33(pl, pm, pn, cmp);
	}

	swap(a, pm);
	pa = pb = (char *) a + es;
	// pa = pb = (char *) a;
	pc = pd = (char *) a + (n - 1) * es;
	for (;;) {
		while (pb <= pc && (r = cmp(pb, a)) <= 0) {
			if (r == 0) {
			        // swap_cnt = 1;
				swap(pa, pb);
				pa += es;
			}
			pb += es;
		}
		while (pb <= pc && (r = cmp(pc, a)) >= 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) > 0; 
			     pl -= es)
				swap(pl, pl - es);
		return;
	}
	*/

	pn = (char *) a + n * es;
	r = min(pa - (char *)a, pb - pa);
	vecswap(a, pb - r, r);
	r = min(pd - pc, pn - pd - es);
	vecswap(pb, pn - r, r);

	/* Ordering on the recursive calls has been added to obtain at most 
	   log2(N) stack space 
	if ((r = pb - pa) > es)
		bentley(a, r / es, es, cmp);
	if ((r = pd - pc) > es) { 
	        // Iterate rather than recurse to save stack space 
		a = pn - r;
		n = r / es;
		goto loop;
	}
	*/

    int left =  pb - pa;
    int right = pd - pc;
    if ( left <= right ) {
       if ( left > es ) bentley(a, left / es, es, cmp);
       if ( right > es ) {
	   // Iterate rather than recurse to save stack space 
	   a = pn - right;
	   n = right / es;
	   goto loop;
       }
    } else {
       if ( right > es ) bentley(pn-right, right / es, es, cmp);
       if ( left > es ) {
	   // Iterate rather than recurse to save stack space 
	   // a = pn - left;
	   n = left / es;
	   goto loop;
       }
    }
} // end of bentley



--
Problem reports:       http://cygwin.com/problems.html
FAQ:                   http://cygwin.com/faq/
Documentation:         http://cygwin.com/docs.html
Unsubscribe info:      http://cygwin.com/ml/#unsubscribe-simple


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]