Re: Array appends are quadratic

[Mikael Magnusson <mikachu@xxxxxxxxx>]

On Fri, Nov 27, 2015 at 8:37 AM, Daniel Shahaf <d.s@xxxxxxxxxxxxxxxxxx> wrote:
> 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:
[...]
> 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?

According to your debug prints, the array is reallocated every time it
is assigned to, even when the required element is already allocated.
Doubling the allocation size would do nothing to fix that, presumably.

% a[100]=foo
 params.c:2585: setarrvalue: Reallocating 'a' to size 100
% a[5]=bar
 params.c:2585: setarrvalue: Reallocating 'a' to size 101
% a[10]=bar
 params.c:2585: setarrvalue: Reallocating 'a' to size 101

Do we have an... off-by-two bug somewhere?

-- 
Mikael Magnusson