From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 27672 invoked by alias); 28 Nov 2015 18:13:00 -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: 37246 Received: (qmail 15571 invoked from network); 28 Nov 2015 18:12:58 -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,T_DKIM_INVALID autolearn=ham autolearn_force=no version=3.4.0 DKIM-Signature: v=1; a=rsa-sha1; c=relaxed/relaxed; d= daniel.shahaf.name; h=content-transfer-encoding:content-type :date:from:in-reply-to:message-id:mime-version:references :subject:to:x-sasl-enc:x-sasl-enc; s=mesmtp; bh=61+WtN5WPdYR+/ok 9hjdGnJFc6g=; b=vyaQjzfL2BGHhD7DfXRhEmzthMR3TlQ4HR9F508WoRqLnu3E Dx8P8IkI9hArR8dJaF+o451lI4FP18Fw/LHZRslFQz3/hc3gQmxIOnyEYhQaqGn4 nicTBf0oCFw4fkRSONTXfi08LuRo9jfTfScvdAE6rKiAWxEqBAwT8Sd+vyY= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed/relaxed; d= messagingengine.com; h=content-transfer-encoding:content-type :date:from:in-reply-to:message-id:mime-version:references :subject:to:x-sasl-enc:x-sasl-enc; s=smtpout; bh=61+WtN5WPdYR+/o k9hjdGnJFc6g=; b=gRpEdHwFtQVy30J4Qw6Y8t5NEauHpCfCpaZUycDADknAWdZ OTdyZr8qAs6ADye+c14HGZR1t6uadcFWCNUi8BX2od9x+T8rIoNokd5wxWKyWjBW HIZTCmjAwyNJWQsHRjVvooJmD+cZJePrJF8jQ0bNlhBQcxoxkthRWollH3bA= X-Sasl-enc: 0OrQ6AoP9yr8YaDn0ZqbBADIbPHHqP0WCz+E1hU14oHA 1448733920 Date: Sat, 28 Nov 2015 18:05:17 +0000 From: Daniel Shahaf To: zsh workers Subject: Re: Array appends are quadratic Message-ID: <20151128180517.GL2498@tarsus.local2> References: <20151127073730.GI1899@tarsus.local2> <151127025958.ZM23933@torch.brasslantern.com> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Disposition: inline Content-Transfer-Encoding: 8bit In-Reply-To: <151127025958.ZM23933@torch.brasslantern.com> User-Agent: Mutt/1.5.21 (2010-09-15) Bart Schaefer wrote on Fri, Nov 27, 2015 at 02:59:58 -0800: > On Nov 27, 9:26am, Mikael Magnusson wrote: > } Subject: Re: Array appends are quadratic > } > } 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. > > Right, this is generic code to handle array splicing, so starting from > an array with 200 elements, > > a[100]=foo > > and > > a[50,150]=(foo) > > use the same loop even though the former does not change the size of > the resulting array and the latter will waste 100 slots at the top. (The reason it'll waste 100 slots is that it will allocate 200 elements even though only 200-(150-50+1) are needed.) > I vaguely recall a conversation in which we decided that fewer code > branches was better than attempting to efficiently re-use array slots. I'm not looking to implement sparse arrays. I just wish it didn't reallocate unless it needed to. That _would_ mean some additional code complexity, but it seems it would be manageable: having the array remember the number of allocated slots, using memmove() to shift the past-the-slice portion, copying the slice directly into the slots. That should make this part of the code O(slice) rather than O(array length). 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. There may be other parts in the code that do O(n) processing instead of O(1) — Mikael points out arrlen() as an example — but those can be improved separately. > } % 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? > > No, it just always allocates 1 more than the largest occupied array > index position if the array isn't empty to begin with. > Cheers, Daniel P.S. It seems that bin_compquote is calling ztrdup() on every element of an array parameter passed as an argument, so it would reallocate all array members even if none of them need quoting. I'm not planning to look into it further, though, since I haven't run into it in practice yet.