Re: cygwin qsort erratic

[Brian Inglis <Brian.Inglis@SystematicSw.ab.ca>]

On 2020-08-31 12:00, Thomas Wolff wrote:
> Am 31.08.2020 um 19:50 schrieb Kurt-Karen Carlson-Lougheed via Cygwin:
>> On Sun, Aug 30, 2020 at 7:55 PM Brian Inglis wrote:
>>> On 2020-08-30 15:27, Kurt-Karen Carlson-Lougheed via Cygwin wrote:
>>>> In a small percentage of qsort requests, the results are erratic. Running
>>>> the same code under Linux (RHEL7) does NOT have this problem. I updated
>>> my
>>>> cygwin to current and the problem persists. I copied the latest
>>> netbsd.org
>>>> qsort.c and compiled into my code, the problem is resolved with that
>>>> version of qsort.
>>>>
>>>> In researching this issue, there was a post to this list 2015-01-11
>>>> reporting a
>>>> 'damaged' qsort. This may still be the same issue. The netbsd version I
>>> am
>>>> now using is dated 2017-05-19.
>>>>
>>>> My code experiencing this is SourceForge uac19, I'll be posting the
>>>> corrected version (v3.2) with the netbsd qsort tomorrow after completing
>>>> validation tests. I would ultimately like to see cygwin's qsort fixed.

>>> As qsort depends on the array object data types and comparison
>>> functions, please post a Simple Test Case, showing at least those types
>>> and function(s), and the faulty output results.
>> Corinna,
>> I'm a cygwin user and neither a cygwin nor netbsd developer. I do not know
>> what newlib or 'git format-patch' are. If I had access to source for
>> cygwin's qsort  I could probably devise a patch, but it's probably better
>> for somebody familiar with the tools cygwin uses to do that. The attached
>> qqsort.h is an easy geek read. That qsort works with Linux/RHEL7 and with
>> netbsd's version under cygwin should make fixing it straight forward for
>> somebody in the know.

>> Brian,
>> It's difficult to produce a simple test case with erratic behavior. I have
>> wrapped my qsort invocations within a qqsort routine. I've attached
>> qqsort.h which includes both the wrapper and the netbad qsort.c renamed as
>> Qsort (and with _DIAGASSERT's commented out). Also attached is cygsort.txt
>> which is script output demonstrating the problem. My apologies that is 200+
>> lines, the Verbose mode states whether Qsort (netbsd) or qsort (cygwin) is
>> being invoked, I added the '$' command to toggle back and forth. Descending
>> sorts on the D/C (dpc) column have been most problematic. The descending
>> '+S dpc' after the ascending '+s dpc' is the most graphic example. I did
>> publish uac19 v3.3 on SourceForge this morning, or I can send somebody a
>> tgz.

> Kurt-Karen, this is hard to comprehend. It is common practice that someone who
> claims something is buggy, especially about something essential like qsort,
> should demonstrate that claim with a reproducible test case, even if, as you
> say, it may be difficult to produce one. If this happens in a series of
> invocations you have it should be possible to identify one case with wrong
> results and reproduce its input and invocation scenario.

You attached the qsort source, which is already in Cygwin, but did not include
your input csv data, data structures, data reading, and qsort comparison
functions, which would allow us to try to reproduce the issue.
We need your raw input and output data, and the core sorting code, to do so.

The simplest approach is to use the sort utility to sort your input data to
produce the expected output, and compare that to the equivalent output generated
from your sort program.
If you added that capability to your code, and did that on every run, you could
capture the problem input and output data when diff returned non-zero status.

Most sort problems are from premature optimization: trying to be too efficient
in comparison functions, which then don't do exactly as expected in all the
input data cases: you create a heisenbug, which you then need to detect and
reproduce.
Often, making the comparison function code as simple and straightforward as
possible, and ensuring it will always give exactly the expected result,
eliminates the issue. First make it correct, then make it fast!

-- 
Take care. Thanks, Brian Inglis, Calgary, Alberta, Canada

This email may be disturbing to some readers as it contains
too much technical detail. Reader discretion is advised.
[Data in IEC units and prefixes, physical quantities in SI.]