http://www.perlmonks.org?node_id=195199


in reply to Shift, Pop, Unshift and Push with Impunity!

Hi. I thought this was a great node, and have recommended its reading and repeated its contents in a number of situations.

One of them was in correspondence with Dominus where he suggested quite strongly that some of what it said is incorrect (specifically the last paragraph). As my C skills arent sufficient to determine the facts on my own im a little curious as to where things stand right now.

Is the information in this node correct? If not, is this due to an implementation change?

I would really like to know the current status of the validity of the information in this node.

I'm somewhat doubtful as to how long this node would have lasted if it was totally incorrect without someone saying so, but on the other hand Dominus has a reputation for knowing his stuff so im in a bit of a quandry as to what to think.

Please advise!

Yves / DeMerphq
---
Software Engineering is Programming when you can't. -- E. W. Dijkstra (RIP)

Replies are listed 'Best First'.
Re: Re: Shift, Pop, Unshift and Push with Impunity!
by Anonymous Monk on Sep 06, 2002 at 20:56 UTC
    Speeding up unshift may explain what is going on.

    Through Perl 5.6.1, unshift left the array aligned on the left. So if you build up an array with unshift's it is forced to realign it on every single unshift. If you build an array with repeated unshifts this makes the cost of each linear, for quadratic total time. What tilly's patch does is realign it indented to the length of the current array. So you only realign after you unshift the length of the array elements. In the simple case of adding one element at a time, this boils down to realigning at powers of 2, for a constant amortized cost.

    The code could be more efficient, but there don't seem to be order of magnitude algorithmic improvements left.