Re: [perl #128340] in-place sort incorrectly preserves elementlvalue identity

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 45c198c1bc981a507ab719edbd292922a896a397
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.

• [perl #128340] in-place sort incorrectly preserves element lvalueidentity by Zefram
• Re: [perl #128340] in-place sort incorrectly preserves elementlvalue identity by Zefram
• Re: [perl #128340] in-place sort incorrectly preserves elementlvalue identity by Dave Mitchell