From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 25171 invoked by alias); 27 Nov 2015 08:26:33 -0000 Mailing-List: contact zsh-workers-help@zsh.org; run by ezmlm Precedence: bulk X-No-Archive: yes List-Id: Zsh Workers List List-Post: List-Help: X-Seq: 37237 Received: (qmail 352 invoked from network); 27 Nov 2015 08:26:30 -0000 X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on f.primenet.com.au X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,FREEMAIL_FROM, T_DKIM_INVALID autolearn=ham autolearn_force=no version=3.4.0 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type:content-transfer-encoding; bh=V3qU8Lwuq9n9kbasPwV5kzNCKBSGhGB58lKNPm8ZCUc=; b=Jb2vZxJnhOlfVhQKYeXqkozzGBxgRWSBCYEqkNYCo/lsZ6xn6XK/5rx/wzKFrp1S4k cIg3ab0pYm1h3eXg4yrlW6cGYYr+fszEqRUjbBAVEFSW8Sd8fPOb3Gn/EiVUjzIozK9m aXiUEbXyyBea62ytM6ENWNbzqa1JBlSnGUe1talyXvXEPbMpSK/frDxLRkxqVswXq5K/ SOZS0e1Am6a/wDWuJj862OJFd2bGl5j5oD7BqFwyJ3zDhRRkGJxR2YTxLery3JeY5B5E /MZSG5/ztyRvdQ9sKN6f8VmM94v866MEWGQUBRynYWLBGmUIkVILyf4s9jaIKDl5+BjW basw== MIME-Version: 1.0 X-Received: by 10.140.151.15 with SMTP id 15mr54836597qhx.79.1448612788246; Fri, 27 Nov 2015 00:26:28 -0800 (PST) In-Reply-To: <20151127073730.GI1899@tarsus.local2> References: <20151127073730.GI1899@tarsus.local2> Date: Fri, 27 Nov 2015 09:26:28 +0100 Message-ID: Subject: Re: Array appends are quadratic From: Mikael Magnusson To: Daniel Shahaf Cc: zsh workers Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable On Fri, Nov 27, 2015 at 8:37 AM, Daniel Shahaf wro= te: > Making N appends takes O(N=C2=B2) time: > > % zsh -fc 'local -a a; time ( repeat 5000 { a+=3D(foo) } )' > ( repeat 5000; do; a+=3D(foo) ; done; ) 1.26s user 0.00s system 99% = cpu 1.268 total > % zsh -fc 'local -a a; time ( repeat 10000 { a+=3D(foo) } )' > ( repeat 10000; do; a+=3D(foo) ; done; ) 5.02s user 0.00s system 99%= cpu 5.028 total > % zsh -fc 'local -a a; time ( repeat 20000 { a+=3D(foo) } )' > ( repeat 20000; do; a+=3D(foo) ; done; ) 19.94s user 0.08s system 99= % cpu 20.036 total > > % zsh -fc 'local -a a; N=3D5000; time ( a[N]=3D(); integer i; while (= ( i++ < N )) { a[i]=3Dfoo } )' > ( a[N]=3D() ; integer i; while (( i++ < N )); do; a[i]=3Dfoo ; done; = ) 2.10s user 0.00s system 99% cpu 2.004 total > % zsh -fc 'local -a a; N=3D10000; time ( a[N]=3D(); integer i; while = (( i++ < N )) { a[i]=3Dfoo } )' > ( a[N]=3D() ; integer i; while (( i++ < N )); do; a[i]=3Dfoo ; done; = ) 8.33s user 0.41s system 99% cpu 8.506 total > % zsh -fc 'local -a a; N=3D20000; time ( a[N]=3D(); integer i; while = (( i++ < N )) { a[i]=3Dfoo } )' > ( a[N]=3D() ; integer i; while (( i++ < N )); do; a[i]=3Dfoo ; 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,=E2=80=A6,5000. The second example triggers the setarrvalue() debug = print > with values 5000,5000,=E2=80=A6,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]=3Dfoo params.c:2585: setarrvalue: Reallocating 'a' to size 100 % a[5]=3Dbar params.c:2585: setarrvalue: Reallocating 'a' to size 101 % a[10]=3Dbar params.c:2585: setarrvalue: Reallocating 'a' to size 101 Do we have an... off-by-two bug somewhere? --=20 Mikael Magnusson