unstable sorting for use integer; sort { $b <=> $a } @foo

p5pRT commented 19 years ago

Migrated from rt.perl.org#36350 (status was 'resolved')

Searchable as RT36350$

p5pRT commented 19 years ago

From @salva

Created by @salva

sorting a list of numbers as integers (via 'use integer') in descending order gives an unstable sort:

$ perl

use sort stable; @a=(2.7\, 1.7\, 1\, 4.8\, 4.3\, 0.8); use integer; @u = sort { $b \<=> $a } @a; @s = sort { int $b \<=> int $a } @a;

sub pa { print join("\, "\, @_)\, "\n"} pa @a; pa @s; pa @u'

__END__

2.7\, 1.7\, 1\, 4.8\, 4.3\, 0.8 4.8\, 4.3\, 2.7\, 1.7\, 1\, 0.8 4.3\, 4.8\, 2.7\, 1\, 1.7\, 0.8

Cheers\,

- Salvador.

Perl Info

``` Flags: category=core severity=medium Site configuration information for perl v5.8.5: Summary of my perl5 (revision 5 version 8 subversion 5) configuration: Platform: osname=solaris, osvers=2.9, archname=sun4-solaris uname='sunos 5.9 generic sun4u sparc sunw,ultra-5_10 solaris ' config_args='-Dcc=gcc -B/usr/ccs/bin/' hint=recommended, useposix=true, d_sigaction=define usethreads=undef use5005threads=undef useithreads=undef usemultiplicity=undef useperlio=define d_sfio=undef uselargefiles=define usesocks=undef use64bitint=undef use64bitall=undef uselongdouble=undef usemymalloc=n, bincompat5005=undef Compiler: cc='gcc -B/usr/ccs/bin/', ccflags ='-fno-strict-aliasing -pipe -I/usr/local/include -I/opt/gnu/include -D_LARGEFILE_SOURCE -D_FILE_OFFSET_BITS=64', optimize='-O', cppflags='-fno-strict-aliasing -pipe -I/usr/local/include -I/opt/gnu/include' ccversion='', gccversion='3.3.2', gccosandvers='solaris2.9' intsize=4, longsize=4, ptrsize=4, doublesize=8, byteorder=4321 d_longlong=define, longlongsize=8, d_longdbl=define, longdblsize=16 ivtype='long', ivsize=4, nvtype='double', nvsize=8, Off_t='off_t', lseeksize=8 alignbytes=8, prototype=define Linker and Libraries: ld='gcc -B/usr/ccs/bin/', ldflags =' -L/usr/local/lib -L/opt/gnu/lib ' libpth=/usr/local/lib /opt/gnu/lib /usr/lib /usr/ccs/lib libs=-lsocket -lbind -lnsl -lgdbm -ldb -ldl -lm -lc perllibs=-lsocket -lbind -lnsl -ldl -lm -lc libc=/lib/libc.so, so=so, useshrplib=false, libperl=libperl.a gnulibc_version='' Dynamic Linking: dlsrc=dl_dlopen.xs, dlext=so, d_dlsymun=undef, ccdlflags=' ' cccdlflags='-fPIC', lddlflags='-G -L/usr/local/lib -L/opt/gnu/lib' Locally applied patches: @INC for perl v5.8.5: /usr/local/lib/perl5/5.8.5/sun4-solaris /usr/local/lib/perl5/5.8.5 /usr/local/lib/perl5/site_perl/5.8.5/sun4-solaris /usr/local/lib/perl5/site_perl/5.8.5 /usr/local/lib/perl5/site_perl . Environment for perl v5.8.5: HOME=/export/home/salva LANG (unset) LANGUAGE (unset) LD_LIBRARY_PATH (unset) LOGDIR (unset) PATH=/usr/local/bin/:/usr/local/mysql/bin:/usr/bin:/bin:/usr/sbin:/sbin PERL_BADLANG (unset) SHELL=/usr/bin/bash ____________________________________________________ Yahoo! Sports Rekindle the Rivalries. Sign up for Fantasy Football http://football.fantasysports.yahoo.com ```

p5pRT commented 19 years ago

From @salva

I have found it is not only affecting integer sorts:

$ perl

use sort stable;

