Array appends are quadratic

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

Making N appends takes O(N²) time:

    % zsh -fc 'local -a a; time ( repeat 5000 { a+=(foo) } )' 
    ( repeat 5000; do; a+=(foo) ; done; )  1.26s user 0.00s system 99% cpu 1.268 total
    % zsh -fc 'local -a a; time ( repeat 10000 { a+=(foo) } )' 
    ( repeat 10000; do; a+=(foo) ; done; )  5.02s user 0.00s system 99% cpu 5.028 total
    % zsh -fc 'local -a a; time ( repeat 20000 { a+=(foo) } )' 
    ( repeat 20000; do; a+=(foo) ; done; )  19.94s user 0.08s system 99% cpu 20.036 total
    
    % zsh -fc 'local -a a; N=5000; time ( a[N]=(); integer i; while (( i++ < N )) { a[i]=foo } )' 
    ( a[N]=() ; integer i; while (( i++ < N )); do; a[i]=foo ; done; )  2.10s user 0.00s system 99% cpu 2.004 total
    % zsh -fc 'local -a a; N=10000; time ( a[N]=(); integer i; while (( i++ < N )) { a[i]=foo } )' 
    ( a[N]=() ; integer i; while (( i++ < N )); do; a[i]=foo ; done; )  8.33s user 0.41s system 99% cpu 8.506 total
    % zsh -fc 'local -a a; N=20000; time ( a[N]=(); integer i; while (( i++ < N )) { a[i]=foo } )' 
    ( a[N]=() ; integer i; while (( i++ < N )); do; a[i]=foo ; done; )  34.92s user 0.00s system 99% cpu 34.246 total

This is because each append reallocates the array with one extra
element.  This may be confirmed by these debug prints:

    diff --git a/Src/params.c b/Src/params.c
    index b121bd6..a4ca3ce 100644
    --- a/Src/params.c
    +++ b/Src/params.c
    @@ -2579,6 +2579,7 @@ setarrvalue(Value v, char **val)
            if (v->end <= n)
                ll += n - v->end + 1;
     
    +       DPUTS2(1, "setarrvalue: Reallocating '%s' to size %d", v->pm->node.nam, ll);
            p = new = (char **) zshcalloc(sizeof(char *) * (ll + 1));
     
            for (i = 0; i < v->start; i++)
    @@ -2909,6 +2910,7 @@ assignaparam(char *s, char **val, int flags)
                    char **new;
                    int lv = arrlen(val);
     
    +               DPUTS2(1, "assignaparam: Reallocating '%s' to size %d", t, lv+1);
                    new = (char **) zalloc(sizeof(char *) * (lv + 2));
                    *new = ztrdup(getstrvalue(v));
                    memcpy(new+1, val, sizeof(char *) * (lv + 1));

The first example triggers the assignaparam() debug print with values
1,2,…,5000.  The second example triggers the setarrvalue() debug print
with values 5000,5000,…,5000, and has five thousand iterations.

Complexity could be reduced to O(N) through doubling reallocation
(whenever reallocating, allocate not oldsize + O(1) but oldsize * O(1)).

Is there a reason not to do that?  Any edge cases to take care of?

Cheers,

Daniel