cygwin qsort erratic

cygwin qsort erratic

[Kurt-Karen Carlson-Lougheed]

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.
Regards, Kurt

Re: cygwin qsort erratic

[Brian Inglis]

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.

-- 
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.]

Re: cygwin qsort erratic

[Corinna Vinschen]

On Aug 30 14: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.

qsort is implemented in newlib, so patches should go to the newlib
AT sourceware DOT org mailing list (in `git format-patch' layout).


Thanks,
Corinna

-- 
Corinna Vinschen
Cygwin Maintainer

Re: cygwin qsort erratic

[Kurt-Karen Carlson-Lougheed]

[-- Attachment #1: Type: text/plain, Size: 2845 bytes --]

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.

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.

Regards, Kurt

On Sun, Aug 30, 2020 at 7:55 PM Brian Inglis <
Brian.Inglis@systematicsw.ab.ca> 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.
>
> --
> 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.]
> --
> Problem reports:      https://cygwin.com/problems.html
> FAQ:                  https://cygwin.com/faq/
> Documentation:        https://cygwin.com/docs.html
> Unsubscribe info:     https://cygwin.com/ml/#unsubscribe-simple
>

[-- Attachment #2: cygsort.txt --]
[-- Type: text/plain, Size: 13438 bytes --]

Script started on 2020-08-31 08:54:58-07:00 [TERM="xterm" TTY="/dev/pty1" COLUMNS="132" LINES="54"]
kc: uac19 --version
# uac19 v3.3, Package: uac19-v3.3
kc: uac19 -use owid -v # curl today's file
# Report     names: 	US WO
Curl: chdir /home/kac/Downloads
# system (curl --insecure -O -# https://covid.ourworldindata.org/data/owid-covid-data.csv 2>/dev/null)
Open: /usr/local/etc/Countries:
Open: /usr/local/etc/Co-Remap:
# Days: 245 First=0 Last=245 Columns=1cipdEevl
# uac19  -m 500  -d 50  -i 1  -v
#  -n US,WO
Date   Confirmed Increase    Inc.%  Deaths  Died+ Days na,cou Location
----   --------- --------    -----  ------  ----- ---- ------ --------
08-31   25251334   221484     0.9%  846841  3687+  1.0 WO,WOR World
08-31    5997163    35581     0.6%  183069   290+  1.0 US,USA United States
kc: uac19 -f ~/Downloads/owid-covid-data.csv -x # interactive mode 
Date   Confirmed Increase    Inc.%  Deaths  Died+ Days Location
----   --------- --------    -----  ------  ----- ---- --------
08-31   25251334   221484     0.9%  846841  3687+  1.0 World
08-31    5997163    35581     0.6%  183069   290+  1.0 United States
Options? -n . +c dpc,-inc.,die -pop 1 -pct 1 # adjust columns, minimum 1% confirmed
Date   Confirmed Increase  Deaths  D/C% Million Pct.Co Days Location
----   --------- --------  ------  ---- ------- ------ ---- --------
08-31     625056     2505   14028  2.2%    59.2  1.056  1.0 South Africa
08-31      43750      124     877  2.0%     3.0  1.477  1.0 Armenia
08-31     114020      397     919  0.8%     8.6  1.320  1.0 Israel
08-31      51574      183     189  0.4%     1.7  3.045  1.0 Bahrain
08-31      85544      539     677  0.8%     5.1  1.682  1.0 Oman
08-31     118575      168     197  0.2%     2.9  4.128  1.0 Qatar
08-31      84636      412     530  0.6%     4.3  1.987  1.0 Kuwait
08-31    5997163    35581  183069  3.1%   331.0  1.812  1.0 United States
08-31      32848      298     434  1.3%     2.9  1.145  1.0 Puerto Rico
08-31      92065      728    1995  2.2%     4.3  2.139  1.0 Panama
08-31    3862311    16158  120828  3.1%   212.3  1.819  1.0 Brazil
08-31     647166     7731   28788  4.4%    32.9  1.966  1.0 Peru
08-31     607938     8024   19364  3.2%    50.8  1.196  1.0 Colombia
08-31     409974     1965   11244  2.7%    19.1  2.147  1.0 Chile
Options? -V +c -v +S conf # very verbose, sort confirme descending
# ChkSort 04 0,0,1 c Confirmed 1
# Days: 245 First=0 Last=245 Columns=1cidWmYel
# uac19  -m 500  -d 50  -P  1.0  -Y  1.0  -i 1  +S Confirmed  -V  -x
Date   Confirmed Increase  Deaths  D/C% Million Pct.Co Days Location
----   --------- --------  ------  ---- ------- ------ ---- --------
# Qsort:Confirmed
# l_sort:0:
08-31    5997163    35581  183069  3.1%   331.0  1.812  1.0 United States
08-31    3862311    16158  120828  3.1%   212.3  1.819  1.0 Brazil
08-31     647166     7731   28788  4.4%    32.9  1.966  1.0 Peru
08-31     625056     2505   14028  2.2%    59.2  1.056  1.0 South Africa
08-31     607938     8024   19364  3.2%    50.8  1.196  1.0 Colombia
08-31     409974     1965   11244  2.7%    19.1  2.147  1.0 Chile
08-31     118575      168     197  0.2%     2.9  4.128  1.0 Qatar
08-31     114020      397     919  0.8%     8.6  1.320  1.0 Israel
08-31      92065      728    1995  2.2%     4.3  2.139  1.0 Panama
08-31      85544      539     677  0.8%     5.1  1.682  1.0 Oman
08-31      84636      412     530  0.6%     4.3  1.987  1.0 Kuwait
08-31      51574      183     189  0.4%     1.7  3.045  1.0 Bahrain
08-31      43750      124     877  2.0%     3.0  1.477  1.0 Armenia
08-31      32848      298     434  1.3%     2.9  1.145  1.0 Puerto Rico
# Displayed 14
Options? +S dpc # sort d/c descending
# ChkSort 12 0,0,1 W D/C% 1
# ChkSort 13 0,0,1 W DpC 1
# Days: 245 First=0 Last=245 Columns=1cidWmYel
# uac19  -m 500  -d 50  -P  1.0  -Y  1.0  -i 1  +S D/C%  -V  -x
Date   Confirmed Increase  Deaths  D/C% Million Pct.Co Days Location
----   --------- --------  ------  ---- ------- ------ ---- --------
# Qsort:D/C%
# lDsort:0
08-31     647166     7731   28788  4.4%    32.9  1.966  1.0 Peru
08-31     607938     8024   19364  3.2%    50.8  1.196  1.0 Colombia
08-31    3862311    16158  120828  3.1%   212.3  1.819  1.0 Brazil
08-31    5997163    35581  183069  3.1%   331.0  1.812  1.0 United States
08-31     409974     1965   11244  2.7%    19.1  2.147  1.0 Chile
08-31     625056     2505   14028  2.2%    59.2  1.056  1.0 South Africa
08-31      92065      728    1995  2.2%     4.3  2.139  1.0 Panama
08-31      43750      124     877  2.0%     3.0  1.477  1.0 Armenia
08-31      32848      298     434  1.3%     2.9  1.145  1.0 Puerto Rico
08-31     114020      397     919  0.8%     8.6  1.320  1.0 Israel
08-31      85544      539     677  0.8%     5.1  1.682  1.0 Oman
08-31      84636      412     530  0.6%     4.3  1.987  1.0 Kuwait
08-31      51574      183     189  0.4%     1.7  3.045  1.0 Bahrain
08-31     118575      168     197  0.2%     2.9  4.128  1.0 Qatar
# Displayed 14
Options? $ # toggle netbsd Qsort to cygwin qsort
# Days: 245 First=0 Last=245 Columns=1cidWmYel
# uac19  -m 500  -d 50  -P  1.0  -Y  1.0  -i 1  +S D/C%  -V  -x
Date   Confirmed Increase  Deaths  D/C% Million Pct.Co Days Location
----   --------- --------  ------  ---- ------- ------ ---- --------
# qsort:D/C%
# lDsort:0
08-31     647166     7731   28788  4.4%    32.9  1.966  1.0 Peru
08-31     607938     8024   19364  3.2%    50.8  1.196  1.0 Colombia
08-31    3862311    16158  120828  3.1%   212.3  1.819  1.0 Brazil
08-31    5997163    35581  183069  3.1%   331.0  1.812  1.0 United States
08-31     409974     1965   11244  2.7%    19.1  2.147  1.0 Chile
08-31     625056     2505   14028  2.2%    59.2  1.056  1.0 South Africa
08-31      92065      728    1995  2.2%     4.3  2.139  1.0 Panama
08-31      43750      124     877  2.0%     3.0  1.477  1.0 Armenia
08-31      32848      298     434  1.3%     2.9  1.145  1.0 Puerto Rico
08-31     114020      397     919  0.8%     8.6  1.320  1.0 Israel
08-31      85544      539     677  0.8%     5.1  1.682  1.0 Oman
08-31      84636      412     530  0.6%     4.3  1.987  1.0 Kuwait
08-31      51574      183     189  0.4%     1.7  3.045  1.0 Bahrain
08-31     118575      168     197  0.2%     2.9  4.128  1.0 Qatar
# Displayed 14
Options? +S conf # resort confirmed
# ChkSort 04 0,0,1 c Confirmed 1
# Days: 245 First=0 Last=245 Columns=1cidWmYel
# uac19  -m 500  -d 50  -P  1.0  -Y  1.0  -i 1  +S Confirmed  -V  -x
Date   Confirmed Increase  Deaths  D/C% Million Pct.Co Days Location
----   --------- --------  ------  ---- ------- ------ ---- --------
# qsort:Confirmed
# l_sort:0:
08-31    5997163    35581  183069  3.1%   331.0  1.812  1.0 United States
08-31    3862311    16158  120828  3.1%   212.3  1.819  1.0 Brazil
08-31     647166     7731   28788  4.4%    32.9  1.966  1.0 Peru
08-31     625056     2505   14028  2.2%    59.2  1.056  1.0 South Africa
08-31     607938     8024   19364  3.2%    50.8  1.196  1.0 Colombia
08-31     409974     1965   11244  2.7%    19.1  2.147  1.0 Chile
08-31     118575      168     197  0.2%     2.9  4.128  1.0 Qatar
08-31     114020      397     919  0.8%     8.6  1.320  1.0 Israel
08-31      92065      728    1995  2.2%     4.3  2.139  1.0 Panama
08-31      85544      539     677  0.8%     5.1  1.682  1.0 Oman
08-31      84636      412     530  0.6%     4.3  1.987  1.0 Kuwait
08-31      51574      183     189  0.4%     1.7  3.045  1.0 Bahrain
08-31      43750      124     877  2.0%     3.0  1.477  1.0 Armenia
08-31      32848      298     434  1.3%     2.9  1.145  1.0 Puerto Rico
# Displayed 14
Options? +S dpc # sort d/c again (cygwin qsort)
# ChkSort 12 0,0,1 W D/C% 1
# ChkSort 13 0,0,1 W DpC 1
# Days: 245 First=0 Last=245 Columns=1cidWmYel
# uac19  -m 500  -d 50  -P  1.0  -Y  1.0  -i 1  +S D/C%  -V  -x
Date   Confirmed Increase  Deaths  D/C% Million Pct.Co Days Location
----   --------- --------  ------  ---- ------- ------ ---- --------
# qsort:D/C%
# lDsort:0
08-31     647166     7731   28788  4.4%    32.9  1.966  1.0 Peru
08-31     607938     8024   19364  3.2%    50.8  1.196  1.0 Colombia
08-31    3862311    16158  120828  3.1%   212.3  1.819  1.0 Brazil
08-31     409974     1965   11244  2.7%    19.1  2.147  1.0 Chile
08-31     625056     2505   14028  2.2%    59.2  1.056  1.0 South Africa
08-31    5997163    35581  183069  3.1%   331.0  1.812  1.0 United States
08-31      92065      728    1995  2.2%     4.3  2.139  1.0 Panama
08-31      43750      124     877  2.0%     3.0  1.477  1.0 Armenia
08-31      32848      298     434  1.3%     2.9  1.145  1.0 Puerto Rico
08-31     114020      397     919  0.8%     8.6  1.320  1.0 Israel
08-31      85544      539     677  0.8%     5.1  1.682  1.0 Oman
08-31      84636      412     530  0.6%     4.3  1.987  1.0 Kuwait
08-31      51574      183     189  0.4%     1.7  3.045  1.0 Bahrain
08-31     118575      168     197  0.2%     2.9  4.128  1.0 Qatar
# Displayed 14
Options? # note above not in order
# Days: 245 First=0 Last=245 Columns=1cidWmYel
# uac19  -m 500  -d 50  -P  1.0  -Y  1.0  -i 1  +S D/C%  -V  -x
Options? +s dpc # sort d/c ascending
# ChkSort 12 0,1,0 W D/C% 1
# ChkSort 13 0,1,0 W DpC 1
# Days: 245 First=0 Last=245 Columns=1cidWmYel
# uac19  -m 500  -d 50  -P  1.0  -Y  1.0  -i 1  +s D/C%  -V  -x
Date   Confirmed Increase  Deaths  D/C% Million Pct.Co Days Location
----   --------- --------  ------  ---- ------- ------ ---- --------
# qsort:D/C%
# lDsort:1
08-31     118575      168     197  0.2%     2.9  4.128  1.0 Qatar
08-31      51574      183     189  0.4%     1.7  3.045  1.0 Bahrain
08-31      84636      412     530  0.6%     4.3  1.987  1.0 Kuwait
08-31      85544      539     677  0.8%     5.1  1.682  1.0 Oman
08-31     114020      397     919  0.8%     8.6  1.320  1.0 Israel
08-31      32848      298     434  1.3%     2.9  1.145  1.0 Puerto Rico
08-31      43750      124     877  2.0%     3.0  1.477  1.0 Armenia
08-31      92065      728    1995  2.2%     4.3  2.139  1.0 Panama
08-31     625056     2505   14028  2.2%    59.2  1.056  1.0 South Africa
08-31     409974     1965   11244  2.7%    19.1  2.147  1.0 Chile
08-31    5997163    35581  183069  3.1%   331.0  1.812  1.0 United States
08-31    3862311    16158  120828  3.1%   212.3  1.819  1.0 Brazil
08-31     607938     8024   19364  3.2%    50.8  1.196  1.0 Colombia
08-31     647166     7731   28788  4.4%    32.9  1.966  1.0 Peru
# Displayed 14
Options? +S d/c # sort d/c descending
# ChkSort 12 0,0,1 W D/C% 1
# Days: 245 First=0 Last=245 Columns=1cidWmYel
# uac19  -m 500  -d 50  -P  1.0  -Y  1.0  -i 1  +S D/C%  -V  -x
Date   Confirmed Increase  Deaths  D/C% Million Pct.Co Days Location
----   --------- --------  ------  ---- ------- ------ ---- --------
# qsort:D/C%
# lDsort:0
08-31     118575      168     197  0.2%     2.9  4.128  1.0 Qatar
08-31      51574      183     189  0.4%     1.7  3.045  1.0 Bahrain
08-31      84636      412     530  0.6%     4.3  1.987  1.0 Kuwait
08-31     114020      397     919  0.8%     8.6  1.320  1.0 Israel
08-31      85544      539     677  0.8%     5.1  1.682  1.0 Oman
08-31      32848      298     434  1.3%     2.9  1.145  1.0 Puerto Rico
08-31     647166     7731   28788  4.4%    32.9  1.966  1.0 Peru
08-31     607938     8024   19364  3.2%    50.8  1.196  1.0 Colombia
08-31    3862311    16158  120828  3.1%   212.3  1.819  1.0 Brazil
08-31    5997163    35581  183069  3.1%   331.0  1.812  1.0 United States
08-31     409974     1965   11244  2.7%    19.1  2.147  1.0 Chile
08-31     625056     2505   14028  2.2%    59.2  1.056  1.0 South Africa
08-31      92065      728    1995  2.2%     4.3  2.139  1.0 Panama
08-31      43750      124     877  2.0%     3.0  1.477  1.0 Armenia
# Displayed 14
Options? # that sure didn't work well, did it?
# Days: 245 First=0 Last=245 Columns=1cidWmYel
# uac19  -m 500  -d 50  -P  1.0  -Y  1.0  -i 1  +S D/C%  -V  -x
Options? $ # toggle cyqwin qsort back to netbsd Qsort
# Days: 245 First=0 Last=245 Columns=1cidWmYel
# uac19  -m 500  -d 50  -P  1.0  -Y  1.0  -i 1  +S D/C%  -V  -x
Date   Confirmed Increase  Deaths  D/C% Million Pct.Co Days Location
----   --------- --------  ------  ---- ------- ------ ---- --------
# Qsort:D/C%
# lDsort:0
08-31     647166     7731   28788  4.4%    32.9  1.966  1.0 Peru
08-31     607938     8024   19364  3.2%    50.8  1.196  1.0 Colombia
08-31    3862311    16158  120828  3.1%   212.3  1.819  1.0 Brazil
08-31    5997163    35581  183069  3.1%   331.0  1.812  1.0 United States
08-31     409974     1965   11244  2.7%    19.1  2.147  1.0 Chile
08-31     625056     2505   14028  2.2%    59.2  1.056  1.0 South Africa
08-31      92065      728    1995  2.2%     4.3  2.139  1.0 Panama
08-31      43750      124     877  2.0%     3.0  1.477  1.0 Armenia
08-31      32848      298     434  1.3%     2.9  1.145  1.0 Puerto Rico
08-31     114020      397     919  0.8%     8.6  1.320  1.0 Israel
08-31      85544      539     677  0.8%     5.1  1.682  1.0 Oman
08-31      84636      412     530  0.6%     4.3  1.987  1.0 Kuwait
08-31      51574      183     189  0.4%     1.7  3.045  1.0 Bahrain
08-31     118575      168     197  0.2%     2.9  4.128  1.0 Qatar
# Displayed 14
Options? # all is well with netbsd version
# Days: 245 First=0 Last=245 Columns=1cidWmYel
# uac19  -m 500  -d 50  -P  1.0  -Y  1.0  -i 1  +S D/C%  -V  -x
Options? quit
kc: exit
exit

Script done on 2020-08-31 09:03:46-07:00 [COMMAND_EXIT_CODE="0"]

[-- Attachment #3: qqsort.h --]
[-- Type: application/octet-stream, Size: 5963 bytes --]

/* (c) Copyright 2020 by Denali Sun Consulting - Kurt Carlson (FSF/GPL)	*/
/************************************************************************/
void	qqsort (void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *), char *type)
{
#ifndef	OS_WIN
	if (qq->v && type)	fprintf (stderr, "# qsort:%s\n", type);
	qsort (base, nmemb, size, compar);
}
#else
if (!qq->cygsort)
{	if (qq->v && type)	fprintf (stderr, "# Qsort:%s\n", type);
	Qsort (base, nmemb, size, compar);
} else
{	if (qq->v && type)	fprintf (stderr, "# qsort:%s\n", type);
	qsort (base, nmemb, size, compar);
}
}
/************************************************************************/
/*	$NetBSD: qsort.c,v 1.23 2017/05/19 19:48:19 christos Exp $	*/
/*-
 * Copyright (c) 1992, 1993
 *	The Regents of the University of California.  All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

#include <sys/cdefs.h>
#if defined(LIBC_SCCS) && !defined(lint)
#if 0
static char sccsid[] = "@(#)qsort.c	8.1 (Berkeley) 6/4/93";
#else
__RCSID("$NetBSD: qsort.c,v 1.23 2017/05/19 19:48:19 christos Exp $");
#endif
#endif /* LIBC_SCCS and not lint */

#include <sys/types.h>

#include <assert.h>
#include <errno.h>
#include <stdlib.h>

static inline char	*med3(char *, char *, char *,
    int (*)(const void *, const void *));
static inline void	 swapfunc(char *, char *, size_t, int);

#define min(a, b)	(a) < (b) ? a : b

/*
 * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".
 */
#define swapcode(TYPE, parmi, parmj, n) { 		\
	size_t i = (n) / sizeof (TYPE); 		\
	TYPE *pi = (TYPE *)(void *)(parmi); 		\
	TYPE *pj = (TYPE *)(void *)(parmj); 		\
	do { 						\
		TYPE	t = *pi;			\
		*pi++ = *pj;				\
		*pj++ = t;				\
        } while (--i > 0);				\
}

#define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \
	es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;

static inline void
swapfunc(char *a, char *b, size_t n, int swaptype)
{

	if (swaptype <= 1) 
		swapcode(long, a, b, n)
	else
		swapcode(char, a, b, n)
}

#define swap(a, b)						\
	if (swaptype == 0) {					\
		long t = *(long *)(void *)(a);			\
		*(long *)(void *)(a) = *(long *)(void *)(b);	\
		*(long *)(void *)(b) = t;			\
	} else							\
		swapfunc(a, b, es, swaptype)

#define vecswap(a, b, n) if ((n) > 0) swapfunc((a), (b), (size_t)(n), swaptype)

static inline char *
med3(char *a, char *b, char *c,
    int (*cmp)(const void *, const void *))
{

	return cmp(a, b) < 0 ?
	       (cmp(b, c) < 0 ? b : (cmp(a, c) < 0 ? c : a ))
              :(cmp(b, c) > 0 ? b : (cmp(a, c) < 0 ? a : c ));
}

void
Qsort(void *a, size_t n, size_t es,
    int (*cmp)(const void *, const void *))
{
	char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
	size_t d, r, s;
	int swaptype, cmp_result;
/*
2020-08-29 kac	Commment out following
	_DIAGASSERT(a != NULL || n == 0 || es == 0);
	_DIAGASSERT(cmp != NULL);
*/
loop:	SWAPINIT(a, es);
	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 = (char *) a;
		pn = (char *) a + (n - 1) * es;
		if (n > 40) {
			d = (n / 8) * es;
			pl = med3(pl, pl + d, pl + 2 * d, cmp);
			pm = med3(pm - d, pm, pm + d, cmp);
			pn = med3(pn - 2 * d, pn - d, pn, cmp);
		}
		pm = med3(pl, pm, pn, cmp);
	}
	swap(a, pm);
	pa = pb = (char *) a + es;

	pc = pd = (char *) a + (n - 1) * es;
	for (;;) {
		while (pb <= pc && (cmp_result = cmp(pb, a)) <= 0) {
			if (cmp_result == 0) {
				swap(pa, pb);
				pa += es;
			}
			pb += es;
		}
		while (pb <= pc && (cmp_result = cmp(pc, a)) >= 0) {
			if (cmp_result == 0) {
				swap(pc, pd);
				pd -= es;
			}
			pc -= es;
		}
		if (pb > pc)
			break;
		swap(pb, pc);
		pb += es;
		pc -= es;
	}

	pn = (char *) a + n * es;
	r = min(pa - (char *) a, pb - pa);
	vecswap(a, pb - r, r);
	r = min((size_t)(pd - pc), pn - pd - es);
	vecswap(pb, pn - r, r);
	/*
	 * To save stack space we sort the smaller side of the partition first
	 * using recursion and eliminate tail recursion for the larger side.
	 */
	r = pb - pa;
	s = pd - pc;
	if (r < s) {
		/* Recurse for 1st side, iterate for 2nd side. */
		if (s > es) {
			if (r > es)
				Qsort(a, r / es, es, cmp);
			a = pn - s;
			n = s / es;
			goto loop;
		}
	} else {
		/* Recurse for 2nd side, iterate for 1st side. */
		if (r > es) {
			if (s > es)
				Qsort(pn - s, s / es, es, cmp);
			n = r / es;
			goto loop;
		}
	}
}
#endif

Re: cygwin qsort erratic

[Thomas Wolff]

Am 31.08.2020 um 19:50 schrieb Kurt-Karen Carlson-Lougheed via Cygwin:
> 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.
Thomas

>
> 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.
>
> Regards, Kurt
>
> On Sun, Aug 30, 2020 at 7:55 PM Brian Inglis <
> Brian.Inglis@systematicsw.ab.ca> 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.
>>
>> --
>> 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.]
>> --
>> Problem reports:      https://cygwin.com/problems.html
>> FAQ:                  https://cygwin.com/faq/
>> Documentation:        https://cygwin.com/docs.html
>> Unsubscribe info:     https://cygwin.com/ml/#unsubscribe-simple
>>
>>
>> --
>> Problem reports:      https://cygwin.com/problems.html
>> FAQ:                  https://cygwin.com/faq/
>> Documentation:        https://cygwin.com/docs.html
>> Unsubscribe info:     https://cygwin.com/ml/#unsubscribe-simple

Re: cygwin qsort erratic

[Brian Inglis]

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.]

Re: cygwin qsort erratic

[Kurt-Karen Carlson-Lougheed]

[-- Attachment #1: Type: text/plain, Size: 6719 bytes --]

  Brian:
1. The Qsort() source I sent was from netbsd.org, NOT cygwin. netbsd works.
2. Complete package is on SourceForge as uac19 v3.3. I'm happy to send a
tgz if you prefer that. Read 3 choices at end before considering this.
3. Data is curl'd from owid as shown in the script example. Likewise I can
send a sample data set. The program analyzes COVID-19 csv files from either
owid or github/nytimes
4. I've used qsort() for years. I agree, keeping the sort routines simple
is always appropriate. I confirmed today the only ones that fail include
float divides, lDsort() and lXsort() in attached c19sort.c. When it's
pre-calculated and added to the struct it works, the code has a toggle now
for testing that.

Thomas:
I tried (again) today  to build a simple test case. The data structures in
use are complex, probably the only thing I can attempt is stripping down
the code which will be very time consuming. I know you don't know me at
all, but I've written code, debugged proprietary operating systems
(assembler), performed OS dump analysis, troubleshot intermittent hardware
issues, identified disk firmware issues causing intermittent data
corruption, identified nfs performance issues, managed large hpc clusters,
etc. etc. etc. over 40+ years.

I see three choices:
A. One of you look at simple the qqsort wrapper. I modified my code to
toggle between the functional netbsd Qsort() and cygwin qsort(). I have
demonstrated erroneous results coming from the cygwin version in a small
percentage of requests. If you can acknowledge that, perhaps you can check
the cygwin version of qsort() vs. the current netbsd.org?
B. If you could kindly provide me or point me to the cygwin qsort() source
I'll check it out myself.
C. We can thank each other and leave cygwin's qsort() as is broken in some
small number of circumstances since I've compiled netbsd's into my code and
that always works.

Regards, kurt

On Mon, Aug 31, 2020 at 11:50 AM Brian Inglis <
Brian.Inglis@systematicsw.ab.ca> wrote:

> 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.]
> --
> Problem reports:      https://cygwin.com/problems.html
> FAQ:                  https://cygwin.com/faq/
> Documentation:        https://cygwin.com/docs.html
> Unsubscribe info:     https://cygwin.com/ml/#unsubscribe-simple
>

[-- Attachment #2: c19sort.c --]
[-- Type: application/octet-stream, Size: 6972 bytes --]

/* (c) Copyright 2020 by Denali Sun Consulting - Kurt Carlson (FSF/GPL)	*/
/************************************************************************
	uac19 *sort() routines		
History:		See ChangeLog for more detailed changes
-------
2020-08-29 kac	due to windows/cygwin erratic sort add qsort from:
		http://cvsweb.netbsd.org/bsdweb.cgi/src/lib/libc/stdlib/qsort.c?rev=1.23&content-type=text/x-cvsweb-markup
2020-05-15 kac	split *sort() into c19sort.c
 ************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include "config.h"
#include "uac19.h"

extern	struct	SORT	*qq;		/* no qsort_r: cygwin != linux	*/
/************************************************************************/
int	f_sort (n1, n2)			/* sort file pointers		*/
struct	DAYS	*n1, *n2;
{
int	n = strcmp (n1->f, n2->f);
return (n);
}
/************************************************************************/
int	d_sort (d1, d2)			/* sort files date 		*/
struct	NDAY	*d1, *d2;
{
time_t	t1 = d1->tm;
time_t	t2 = d2->tm;
int	ti = (int) (t1-t2);
return (ti);
}
/************************************************************************/
int	t_sort (struct DATM *d1, struct DATM *d2)	/* date		*/
{
time_t	t1 = d1->t;
time_t	t2 = d2->t;
int	ti = (int) (t1-t2);
return (ti);
}
/************************************************************************/
int	a_sort (struct NAME *n1, struct NAME *n2)	/* index	*/
{
int	x1 = n1->ix;
int	x2 = n2->ix;
if (qq->v)	qq->v = 0,	fprintf (stderr, "# a_sort:%d\n", qq->o);
if (qq->o)	return (x1-x2);		else	return (x2-x1);
}
/************************************************************************/
int	l_sort (struct NAME *n1, struct NAME *n2)	/* confimed	*/
{
int	c1, c2;
if (qq->v)	qq->v = 0,	fprintf (stderr, "# l_sort:%d:\n", qq->o);
	c1 = n1->dx[*qq->l -1].co;
	c2 = n2->dx[*qq->l -1].co;
if (qq->o)	return (c1-c2);		else	return (c2-c1);
}
/************************************************************************/
int	lMsort (struct NAME *n1, struct NAME *n2)	/* confimed+	*/
{
int	c1 = n1->dx[*qq->l -1].co - n1->dx[*qq->p].co;
int	c2 = n2->dx[*qq->l -1].co - n2->dx[*qq->p].co;
if (c1==c2)
{	c1 = n1->dx[*qq->l -1].co;
	c2 = n2->dx[*qq->l -1].co;
}
if (qq->v)	qq->v = 0,	fprintf (stderr, "# lMsort:%d\n", qq->o);
if (qq->o)	return (c1-c2);		else	return (c2-c1);
}
/************************************************************************/
int	ldsort (struct NAME *n1, struct NAME *n2)	/* deaths	*/
{
int	d1 = n1->dx[*qq->l -1].de;
int	d2 = n2->dx[*qq->l -1].de;
if (d1==d2)
{	d1 = n1->dx[*qq->l -1].co;
	d2 = n2->dx[*qq->l -1].co;
}
if (qq->v)	qq->v = 0,	fprintf (stderr, "# ldsort:%d\n", qq->o);
if (qq->o)	return (d1-d2);		else	return (d2-d1);
}
/************************************************************************/
int	lEsort (struct NAME *n1, struct NAME *n2)	/* died+	*/
{
int	i1 = n1->dx[*qq->l -1].de - n1->dx[*qq->p].de;
int	i2 = n2->dx[*qq->l -1].de - n2->dx[*qq->p].de;
if (i1==i2)				/* identical?	*/
{	i1 = n1->dx[*qq->l -1].de;
	i2 = n2->dx[*qq->l -1].de;
}
if (i1==i2)				/* identical?	*/
{	i1 = n1->dx[*qq->l -1].co;
	i2 = n2->dx[*qq->l -1].co;
}
if (qq->v)	qq->v = 0,	fprintf (stderr, "# lEsort:%d\n", qq->o);
if (qq->o)	return (i1-i2);		else	return (i2-i1);
}
/************************************************************************/
int	lPsort (struct NAME *n1, struct NAME *n2)	/* pct		*/
{
float	f1 = 10000.* n1->pct;
float	f2 = 10000.* n2->pct;
if (qq->v)	qq->v = 0,	fprintf (stderr, "# lPsort:%d\n", qq->o);
if (qq->o)	return ((int) (f1-f2));	else	return ((int) (f2-f1));
}
/************************************************************************/
int	lDsort (struct NAME *n1, struct NAME *n2)	/* dead/confirm	*/
{
int	c1 = n1->dx[*qq->l -1].co,	d1 = n1->dx[*qq->l -1].de;
int	c2 = n2->dx[*qq->l -1].co,	d2 = n2->dx[*qq->l -1].de;
float	f1, f2;
if (qq->divide)				/* this fails w/cygwin's qsort	*/
{	f1 = 10000.* (float) d1 / (float) c1;
	f2 = 10000.* (float) d2 / (float) c2;
} else					/* pre-calculated into struct	*/
{	f1 = n1->dpc * 10000.;
	f2 = n2->dpc * 10000.;
}
if (qq->v)	qq->v = 0,	fprintf (stderr, "# lDsort:%d\n", qq->o);
if (qq->o)	return ((int) (f1-f2));	else	return ((int) (f2-f1));
}
/************************************************************************/
int	lXsort (struct NAME *n1, struct NAME *n2)	/* dead/million	*/
{
float	f1, f2;
if (qq->divide)				/* this fails w/cygwin's qsort	*/
{	f1 = 10000. * n1->dx[*qq->l -1].de / (float) n1->pop;
	f2 = 10000. * n2->dx[*qq->l -1].de / (float) n2->pop;
} else					/* pre-calculated into struct	*/
{	f1 = 10000. * n1->dpm;
	f2 = 10000. * n2->dpm;
}
if (qq->v)	qq->v = 0,	fprintf (stderr, "# lXsort:%d\n", qq->o);
if (qq->o)	return ((int) (f1-f2));	else	return ((int) (f2-f1));
}
/************************************************************************/
int	lYsort (struct NAME *n1, struct NAME *n2)	/* pct conf	*/
{
float	f1 = 1000000.* n1->pcp;
float	f2 = 1000000.* n2->pcp;
if (qq->v)	qq->v = 0,	fprintf (stderr, "# lYsort:%d\n", qq->o);
if (qq->o)	return ((int) (f1-f2));	else	return ((int) (f2-f1));
}
/************************************************************************/
int	lksort (struct NAME *n1, struct NAME *n2)	/* incr/100k	*/
{
float	f1 = 10000.* n1->ipk;
float	f2 = 10000.* n2->ipk;
if (qq->v)	qq->v = 0,	fprintf (stderr, "# hksort:%d\n", qq->o);
if (qq->o)	return ((int) (f1-f2));	else	return ((int) (f2-f1));
}
/************************************************************************/
int	losort (struct NAME *n1, struct NAME *n2)	/* population	*/
{
long	ii = n1->pop - n2->pop;
if (qq->v)	qq->v = 0,	fprintf (stderr, "# losort:%d\n", qq->o);
if (qq->o)
{ if (0<ii)	return (1);	else	if (0>ii)	return (-1);
} else
{ if (0>ii)	return (1);	else	if (0<ii)	return (-1);
}
return (0);
}
/************************************************************************/
int	lvsort (struct NAME *n1, struct NAME *n2)	/* c3,c2	*/
{
int	i = strncmp (n1->c3, n2->c3, 3);
if (!i)	i = strncmp (n1->c2, n2->c2, 2);
if (qq->v)	qq->v = 0,	fprintf (stderr, "# lvsort:%d\n", qq->o);
if (qq->o)	return (i);		else	return (-i);
}
/************************************************************************/
int	lrsort (struct NAME *n1, struct NAME *n2)	/* region	*/
{
int	i = strncmp (n1->r4, n2->r4, 4);
if (!i)	i = strcmp  (n1->na, n2->na);
if (qq->v)	qq->v = 0,	fprintf (stderr, "# lrsort:%d\n", qq->o);
if (qq->o)	return (i);		else	return (-i);
}
/************************************************************************/
int	llsort (struct NAME *n1, struct NAME *n2)	/* location	*/
{
int	i = strcmp (n1->na, n2->na);
if (qq->o)	return (i);		else	return (-i);
}
/************************************************************************/
int	r_sort (struct RECS *n2, struct RECS *n1)	/* conf (top)	*/
{
int	i = n1->co - n2->co;
return (i);
}
/************************************************************************/
#include "qqsort.h"		/* qsort invocation, netbsd for cygwin	*/

Re: cygwin qsort erratic

[Stephen John Smoogen]

On Tue, 1 Sep 2020 at 16:31, Kurt-Karen Carlson-Lougheed via Cygwin <
cygwin@cygwin.com> wrote:

>
> B. If you could kindly provide me or point me to the cygwin qsort() source
> I'll check it out myself.
>


The source code is availble at
https://sourceware.org/git/gitweb.cgi?p=newlib-cygwin.git and with the git
command can be cloned using

git clone https://sourceware.org/git/newlib-cygwin.git

this will create a directory called newlib-cygwin you can cd into . The
qsort source code is in the directory newlib-cygwin/newlib/libc/search and
looks to be based off the BSD qsort from around 2002. To see the changes to
this over time one can do a

git blame newlib-cygwin/newlib/libc/search/qsort.c

and

git log newlib-cygwin/newlib/libc/search/qsort.c

The git log is clear on the changes done in 2018 to reduce stack size.

-- 
Stephen J Smoogen.

Re: cygwin qsort erratic

[Thomas Wolff]

Am 01.09.2020 um 22:29 schrieb Kurt-Karen Carlson-Lougheed via Cygwin:
>    Brian:
> 1. The Qsort() source I sent was from netbsd.org, NOT cygwin. netbsd works.
> 2. Complete package is on SourceForge as uac19 v3.3. I'm happy to send a
> tgz if you prefer that. Read 3 choices at end before considering this.
> 3. Data is curl'd from owid as shown in the script example. Likewise I can
> send a sample data set. The program analyzes COVID-19 csv files from either
> owid or github/nytimes
> 4. I've used qsort() for years. I agree, keeping the sort routines simple
> is always appropriate. I confirmed today the only ones that fail include
> float divides, lDsort() and lXsort() in attached c19sort.c. When it's
> pre-calculated and added to the struct it works, the code has a toggle now
> for testing that.
>
> Thomas:
> I tried (again) today  to build a simple test case. The data structures in
> use are complex, probably the only thing I can attempt is stripping down
> the code which will be very time consuming. I know you don't know me at
> all, but I've written code, debugged proprietary operating systems
> (assembler), performed OS dump analysis, troubleshot intermittent hardware
> issues, identified disk firmware issues causing intermittent data
> corruption, identified nfs performance issues, managed large hpc clusters,
> etc. etc. etc. over 40+ years.
Your code does not even compile. I did not ask for a minimal test case 
although that is generally appreciated. But a working test case at least 
is required to establlish your claim of a bug.
>
> I see three choices:
> A. One of you look at simple the qqsort wrapper. I modified my code to
> toggle between the functional netbsd Qsort() and cygwin qsort(). I have
> demonstrated erroneous results coming from the cygwin version in a small
> percentage of requests. If you can acknowledge that, perhaps you can check
> the cygwin version of qsort() vs. the current netbsd.org?
> B. If you could kindly provide me or point me to the cygwin qsort() source
> I'll check it out myself.
> C. We can thank each other and leave cygwin's qsort() as is broken in some
> small number of circumstances since I've compiled netbsd's into my code and
> that always works.
>
> Regards, kurt

Re: cygwin qsort erratic

[Kurt-Karen Carlson-Lougheed]

Thomas:
As stated, twice, the full code is on SourceForge as uac19 v3.3. If you
need me to send you a tgz with sample data please let me know, but note the
comments and patch below. I can certainly walk you through reproducing the
problem if you believe that is worthwhile.

Stephen:
Thank you. I couldn't get the 'blame' to work (I am not git savvy), but I
got the cygwin qsort.c. The problem is *EXACTLY* as described by Dennis de
Champeaux in the 2015-01-11 cygwin list posting. The secondary insertion
sort attempt is not safe. I patched as follows, the de Champeaux is code is
more correct in removing swap_cnt as it is no longer used:

kc: diff -u qsort.c cygsort.c
--- qsort.c     2020-09-01 15:36:39.716029300 -0700
+++ cygsort.c   2020-09-01 16:47:30.152545600 -0700
@@ -252,14 +252,15 @@
                pb += es;
                pc -= es;
        }
-       if (swap_cnt == 0) {  /* Switch to insertion sort */
+/* kc
+       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(thunk, pl -
es, pl) > 0;
                             pl -= es)
                                swap(pl, pl - es);
                goto pop;
        }
-
+kc */
        /*
         * Rearrange the array in three parts sorted like this:
         * { elements < pivot, elements == pivot, elements > pivot }

If you need me to provide further information, please advise.
Regards, kurt

On Tue, Sep 1, 2020 at 3:02 PM Thomas Wolff <towo@towo.net> wrote:

> Am 01.09.2020 um 22:29 schrieb Kurt-Karen Carlson-Lougheed via Cygwin:
> >    Brian:
> > 1. The Qsort() source I sent was from netbsd.org, NOT cygwin. netbsd
> works.
> > 2. Complete package is on SourceForge as uac19 v3.3. I'm happy to send a
> > tgz if you prefer that. Read 3 choices at end before considering this.
> > 3. Data is curl'd from owid as shown in the script example. Likewise I
> can
> > send a sample data set. The program analyzes COVID-19 csv files from
> either
> > owid or github/nytimes
> > 4. I've used qsort() for years. I agree, keeping the sort routines simple
> > is always appropriate. I confirmed today the only ones that fail include
> > float divides, lDsort() and lXsort() in attached c19sort.c. When it's
> > pre-calculated and added to the struct it works, the code has a toggle
> now
> > for testing that.
> >
> > Thomas:
> > I tried (again) today  to build a simple test case. The data structures
> in
> > use are complex, probably the only thing I can attempt is stripping down
> > the code which will be very time consuming. I know you don't know me at
> > all, but I've written code, debugged proprietary operating systems
> > (assembler), performed OS dump analysis, troubleshot intermittent
> hardware
> > issues, identified disk firmware issues causing intermittent data
> > corruption, identified nfs performance issues, managed large hpc
> clusters,
> > etc. etc. etc. over 40+ years.
> Your code does not even compile. I did not ask for a minimal test case
> although that is generally appreciated. But a working test case at least
> is required to establlish your claim of a bug.
> >
> > I see three choices:
> > A. One of you look at simple the qqsort wrapper. I modified my code to
> > toggle between the functional netbsd Qsort() and cygwin qsort(). I have
> > demonstrated erroneous results coming from the cygwin version in a small
> > percentage of requests. If you can acknowledge that, perhaps you can
> check
> > the cygwin version of qsort() vs. the current netbsd.org?
> > B. If you could kindly provide me or point me to the cygwin qsort()
> source
> > I'll check it out myself.
> > C. We can thank each other and leave cygwin's qsort() as is broken in
> some
> > small number of circumstances since I've compiled netbsd's into my code
> and
> > that always works.
> >
> > Regards, kurt
> --
> Problem reports:      https://cygwin.com/problems.html
> FAQ:                  https://cygwin.com/faq/
> Documentation:        https://cygwin.com/docs.html
> Unsubscribe info:     https://cygwin.com/ml/#unsubscribe-simple
>

Re: cygwin qsort erratic

[Thomas Wolff]

Am 02.09.2020 um 02:26 schrieb Kurt-Karen Carlson-Lougheed:
> Thomas:
> As stated, twice, the full code is on SourceForge as uac19 v3.3. If 
> you need me to send you a tgz with sample data please let me know, but 
> note the comments and patch below. I can certainly walk you through 
> reproducing the problem if you believe that is worthwhile.
Kurt-Karen:
I am not uac savvy. The proposal to dig out some software package, build 
it (which may create hours-long trouble in some cases), collect data 
from somewhere else etc, to reproduce an assumed bug, is not 
appropriate. It's your term to provide a single, reproducible 
demonstration of a bug. If this were an issue in my project, I would 
close it now for refusal of cooperation.

>
> Stephen:
> Thank you. I couldn't get the 'blame' to work (I am not git savvy), 
> but I got the cygwin qsort.c. The problem is *EXACTLY* as described by 
> Dennis de Champeaux in the 2015-01-11 cygwin list posting. The 
> secondary insertion sort attempt is not safe. I patched as follows, 
> the de Champeaux is code is more correct in removing swap_cnt as it is 
> no longer used:
>
> kc: diff -u qsort.c cygsort.c
> --- qsort.c     2020-09-01 15:36:39.716029300 -0700
> +++ cygsort.c   2020-09-01 16:47:30.152545600 -0700
> @@ -252,14 +252,15 @@
>                 pb += es;
>                 pc -= es;
>         }
> -       if (swap_cnt == 0) {  /* Switch to insertion sort */
> +/* kc
> +       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(thunk, pl 
> - es, pl) > 0;
>                              pl -= es)
>                                 swap(pl, pl - es);
>                 goto pop;
>         }
> -
> +kc */
>         /*
>          * Rearrange the array in three parts sorted like this:
>          * { elements < pivot, elements == pivot, elements > pivot }
>
> If you need me to provide further information, please advise.
> Regards, kurt
>
> On Tue, Sep 1, 2020 at 3:02 PM Thomas Wolff <towo@towo.net 
> <mailto:towo@towo.net>> wrote:
>
>     Am 01.09.2020 um 22:29 schrieb Kurt-Karen Carlson-Lougheed via Cygwin:
>     >    Brian:
>     > 1. The Qsort() source I sent was from netbsd.org
>     <http://netbsd.org>, NOT cygwin. netbsd works.
>     > 2. Complete package is on SourceForge as uac19 v3.3. I'm happy
>     to send a
>     > tgz if you prefer that. Read 3 choices at end before considering
>     this.
>     > 3. Data is curl'd from owid as shown in the script example.
>     Likewise I can
>     > send a sample data set. The program analyzes COVID-19 csv files
>     from either
>     > owid or github/nytimes
>     > 4. I've used qsort() for years. I agree, keeping the sort
>     routines simple
>     > is always appropriate. I confirmed today the only ones that fail
>     include
>     > float divides, lDsort() and lXsort() in attached c19sort.c. When
>     it's
>     > pre-calculated and added to the struct it works, the code has a
>     toggle now
>     > for testing that.
>     >
>     > Thomas:
>     > I tried (again) today  to build a simple test case. The data
>     structures in
>     > use are complex, probably the only thing I can attempt is
>     stripping down
>     > the code which will be very time consuming. I know you don't
>     know me at
>     > all, but I've written code, debugged proprietary operating systems
>     > (assembler), performed OS dump analysis, troubleshot
>     intermittent hardware
>     > issues, identified disk firmware issues causing intermittent data
>     > corruption, identified nfs performance issues, managed large hpc
>     clusters,
>     > etc. etc. etc. over 40+ years.
>     Your code does not even compile. I did not ask for a minimal test
>     case
>     although that is generally appreciated. But a working test case at
>     least
>     is required to establlish your claim of a bug.
>     >
>     > I see three choices:
>     > A. One of you look at simple the qqsort wrapper. I modified my
>     code to
>     > toggle between the functional netbsd Qsort() and cygwin qsort().
>     I have
>     > demonstrated erroneous results coming from the cygwin version in
>     a small
>     > percentage of requests. If you can acknowledge that, perhaps you
>     can check
>     > the cygwin version of qsort() vs. the current netbsd.org
>     <http://netbsd.org>?
>     > B. If you could kindly provide me or point me to the cygwin
>     qsort() source
>     > I'll check it out myself.
>     > C. We can thank each other and leave cygwin's qsort() as is
>     broken in some
>     > small number of circumstances since I've compiled netbsd's into
>     my code and
>     > that always works.
>     >
>     > Regards, kurt
>     --
>     Problem reports: https://cygwin.com/problems.html
>     FAQ: https://cygwin.com/faq/
>     Documentation: https://cygwin.com/docs.html
>     Unsubscribe info: https://cygwin.com/ml/#unsubscribe-simple
>