X-Recipient:	archive-cygwin AT delorie DOT com
DomainKey-Signature:	a=rsa-sha1; c=nofws; d=sourceware.org; h=list-id
	:list-unsubscribe:list-subscribe:list-archive:list-post
	:list-help:sender:from:message-id:subject:to:date:cc
	:mime-version:content-transfer-encoding:content-type; q=dns; s=
	default; b=KWkZK3v+ToJiZcap7ircKJGWTh8MkQ1LBLbaZdhNzVhEOPCyH75eQ
	Xr0zWFbJrQ+uSUY/X1hrG7kkwpVlGiLYzycz/rOh+WERHVn/JrpnRLZSA49nZ3rm
	LakxGVIbsaRwTnWempJKBrrsFtiQqXYZ5WqOoRSnAZNiNEgPctBFic=
DKIM-Signature:	v=1; a=rsa-sha1; c=relaxed; d=sourceware.org; h=list-id
	:list-unsubscribe:list-subscribe:list-archive:list-post
	:list-help:sender:from:message-id:subject:to:date:cc
	:mime-version:content-transfer-encoding:content-type; s=default;
	bh=6P2aCPBj4/CeXf1FJ8kjocOMmYI=; b=ywU8/X5Nzs1+VzibyrEuXJ+10vHw
	8gF8012aWWdIL76mfk1D3ONbyrTINnViHN0p/nw2ZX634Zcec91Loyjm7SS+xAnA
	yCMq0s5/e6fPdSHe6w5GinS03UVugF++Vz4n2P72/+iO1lqK0eStZU38/SPrLqdk
	KxOCEHthm1ca3oQ=
Mailing-List:	contact cygwin-help AT cygwin DOT com; run by ezmlm
List-Id:	<cygwin.cygwin.com>
List-Subscribe:	<mailto:cygwin-subscribe AT cygwin DOT com>
List-Archive:	<http://sourceware.org/ml/cygwin/>
List-Post:	<mailto:cygwin AT cygwin DOT com>
List-Help:	<mailto:cygwin-help AT cygwin DOT com>, <http://sourceware.org/ml/#faqs>
Sender:	cygwin-owner AT cygwin DOT com
Mail-Followup-To:	cygwin AT cygwin DOT com
Delivered-To:	mailing list cygwin AT cygwin DOT com
Authentication-Results:	sourceware.org; auth=none
X-Virus-Found:	No
X-Spam-SWARE-Status:	No, score=-0.2 required=5.0 tests=AWL,BAYES_00,T_RP_MATCHES_RCVD autolearn=ham version=3.3.2
X-HELO:	rs6.risingnet.net
From:	ddcc <ddcc AT rs6 DOT risingnet DOT net>
Message-Id:	<201501112354.t0BNsoMk039694@rs6.risingnet.net>
Subject:	damaged version of qsort.c in the Cygwin library
To:	cygwin AT cygwin DOT com
Date:	Sun, 11 Jan 2015 15:54:50 -0800 (PST)
CC:	ddcc <ddcc AT rs6 DOT risingnet DOT net>
MIME-Version:	1.0
X-IsSubscribed:	yes

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

- Raw text -