in reply to Re: Re: Re: Re: aliasing
in thread aliasing

The relevant piece of code is this 

    if (GIMME == G_ARRAY) {
    MARK++;
    while (MARK < SP) {
        tmp = *MARK;
        *MARK++ = *SP;
        *SP-- = tmp;
    }
    /* safe as long as stack cannot get extended in the above */
    SP = oldsp;
    }

[download]

which is roughly equivalent to 

( $MARK, $SP ) = ( 0, $#array );
while( $MARK < $SP ) {
    $tmp = $array[ $mark ];
    $array[ $MARK++ } = $array[ $SP ];
    $array[ $SP-- ] = tmp;
}

[download]

which suggests that if the argument to reverse is a single array, rather than stack the array to create @_, the stack pointer is effectively pointed at the top of the array. This is born out (but not confirmed--I can;t find the relevant part of the source) by doing 

@r = reverse 1, @r;

[download]

when substantial memory growth occurs. In this case, @_ has to be built fresh to incorporate the extra element.

Examine what is said, not who speaks.
"Efficiency is intelligent laziness." -David Dunham
"Think for yourself!" - Abigail
Timing (and a little luck) are everything!

Replies are listed 'Best First'.
Re: Re: Re: Re: Re: Re: aliasing
by ysth (Canon) on Jan 13, 2004 at 01:35 UTC
    Goodness knows, there are optimizations lurking that are hard to spot, and there may be one for the @r = reverse @r, but if so I don't see it.

    The above (in pp_reverse) is only executed after the array has been moved onto the stack, and in your pseudo-code, @array represents the stack, not the array being reversed. What you quote is the general code for any list-context reverse, which just reverses everything from the MARK showing the beginning of reverse's arguments to the SP stack pointer at the top of the stack.

    I'm intrigued that @r = reverse 1,@r seems to take more memory; how much more?

[reply]
      how much more?
      P:\test>p1
# 2368k
@r = 1 .. 1000000;
# 62804k
@r = reverse @r;
# 62812k
@r = reverse 1, @r;
# 71020k

      [download]

      I work that out at around 8MB, or 8 bytes per element. Just enough to build a single linked list of references to the scalars that constitute the elements of the array.

      The above (in pp_reverse) is only executed after the array has been moved onto the stack, and in your pseudo-code, @array represents the stack, not the array being reversed.

      Agreed. But the reversal, is done by reversing the order ot the linked list of pointers to the scalars. So, if the input argument is a single array, rather than copying the array's linked list onto the stack and set @_ to point to the copy.

      I speculate that the SP is pointed at the end of the linked-list that is the array argument, and the linked list is reversed in place. When the sub exits, and the SP is reset to its previous position, the array has been reversed in-situ with no copying to/from the stack required.

      That doesn't work when the extra element is passed to reverse, so it has to copy the new element + linked list from the array, to a new lump of memory before calling PP_reverse to re-order the new list. Afterwards, the stash entry for the array is pointed at the new list which was reversed in-situ, and the old list becomes available for garbage collection.

      The scalars that form the elements of the array never move at all.

      Examine what is said, not who speaks.
      "Efficiency is intelligent laziness." -David Dunham
      "Think for yourself!" - Abigail
      Timing (and a little luck) are everything!
[reply]
[d/l]

In Section Seekers of Perl Wisdom