* cygwin qsort erratic @ 2020-08-30 21:27 Kurt-Karen Carlson-Lougheed 2020-08-31 2:54 ` Brian Inglis 2020-08-31 7:31 ` Corinna Vinschen 0 siblings, 2 replies; 11+ messages in thread From: Kurt-Karen Carlson-Lougheed @ 2020-08-30 21:27 UTC (permalink / raw) To: cygwin 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 ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: cygwin qsort erratic 2020-08-30 21:27 cygwin qsort erratic Kurt-Karen Carlson-Lougheed @ 2020-08-31 2:54 ` Brian Inglis 2020-08-31 17:50 ` Kurt-Karen Carlson-Lougheed 2020-08-31 7:31 ` Corinna Vinschen 1 sibling, 1 reply; 11+ messages in thread From: Brian Inglis @ 2020-08-31 2:54 UTC (permalink / raw) To: cygwin 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.] ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: cygwin qsort erratic 2020-08-31 2:54 ` Brian Inglis @ 2020-08-31 17:50 ` Kurt-Karen Carlson-Lougheed 2020-08-31 18:00 ` Thomas Wolff 0 siblings, 1 reply; 11+ messages in thread From: Kurt-Karen Carlson-Lougheed @ 2020-08-31 17:50 UTC (permalink / raw) To: cygwin [-- 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 ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: cygwin qsort erratic 2020-08-31 17:50 ` Kurt-Karen Carlson-Lougheed @ 2020-08-31 18:00 ` Thomas Wolff 2020-08-31 18:50 ` Brian Inglis 0 siblings, 1 reply; 11+ messages in thread From: Thomas Wolff @ 2020-08-31 18:00 UTC (permalink / raw) To: cygwin 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 ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: cygwin qsort erratic 2020-08-31 18:00 ` Thomas Wolff @ 2020-08-31 18:50 ` Brian Inglis 2020-09-01 20:29 ` Kurt-Karen Carlson-Lougheed 0 siblings, 1 reply; 11+ messages in thread From: Brian Inglis @ 2020-08-31 18:50 UTC (permalink / raw) To: cygwin 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.] ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: cygwin qsort erratic 2020-08-31 18:50 ` Brian Inglis @ 2020-09-01 20:29 ` Kurt-Karen Carlson-Lougheed 2020-09-01 20:55 ` Stephen John Smoogen 2020-09-01 22:00 ` Thomas Wolff 0 siblings, 2 replies; 11+ messages in thread From: Kurt-Karen Carlson-Lougheed @ 2020-09-01 20:29 UTC (permalink / raw) To: cygwin [-- 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 */ ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: cygwin qsort erratic 2020-09-01 20:29 ` Kurt-Karen Carlson-Lougheed @ 2020-09-01 20:55 ` Stephen John Smoogen 2020-09-01 22:00 ` Thomas Wolff 1 sibling, 0 replies; 11+ messages in thread From: Stephen John Smoogen @ 2020-09-01 20:55 UTC (permalink / raw) To: Kurt-Karen Carlson-Lougheed; +Cc: cygwin 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. ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: cygwin qsort erratic 2020-09-01 20:29 ` Kurt-Karen Carlson-Lougheed 2020-09-01 20:55 ` Stephen John Smoogen @ 2020-09-01 22:00 ` Thomas Wolff 2020-09-02 0:26 ` Kurt-Karen Carlson-Lougheed 1 sibling, 1 reply; 11+ messages in thread From: Thomas Wolff @ 2020-09-01 22:00 UTC (permalink / raw) To: cygwin 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 ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: cygwin qsort erratic 2020-09-01 22:00 ` Thomas Wolff @ 2020-09-02 0:26 ` Kurt-Karen Carlson-Lougheed 2020-09-02 7:23 ` Thomas Wolff 0 siblings, 1 reply; 11+ messages in thread From: Kurt-Karen Carlson-Lougheed @ 2020-09-02 0:26 UTC (permalink / raw) To: Thomas Wolff; +Cc: cygwin 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 > ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: cygwin qsort erratic 2020-09-02 0:26 ` Kurt-Karen Carlson-Lougheed @ 2020-09-02 7:23 ` Thomas Wolff 0 siblings, 0 replies; 11+ messages in thread From: Thomas Wolff @ 2020-09-02 7:23 UTC (permalink / raw) To: Kurt-Karen Carlson-Lougheed, cygwin 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 > ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: cygwin qsort erratic 2020-08-30 21:27 cygwin qsort erratic Kurt-Karen Carlson-Lougheed 2020-08-31 2:54 ` Brian Inglis @ 2020-08-31 7:31 ` Corinna Vinschen 1 sibling, 0 replies; 11+ messages in thread From: Corinna Vinschen @ 2020-08-31 7:31 UTC (permalink / raw) To: Kurt-Karen Carlson-Lougheed; +Cc: cygwin 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 ^ permalink raw reply [flat|nested] 11+ messages in thread
end of thread, other threads:[~2020-09-02 7:23 UTC | newest] Thread overview: 11+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2020-08-30 21:27 cygwin qsort erratic Kurt-Karen Carlson-Lougheed 2020-08-31 2:54 ` Brian Inglis 2020-08-31 17:50 ` Kurt-Karen Carlson-Lougheed 2020-08-31 18:00 ` Thomas Wolff 2020-08-31 18:50 ` Brian Inglis 2020-09-01 20:29 ` Kurt-Karen Carlson-Lougheed 2020-09-01 20:55 ` Stephen John Smoogen 2020-09-01 22:00 ` Thomas Wolff 2020-09-02 0:26 ` Kurt-Karen Carlson-Lougheed 2020-09-02 7:23 ` Thomas Wolff 2020-08-31 7:31 ` Corinna Vinschen
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).