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

p5pRT · 2005-06-21T14:45:30Z

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

Searchable as RT36350$

p5pRT · 2005-06-21T14:45:31Z

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 · 2005-06-21T15:02:24Z

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 · 2005-06-21T15:02:26Z

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

p5pRT · 2005-06-21T22:01:07Z

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 · 2005-06-21T22:01:07Z

From @salva

sorthints-0.patch

--- 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 · 2005-06-22T11:47:58Z

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 · 2005-06-22T13:21:27Z

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 · 2005-06-22T17:10:37Z

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 · 2005-06-23T11:06:31Z

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

p5pRT · 2005-06-23T11:06:44Z

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.

p5pRT closed this as completed Jun 23, 2005

p5pRT added Severity Medium distro-Solaris type-core labels Oct 18, 2019

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

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

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

p5pRT commented Jun 21, 2005

p5pRT commented Jun 21, 2005

p5pRT commented Jun 21, 2005

p5pRT commented Jun 21, 2005

p5pRT commented Jun 21, 2005

p5pRT commented Jun 21, 2005

p5pRT commented Jun 22, 2005

p5pRT commented Jun 22, 2005

p5pRT commented Jun 22, 2005

p5pRT commented Jun 23, 2005

p5pRT commented Jun 23, 2005

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

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

Comments

p5pRT commented Jun 21, 2005

p5pRT commented Jun 21, 2005

From @salva

Created by @salva

p5pRT commented Jun 21, 2005

From @salva

p5pRT commented Jun 21, 2005

p5pRT commented Jun 21, 2005

From @salva

p5pRT commented Jun 21, 2005

From @salva

p5pRT commented Jun 22, 2005

From @pjcj

p5pRT commented Jun 22, 2005

From @doughera88

p5pRT commented Jun 22, 2005

From @doughera88

p5pRT commented Jun 23, 2005

p5pRT commented Jun 23, 2005

From @rgs