<?xml version="1.0" encoding="windows-1252"?>
<node id="276051" title="Re: Re: Re: Re: Re: Slowness when inserting into pre-extended array" created="2003-07-20 11:14:32" updated="2005-08-11 07:13:22">
<type id="11">
note</type>
<author id="155191">
Elian</author>
<data>
<field name="doctext">
Perl doesn't use a power-of-two size extension mechanism. When perl increases the size of an array's cache, the formula is generally:
&lt;code&gt;
new_top_index + (allocated_elements / 5)
&lt;/code&gt;
For a push, top index is just the allocated size plus one if we've triggered an extension, so when pushes blow past the end of an array they make it 20% bigger. There's a lot more memory copying going on in that case than with a power-of-two extension system. (For folks following along at home, this formula isn't always used, but it is for the case in question)
&lt;P&gt;
Given that the system in question is a Windows box, it wouldn't at all surprise me to find that this &lt;i&gt;is&lt;/i&gt; the problem, with the big speed hits coming as the array is resized and ever-larger chunks of memory have to be allocated from the system and copied into. The individual pushes are probably running at full speed, but with ever-increasing performance hits for reallocation you'd not necessarily notice that.</field>
<field name="root_node">
275917</field>
<field name="parent_node">
275934</field>
</data>
</node>