@a=map{(int rand 5).(q(#)\, q(@))[rand 2]} 0..5; @u = sort { $b \<=> $a } @a; @s = sort { int $b \<=> int $a } @a;

sub pa { print join("\, "\, @_)\, "\n"} pa @a; pa @s; pa @u'

__END__

2#\, 2@\, 1#\, 3@\, 3#\, 1@ 3@\, 3#\, 2#\, 2@\, 1#\, 1@ 3#\, 3@\, 2@\, 2#\, 1@\, 1#

p5pRT commented 19 years ago

@salva - Status changed from 'new' to 'open'

p5pRT commented 19 years ago

From @salva

perlbug-followup@perl.org wrote:

# New Ticket Created by Salvador FandiÃ±o # Please include the string: [perl #36350] # in the subject line of all future correspondence about this issue. # \<URL: https://rt-archive.perl.org/perl5/Ticket/Display.html?id=36350 >

This is a bug report for perl from sfandino@yahoo.com\, generated with the help of perlbug 1.35 running under perl v5.8.5.

----------------------------------------------------------------- [Please enter your report here]

sorting a list of numbers as integers (via 'use integer') in descending order gives an unstable sort:

$ perl

use sort stable; @a=(2.7\, 1.7\, 1\, 4.8\, 4.3\, 0.8); use integer; @u = sort { $b \<=> $a } @a; @s = sort { int $b \<=> int $a } @a;

sub pa { print join("\, "\, @_)\, "\n"} pa @a; pa @s; pa @u'

__END__

2.7\, 1.7\, 1\, 4.8\, 4.3\, 0.8 4.8\, 4.3\, 2.7\, 1.7\, 1\, 0.8 4.3\, 4.8\, 2.7\, 1\, 1.7\, 0.8

Cheers\,

- Salvador.

I have not been able to reproduce the bug on any perl compiled by myself\, but anyway\, I am sure the problem is caused by the nasty macro SORTHINTS(hintsv)\, that relays on the evaluation order of something like

result = (v = foo()\, bar(v));

The patch attached breaks the macro in two: dSORTHINTS and SORTHINTS\, they do the same operation but in two steps.

Cheers\,

- Salvador.

p5pRT commented 19 years ago

From @salva

sorthints-0.patch

```diff --- pp_sort.c~ 2005-06-20 12:16:05.000000000 +0200 +++ pp_sort.c 2005-06-21 18:09:04.000000000 +0200 @@ -46,9 +46,8 @@ #define sv_cmp_static Perl_sv_cmp #define sv_cmp_locale_static Perl_sv_cmp_locale -#define SORTHINTS(hintsv) \ - (((hintsv) = GvSV(gv_fetchpv("sort::hints", GV_ADDMULTI, SVt_IV))), \ - (SvIOK(hintsv) ? ((I32)SvIV(hintsv)) : 0)) +#define dSORTHINTS SV *hintsv = GvSV(gv_fetchpv("sort::hints", GV_ADDMULTI, SVt_IV)) +#define SORTHINTS (SvIOK(hintsv) ? ((I32)SvIV(hintsv)) : 0) #ifndef SMALLSORT #define SMALLSORT (200) @@ -1347,9 +1346,10 @@ STATIC void S_qsortsv(pTHX_ gptr *list1, size_t nmemb, SVCOMPARE_t cmp, U32 flags) { - SV *hintsv; - if (SORTHINTS(hintsv) & HINT_SORT_STABLE) { + dSORTHINTS; + + if (SORTHINTS & HINT_SORT_STABLE) { register gptr **pp, *q; register size_t n, j, i; gptr *small[SMALLSORT], **indir, tmp; @@ -1442,14 +1442,8 @@ { void (*sortsvp)(pTHX_ SV **array, size_t nmemb, SVCOMPARE_t cmp, U32 flags) = S_mergesortsv; - SV *hintsv; - - /* Sun's Compiler (cc: WorkShop Compilers 4.2 30 Oct 1996 C 4.2) used - to miscompile this function under optimization -O. If you get test - errors related to picking the correct sort() function, try recompiling - this file without optimiziation. -- A.D. 4/2002. - */ - const I32 hints = SORTHINTS(hintsv); + dSORTHINTS; + const I32 hints = SORTHINTS; if (hints & HINT_SORT_QUICKSORT) { sortsvp = S_qsortsv; } @@ -1467,14 +1461,8 @@ { void (*sortsvp)(pTHX_ SV **array, size_t nmemb, SVCOMPARE_t cmp, U32 flags) = S_mergesortsv; - SV *hintsv; - - /* Sun's Compiler (cc: WorkShop Compilers 4.2 30 Oct 1996 C 4.2) used - to miscompile this function under optimization -O. If you get test - errors related to picking the correct sort() function, try recompiling - this file without optimiziation. -- A.D. 4/2002. - */ - const I32 hints = SORTHINTS(hintsv); + dSORTHINTS; + const I32 hints = SORTHINTS; if (hints & HINT_SORT_QUICKSORT) { sortsvp = S_qsortsv; } ```

p5pRT commented 19 years ago

From @pjcj

On Tue\, Jun 21\, 2005 at 07:50:35PM +0200\, Salvador Fandino wrote:

I have not been able to reproduce the bug on any perl compiled by myself\, but anyway\, I am sure the problem is caused by the nasty macro SORTHINTS(hintsv)\, that relays on the evaluation order of something like

result = (v = foo()\, bar(v));

The patch attached breaks the macro in two: dSORTHINTS and SORTHINTS\, they do the same operation but in two steps.

I think the evaulation order here is quite well defined but\, of course\, perl has a fine tradition of working around broken compilers.

- /* Sun's Compiler (cc: WorkShop Compilers 4.2 30 Oct 1996 C 4.2) used - to miscompile this function under optimization -O. If you get test - errors related to picking the correct sort() function\, try recompiling - this file without optimiziation. -- A.D. 4/2002. - */

So yes\, hopefully this is fixed too but it would be interesting to hear from someone who can test under this compiler.

-- Paul Johnson - paul@pjcj.net http://www.pjcj.net

p5pRT commented 19 years ago

From @doughera88

On Wed\, 22 Jun 2005\, Paul Johnson wrote:

On Tue\, Jun 21\, 2005 at 07:50:35PM +0200\, Salvador Fandino wrote:

I have not been able to reproduce the bug on any perl compiled by myself\, but anyway\, I am sure the problem is caused by the nasty macro SORTHINTS(hintsv)\, that relays on the evaluation order of something like

result = (v = foo()\, bar(v));

The patch attached breaks the macro in two: dSORTHINTS and SORTHINTS\, they do the same operation but in two steps.

I think the evaulation order here is quite well defined but\, of course\, perl has a fine tradition of working around broken compilers.

- /* Sun's Compiler (cc: WorkShop Compilers 4.2 30 Oct 1996 C 4.2) used - to miscompile this function under optimization -O. If you get test - errors related to picking the correct sort() function\, try recompiling - this file without optimiziation. -- A.D. 4/2002. - */

So yes\, hopefully this is fixed too but it would be interesting to hear from someone who can test under this compiler.

That'd be me. What\, precisely\, would you like me to test? I haven't had any recent problems with that compiler under -O\, so as far as I know\, but I haven't compiled bleadperl for a few weeks.

-- Andy Dougherty doughera@lafayette.edu

p5pRT commented 19 years ago

From @doughera88

On Wed\, 22 Jun 2005\, Andy Dougherty wrote:

On Wed\, 22 Jun 2005\, Paul Johnson wrote:

On Tue\, Jun 21\, 2005 at 07:50:35PM +0200\, Salvador Fandino wrote:

I have not been able to reproduce the bug on any perl compiled by myself\, but anyway\, I am sure the problem is caused by the nasty macro SORTHINTS(hintsv)\, that relays on the evaluation order of something like

result = (v = foo()\, bar(v));

The patch attached breaks the macro in two: dSORTHINTS and SORTHINTS\, they do the same operation but in two steps.

I think the evaulation order here is quite well defined but\, of course\, perl has a fine tradition of working around broken compilers.

- /* Sun's Compiler (cc: WorkShop Compilers 4.2 30 Oct 1996 C 4.2) used - to miscompile this function under optimization -O. If you get test - errors related to picking the correct sort() function\, try recompiling - this file without optimiziation. -- A.D. 4/2002. - */

So yes\, hopefully this is fixed too but it would be interesting to hear from someone who can test under this compiler.

That'd be me. What\, precisely\, would you like me to test? I haven't had any recent problems with that compiler under -O\, so as far as I know\, but I haven't compiled bleadperl for a few weeks.

Ok\, I've looked at the RT ticket now. Yes\, this patch works fine for me with Sun's old compiler. (It was also working fine without the patch\, but that's ok. The patch didn't break anything!)

My original problem also had to do with embedding SORTINTS(hintsv) inside an if() statement. My solution back in 2002 was to break it out as two separate steps. Then the optimizer didn't get confused. (This is Change #15911.)

I32 hints = SORTHINTS(hintsv); if (hints & HINT_SORT_QUICKSORT) ...

This patch looks similar in spirit to me and is probably fine.

-- Andy Dougherty doughera@lafayette.edu

p5pRT commented 19 years ago

@rgs - Status changed from 'open' to 'resolved'

p5pRT commented 19 years ago

From @rgs

Salvador Fandino wrote:

I have not been able to reproduce the bug on any perl compiled by myself\, but anyway\, I am sure the problem is caused by the nasty macro SORTHINTS(hintsv)\, that relays on the evaluation order of something like
result = $v = foo\($\, bar$v$\);
The patch attached breaks the macro in two: dSORTHINTS and SORTHINTS\, they do the same operation but in two steps.

Thanks\, applied as change #24951.

Perl / perl5