Re: Array appends are quadratic

[Daniel Shahaf <d.s@daniel.shahaf.name>]

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@daniel.shahaf.name> 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().

I'm not sure I see the problem.  Doubling reallocations would require
the array to track its allocated size (the N in «pm->u.arr = alloc(N
* sizeof(void*))», which is strictly greater than its arrlen).  I assume
only affect places that modify the array would be affected: that is,
places that modify pm->u.arr directly (list below) and places that call
setfn.  So, I think doubling allocations can be made to work, if each
place that modifies the array knows what arrlen() would be after the
modification, in order to be able to cheaply determine whether its
smaller than the allocated length.

So maybe it's better to first teach arrays to know their arrlen in O(1),
before investigating doubling allocations.  (Mikael had investigated
this direction.)

Daniel

typeset_single:Src/builtin.c:2428:     tdp->arrptr = &altpm->u.arr;
bin_unset:Src/builtin.c:3379:                     if (start < arrlen(vbuf.pm->u.arr)) {
restore_params:Src/exec.c:3898:                    tpm->gsu.a->setfn(tpm, pm->u.arr);
copyparam:Src/params.c:1028:      tpm->u.arr = zarrdup(pm->gsu.a->getfn(pm));
arrgetfn:Src/params.c:3341:    return pm->u.arr ? pm->u.arr : &nullarray;
arrsetfn:Src/params.c:3350:    if (pm->u.arr && pm->u.arr != x)
arrsetfn:Src/params.c:3351:      freearray(pm->u.arr);
arrsetfn:Src/params.c:3354:    pm->u.arr = x;
scanendscope:Src/params.c:5096:                  pm->gsu.a->setfn(pm, tpm->u.arr);
paramsubst:Src/subst.c:2499:               pm->u.arr = aval;