in-place sort incorrectly preserves element lvalue identity

[p5pRT]

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

Searchable as RT128340$

[p5pRT]

From zefram@fysh.org

Created by zefram@fysh.org

[perl #127759] led me to spot another problem with in-place sort optimisation​:

$ perl -le '@​c=(55,44,33); $d = \$c[2]; @​c = @​e = sort { $a <=> $b } @​c; $$d = "z"; print @​c'
334455
$ perl -le '@​c=(55,44,33); $d = \$c[2]; @​c = sort { $a <=> $b } @​c; $$d = "z"; print @​c'
z4455

The latter case triggers the in-place sort optimisation, while the former
is semantically equivalent (except for clobbering @​e) but does not get
the optimisation. The former is behaving correctly, in that the array
ends up with fresh element scalars not aliased to the old ones, so the
mutation via reference doesn't affect the new array content. But with
the in-place optimisation, it turns out that the original element scalars
are merely being rearranged. The copying to fresh scalars that is part
of list assignment semantics is not happening.

It is incorrect to apply the in-place optimisation if any of the array's
element scalars might be aliased somewhere else. I considered saying
"has SvREFCNT != 1" there, but I'm concerned about uncounted references
hiding in @​_ or elsewhere on the stack.

Perl Info

Flags:
    category=core
    severity=low

Site configuration information for perl 5.24.0:

Configured by zefram at Mon May  9 19:42:55 BST 2016.

Summary of my perl5 (revision 5 version 24 subversion 0) configuration:
   
  Platform:
    osname=linux, osvers=3.16.0-4-amd64, archname=x86_64-linux-thread-multi
    uname='linux barba.rous.org 3.16.0-4-amd64 #1 smp debian 3.16.7-ckt11-1+deb8u6 (2015-11-09) x86_64 gnulinux '
    config_args='-des -Dprefix=/home/zefram/usr/perl/perl_install/perl-5.24.0-i64-f52 -Duselargefiles -Dusethreads -Uafs -Ud_csh -Uusesfio -Uusenm -Duseshrplib -Dusedevel -Uversiononly -Ui_db'
    hint=recommended, useposix=true, d_sigaction=define
    useithreads=define, usemultiplicity=define
    use64bitint=define, use64bitall=define, uselongdouble=undef
    usemymalloc=n, bincompat5005=undef
  Compiler:
    cc='cc', ccflags ='-D_REENTRANT -D_GNU_SOURCE -fwrapv -fno-strict-aliasing -pipe -fstack-protector-strong -I/usr/local/include -D_LARGEFILE_SOURCE -D_FILE_OFFSET_BITS=64 -D_FORTIFY_SOURCE=2',
    optimize='-O2',
    cppflags='-D_REENTRANT -D_GNU_SOURCE -fwrapv -fno-strict-aliasing -pipe -fstack-protector-strong -I/usr/local/include'
    ccversion='', gccversion='4.9.2', gccosandvers=''
    intsize=4, longsize=8, ptrsize=8, doublesize=8, byteorder=12345678, doublekind=3
    d_longlong=define, longlongsize=8, d_longdbl=define, longdblsize=16, longdblkind=3
    ivtype='long', ivsize=8, nvtype='double', nvsize=8, Off_t='off_t', lseeksize=8
    alignbytes=8, prototype=define
  Linker and Libraries:
    ld='cc', ldflags =' -fstack-protector-strong -L/usr/local/lib'
    libpth=/usr/local/lib /usr/lib/gcc/x86_64-linux-gnu/4.9/include-fixed /usr/include/x86_64-linux-gnu /usr/lib /lib/x86_64-linux-gnu /lib/../lib /usr/lib/x86_64-linux-gnu /usr/lib/../lib /lib
    libs=-lpthread -lnsl -ldb -ldl -lm -lcrypt -lutil -lc
    perllibs=-lpthread -lnsl -ldl -lm -lcrypt -lutil -lc
    libc=libc-2.19.so, so=so, useshrplib=true, libperl=libperl.so
    gnulibc_version='2.19'
  Dynamic Linking:
    dlsrc=dl_dlopen.xs, dlext=so, d_dlsymun=undef, ccdlflags='-Wl,-E -Wl,-rpath,/home/zefram/usr/perl/perl_install/perl-5.24.0-i64-f52/lib/5.24.0/x86_64-linux-thread-multi/CORE'
    cccdlflags='-fPIC', lddlflags='-shared -O2 -L/usr/local/lib -fstack-protector-strong'



@INC for perl 5.24.0:
    /home/zefram/usr/perl/perl_install/perl-5.24.0-i64-f52/lib/site_perl/5.24.0/x86_64-linux-thread-multi
    /home/zefram/usr/perl/perl_install/perl-5.24.0-i64-f52/lib/site_perl/5.24.0
    /home/zefram/usr/perl/perl_install/perl-5.24.0-i64-f52/lib/5.24.0/x86_64-linux-thread-multi
    /home/zefram/usr/perl/perl_install/perl-5.24.0-i64-f52/lib/5.24.0
    .


Environment for perl 5.24.0:
    HOME=/home/zefram
    LANG (unset)
    LANGUAGE (unset)
    LD_LIBRARY_PATH (unset)
    LOGDIR (unset)
    PATH=/home/zefram/usr/perl/perl_install/perl-5.24.0-i64-f52/bin:/home/zefram/usr/perl/util:/home/zefram/pub/x86_64-unknown-linux-gnu/bin:/home/zefram/pub/common/bin:/usr/bin:/bin:/usr/local/bin:/usr/games
    PERL_BADLANG (unset)
    SHELL=/usr/bin/zsh

[p5pRT]

From zefram@fysh.org

I wrote​:

It is incorrect to apply the in-place optimisation if any of the array's
element scalars might be aliased somewhere else.

If we can detect which ones are (or might be) aliased, it's not necessary
to drop the optimisation entirely when there are some. It would suffice
to add a step that dealiases the aliased ones, after the actual sorting.
In my proposal for [perl #127759] that does one copy of the AvARRAY,
the dealiasing would be applied to the sorted version of the AvARRAY,
just before it gets installed into the AV.

                          I'm concerned about uncounted references

hiding in @​_ or elsewhere on the stack.

If the stack is a problem, it may still be acceptable to just look
at SvREFCNT != 1. The remaining broken cases would be classed as yet
another stack-not-refcounted bug. I live in hope that some day we'll
address those.

-zefram

[p5pRT]

From @iabyn

On Tue, Jun 07, 2016 at 09​:39​:47PM +0100, Zefram wrote​:

I wrote​:

It is incorrect to apply the in-place optimisation if any of the array's
element scalars might be aliased somewhere else.

If we can detect which ones are (or might be) aliased, it's not necessary
to drop the optimisation entirely when there are some. It would suffice
to add a step that dealiases the aliased ones, after the actual sorting.
In my proposal for [perl #127759] that does one copy of the AvARRAY,
the dealiasing would be applied to the sorted version of the AvARRAY,
just before it gets installed into the AV.

                          I'm concerned about uncounted references

hiding in @​_ or elsewhere on the stack.

If the stack is a problem, it may still be acceptable to just look
at SvREFCNT != 1. The remaining broken cases would be classed as yet
another stack-not-refcounted bug. I live in hope that some day we'll
address those.

Now done with​:

commit 45c198c
Author​: David Mitchell <davem@​iabyn.com>
AuthorDate​: Wed Aug 10 16​:19​:55 2016 +0100
Commit​: David Mitchell <davem@​iabyn.com>
CommitDate​: Wed Aug 10 16​:34​:04 2016 +0100

  in-place sort preserved element lvalue identity
 
  RT #128340
 
  The in-place sorting optimisation @​a = sort @​a, was preserving the
  elements of @​a rather than (logically) making copies. So make a copy
  of any element whose refcount is greater than 1. This may not be the
  perfect condition, but keeps performance for the common cases.
 
  Note that several of the tests in t/op/sort.t actually relied on this
  behaviour to test whether the sort was being in-placed, so I've added
  tests for in-placing to t/perf/opcount.t instead.
 
  See the previous commit for a general discussion of performance;
  to the A, B, C in that commit message, here's a fourth column added​:
  D is like C but with this commit added​:
 
  A B C D
  ------ ------ ------ ------
  Ir 5238.0 2324.0 2772.0 2801.0
  Dr 1464.0 649.0 765.0 765.0
  Dw 919.0 298.0 370.0 380.0
  COND 782.0 320.0 405.0 405.0
  IND 25.0 25.0 26.0 26.0
 
  COND_m 14.9 13.0 17.0 17.1
  IND_m 8.0 5.0 5.0 5.0
 
  so it has little effect on performance.

--
I thought I was wrong once, but I was mistaken.

[p5pRT]

The RT System itself - Status changed from 'new' to 'open'

[p5pRT]

@iabyn - Status changed from 'open' to 'pending release'

[p5pRT]

From @khwilliamson

Thank you for filing this report. You have helped make Perl better.

With the release today of Perl 5.26.0, this and 210 other issues have been
resolved.

Perl 5.26.0 may be downloaded via​:
https://metacpan.org/release/XSAWYERX/perl-5.26.0

If you find that the problem persists, feel free to reopen this ticket.

[p5pRT]

@khwilliamson - Status changed from 'pending release' to 'resolved'