From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 21592 invoked by alias); 28 Nov 2015 19:42:27 -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: 37247 Received: (qmail 4167 invoked from network); 28 Nov 2015 19:42:25 -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 autolearn=ham autolearn_force=no version=3.4.0 X-Originating-IP: [86.6.158.222] X-Spam: 0 X-Authority: v=2.1 cv=dtgmcAU4 c=1 sm=1 tr=0 a=2SBOh4l1h08DI0L+aujZyQ==:117 a=2SBOh4l1h08DI0L+aujZyQ==:17 a=NLZqzBF-AAAA:8 a=kj9zAlcOel0A:10 a=dbBmIgL5g5-3pwfcWAYA:9 a=EHVZg3VKJTYqJ_Gz:21 a=dJn-7MeaDLjNJK-I:21 a=CjuIK1q_8ugA:10 Date: Sat, 28 Nov 2015 19:36:52 +0000 From: Peter Stephenson To: zsh workers Subject: Re: Array appends are quadratic Message-ID: <20151128193652.777742be@ntlworld.com> In-Reply-To: <20151128180517.GL2498@tarsus.local2> References: <20151127073730.GI1899@tarsus.local2> <151127025958.ZM23933@torch.brasslantern.com> <20151128180517.GL2498@tarsus.local2> X-Mailer: Claws Mail 3.11.1 (GTK+ 2.24.28; x86_64-redhat-linux-gnu) MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit On Sat, 28 Nov 2015 18:05:17 +0000 Daniel Shahaf 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(). Not allocating when the size hasn't changed should be much easier and is easy to test for. pws