Re: Array appends are quadratic

[Daniel Shahaf <d.s@xxxxxxxxxxxxxxxxxx>]

Peter Stephenson wrote on Sat, Nov 28, 2015 at 19:36:52 +0000:
> On Sat, 28 Nov 2015 18:05:17 +0000
> Daniel Shahaf <d.s@xxxxxxxxxxxxxxxxxx> wrote:
> > The effort involved in implementing the redoubling allocation (for the
> > other problem indicated in 37236) would be similar: mainly having the
> > array remember the number of allocated slots.  I'll have to track done
> > all places in the code that allocate/reallocate arrays, hopefully there
> > aren't too many.
> 
> I suspect (though I haven't actually done a search) you're out of luck
> here, as there's a wide assumption that null-terminated char **'s are
> the the way to carray a fixed number of elements with generic contents
> that might get presented to the user.  See for example the number of
> uses of mkarry().

Thanks for the pointer, I shall have a look.

> Not allocating when the size hasn't changed should be much easier and is
> easy to test for.

It'll be just a local fix to setarrvalue(), and it would fix the problem
for callers that preallocate the array (by doing 'a[10000]=""').  Sounds
simple enough.  I'll look into it.

Cheers,

Daniel

> 
> pws