I tried to phrase my reply to have as little controversy interpretable as possible. I really wanted to hear your thoughts and wisdom.

I wasn't attempting to refute what you said, only show that O(1) doesn't tell the whole story. "amortized average O(1)" probably does, but only if you disregard the localised impact of reallocations which is what I was looking to avoid. The example I am working with is a 25 MB file producing 400,000 offsets. Building 400,000 element array with individual pushes is not insignificant, and I'm hoping to support larger. My current thinking is that building a smaller intermediate array amd then adding it to the main array, or building an array of arrays would avoid the larger reallocation/copies.

The latter may also provide some additional benefits. By building an AoA where the each element of the top level array is an array of (say) 1000 offsets from the base rather than absolute positions, when the string is modifed by insertion or deletions, adjusting the offsets within one sub array and the absolute positions the base addresses of the others, would be quicker than adjusting all the absolute positions. It would also require less ram to store offsets rather than absolute positions.

To extract the greatest benefit from this, knowing at what points the reallocations will occur and chosing the size of the nested arrays to avoid stepping over the next boundary is important. I thought that the reallocations might go in powers of two--hence my choice of 130900 + 200 stepping over the 2**17 boudary--but this does not appear to be the case.

Could you explain the "1/5 th" thing for me in a little more detail? Or point me at the appropraite place to read about it?

To see the source of 1/5 thing, look at the source to av.c. The newmax variable tracks Perl's buffering decisions quite precisely. That doesn't explain the consequences though. To understand the consequences, consider what happens just after you've had to reallocate. At that point all elements were reallocated once, 5/6 of them twice, 25/36 of them three times and so on. The total number of reallocations is therefore (1 + 5/6 + (5/6)**2 + ...). Multiply and divide by (1-5/6) then simplify to see that on average, each element has been reallocated 6 times. (Right before a reallocation that average drops to 5.)

The point about amortized constant is critical. The convergence to that behaviour is quite fast. For instance if you break the 400,000 array into building 400 arrays of 1000 elements that you then push together, you'll find the same amortized constant coming into play both in building 1000 element arrays and in building the 400,000 element array. So instead of eliminating that overhead, you're now paying twice the overhead! (By separating arrays you've kept Perl from deciding to allocate big enough chunks.)

If you want to reduce that overhead, you can change the constant fairly easily by pre-extending the array at specified intervals. Assign by index and keep track of the size of the array. Any time you're about to pass the maximum size of the array, assign undef to a spot that is twice as far. That'll change the constant from 5 to 2, and the average reallocations from ranging from 5-6 down to ranging from 2-3. (At the cost of a constant amount of logic per iteration. I don't know which constant will be bigger - this might be a loss.)

Overall I'm going to guess, though, that with 400,000 offsets your biggest source of overhead is that you have 400,000 Perl scalars. If performance is a problem it might save effort to have the data packed into a long string. You might even use C to build said string.

Okay. Thanks for that.

assign undef to a spot that is twice as far ....

Is this better/prefereable to assigning to $#array?

For instance if you break the 400,000 array into building 400 arrays of 1000 elements that you then push together, you'll find the same amortized constant coming into play both in building 1000 element arrays and in building the 400,000 element array. So instead of eliminating that overhead, you're now paying twice the overhead!

That's where the AoA idea came up. Effectively making my index a two level affair and reducing the reallocations by only building (and probably preallocating) 400 arrays of 1000 elements rather than 1 of 400,000. The zeroth element of each of the 400 arrays would be an absolute value, but the other 999 would be relative to that base. Hence adjustments required to insert or delete affect (upto) 999 elements in the subarray affected + (upto) 400 absolute base values rather than 400,000 absolute values each time.

If performance is a problem it might save effort to have the data packed into a long string.

And that the final piece in the puzzle. packing the relative values into strings reduces the number of scalers by 3 orders. For most purposes, offsets (line lengths) can be packed into 8 bits reducing memory consuption further. By wrapping an exception eval around the packing and looking for "Character in 'C' format wrapped in pack" errors, I can detect if a line goes over 255 chars with the penalty of re-indexing to use 'n' if it happens. Ditto 'n' _> 'N'.

Moving to Inline:C or XS is an option if needed.

---

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal?

"Science is about questioning the status quo. Questioning authority".

The "good enough" maybe good enough for the now, and perfection maybe unobtainable, but that should not preclude us from striving for perfection, when time, circumstance or desire allow.